"ADB-Trees: Controlling the Error of Time-Critical Collision Detection"

ADB-Trees: Controlling the Error of Time-Critical Collision Detection

Paper

	gzipped Postscript	PDF
Print:	VMV'03 (520 kB)	VMV'03 (620 kB)
Screen:	VMV'03 (400 kB)	VMV'03 (550 kB)
Slides:	VMV'03 (380 kB)	VMV'03 (1 MB)

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

XViD (3.6 MB)

Indeo 5.1 (22 MB)

Another version (5 MB)

Abstract

We present a novel framework for hierarchical collision detection that can be applied to virtually all bounding volume (BV) hierarchies. It allows an application to trade quality for speed. Our algorithm yields an estimation of the quality, so that applications can specify the desired quality. In a time-critical system, applications can specify the maximum time budget instead, and quantitatively assess the quality of the results returned by the collision detection afterwards.

Our framework stores various characteristics about the average distribution of the set of polygons with each node in a BV hierarchy, taking only minimal additional memory footprint and construction time. We call such augmented BV hierarchies average-distribution tree or ADB-trees.

We have implemented our new approach by augmenting AABB trees 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.

BibTeX entry

@INPROCEEDINGS{Zach03d
,  author = "Jan Klein and Gabriel Zachmann"
,  title = "ADB-Trees: Controlling the Error of Time-Critical Collision
            Detection"
,  booktitle = "8th International Fall Workshop Vision, Modeling, and
                Visualization (VMV)"
,  year = 2003
,  month = nov # "19--21"
,  address = "University M{\"u}nchen, Germany"
,  isbn = "1-58603-393-X"
,  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: Tue Dec 06 14:34:49 MET 2005