Efficient collision detection using bounding volume hierarchies ofk-DOPs

摘要

Collision detection is of paramount importance for manynapplications in computer graphics and visualization. Typically, theninput to a collision detection algorithm is a large number of geometricnobjects comprising an environment, together with a set of objects movingnwithin the environment. In addition to determining accurately thencontacts that occur between pairs of objects, one needs also to do so atnreal-time rates. Applications such as haptic force feedback can requirenover 1000 collision queries per second. We develop and analyze a method,nbased on bounding-volume hierarchies, for efficient collision detectionnfor objects moving within highly complex environments. Our choice ofnbounding volume is to use a discrete orientation polytope (k-DOP), anconvex polytope whose facets are determined by halfspaces whose outwardnnormals come from a small fixed set of k orientations. We compare anvariety of methods for constructing hierarchies (BV-trees) of boundingnk-DOPs. Further, we propose algorithms for maintaining an effectivenBV-tree of k-DOPs for moving objects, as they rotate, and for performingnfast collision detection using BV-trees of the moving objects and of thenenvironment. Our algorithms have been implemented and tested. We providenexperimental evidence showing that our approach yields substantiallynfaster collision detection than previous methods