一个快速并且健壮的碰撞检测检测算法在很多领域比如虚拟现实、计算机游戏、计算机辅助设计都扮演着重要角色。近几年来,随着虚拟现实技术和分布式仿真技术的兴起,碰撞检测问题成为一个研究的热点。 相对于刚体对象,变形对象表现在当它移动时组成变形体对象的顶点之间的相对位置发生变化。对于刚体对象,大部分碰撞检测算法所依赖的数据结构都可以在预处理阶段处理完毕。但对于变形体对象,适用于刚体对象的碰撞检测算法将不能直接应用。因为顶点之间的相对位移发生变化,因此用于碰撞检测算法的数据结构必须实时的重新构建或者更新。 对于变形体的碰撞检测算法,本文从两个方面对传统的算法进行改进。第一种方法是处理可变形体对象时更新而不是重新构建数据结构,因为重新构建整个数据结构的时间耗费在一个实时的仿真环境中是不能接受的。同时通过压缩方法对传统AABB层次包围盒进行了改进,通过从空间的角度来对传统的层次AABB包围盒进行优化,从而节省了大量的存储空间,提高了变形体的碰撞检测效率。第二种方法提出了一种基于包围盒方法与空间分解方法相结合的碰撞检测算法,与其他碰撞检测算法相比较,本算法不仅具有能够节省空间,而且时间复杂度也比较低。除此之外,本算法不仅能够找出发生碰撞的基本几何元素对,而且还能够精确地找出碰撞点。