Time-Critical Collision Detection Using an Average-Case Approach

Paper
gzipped Postscript PDF
Print version: VRST'03 (850 kB) VRST'03 (830 kB)
Screen: VRST'03 (740 kB) VRST'03 (780 kB)
Slides: VRST'03 (250 kB) VRST'03 (620 kB)

The screen version is optimized for on-screen viewing: color plots, hyperlinks, lores images.
The print version is optimized for printing: no color plots, no hyperlinks, but hires images.

Movies
AVI (12 MB)

The movie shows those bounding volume pairs that have at least one collision cell with probability larger than the predefined threshold. The different colors of the BVs just denote which object they belong to.
Abstract
We present a novel, generic framework and algorithm for hierarchical collision detection, which allows an application to balance speed and quality of the collision detection.

We pursue an average-case approach that yields a numerical measure of the quality. This can either be specified by the simulation or interaction, or it can help to assess the result of the collision detection in a time-critical system.

Conceptually, we consider sets of polygons during traversal and estimate probabilities that there is an intersection among these sets. This can be done efficiently by storing characteristics about the average distribution of the set of polygons with each node in a bounding volume hierarchy (BVH). Consequently, we neither need any polygon intersection tests nor access to any polygons during the collision detection process.

Our approach can be applied to virtually any BVH. Therefore, we call a BVH that has been augmented in this way an average-distribution tree or ADB-tree.

We have implemented our new approach with two basic BVHs and present performance measurements and comparisons with a very fast previous algorithm, namely the DOP-tree. The results show a speedup of about a factor 3 to 6 with only approximately 4% error.

Keywords
Interference Detection, Virtual Prototyping, Hierarchical Partitioning, Bounding Volume Trees, Hierarchical Data Structures, Probabilistic Analysis, Average-Case Algorithms
BibTeX entry
@INPROCEEDINGS{Zach03b
,  author = "Jan Klein and Gabriel Zachmann"
,  title = "Time-Critical Collision Detection Using an Average-Case Approach"
,  booktitle = "Proc. ACM Symp. on Virtual Reality Software and Technology
                (VRST)"
,  year = 2003
,  address = "Osaka, Japan"
,  month = oct # "1--3"
,  url = "http://www.gabrielzachmann.org/"
}
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:58:45 MDT 2005