论文部分内容阅读
碰撞检测算法广泛应用于机器人运动规划、计算机图形学、分布交互仿真等领域。针对虚拟环境的复杂性、精确性、实时性等要求,高效的碰撞检测算法对提高虚拟环境的真实性和沉浸感具有重要的意义。包围盒算法是解决碰撞检测问题固有时间复杂性的一种有效的方法,它是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象。以大型多人在线游戏为代表的3D应用正快速发展并催生出巨大的市场需求。3D游戏已俨然成为推动计算机硬件和软件飞速前进的强大动力。随着移动互联网时代的到来,移动平台的发展也日新月异,越来越多的3D应用开始登录移动平台。由于移动设备自身的局限性,对碰撞检测算法在移动平台上的应用也提出了更高的要求。本文以移动平台的游戏应用为背景,通过iPhone手机平台上一款3D多米诺骨牌游戏的开发,论述了碰撞检测算法在移动平台上的研究和应用。本文在充分研究移动平台特点和各种碰撞检测算法的基础上,通过基于OBB包围盒碰撞检测算法的优化,着重解决了移动平台游戏中简单3D物体的实时碰撞检测问题。通过分析和比较主流移动平台与桌面电脑之间的差异,针对移动平台的特点,对游戏在移动平台上的需求和设计进行了深入研究,提出了移动平台上3D游戏应用开发中所应该遵循的基本原则,并阐述了如何发挥移动平台的特点开发出更好的游戏应用。针对移动平台上大量的简单3D物体实时碰撞检测效率不高的问题,文中提出了以构建碰撞树为基础的碰撞遍历算法。通过在碰撞过程中实时构造和更新碰撞树,较好解决了简单3D物体在实时运动过程中的碰撞检测和状态更新问题,特别是为多条运动分支组成的复杂碰撞场景中的碰撞检测问题提供了一种直观简洁的解决方案。此外,本文在充分开发和利用虚拟环境中运动物体的时空相关性的基础上,通过构建和维护运动物体的碰撞邻接表和记录物体的历史碰撞情况,提高了碰撞检测算法的效率。另外,经过对碰撞检测算法中分离轴原理的思考,提出了针对不同应用场景删减冗余的判断轴以加快碰撞物体间分离情况判定速度的思想。实验结果和具体应用表明,通过基于OBB碰撞检测算法的优化,能较好解决移动平台游戏中简单3D物体的实时碰撞检测问题,而且为在虚拟环境中解决和处理复杂的3D物体碰撞检测问题提供了一种有效的途径。本文的应用成果,对移动平台上游戏开发者有重要的参考价值和实际意义。