Large scale particle collision systems

Math and Physics Programming

Started by JakeM October 10, 2005 04:04 PM

22 comments, last by sbroumley 18 years, 6 months ago

656

October 11, 2005 11:07 AM

Quote: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.

Unfortunatly no :(
I got the idea from some sphere tree demo I saw (just an executable). It had a fixed number of levels in the tree, i.e two supernodes and leaf nodes.
I also didn't like the fact that finding the minimaly enclosing sphere for a set of spheres is a very complicated thing, that's why I choose aabb's.

My approach is totally dynamic, I've seen 20+ tree levels.
There are a few heuristics that can be modified, i.e how much to expand the nodes depending on an aabb's velocity etc, when to remove an aabb from the parent and so on.
As you can guess from the test exe's, my heuristics are based on the aabb volumes. If the ratio between the sum of the contained aabb's and the parent aabb, violates some threshold then do this or that and so on..
It was quite a challenge to implement the system from scratch but I liked the end result, it's quite clean and the expensive operations are used very seldom.

The "No update" in the demos is the number of times I didn't have to do anything when an aabb was updated (moved or resized). This is a very fast operation (basically: test if my new aabb is "visible" outside the parent aabb).
The "Grow node" is the number of times I had to grow an existing node in the tree (the tree structure is intact). This is also a quite fast operation, just calculating the "expansion" velocity of the updated aabb and merge it with the parent aabb.
The "Reinsert" is the number of times I need to remove the aabb from the tree, then reinsert it again from the root.
This is the only operation that reorganizes the tree structure and is relatively expensive.
In the 10000 aabb test, less then 2% of the updates performs the expensive path.
About 94% of the updates doesn't need to do anything.

Sorry for not being able to point out some good papers on the subject :(

sbroumley

283

October 11, 2005 12:25 PM

Thanks for the info eq.

One more question - how do you find/update the overlapping pairs of AABBs? Is it similar to sweep and prune where you use frame coherency or do you rebuild from scratch each frame?

Steve Broumley

656

October 11, 2005 01:03 PM

In the samples I don't use any frame coherence.
For every aabb, I do an aabb query on the structure, this returns all overlapping aabb's in the tree.
In the example I have 2500 aabb queries, one for each aabb (not entirely true since if aabb X overlaps aabb Y, I mark Y as tested).

In my real applications I've only used the aabb tree for frustum culling and object picking (ray casting).
I haven't got the need for real collisions and physics at the moment, so I don't know how good it work in a real game situation.

To handle swept objects I guess you could store the swept aabb in the tree, I.e the aabb for the object that surronds the object at all timesteps from the previous frame to the next. In it's simplest form the aabb that encapsuls the aabb of the previous frame and the current.
Then for every object that moves, you input the swept aabb instead of the static aabb to get all overlapping aabb over the time.

MooMansun

100

October 11, 2005 01:21 PM

Quote:What do you mean by "a modified BSP format"?

BSP Particle Collision Format. It would adhere to most of what I describe in this post.

Quote: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.

No, its not nonsense, very good questions.

Quote:(1) If we choose AABB, we have 6 partitioning planes for every particle.

I am considering that each of the following should be attributed to a dimension, or aspect, of each particle. I feel that the node based structure of BSP lends to that application. Saving state information, from a particular point of view (i.e. a particular electron) can be achieved using the 'Neighbouring Entities'. One thing I think is not studied enough in partical collisions is relativity and this method just seems nice and flexible for that application.

Velocity
Direction
Orientation
Energy State
Temperature (K)
Neighbouring Entities (optimisation trick)
Charge
Spin
(Numerous Others...)

"The partitioning can be represented as a tree, which has the partitioning planes at the internal nodes and objects of interest at the leaves."
http://66.102.9.104/search?q=cache:peBGp8xJ6CkJ:www.cc.gatech.edu/classes/AY2006/cs4451b_fall/bsp.pdf+partitioning+planes&hl=en

Quote:(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.

I did briefly consider this during my post, however, I felt that most simulations are pre-computed to provide accuracy and speed. I also felt that considering the number of dimensions, or aspects, to each particles current state, that the node structure would allow flexibility to alter, add or remove those. Finally, it also allows flexibility to increase the physical dimensions, 4, 10 or 26.

Quote:(3) When the colliding object intersects with the partitioning plane, we have to traverse the BSP in both directions.

Actually, with Neighbouring Entities, the BSP would be traversed in both directions multiple times. Again, I see this as acceptable for pre-computed data, especially because of the flexibility.

Quote:(4) Classic BSP was not designed to handle dynamic data. In fact, you would have to reconstruct it all over again for each frame.

Most of the dynamic aspect would be carried out in main memory, much like a standard BSP. The way I was thinking about this implementation was that the BSP file would be loaded into memory and manipulated by another file to achieve pre-computation of a desired reaction/collision. This would allow separation of the simulated test environment and the data used to manipulate it. Otherwise, a new test environment would need to be composed each and every time a new simulation was run. I don't view that lack of re-usability as acceptable.

Quote: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'm afraid this is one of the problems with collision simulation. This is why most of it, even with super-computers, is pre-computed as much as possible. If you do not perform those calculations, your accuracy is questionable.

Quote: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.

Neither am I, that is why I used the term 'modified' loosely.

Quote:As for my example. Unless you have a solution to that, I wouldn't touch BSP with a 10 inch stick. :)

There's life in that old BSP horse yet... :)

JakeM

168

Author

October 11, 2005 03:46 PM

I don't mind anyone hijacking my thread, as long as it addresses my specific problem,
and I don't see what this has to do with my problem.

MooMansun

100

October 11, 2005 03:54 PM

Quote:What do people use to speed up large-scale particle collision, like thousands of particles?

You never specified what exactly you wanted to monitor/alter. How you speed it up, depends on what information is being processed, as much as how it should be presented to the end user.

hplus0603

11,916

October 11, 2005 04:08 PM

An alternate approach, which would cache very well, is to sort along one axis, and march along, collecting duplicates. The sort is a fast N lg N, the marching is "approximately" N lg N as well.

Assuming all the particles have the same radius, you can sort on the midpoint; else you must sort on the left edge of the bounding volume of each particle.

// pseudo-codestruct ParticleInfo {  float x, y, z;  ActualParticle * p;};std::vector< ParticleInfo > particles;void check_collisions() {  // assume the particles have some spread along the x axis  sort_particles_on_x( particles );  std::deque< ParticleInfo * > active;  foreach ( ParticleInfo & pi in particles ) {    retire_active( active, pi.x-radius );    check_collisions( active, pi );    active.push_back( π );  }}void retire_active( deque active, float minx ) {  foreach( iterator i in active ) {    if( i->x <= minx ) {      active.erase( i );    }  }}void check_collisions( deque active, ParticleInfo & pi ) {  foreach( iterator i in active ) {    if( distance( pi, *i ) < 2*radius ) {      got_a_collision( pi, *i );    }  }}

Instead of a deque, you can use a list or a vector if the number of expected size of the container is small. In fact, vector may perform the best there, too, for many cases.

If you find that most of your particles bunch in the middle, you might want to do a secondary sort along another axis for the active list, and do a binary search when looking for collisions when adding the new particleinfo; this will reduce the average-case number of tests a little bit. However, it should only be necessary with thousands of particles that intersect a lot.

Note that the worst case is always N * N, because each particle may actually collide with every other particle, and thus you need to generate N * N / 2 actual collision pairs, thus that's the runtime of the algorithm in that case.

enum Bool { True, False, FileNotFound };

sbroumley

283

October 11, 2005 06:24 PM

Quote:Original post by eq
Quote: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.

Unfortunatly no :(
I got the idea from some sphere tree demo I saw (just an executable). It had a fixed number of levels in the tree, i.e two supernodes and leaf nodes.
I also didn't like the fact that finding the minimaly enclosing sphere for a set of spheres is a very complicated thing, that's why I choose aabb's.

My approach is totally dynamic, I've seen 20+ tree levels.
There are a few heuristics that can be modified, i.e how much to expand the nodes depending on an aabb's velocity etc, when to remove an aabb from the parent and so on.
As you can guess from the test exe's, my heuristics are based on the aabb volumes. If the ratio between the sum of the contained aabb's and the parent aabb, violates some threshold then do this or that and so on..
It was quite a challenge to implement the system from scratch but I liked the end result, it's quite clean and the expensive operations are used very seldom.

The "No update" in the demos is the number of times I didn't have to do anything when an aabb was updated (moved or resized). This is a very fast operation (basically: test if my new aabb is "visible" outside the parent aabb).
The "Grow node" is the number of times I had to grow an existing node in the tree (the tree structure is intact). This is also a quite fast operation, just calculating the "expansion" velocity of the updated aabb and merge it with the parent aabb.
The "Reinsert" is the number of times I need to remove the aabb from the tree, then reinsert it again from the root.
This is the only operation that reorganizes the tree structure and is relatively expensive.
In the 10000 aabb test, less then 2% of the updates performs the expensive path.
About 94% of the updates doesn't need to do anything.

Sorry for not being able to point out some good papers on the subject :(

I've thought of another question: How do you initially setup the tree? Do you create it as if you were creating a tree for static objects ie. perform a one step creation (slow) once all of your world objects are known? Also - once you have the tree running, how do you add new created objects to it? Do they have to go into an existing node? This maybe related, but how do you "reinsert" an object? I guess I'm confused as how you create new parts of the tree when removing/adding objects. Oh and if you haven't guessed by now I'm very curious about possibly using such a system to replace the sweep and prune system I currently have in my ongoing physics engine.

thanks!

Steve Broumley

JakeM

168

Author

October 11, 2005 10:58 PM

Quote:Original post by hplus0603
An alternate approach, which would cache very well, is to sort along one axis, and march along, collecting duplicates. The sort is a fast N lg N, the marching is "approximately" N lg N as well.

If I went with an uniform grid with rectangular cells, how would I resolve collisions on
the boundaries of these cells? Putting the particles in the grid cells is fast, I just cast
their floating-point position to an integer, so no sorting is necessary.

I was thinking maybe of having overlapping rectangular cells or maybe overlapping
circular cells, but not quite sure how to place the particles in them.

ury

476

October 12, 2005 10:49 AM

Quote:Original post by JakeM
If I went with an uniform grid with rectangular cells, how would I resolve collisions on
the boundaries of these cells? Putting the particles in the grid cells is fast, I just cast
their floating-point position to an integer, so no sorting is necessary.

I was thinking maybe of having overlapping rectangular cells or maybe overlapping
circular cells, but not quite sure how to place the particles in them.

If you do that, then you are better of using a loose AABB tree.

Uniform grids are usually used somewhat differently. Suppose that we enclose a particle with a box. After "placing" it in a grid cell we can find potentially intersecting particles by looking up all neighboring cells that intersect with our box.
In a perfect situation, where the cells are bigger than the particle radius, you have to test at most 27 cells, (1 for the cell that you are in and 26 for its neighbors). As suggested in my previous post, the process can be optimized. In fact, an approach similar to the one proposed by hplus0603 can be devised, only without the worst case scenario.

You can read more about spatial hashing here:
http://erinhastings.net/papers/hashing-sim.zip
http://www.merl.com/reports/docs/TR97-23.pdf
http://graphics.ethz.ch/~brunoh/download/CollisionDetectionHashing_VMV03.pdf

Large scale particle collision systems

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Large scale particle collision systems

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines