Research on Bounding Box-Tree Algorithm for Collision Detection

Abstract:

In order to improve the efficiency of the collision detection for polyhedron, the paper proposed a collision detection algorithm based on bounding box-tree. The hierarchical bounding box –tree was built by dividing the polyhedron into tetrahedron. The collision detection can be completed by the method searching the bounding box-tree from top to bottom or from bottom to top. The algorithm quickly eliminated the possibility of collision between objects far apart. And it well adapted to the needs of the dynamic collision detection. Test results showed that the algorithm greatly improved the collision detection’s speed in virtual environment.

• Periodical: Advanced Materials Research (Volume 186)
• Pages: 645-649
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.186.645
• Online since: January 2011
• Authors: Yu Mei Xiong, Yi Min Chen, Yi Hao Chen
• Keywords: Bounding Box-Tree, Collision Detection, Polyhedron, Tetrahedron

References

[1] Ilan Grinberg, Yair Wiseman, Scalable parallel collion detection simulation. IIE Transactions(2003)15, 11-15.

[2] M. TESCHNER, B. HEIDELBERGER, M. MUELLER, D. POMERANETS, and M. GROSS. Optimized spatial hashing for collision detection of deformable objects[C]. In Proc. of Vision, Modeling, Visualization, pp: 47–54(2003).

[3] R. G. LUQUE, J. L. D. COMBA and C. M. D. S. FREITAS. Broad-phase collision detection using semi-adjusting bsp-trees [C]. In SI3D '05: Proceedings of the 2005 symposium on Interactive 3D graphics and games, New York, USA(2005).

DOI: 10.1145/1053427.1053457

[4] B. Heidelberger, M. Teschner and M. Gross. Detection of collisions and self-collisions using image-space techniques. In Proceedings of WSCG'04, p.145–152(2004).

[5] G. Bergen. Collision Detection in Interactive 3D Environments. Morgan Kaufmann Publishers. Elsevier, San Francisco(2004).

[6] J.M. Keil,T. Vassilev, Algorithms for optimal area triangulations of a convex polygon, Computational Geometry: Theory and Ap-plications(2006), 35(3): 173-187.

DOI: 10.1016/j.comgeo.2006.03.004

[7] Rade Besic, Pat Banerjee, Exact collision detection for a virtual manufacturing simulator, IIE Transactions(2001)33, 43-54.

DOI: 10.1080/07408170108936805

[8] Tian Zun-hua, Zhao Long, Research of dynamic collision detection algorithm based on entity behaviors, Journal of System Simulation(2009), 21(5): 1380-1383.

[9] Xiong, Yumei, Chen Yimin, Parallel Collision Detection Algorithm Based on decomposing a Polyhedron into Tetrahedrons, Proceeding of the 2009 Second International Workshop on Computer Science and Engineering(2009), pp.501-503.

DOI: 10.1109/wcse.2009.719

[10] Ren Shijun, Hong Bingrong, A Fast Algorithm to Determine Whether the Intersection of Two Convex Regions Is Empty, Journal of Software(2000), 11(4)：563-568.