Thanks to Budda, David, and everyone else. I will incorporate your ideas and run empirical tests to compare the speeds.
I'll let you all know the results.
Thanks to Budda, David, and everyone else. I will incorporate your ideas and run empirical tests to compare the speeds.
I'll let you all know the results.
Okay, given the updated information, using voxels is certainly going to be slower, for two reasons:Originally Posted by cybernike
1. It takes far more memory, and memory will probably be the bottleneck.
2. Only 1 cell out of a million will be occupied, therefore every update will process 999999 empty cells for each occupied cell.
Try using a list of particles plus a multiway-trie structure for the data.
For a 1000-way trie this means an array of 1000 pointers that are either NULL, or point to arrays of 1000 pointers, which themselves are either NULL, or point to an array of 1000 bits.
Write a function called e.g. 'trieLookup', that takes 3 parameters (x, y, z) and does a lookup in the trie structure to see if the point is occupied.
Each update, iterate through the list calling trieLookup up to 6 times as necessary for each particle, then remove the particle from the multiway-trie structure, and insert it again at the new position.
trieLookup should be very fast, still O(1), yet this uses much less memory than before.
Using a free-list or custom allocator can make this even faster.
You can trade off between memory usage and steps per lookup by making the trie size configurable. You may find that a 10-way trie of up to 9 levels gives even better performance due to less memory usage, for example.
Better still, this method would allow you to scale up to 10000x10000x10000, no worries!
Last edited by iMalc; 06-28-2007 at 01:30 AM.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
My post crossed with Bubba and DavidP.
A trie is much faster than a map in this case. It's log(k) levels vs log(n) levels (k is fixed), and has a much lower constant factor too (no tree rebalancing etc).
Heck, I'll even write Add, Remove, and Lookup functions for you if you want. It's really easy.
If you wanted to get really carried away, you could try and implement a Van-Emde-Boas tree... I haven't tried that myself yet though...
http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Okay, well I've just implemented my Multiway Trie idea.
Haven't finished testing it, but I'm optimistic it should work well.
You'll find it in the Useful Classes section of my web page (link in my sig).
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Compile and run this and you will see what I'm talking about.
Code:#include <windows.h> int main() { BOOL boolean; boolean = (BOOL)((rand()%1000) - 500); // I'm putting an int into a bool here. char sz[250]; wsprintf(sz, "boolean = %d", (int)boolean); // This puts the "bool" back into int from. MessageBox(0, sz, "Report", MB_OK); // As you can see. return 0; }
Just because you can cast a type to another doesn't mean that the types fundamentally hold one another.
>> Compile and run this and you will see what I'm talking about.
You are confusing bool and BOOL. They are two completely different types. BOOL is a typedef for an integral type, so of course it can hold integer values, while bool can only hold true and false.
The reason a bool is a byte is because a byte is the smallest addressable size, and a bool variable must be able to have a unique address. This is why vector<bool> is screwy, because vectors work like regular arrays for all types except bool. When you have a vector<bool>, the individual bools are no longer addressable.
Just to bring everyone onto the same page about vector<bool>:
Quote taken from Wikipedia.The 1998 C++ Standard Library defines a specialization of the vector<bool> class. To optimize space, the elements are packed so that every bool only uses one bit of memory. This is widely considered a mistake. vector<bool> does not meet the requirements for a STL container.For instance, a container<T>::reference must be a true lvalue of type T. This is not the case with vector<bool>. Similarly, the vector<bool>::iterator does not yield a bool& when dereferenced. There is a general consensus among the C++ Standard Committee and the Library Working Group that vector<bool> should be deprecated or entirely removed from the next version of the standard.
