ALCOMFT-TR-03-132

Jan Klein and Gabriel Zachmann
ADB-Trees: Controlling the Error of Time-Critical Collision Detection
Paderborn. Work package 5. December 2003.

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.

Postscript file: ALCOMFT-TR-03-132.ps.gz (414 kb).