An Architecture for Hierarchical Collision Detection
You can download different versions of the paper:
The PDF version is optimized for onscreen 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 singlechip
accelerator. We use a hierarchy of bounding volumes defined by
kDOPs for maximum performance. A new hierarchy traversal
algorithm and an optimized triangletriangle intersection test
reduce bandwidth and computation costs. The resulting hardware
architecture can process two object hierarchies and identify
intersecting triangles autonomously at high speed. Realtime
collision detection of complex objects at rates required by forcefeedback
and physicallybased 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 = "149156"
, month = feb # "37"
, 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 = d_{start} 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 xaxis 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:
 Time: average collision detection time for a certain
distance; the average was taken over many collision queries with
different object orientations (see above).
 Num overlap tests: average number of BV pair overlap tests during
one collision test.
 Num DOP transforms: average number of DOP transformations that are
performed during one collision test.
 Num nodes visited: total average number of BV tree nodes that are
visited during one collision test; this counts both tree's nodes, and
multiple visits of the same node are counted multiple times. So, this
number is proportional to the amount of data that must be transfered
from memory during collision test.
 Num pgon intersection tests: average number of polygonpolygon
intersection tests; this is the number of leaf pairs that are reached
during one collision test without finding a collision.
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 worldwide Domain
Name Service (DNS), then you will not be able to ftp ...)
Gabriel Zachmann
Last modified:
Sat Sep 10 15:59:23 MDT 2005