You can download the Postscript version (208 kB)

You can also download the PDF version (1.0 MB).

An appendix describes more mathematical details.

Abstract
An algorithm for exact collision detection is presented which can handle arbitrary non-convex polyhedra efficiently. Despite the wealth of literature, there are not many fast algorithms for this class of objects.

The approach attains its speed 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 to implement and it is described in great detail in an appendix to facilitate easy implementation. The construction of the data structure is very simple and very fast. Timing results show the efficiency of this approach.

Location
SIVE95 (First Workshop on Simulation and Interaction in Virtual Environments), University of Iowa, July 1995.

In case of problems
In case of problems, please don't hesitate to contact me.
(For instance, if your host is not registered by the world-wide Domain Name Service (DNS), then you will not be able to ftp ...)
Gabriel Zachmann
Last modified: Sat Sep 10 15:53:15 MDT 2005