How to sort objects for Guandelman sound propagation?

Question

This is a question about creating a topographic tree in 3D. A bit of context: I have a physics engine where I have bodies and points of collision and some limitations. This is not homework, but an experiment in multi-threaded mode.

I need to sort bodies from the bottom up with groups of objects belonging to layers, as in this document: see the section “Accelerate the spread”, http://www2.imm.dtu.dk/visiondag/VD05/graphical/slides/ kenny.pdf

the pseudocode that he uses to describe how to iterate over a tree makes sense:

shock-propagation(algorithm A) compute contact graph for each stack layer in bottom up order fixate bottom-most objects of layer apply algorithm A to layer un-fixate bottom-most objects of layer next layer 

I already have an algorithm. It turned out (my pulse code). What would the pseudo-code look like for sorting a tree / layer (topo sort?) With a list of three-dimensional points?

IE, I don’t know where to stop / start the next "step" or "branch". I guess I could just break it down by y position, but that seems awkward and error prone. Am I looking at topographic sorting? I really don't know how to do this in 3D. How can I get the “edges” for sorting topo if this is the way to do it?

Do I really think about this, and I just “connect the dots” by finding the point p1, then the least distant next point p2, where p2.y> p1.y? Here I see a problem where the distance p1 from p0 can be greater than p2 using pure distances, which will lead to poor sorting.

Answer 1

I just decided it myself.

I found an example of how to accomplish this in the downloadable source code associated with this article:

http://www-cs-students.stanford.edu/~eparker/files/PhysicsEngine/

In particular, the WorldState.cs file starts at line 221.

But the idea is that you assign all static objects with a level of -1 and with each other an object with a different level by default of -2. Then for each collision with bodies at level -1, you add the body into which it collided, and list it at 0.

After that, using the while while loop (list.Count> 0), check the bodies that encounter it and set the levels there to body.level + 1.

After that, for each body in the simulation that still has a default level (I said -2 before), set its level to the highest level.

There are a few more minor details, but looking at the code in the example will explain this better than ever.

Hope this helps!

Corresponding code from Evan Parker's code. [Stanford]

 {{{ // topological sort (bfs) // TODO check this int max_level = -1; while (queue.Count > 0) { RigidBody a = queue.Dequeue() as RigidBody; //Console.Out.WriteLine("considering collisions with '{0}'", a.Name); if (a.level > max_level) max_level = a.level; foreach (CollisionPair cp in a.collisions) { RigidBody b = (cp.body[0] == a ? cp.body[1] : cp.body[0]); //Console.Out.WriteLine("considering collision between '{0}' and '{1}'", a.Name, b.Name); if (!b.levelSet) { b.level = a.level + 1; b.levelSet = true; queue.Enqueue(b); //Console.Out.WriteLine("found body '{0}' in level {1}", b.Name, b.level); } } } int num_levels = max_level + 1; //Console.WriteLine("num_levels = {0}", num_levels); ArrayList[] bodiesAtLevel = new ArrayList[num_levels]; ArrayList[] collisionsAtLevel = new ArrayList[num_levels]; for (int i = 0; i < num_levels; i++) { bodiesAtLevel[i] = new ArrayList(); collisionsAtLevel[i] = new ArrayList(); } for (int i = 0; i < bodies.GetNumBodies(); i++) { RigidBody a = bodies.GetBody(i); if (!a.levelSet || a.level < 0) continue; // either a static body or no contacts // add a to a level bodiesAtLevel[a.level].Add(a); // add collisions involving a to a level foreach (CollisionPair cp in a.collisions) { RigidBody b = (cp.body[0] == a ? cp.body[1] : cp.body[0]); if (b.level <= a.level) // contact with object at or below the same level as a { // make sure not to add duplicate collisions bool found = false; foreach (CollisionPair cp2 in collisionsAtLevel[a.level]) if (cp == cp2) found = true; if (!found) collisionsAtLevel[a.level].Add(cp); } } } for (int step = 0; step < num_contact_steps; step++) { for (int level = 0; level < num_levels; level++) { // process all contacts foreach (CollisionPair cp in collisionsAtLevel[level]) { cp.ResolveContact(dt, (num_contact_steps - step - 1) * -1.0f/num_contact_steps); } } } }}}