Computer Science ›› 2021, Vol. 48 ›› Issue (6A): 331-333.doi: 10.11896/jsjkx.200600113

• Intelligent Computing • Previous Articles     Next Articles

Collision Detection Algorithm of AABB Bounding Box Based on B+ Tree

YANG Fan   

  1. University of Electronic Science and Technology of China,Chengdu 611731,China
  • Online:2021-06-10 Published:2021-06-17
  • About author:YANG Fan,born in 1995,postgraduate.His main research interests include artificial intelligence and big data.

Abstract: For the collision detection algorithm,when using a traditional AABB bounding box to construct a bounding box hierarchy tree,the number of bounding box hierarchy trees,the number of leaf nodes,and the number of bytes stored in each node are the main factors that affect the efficiency of collision detection factor.In order to reduce the impact of node storage capacity on collision detection efficiency and improve the efficiency of collision detection,this paper adopts a B+ tree storage structure to store information such as bounding boxes.Before the bounding box intersection test,the storage index of each node is ordered,no additional sorting of each node is required,which reduces the memory overhead and avoids unnecessary bounding box testing.In addition,the non-leaf nodes of the B+ tree do not store specific data information,thereby reducing the storage space of the entire tree.Experiments show that the detection time of the AABB bounding box collision detection algorithm using B+ tree storage is significantly shorter than the traditional AABB algorithm under the same detection environment and detection object.

Key words: AABB, B+ tree, Collision detection, Hierarchical bounding box, Intersection test

CLC Number: 

  • TP391.41
[1] 王志强,洪嘉振,杨辉.碰撞检测问题研究综述[J].软件学报,1999(5):98-104.
[2] GARICA-ALONSO A,SERRANO N.Solving the Collision Detection Problem[J].IEEE Computer Graphics and Application,1994,13(3):36-43.
[3] 王伟.轴对齐包围盒算法的研究[J].网络安全技术与应用,2013(10):127-128.
[4] 潘振宽,李建波.基于压缩的AABB树的碰撞检测算法[J].计算机科学,2005,33(2):213-215.
[5] 沈学利,吴琼.基于包围盒和空间分割的混合碰撞检测算法[J].计算机工程,2012,38(6):256-258.
[6] LI C F,FENG Y T,OWEN D R J.SMB:Collision detectionbased on temporal coherence[J].Computer Methods in AppliedMechanics and Engineering,2005,195(19):2252-2269.
[7] 施恩,顾大权,冯径,等.B+树索引机制的研究及优化[J].计算机应用研究,2017,34(6):1766-1769.
[8] 王崴,周诚,杨云,等.面向虚拟维修的碰撞检测算法[J].计算机应用与软件,2016,33(4):235-238.
[9] AKENINE-MÖLLSER T.Fast 3D Triangle-Box Overlap Testing[J].Journal of Graphics Tools,2001,6(1):29-33.
[10] 金汉均.虚拟环境中物体碰撞检测算法研究[D].武汉:华中科技大学,2006.
[11] 孙黎阳,毛少杰,林剑柠,等.基于XYZ/ADL的网络中心化仿真运行支撑平台体系结构形式化描述[J].计算机科学,2012,39(S1):365-369.
[1] LI Pu, SUN Chang-le, XIONG Wei, WANG Hai-tao. Collision Detection Algorithm Based on Semi-transparent Color Overlay and Depth Value [J]. Computer Science, 2018, 45(6A): 193-197.
[2] SHEN Ying, WANG Hui, WANG Li-hui and WU Qing-qing. Simplifying 3D Models and Collision Detection on Smartphones [J]. Computer Science, 2017, 44(Z11): 251-256.
[3] PAN Ren-yu, SUN Chang-le, XIONG Wei and WANG Hai-tao. Survey and Prospect of Collision Detection Based on Virtual Assembly Environment [J]. Computer Science, 2016, 43(Z11): 136-139.
[4] LIU Hai-ping. Research on Collision Detection of Convex Polyhedron Based on Mixed Artificial Fish Swarm Algorithm [J]. Computer Science, 2014, 41(Z6): 61-63.
[5] WU Yan-lian,TANG Liang.CAO Wei-xing,ZHU Yan. Collision Detection and Response in Crop Visualization [J]. Computer Science, 2011, 38(10): 263-266.
[6] ZHAO Wei,LI Wen-hui. Fast Collision Detection Algorithm for Spherical Blend Reconstruction [J]. Computer Science, 2009, 36(7): 164-169.
[7] . [J]. Computer Science, 2008, 35(7): 161-165.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!