适用于复杂场景的碰撞检测算法研究

摘要

创建虚拟场景不仅要进行静态建模,更重要的是进行动态建模,而且物体之间的实时碰撞检测是关键.首先对常用检测算法的检测效率进行了分析和比较.然后重点针对复杂虚拟场景中含有大量物体的特点,提出了混合包围盒碰撞检测算法.该算法利用帧与帧之间的时间和几何相关性,把对(c2n+m)个对象的动态跟踪转化为它们在三个坐标轴上的投影的排序问题,把时间复杂度由O(n2)降低为O(n).并引入树的深度的概念,根据不同的应用场合合理控制检测深度以加快检测速度.理论分析和仿真计算都表明,该算法能够满足多达几百个运动物体的实时交互碰撞检测.