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

T. Ertl, B. Girod, G. Greiner, H. Niemann, H.-P. Seidel, E. Steinbach, and R. Westermann (Editors)
J. Klein and Gabriel Zachmann
In proceedings of Vision, Modeling and Visualisation 2003, pages 37-46, Akademische Verlagsgesellschaft Aka GmbH, Berlin, Nov. 2003
Presented at The 8th International Fall Workshop Vision, Modeling and Visualisation 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 timecritical 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 trees 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.

Download Paper

Download Paper

Bibtex

@INPROCEEDINGS{klein-2003-adb-trees,
      author = {Klein, J. and Zachmann, Gabriel},
      editor = {Ertl, T. and Girod, B. and Greiner, G. and Niemann, H. and Seidel, H.-P. and Steinbach, E. and
                Westermann, R.},
       pages = {37--46},
       title = {ADB-Trees: Controlling the Error of Time-Critical Collision Detection},
   booktitle = {Vision, Modeling and Visualisation 2003},
        year = {2003},
       month = nov,
   publisher = {Akademische Verlagsgesellschaft Aka GmbH, Berlin},
    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 timecritical 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 trees 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.},
        isbn = {3-89838-048-3},
  conference = {The 8th International Fall Workshop Vision, Modeling and Visualisation 2003}
}