Handle Collision Pair

At this point we are ready to handle the "possible" collision between the top collision heap pair of objects. We compute the closest feature pair between the pair of objects using the Lin-Canny Closest Features Algorithm. This algorithm allows us to quickly determine the closest feature pairs between the two objects. From that we can determine if we actually have a collision between the two objects. A collision is declared only when the two objects are within some epsilon of one another. Typical epsilon values are many orders of magnitude smaller than the objects in the simulation. For example a bowling simulation that involves a 60 foot alley and 18 inch pins has an epsilon value of one millimeter.

If we have an actual collision, between the two objects an impulse is applied to one of the objects to prevent interpenetration and an equal but opposite impulse is applied to the other object. A complete discussion of the technique for determining the proper impulse to apply to the rigid bodies appear in the papers Impulse-based Simulation of Rigid Bodies and Impulse-based Dynamic Simulation both by Brian Mirtich.

Once the proper impulses have been applied to the two objects, we must compute a new time to impact and update this pair of objects in the collision heap. In addition we must also update any object pair already in the heap which involves either of the two recently collided objects. Normally this would be a tremendously expensive operation, but since we will typically have small heap sizes we will rarely need to update all of the O(n) object pairs potentially affected. Instead we will update only the object pairs that we have previously tagged as close to one of the recently collided objects. This heap reduction significantly reduced the number of heap updates necessary before we can continue with the simulation.

Since this operation does not immediately involve any of the other objects we handle the collision on one processor. We do choose this processor with some intelligence. If the collision is between a moving object and a fixed object, we choose to perform the collision calculations on the processor local to the moving object. This will insure that the entire collision operation can occur locally since fixed objects are local to all processors. We may also have a collision between two objects that are on the same processor in which case collision calculations can proceed without communication. Since these first two cases are highly desirable it would be an important improvement for future parallel implementations to bias the locality of the objects to significantly increase the probability of colliding objects residing on the same processor. In the worst case the two objects will be on separate processors. If so, we simply choose one of the processors to handle the collision and spend time in communicating a few of the necessary pieces of data about the remote object to the controlling processor. Once there, collision and impulse calculations can proceed locally.

After the impulses have been applied to the two objects we need to perform any necessary updates to the heap as describe earlier in this section. Since we have reduced the heap size to include only object pairs that are close to one another, we will only need to perform heap updates and new time to impact estimations for objects that are close, as defined by the spatial hash tiling, to one of the recently collided objects. Rather than performing all of the necessary communication to this single processor, we simply broadcast flags about the necessary heap updates to processors with at least one of the objects in the pair to be updated as local. This improves the performance of this obviously expensive operation.

[ Prev | Home | Next ]

Eric Paulos / paulos@robotics.eecs.berkeley.edu / 10 May 1995