关键词: AABB, B+树, 层次包围盒, 碰撞检测, 相交测试

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