Stephen Sorkin

Stanford University

“Efficient Collision Detection for Flexible Objects”

This paper presents an efficient algorithm for determining whether two deformable, non-convex objects are in collision. The algorithm is based on sphere-tree hierarchies and provides a method to quickly adjust the hierarchies when the objects deform.  Although the algorithm allows for arbitrary deformations of the objects, the actual collision query remains most efficient when the deformation from the original object remains bounded.  Like Quinlan's algorithm on which this work is based, we allow for query-time settable error rates to provide a continuum of information between collision detection and exact distance computation.  Empirical evidence demonstrates that the algorithm provides real-time performance on useful-sized models.