基于B+树存储的AABB包围盒碰撞检测算法

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

对于碰撞检测算法,使用传统的AABB包围盒来构建包围盒层次树时,其包围盒层次树的层数、叶子结点的个数和各结点的存储字节数是影响碰撞检测效率的主要因素。为了减少结点存储容量对碰撞检测效率的影响,提高碰撞检测的效率,文中采取B+树的存储结构来存储包围盒等信息。在包围盒相交测试之前,使得各结点存储索引有序,不需要再对各结点进行额外的排序,减少了内存开销,并且避免了不必要的包围盒测试。此外B+树的非叶子结点不存储具体的数据信息,从而减少了整棵树的存储空间。实验表明,在检测环境和检测对象相同的条件下,使用B+树存储的AABB包围盒碰撞检测算法的检测时间明显比传统的AABB算法短。

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.