Summary

In this work, we present a scalable high-level parallel solution to a large subclass of collision detection problems. Our approach is to divide space into a sparse grid of regular axis-aligned voxels distributed across the parallel machine. Objects are then sent to all the voxels they intersect. Once all the objects have arrived, each voxel becomes a self-contained subproblem, which is then solved using standard serial collision detection approaches.

The voxels efficiently and naturally separate many objects that cannot ever collide, by placing them in separate voxels. Simultaneously, it brings together adjacent objects that may intersect.

The basic voxel algorithm is theoretically independent of the object type and serial collision detection method used. In practice, the method works best when there is not too much scale disparity- objects much larger than a voxel will be sent to several voxels, wasting space and time; while structures much smaller than a voxel must be dealt with entirely via the serial approach. Further, the serial collision detection method used must be able to gracefully handle objects entering and leaving the problem space as time progresses.

For problems which conform to these limitations, however, the serial and parallel performance of the voxel scheme is excellent. Subject to certain reasonable assumptions, the theoretical time taken by the voxel algorithm for $n$ objects on $p$ processors is the optimal $O(n/p)$- that is, linear serial time and perfect parallel speedup. In this work, we present and analyze an implementation of the voxel method.