An Architecture for Hierarchical Collision Detection

You can download different versions of the paper:
gzipped Postscript PDF
Same as proceedings: WSCG'03 (380 kB) WSCG'03 (960 kB)
Extended: WSCG'03 (380 kB) WSCG'03 (1 MB)
The PDF version is optimized for on-screen viewing (color plots, hyperlinks, lores images).
The Postscript version is optimized for printing (no color plots, no hyperlinks, but hires images).

And here are a the slides of the talk (140 kB).

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.
Keywords
Graphics hardware, computer animation, virtual reality, hierarchical algorithms, triangle intersection.
BibTeX Entry
@INPROCEEDINGS{Zach03
,  author = "Gabriel Zachmann and GŁnter Knittel"
,  title = "An Architecture for Hierarchical Collision Detection"
,  booktitle = "Journal of WSCG '2003"
,  pages = "149--156"
,  month = feb # "3--7"
,  year = 2003
,  address = "University of West Bohemia, Plzen, Czech Republic"
,  url = "http://www.gabrielzachmann.org/"
}
Additional Material
Here are some additional plots showing various aspects of a comparison of the performance of the old traversal scheme (red) and the new one (green):
Average Maximum
Object Obj name Time Num overlap tests Num DOP transforms Num nodes visited Num pgon intersection tests Time Num overlap tests Num DOP transforms Num nodes visited Num pgon intersection tests
Cover (Abdeckung), 30477 polygons each
Happy Buddha (buddha), 125,000 polygons each
Front Light (scheinwerfer), 30075 polygons each
Door Lock (schloss), 26136 polygons each
Car Body (sharan), 28167 polygons each
The time plots show the collision detection time depending on the "distance" between the two objects, for one polygon count (as given in the column "obj name"). The "num" plots show statistics of various characteristic numbers (see below for an explanation), depending on the polygon count.

Benchmarking procedure: two identical objects are positioned at a certain distance d = dstart from each other. The distance is computed between the centers of the bounding boxes of the two objects; objects are scaled uniformly so they fit in a cube of size [-1,+1]3. Then, one of them performs a full tumbling turn about the z- and the x-axis by a fixed, large number of small steps (5000). With each step, a collision query is done, and the average collision detection time for a complete revolution at that distance is computed. Then, d is decreased, and a new average collision detection time is computed. The collision detection algorithm always stopped whenever the first pair of intersecting polygons was found.

Explanation of the columns:

The maxium columns are exactly the same as the average, except that here, the maximum over all rotations (with one distance) is listed.

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: Sat Sep 10 15:59:23 MDT 2005