TABLE OF CONTENTS Ming C. Lin, U. S. Army Research Office and University of North Carolina, Chapel Hill, NC, USA
Dinesh Manocha, University of North Carolina, Chapel Hill, NC, USA
Jon Cohen, University of North Carolina, Chapel Hill, NC, USA
Stefan Gottschalk, University of North Carolina, Chapel Hill, NC, USA
Fast and accurate collision detection between general geometric models is a fundamental problem in modeling, 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 applications. We present an efficient and accurate algorithm for collision detection between general polygonal models in dynamic environments. The algorithm makes use of hierarchical representations along with frame to frame coherence to rapidly detect collisions. It is robust 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.
Collision detection is a fundamental problem in robotics, computer animation, physically-based modeling, molecular modeling and computer simulated environments. In these applications, an object's motion is constrained by collisions with other objects and by other dynamic constraints. The problem has been...
