Minimal Hierarchical Collision Detection

The original paper as PDF version (860 kB).
It is optimized for on-screen viewing (color plots, hyperlinks, lores images).

The original paper as Postscript version (360 kB).
It is optimized for printing (no color plots, no hyperlinks, but hires images).

Extended version (and different font): as PDF version (480 kB) or as Postscript version (400 kB).

The slides from the confence talk (PDF, 100kB).

Abstract
We present a novel bounding volume hierarchy that allows for extremely small data structure sizes while still performing collision detection as fast as other classical hierarchical algorithms in most cases. The hierarchical data structure is a variation of axis-aligned bounding box trees. In addition to being very memory efficient, it can be constructed efficiently and very fast. We also propose a criterion to be used during the construction of the BV hierarchies is more formally established than previous heuristics. The idea of the argument is general and can be applied to other bounding volume hierarchies as well. Furthermore, we describe a general optimization technique that can be applied to most hierarchical collision detection algorithms. Finally, we describe several box overlap tests that exploit the special features of our new BV hierarchy. These are compared experimentally among each other and with the DOP tree using a benchmark suite of CAD data.

Keywords
Interference detection, virtual prototyping, hierarchical partitioning, hierarchical data structures, physically-based modeling, R-trees.

BibTeX entry
@INPROCEEDINGS{Zach02c
,  author      = "Gabriel Zachmann"
,  title       = "Minimal Hierarchical Collision Detection"
,  booktitle   = "Proc. ACM Symposium on Virtual Reality Software and Technology
                (VRST)"
,  year        = 2002
,  address     = "Hong Kong, China"
,  month       = nov # "11--13"
,  pages       = "121--128"
,  url         = "http://www.gabrielzachmann.org/"
}




In case of problems
In case of problems, please don't hesitate to contact me.
Gabriel Zachmann
Last modified: Sat Sep 10 15:58:35 MDT 2005