Rapid collision detection by dynamically aligned DOP-trees

Abstract

Based on a general hierarchical data structure, we present a fast algorithm for exact collision detection of arbitrary polygonal rigid objects. Objects consisting of hundreds of thousands of polygons can be checked for collision at interactive rates. The pre-computed hierarchy is a tree of discrete oriented polytopes (DOPs). An efficient way of realigning DOPs during the traversal of such trees allows us to use simple interval tests for determining the overlap between DOPs. The data structure is very efficient in terms of memory and construction time. Extensive experiments with synthetic and real-world CAD data have been carried out to analyze the performance and memory usage of the data structure. A comparison with oriented bounding box (OBB) trees indicates that DOP-trees are as efficient in terms of collision query time and more efficient in memory usage and construction time.