基于AABB包围盒的碰撞检测算法的研究

Research of Collision Detection Algorithms Based on AABB

利用虚拟空间中对象运动的特性和AABB包围盒的构造特性,改进了基于AABB层次包围盒的碰撞检测算法。传统的该类算法分为两个检测过程,在初步检测过程中,基于运动对象碰撞行为的局部性,改进了原来的排序方法,采用希尔排序。为了提高检测效率,在相交测试之前将检测对象细分,划分测试区域,避免了不必要的相交测试;在对可能相交的对象进行精确检测过程中,基于AABB包围盒的构造特性,对可能碰撞对象的层次包围盒树进行压缩存储,通过减少算法的存储空间来提高算法的检测速度。对算法的两个检测过程同时进行改进,实验表明在检测对象较多的情况下减少了算法所需的执行时间。

An improved collision detection algorithm based on AABB is presented. Collision is a local behavior, during the sorting procedure, each axis is cut into a series of segments containing the same number of projection intervals. This will avoid needless intersecting test of AABB. And Shell sorting is adopted. Then the storage of the AABB tree is compressed. This way can save a large amount of space and speed up the algorithm.