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