● 摘要
碰撞检测问题（Collision Detection）在计算机图形学、动画、游戏和虚拟现实等领域中占有很重要的位置。随着计算机软硬件及网络技术的高速发展，人们迫切要求对现实世界的真实模拟及与计算机的实时交互操作。要真实地模拟现实世界中物体的运动，关键之一是必须对场景中的所有物体进行实时碰撞检测。论文中按照两类经典的碰撞检测算法对碰撞检测问题进行综述：物体空间的方法和图像空间的方法。早期的研究以及传统的算法基本上都属于物体空间的方法。论文对比较典型的物体空间的方法进行分类讨论。图像空间的方法是随着图形硬件的快速高效的发展而兴起的一类新的碰撞检测算法，论文在简单介绍了图形硬件的发展之后，列举了几种具有代表性的图像空间算法，然后对这两类算法的优点和缺陷进行了讨论。在本论文中引入了一种特殊的几何结构——单调簇。在详细的介绍了单调簇之后，讨论了单调簇的判定问题以及对物体进行单调剖分的方法。介绍了一种具有线性时间复杂度的flooding算法用于近似计算极大单调簇,从而达到把物体进行单调剖分的目的。为了解决上面提到的启发式的flooding算法的缺点——过分割问题，文中提出了一种改进的flooding算法，改进的目标是要保证获得尽可能少的分割单调片的同时，避免产生过多的“碎片”，从而能比较有效地解决过分割的问题。这种改进的flooding算法同样是利用了图形硬件的遮挡检测功能，在剖分的过程中采用了一定的优化规则来达到单调剖分的目的。在论文的最后实现了这种可处理大规模复杂场景的实时碰撞检测算法。该算法基于前面介绍的单调剖分技术，同时利用图形硬件的遮挡检测功能实现了单调簇与物体的快速相交检测。论文详细描述了算法的原理、实现以及优化策略等，并对算法进行了功能测试，给出了试验结果和测试结果，对性能进行了分析。