Space-Efficient FPGA-Accelerated Collision Detection for Virtual Prototyping

Paper

Abstract

We present a space-efficient, FPGA-optimized architecture to detect collisions among virtual objects, as well as simulation results for collision queries using this architecture. The design consists of two main modules, one for traversing a hierarchical acceleration data structure, and one for intersecting triangles. This paper focuses on the former. The design is based on a novel algorithm for testing discretely oriented polytopes for overlap in 3D space. In addition, we derive a new overlap test algorithm that can be implemented using fixed-point arithmetic without producing false negatives and with bounded error. SystemC simulation results on different levels of abstraction 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 show that the design can still be fitted into a six-million gates FPGA. Furthermore, we compare our FPGA-based design with a fully parallelized ASIC-targeted architecture and a software implementation.

BibTeX entry

@INPROCEEDINGS{Zach06a,
  author      = "Andreas Raabe and Stefan Hochgürtel and
                 Gabriel Zachmann and Joachim K.~Anlauf",
  title       = "Space-Efficient FPGA-Accelerated Collision Detection for 
                    Virtual Prototyping",
  booktitle   = "Design Automation and Test in Europe (DATE)",
  year        = "2006",
  month       = mar # "6--10",
  address     = "Munich, Germany",
  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 16:47:29 MET 2006