Collision Heap Removal

Since the collision heap is an ordering on possible collision object pairs by soonest expected time to collision, we simply remove the top heap element. We are guaranteed that no such collision can occur before this top heap element pair. Therefore, we prepare to advance the simulation clock up to the point of this "possible" impact. Typically, most of the possible O(n^2) object pairs in the heap will not even be in the heap because they are not close to each other in the spatial hash tiling.

The heap is local to only one processor. Therefore, that processor simply removes the top heap element and broadcasts to all of the other processors both the pair involved in the collision and the time step for this simulation loop. An earlier approach to this problem on a 2D system explored the results of randomly spreading the heap across processors.

[ Prev | Home | Next ]

Eric Paulos / / 10 May 1995