Time-Critical Collision Detection Using an Average-Case Approach

J. Klein and Gabriel Zachmann
In proceedings of VRST 2003, Oct. 2003
Presented at VRST 2003
 

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 DOPtree. 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-time-critical,
      author = {Klein, J. and Zachmann, Gabriel},
       title = {Time-Critical Collision Detection Using an Average-Case Approach},
   booktitle = {VRST 2003},
        year = {2003},
       month = oct,
    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 DOPtree. The results show a speedup of
                about a factor 3 to 6 with only approximately 4% error.},
  conference = {VRST 2003}
}