Real-time and exact collision detection for interactive Virtual Prototyping

Many companies have started to investigate Virtual Reality as a tool for evaluating digital mock-ups. One of the key funtions needed for interactive evaluation is real-time collision detection. An algortithm 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 BosTree, 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" a[[endix to facilitate easy implementation. Pre-computation 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.