UC San Diego

We introduce a framework for collision detection between a pair of rigid polyhedra. Given the initial and final positions and orientations of two objects, the algorithm determines whether they collide, and if so, when and where. All collisions, including collisions at different times, are computed at once along with "properness" values that measure the extent to which the collisions are between parts of the objects that properly face each other. This is useful for handling multiple (nearly) concurrent collisions and contact points. The relative motions of the rigid bodies are limited to screw motions. This limitation is not always completely accurate, but we can estimate the error introduced by the assumption. Our implementation uses rasterization to approximate the position and time of the collisions. This allows level-of-detail techniques that provide a tradeoff between accuracy and computational expense. The collision detection algorithms are only approximate, both because of the screw motion assumption and because of the rasterization. However, they can be made robust so as to give consistent information about collisions and to avoid sensitivity to roundoff errors.