Hardware-Accelerated Collision Detection
using Bounded-Error Fixed-Point Arithmetic
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.
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
(For instance, if your host is not registered by the world-wide Domain
Name Service (DNS), then you will not be able to ftp ...)
Tue Mar 21 18:36:01 MET 2006