The BoxTree. Enabling real-time and exact collision detection of arbitrary polyhedra

An algorithm for exact collision detection is presented which can handle arbitrary non-convex polyhedra efficiently. Despite the wealth of literature, there are not namy fast algorithms for this class of objects. The approach attains its speeed by a hierarchical data structure, the BoxTree, and an associated divide-and-conquer traversal algorithm, which exploits the very special geometry of boxes. Boxes were chosen, because they offer much tighter space partitioning than spheres. The method is generic, so it can be endowed with other semantics operating on polyhedra. The algorithm is fairly simple and it is described in great detail in the appendix to facilitate easy implementation. Timing results show the efficiency of this approach.