for(i=0; i < num_particles; i++) {
for(k = (i + 1); k < num_particles; k++) {
// if particle is within distance to particle[k], then repel them.
}
}
Large scale particle collision systems
Author
What do people use to speed up large-scale particle collision, like thousands of particles?
Something that is better than:
Author
I believe I'm looking for a type of optimization. Did some searching and found a list of some
interesting structures to use:
Octree
KD Tree
BSP
OBB tree (BVH)
K-dop tree
Uniform grid
Hashing
Dimension reduction
If my collisions are purely particle collisions, is there any one type of optimization that is
best to use?
interesting structures to use:
Octree
KD Tree
BSP
OBB tree (BVH)
K-dop tree
Uniform grid
Hashing
Dimension reduction
If my collisions are purely particle collisions, is there any one type of optimization that is
best to use?
If we can assume that the particles share the same (or similar) radii, I would definitely go for a uniform grid and hashing hybrid.
Consider an infinite uniform grid and a mapping function:
f(x,y,z) -> grid's element.
One way to define f is:
f(x,y,z) = floor( x/sx, y/sy, z/sz ),
where sx, sy and sz are the grid's element size.
In this case, each grid element is represented by three integers.
Moreover, if the particle's radius is R, a good choice for the grid's element size would be:
sx = sy = sz = R.
Now, for each non empty element, we keep an entry inside a hash table. In our example, since we define each element as a triplet (a,b,c), a reasonable hashing function would be something like:
hfunc(a,b,c) = prime0*a + prime1*b + c.
Given some particle at (x,y,z), we can retrieve potentially colliding particles by looking up the appropriate grid's elements in the vicinity of f(x,y,z).
If all particles have the radius R and sx = sy = sz = R, we have to check at most 27 elements inside the hash table.
Of course we don't have to repeat the same process for each particle. Consider the case where several particles are located inside f(x,y,z). Repeating the same process for each particle means that we are virtually doing the same thing all over again.
This method is SLOWER than a regular uniform grid approach because of the overhead in using the hash table. We do have two very important advantages though:
1) The memory usage is reduced dramatically.
2) This approach allows us to work with infinite grids which is a big plus
if we are working inside a large environment.
Consider an infinite uniform grid and a mapping function:
f(x,y,z) -> grid's element.
One way to define f is:
f(x,y,z) = floor( x/sx, y/sy, z/sz ),
where sx, sy and sz are the grid's element size.
In this case, each grid element is represented by three integers.
Moreover, if the particle's radius is R, a good choice for the grid's element size would be:
sx = sy = sz = R.
Now, for each non empty element, we keep an entry inside a hash table. In our example, since we define each element as a triplet (a,b,c), a reasonable hashing function would be something like:
hfunc(a,b,c) = prime0*a + prime1*b + c.
Given some particle at (x,y,z), we can retrieve potentially colliding particles by looking up the appropriate grid's elements in the vicinity of f(x,y,z).
If all particles have the radius R and sx = sy = sz = R, we have to check at most 27 elements inside the hash table.
Of course we don't have to repeat the same process for each particle. Consider the case where several particles are located inside f(x,y,z). Repeating the same process for each particle means that we are virtually doing the same thing all over again.
This method is SLOWER than a regular uniform grid approach because of the overhead in using the hash table. We do have two very important advantages though:
1) The memory usage is reduced dramatically.
2) This approach allows us to work with infinite grids which is a big plus
if we are working inside a large environment.
Quote:If we can assume that the particles share the same (or similar) radii, I would definitely go for a uniform grid and hashing hybrid.
This will work fine when particles can collide with eachother ONLY.
If they need to collide against meshes and other collision primitives of very different sizes a grid/cell based approach might not be the best choise.
I'm using a dynamic loose aabb tree for all collision queries, to see what I'm talking about I've got some test exe's here (the text below is shamelessly copied from a previous post of mine):
Be aware that the fps is quite bad, mostly thanks to the slow/bad drawing of my debug objects.
The interseting numbers are the "Update took" and "Query took" counter, they are all in micro seconds (10e-6).
Press and hold the right mouse button to activate mouse look. W/A/S/D to move around (or arrows).
Press space to start/pause animation.
Press T to toggle tree hierarchy view on/off.
* FrustumTest_10000.exe, shows 10000 aabb's that moves around (Update took), aabb's that are within one of the three "frustums" are solid (Query took).
Tetrahedral frustums performs similar (just to lazy to draw them :)
* OverlapTest_2500.exe, shows 2500 aabb's that moves around (Update took), aabb's that overlaps ANY other aabb are solid (Query took).
Using bruteforce this would require over 3 million aabb vs aabb tests.
The tests takes about 12ms on my machine = 60+ fps.
* SimpleFrustumTest_16.exe, shows 16 aabb's that moves around (Update took), aabb's that overlaps the frustum (cube) are solid (Query took).
This sample is basicly where you'd like to hit T to see how the tree is created/modified.
I don't remember the hardware requirements for these demos, it's DX9 and uses SSE anyway (think you need a P4, using the Intel compiler).
Also note that the code isn't super optimized, but a rather flexible templated class.
You could probably optimize it a bit more by removing some templating stuff.
Also consider using spheres instead of aabb's.
Author
Quote:
This will work fine when particles can collide with eachother ONLY.
If they need to collide against meshes and other collision primitives of very different sizes a grid/cell based approach might not be the best choise.
I did mention that my system consisted only of particles. They all will be the same size, so it is ok.
Quote:Original post by eqQuote:If we can assume that the particles share the same (or similar) radii, I would definitely go for a uniform grid and hashing hybrid.
This will work fine when particles can collide with eachother ONLY.
If they need to collide against meshes and other collision primitives of very different sizes a grid/cell based approach might not be the best choise.
You are correct. One way to handle widely varying radii, is to use several hashing tables with different resolutions. A good algorithm that does that was proposed by M. Overmars. Tell me if you want to hear more details.
I, for one, never had the chance to test both AABB trees and spatial hashing in the same environment so I don't really know which is better or faster.
I'd like to hear from someone who did.
There are other considerations in your search, for example you will probably want to assign a range of characteristics to each particle:
Velocity
Direction
Orientation
Energy State
Temperature (K)
Neighbouring Entities (optimisation trick)
Charge
Spin
I would be more inclined towards a modified BSP format as it allows for conditional analysis and order sorting. A highspeed database essentially.
Velocity
Direction
Orientation
Energy State
Temperature (K)
Neighbouring Entities (optimisation trick)
Charge
Spin
I would be more inclined towards a modified BSP format as it allows for conditional analysis and order sorting. A highspeed database essentially.
Quote:Original post by eqQuote:If we can assume that the particles share the same (or similar) radii, I would definitely go for a uniform grid and hashing hybrid.
This will work fine when particles can collide with eachother ONLY.
If they need to collide against meshes and other collision primitives of very different sizes a grid/cell based approach might not be the best choise.
I'm using a dynamic loose aabb tree for all collision queries, to see what I'm talking about I've got some test exe's here (the text below is shamelessly copied from a previous post of mine):
Be aware that the fps is quite bad, mostly thanks to the slow/bad drawing of my debug objects.
The interseting numbers are the "Update took" and "Query took" counter, they are all in micro seconds (10e-6).
Press and hold the right mouse button to activate mouse look. W/A/S/D to move around (or arrows).
Press space to start/pause animation.
Press T to toggle tree hierarchy view on/off.
* FrustumTest_10000.exe, shows 10000 aabb's that moves around (Update took), aabb's that are within one of the three "frustums" are solid (Query took).
Tetrahedral frustums performs similar (just to lazy to draw them :)
* OverlapTest_2500.exe, shows 2500 aabb's that moves around (Update took), aabb's that overlaps ANY other aabb are solid (Query took).
Using bruteforce this would require over 3 million aabb vs aabb tests.
The tests takes about 12ms on my machine = 60+ fps.
* SimpleFrustumTest_16.exe, shows 16 aabb's that moves around (Update took), aabb's that overlaps the frustum (cube) are solid (Query took).
This sample is basicly where you'd like to hit T to see how the tree is created/modified.
I don't remember the hardware requirements for these demos, it's DX9 and uses SSE anyway (think you need a P4, using the Intel compiler).
Also note that the code isn't super optimized, but a rather flexible templated class.
You could probably optimize it a bit more by removing some templating stuff.
Also consider using spheres instead of aabb's.
eq - do you know of any links of information on how to implement the "dynamic loose aabb tree" you mention? I've read lot's of posts here that show how to create trees for static geometry/object, but no info for dynamic objects.
thanks
-Steve
Quote:Original post by MooMansun
I would be more inclined towards a modified BSP format as it allows for conditional analysis and order sorting. A highspeed database essentially.
What do you mean by "a modified BSP format"?
I have a very little experience with BSPs so please forgive me if what I am about to say is nonsense.
Classic BSP is used to partition space, so I guess that in order to incorporate BSP in a particle collision scheme you should enclose the particles with some sort of a convex polyhedron, say AABB.
(1) If we choose AABB, we have 6 partitioning planes for every particle.
(2) While traversing the BSP, we have to perform some (relatively fast)computation for each plane that we encounter, in order to determine where the colliding object stands relative to the plane.
(3) When the colliding object intersects with the partitioning plane, we have to traverse the BSP in both directions.
(4) Classic BSP was not designed to handle dynamic data. In fact, you would have to reconstruct it all over again for each frame.
Also, consider the following example:
All of your particles lie on the ground which is aligned with the X-Z plane.
If your particles have the same radius and we use AABB to encapsulate them,
then ALL of the particles have two identical planes!!! This means that performing the collision will be roughly a O(n^2) process because of (3).
I am not sure how well the algorithm scales because of (1), (2) and (3) as the number of particles become larger when compared to loose AABB and spatial hashing. Any thoughts on that?
Moreover, one has to understand that (3) might have a considerable impact in the event where we have dense clustering of the particles.
As for my example. Unless you have a solution to that, I wouldn't touch BSP with a 10 inch stick. :)
(4) is a very important issue since the construction of a BSP is not linear,
while both loose AABB and spatial hashing are. I guess that you probably have an answer to (4) so I would love to hear about it.
Tell me what you think.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
