Approximating polyhedra with spheres for time-critical collision detection

This article presentsa method for approximatingpolyhedralobjects to support a time-critical collision-detectionalgorithm. The approximationsare hierarchies of spheres, and they allow the time-critical algorithm to progressively refine the accuracy of its detection, stopping as needed to maintain the real-time performanceessential for interactive applications. The key to this approach is a preprocessthat automaticallybuilds tightly fitting hierarchies for rigid and articulatedobjects.The preprocessuses medial-axis surfaces, which are skeletal representations of objects. These skeletons guide an optimizationtechnique that gives the hierarchies accuracy properties appropriate for collision detection. In a sample application, hierarchies built this way allow the time-criticalcollision-detectionalgorithmto have acceptableaccuracy, improving significantly on that possible with hierarchies built by previous techniques. The performanceof the time-critical algorithm in this application is consistently 10 to 100 times better than a previous collision-detection algorithm, maintaining low latency and a nearIy constant frame rate of 10 frames per second on a conventional graphics workstation. The time-critical algorithm maintains its real-time performance as objects become more complicated, even as they exceed previously reported complexity levels by a factor of more than 10.