Accurate and fast proximity queries between polyhedra using convex surfacedecomposition

The need to perfom fast and accurate proximity queries arises frequently in physically-based modeling, simulation, animation real-time interaction wit hin a virtual environment, and game dynamics. The set of proximity queries include intersection detection, tolerance verification, exact and approxima te minimum distance computation, and (disjoint) contact determination. Spec ialized data structures and algorithms have often been designed to perform each type of query separately. We present a unified approach to perform any of these queries seamlessly for general, rigid polyhedral objects with bou ndary representations which are orientable 2-manifolds. The proposed method involves a hierarchical data structure built upon a surface decomposition of the models. Furthermore, the incremental query algorithm takes advantage of coherence between successive frames. It has been applied to complex ben chmarks and compares very favorably with earlier algorithms and systems.