Hardware-Accelerated Collision Detection using Bounded-Error Fixed-Point Arithmetic

Documents
Paper Slides

Abstract
A novel approach for highly space-efficient hardware-accelerated collision detection is presented. This paper focuses on the architecture to traverse bounding volume hierarchies in hardware. It is based on a novel algorithm for testing discretely oriented polytopes (DOPs) for overlap, utilizing only fixed-point (i.e., integer) arithmetic. We derive a bound on the deviation from the mathematically correct result and give formal proof that no false negatives are produced. Simulation results show that real-time collision detection of complex objects at rates required by force-feedback and physically-based simulations can be obtained. In addition, synthesis results prove the architecture to be highly space efficient. We compare our FPGA-optimized design with a fully parallelized ASIC-targeted architecture and a software implementation.
BibTeX entry
@INPROCEEDINGS{Zach06b,
  author      = "Andreas Raabe and  Stefan Hochgürtel and
                 Gabriel Zachmann and Joachim K.~Anlauf",
  title       = "Hardware-Accelerated Collision Detection
                 using Bounded-Error Fixed-Point Arithmetic",
  booktitle   = "The 14-th Int'l Conference in Central Europe on
                Computer Graphics, Visualization and
                Computer Vision (WSCG)",
  year        = "2006",
  address     = "Plzen,  Czech Republic",
  url         = "http://www.collisionchip.de",
}
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: Tue Mar 21 18:36:01 MET 2006