Collision Detection Using Sphere-Tree Construction

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 algorithms are either restricted to a class of geometric models, say convex polytopes, or are not fast enough for practical applications. We present a new algorithm for collision detection between general polygonal models. The algorithm makes use of hierarchical representations along with frame to frame coherence to rapidly detect collisions. It has been implemented as part of a motion planning package. In practice, it can accurately detect the contacts between large geometries composed of thousands of polygons at interactive rates.