gzipped Postscript | ||
---|---|---|
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) |
AVI (12 MB) |
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.
@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/" }