Fast and Accurate Collision Detection for Virtual Environments

A realistic simulation system, which couples geometry and physics, can provide a useful toolkit for virtual environments. Interactions among moving objects in the virtual worlds are modeled by dynamic constraints and contact analysis. In order to portray the geometric interaction in a dynamical system or to simulate physical behaviors of entities in the virtual environments, it is essential to perform collision detection at interactive rate with minimal computation possible. In this paper, we present efficient algorithms for contact determination and interference detection between geometric models undergoing rigid motion. The set of models includes polyhedra and surfaces described by B-splines. The algorithms make use of temporal and spatial coherence between successive instances to reduce the number of pairwise tests and hierarchical data structures for checking overlaps between a pair of objects. Their running time is a function of the motion between successive instances. The main characteristics of these algorithms are their simplicity and efficiency. They have been implemented. A subset of these implementations, including I-Collide, RAPID and V-Collide are available as part of the collision detection packages at the UNC-CH website.