摘要： 本文提出了一种基于包围盒方法与空间分解方法相结合的碰撞检测算法，用于解决变形体的碰撞检测问题。该算法首先用包围盒来快速判断物体之间是否相交，如果相交则进一步用空间分解法来定位相交的区域，在此阶段用哈希表的数据结构来保存物体的几何信息。与其他碰撞检测算法相比较，本算法不仅能够较大地节省空间，而且时间复杂度也比较低。除此之外，本算法不仅能够找出发生碰撞的基本几何元素对，而且还能够精确地找出碰撞点。

关键词: 碰撞检测算法 包围盒 空间分解 时间复杂度 分解方法 快速判断 几何信息 数据结构 几何元素 变形体 相交 分解法 哈希表 碰撞点 物体