● 摘要
碰撞检测和碰撞处理是游戏物理引擎的重要组成部分。它们是游戏规则系统的最底层规则，它们对游戏的真实性和可玩性有着至关重要的影响。碰撞检测和碰撞处理实际上是对现实物理规律的一种模拟，模拟的精确程度是根据游戏的不同而不同的。影响处理器计算碰撞检测和碰撞时间的因素主要有两个。第一个是碰撞模拟的精确程度，精确程度越高占用处理器时间越多；第二个是场景复杂度，处理器的运行代价会随着场景复杂度的增加而急剧增加。如果一个游戏既要求场景复杂（有很多运动物体）又要求物理模拟精度很高，那么处理器的处理效率就成了瓶颈问题。本文正是研究一种基于时间预测的碰撞检测算法来解决这个瓶颈问题。一般的碰撞检测算法是在每一步对周围的所有物体检查是否相交，如果相交就发生了碰撞。求两物体相交必然通过距离来判断。既然求出了距离就不如进一步除以速度求出下一次的碰撞时间，以后就不必再对此物体进行碰撞检测了，到时间再触发碰撞反应。这正是基于时间预测的碰撞检测算法的最初想法。当然事情没那么简单，在预测的碰撞时刻之前两物体运动状态的任何改变都会使此预测失效。此外物体的运动方式也许很复杂，这样对时间的预测也会变得很难。本文正是通过数学物理原理分析流行碰撞检测算法，并在此基础上设计基于时间预测的碰撞检测算法。并对一些常规算法加以改造和综合利用以提高基于时间预测算法的运行效率。本文还通过两个程序来验证该算法的正确性和在巨量物体环境中的效率。