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

关键词：碰撞检测 包围盒树 相交测试 希尔排序 压缩存储 

单位：广西工学院计算机工程系 广西柳州545006