Colli sion Detection: Algorithms and Applications

Abstract

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 e cient 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 torapidly detect collisions. It is robust and has been implemented aspart 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. 1