Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

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

 
: Zachmann, G.; Felger, W.

Association for Computing Machinery -ACM-:
1st Workshop on Simulation and Interaction in Virtual Environments 1995. Informal proceedings for participants only
Iowa City, 1995
pp.104-113
Workshop on Simulation and Interaction in Virtual Environments (SIVE) <1, 1995, Iowa City>
English
Conference Paper
Fraunhofer IGD ()
Collision Detection; hierarchical data structure; virtual reality

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 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.

: http://publica.fraunhofer.de/documents/PX-6892.html