Real-time and Exact Collision Detection for Interactive Virtual Prototyping

You can download the Postscript version (630 kB).

You can also download the PDF version (550 kB).

Many companies have started to investigate Virtual Reality as a tool for evaluating digital mock-ups. One of the key functions needed for interactive evaluation is real-time collision detection.

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.

Proc. of the 1997 ASME Design Engineering Technical Conferences, September 14-17, 1997, Sacramento, California. Paper #CIE-4306.

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:52:33 MDT 2005