EFFICIENT COLLISION DETECTION USING BOUNDING VOLUME HIERARCHIES OF K-DOPS

Collision detection is of paramount importance for many applications i n computer graphics and visualization. Typically, the input to a colli sion detection algorithm is a large number of geometric objects compri sing an environment, together with a set of objects moving within the environment. In addition to determining accurately the contacts that o ccur between pairs of objects. one needs also to do so at real-time ra tes. Applications such as haptic force-feedback can require over 1,000 collision queries per second. In this paper, we develop and analyze a method, based on bounding-volume hierarchies, for efficient collision detection for objects moving within highly complex environments. Our choice of bounding volume is to use a ''discrete orientation polytope' ' (''k-dop''), a convex polytope whose facets are determined by half s paces whose outward normals come from a small fixed set of k orientati ons. We compare a variety of methods for constructing hierarchies (''B V-trees'') of bounding k-dops. Further, we propose algorithms for main taining an effective BV-tree of k-dops for moving objects, as they rot ate, and for performing fast collision detection using BV-trees of the moving objects and of the environment. Our algorithms have been imple mented and tested. We provide experimental evidence showing that our a pproach yields substantially faster collision detection than previous methods.