INCREMENTAL ALGORITHMS FOR COLLISION DETECTION BETWEEN POLYGONAL MODELS

Fast and accurate collision detection between general polygonal models is a fundamental problem in physically based and geometric modeling, robotics, animation, and computer-simulated environments. Most earlier collision detection algorithms are either restricted to a class of mo dels (such as convex polytopes) or are not fast enough for practical a pplications. We present an incremental algorithm for collision detecti on between general polygonal models in dynamic environments. The algor ithm combines a hierarchical representation with incremental computati on to rapidly detect collisions. It makes use of coherence between suc cessive instances to efficiently determine the number of object featur es interacting. For each pair of objects, it tracks the closest featur es between them on their respective convex hulls. It detects the objec ts' penetration using pseudo internal Voronoi cells and constructs the penetration region, thus identifying the regions of contact on the co nvex hulls. The features associated with these regions are represented in a precomputed hierarchy. The algorithm uses a coherence based appr oach to quickly traverse the precomputed hierarchy and check for possi ble collisions between the features. We highlight its performance on d ifferent applications.