碰撞检测是计算机动画、计算机图形学、机器人路径规划等领域的重要课题。近几年来，随着虚拟现实技术和分布式仿真技术的兴起，碰撞检测问题成为一个研究热点。快速的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的交互性有着至关重要的作用。层次包围盒方法是解决碰撞检测问题时间复杂性的一种有效的方法，它是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，并通过构造树状层次结构来逼近对象的几何模型。本文首先分析了不同类型的包围盒及其相关算法，由于AABB包围盒平行于空间坐标，很多方面都表现为线性，因此选择AABB包围盒来近似描述对象。本文进一步分析了基于AABB包围盒的相关算法，发现算法的执行速度主要受三个方面的影响：AABB包围盒间的相交测试、AABB树的遍历和基本几何元素的相交测试。本文总结了基于AABB包围盒的碰撞检测算法关于这三个方面采用的算法，然后从时空相关性和存储空间的角度提出了改进。AABB相交测试的速度直接影响着碰撞检测算法的整体速度，包围盒排序法是进行AABB间相交测试的有效方法。本文采用一维空间排序法将AABB的端点值投影到三个坐标轴上，基于对象运动的时空相关性，选用希尔排序法对投影值序列进行排序。由于碰撞行为的局部性，算法在排序之前对坐标轴进行适当的划分，避免了不必要的相交测试，提高了全局搜索阶段算法的速度。在算法的局部检测阶段，本文从存储空间角度来加快对AABB树的遍历。由于构造的AABB树是一棵二叉树，树中每个内部节点只有两个孩子节点，结合孩子节点的包围盒信息可以得到其父结点的包围盒，因此可以压缩存储AABB树。算法首先简化树中每个节点存储结构的包围盒信息，减少父结点和孩子节点间冗余数据的存储，然后将树中所有叶节点的存储信息放置到其父节点里，从AABB树的存储结构里删除叶结点。实验表明，结合包围盒和叶结点的存储优化，既节省了算法所需的存储空间，又加快了算法的执行速度。