碰撞检测是虚拟现实、动画仿真、计算机辅助设计等领域不可回避的问题之一,其基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。尽管人们已经取得了一系列成果,但是这些算法侧重于考虑碰撞检测的精确性,很少涉及实时性。随着计算机软硬件及网络等技术的日益成熟,交互实时性、场景真实性要求令碰撞检测再度成为图形学研究的热点。本文主要研究基于K-DOPS包围盒方法的碰撞检测,阐述了K-DOPS包围盒的原理,提出并证明了一种快速区间测试法以解决两个K-DOPS包围盒间的相交测试问题,通过查找两个包围盒在由固定方向集合所定义的方向轴上的范围区间是否存在不重叠的情况,来判断它们是否不相交。通过这种简单的区间测试法,两个包围盒间的相交测试最多只需要k次比较运算(k为固定方向集合的大小)。在充分开发和利用虚拟环境中对象运动的时空相关性的基础上,提出了加速对象间碰撞检测速度的遍历跟踪策略。这是一个启发式的策略,通过跟踪上一时间采样点对包围盒树的遍历过程,确定当前时间采样点的遍历路径,从而有效地减少了遍历过程中包围盒相交测试的次数,提高了算法效率,同时通过对跟踪表的维护,保证了碰撞检测的正确性和有效性。