“The expected running time of hierarchical collision detection” by Klein and Zachmann
Conference:
Type:
Title:
- The expected running time of hierarchical collision detection
Presenter(s)/Author(s):
Abstract:
We propose a model to analyze the expected running time of hierarchical collision detection that utilizes bounding volume hierarchies (BVHs). It depends on two characteristic parameters: the overlap of the root BVs and the BV diminishing factor within the hierarchies. We show that the average running time is in O(n) or even in O(log n) for realistic cases, where n is the number of leaves. Our theoretical analysis is verified by practical experiments.
References:
1. Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A hierarchical structure for rapid interference detection. ACM Transactions on Graphics (SIGGRAPH 1996) 15, 3, 171–180.
2. James, D. L., and Pai, D. K. 2004. BD-Tree: Output-sensitive collision detection for reduced deformable models. ACM Transactions on Graphics (SIGGRAPH 2004) 23, 3 (Aug.), 393–398.
3. Weghorst, H., Hooper, G., and Greenberg, D. P. 1984. Improved computational methods for ray tracing. ACM Trans. Graph. 3, 1, 520–69.
