www.xbdev.net xbdev - software development
Friday December 14, 2018
home | about | contact | Donations

     
 

Game Physics Programming..

Bouncing Objects, Springs, Balls, Rigid Bodies...

 

Sparse Arrays

by Ben Kenwright

 
One thing that crops up a lot in physics, is sparse arrays.  It might seem a general C/C++ thing, and you might be wondering what and why we need sparse arrays.  Well its all about memory and speed.  When we have some crazy matrix sizes, such as
int a[2000000];
But most of the array isn't used or is set to some default value such as 0.  If we for example did this, we would have sizeof(int) which is 4 bytes, and then we have 2,000,000 of them, thats 4 * 2,000,000 which is about 7 meg!  7 MEG!  Thats a lot.  And now lets say we want a second one.  Well first theres the overhead of another 7 meg, but even if we had a super computer, we'd have to copy that 7 meg!  But lets say our realtime physics engine needs to do this 30 times a second.  Well it can't be done...well not yet with computers, maybe one day.


So where going to go through the stages of building a sparse array, which only allocates enough memory for the elements that are being used, and also can use some tricks such as binary tree searching to make it very fast to grab elements from the array.


C++ with its operator overloading does make life easy for us.  We can develop a brute force method and wrap it in a class, we'll call it 'class Array', then as we can swap it out and try new SparseArray and compare results.  And then move onto squeeze a few extra drops of memory or cycles from our creation, SparseArrayFast maybe?  We'll have to see.


[*NOTE*]
When writing a simple physics engine using an itterative LCP solver, I found that 90% of my cpu performance was getting used copying/initialising and indexing my large arrays in my solver.






 

 

 

 


Tips & Ideas
o Memory Pool (Considerably faster than new'ing)
o Hash maps?

o Templates
o Macros (speed ups)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 Visitor: 9534626  { 209.237.238.175 } Copyright (c) 2002-2017 xbdev.net - All rights reserved.
Designated tutorial and software are the property of their respective owners.