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