You can also download the
PDF version (550 kB).
An algorithm for exact collision detection is presented which can handle arbitrary non-convex polyhedra efficiently. The approach attains its speed by a hierarchical adaptive space subdivision scheme, the BoxTree, and an associated divide-and-conquer traversal algorithm, which exploits the very special geometry of boxes.
The traversal algorithm is generic, so it can be endowed with other semantics operating on polyhedra, e.g., distance computations.
The algorithm is fairly simple to implement and it is described in great detail in an ``ftp-able'' appendix to facilitate easy implementation. Pre-com\-pu\-ta\-tion of auxiliary data structures is very simple and fast.
The efficiency of the approach is shown by timing results and two real-world digital mock-up scenarios.