Gabriel Zachmann
University of Bonn
Department of Computer Graphics
53117 Bonn
Germany
e-mail: zach@cs.uni-bonn.de http://cg.cs.uni-bonn.de
Günter Knittel
University of Tübingen
Department of Graphical Interactive Systems
72076 Tübingen
Germany
e-mail: knittel@gris.uni-tuebingen.de
http://www.gris.uni-tuebingen.de
Keywords: graphics hardware, computer animation, virtual %reality, hierarchical algorithms, triangle intersection
Abstract
We present novel algorithms for efficient hierarchical collision detection and propose a hardware architecture for a single-chip accelerator. We use a hierarchy of bounding volumes defined by k-DOPs for maximum performance. A new hierarchy traversal algorithm and an optimized triangle-triangle intersection test reduce bandwidth and computation costs. The resulting hardware architecture can process two object hierarchies and identify intersecting triangles autonomously at high speed. Real-time collision detection of complex objects at rates required by force-feedback and physically-based simulations can be achieved.