ABSTRACT
Fast and accurate collision detection between general geometric models is a fundamental problem in model ing, robotics, manufacturing and computer-simulated environments. Most of the earlier algorithm are either restricted to a class of geometric models, say convex polytopes, or are not fast enough for practical applica tions. We present an efficient and accurate algorithm for collision detection between general polygonal mod els in dynamic environments. The algorithm makes use of hierarchical representations along with frame to frame coherence to rapidly detect collisions. It is ro bust and has been implemented as part of public domain packages. In practice, it can accurately detect all the contacts between large complex geometries composed of hundreds of thousands of polygons at interactive rates.
