论文部分内容阅读
目前,3D游戏已经成为计算机游戏领域的主流,虚拟现实交互式仿真等都有很广泛的应用,不可否认的是,随着这些应用的复杂度不断上升,在处理这类较大的数据时,与碰撞检测相关的数据结构和算法也变得日趋复杂。无论是游戏,还是其他类型的模拟仿真应用程序,碰撞检测始终是程序开发的核心之处。本文选用的OBB层次包围盒算法,就是碰撞检测算法中应用比较广的一种方法。其他还有诸如球形包围盒,轴对齐包围盒(AABB)和离散有向多面体(K-Dops)等算法。在众多算法中,又以OBB的检测性能最好。论文着重论述了基于OBB碰撞检测算法的相关问题。主要从事了以下几个方面的工作：(1)在研究OBB包围盒固有特性的基础上,通过研究构建OBB层次包围树、包围盒间的重叠测试和三角形间重叠测试等问题,发现相对于Sphere方法OBB有较高的重叠测试复杂度,利用Sphere检测的简单性提出分层构建OBB层次包围树的改进方法。(2)提出将算法分为两级碰撞检测——第一级用Sphere包围盒作为层次包围树的上层,通过Sphere的快速检测筛选出重叠的物体对象送到下层检测,其中采用双向链表结构对Sphere包围盒进行管理,在每一帧中更新链表；OBB包围盒作为下层包围,用二叉树构建层次树,提供精确的碰撞检测。模拟实验根据程序中的结果做出碰撞信息的报告,并记录每一帧内发生碰撞的物体对象id。实验数据表明,经过层次优化后的OBB碰撞检测算法,通过上层的初步筛选能减少无用检测的时间浪费,使得整体检测效率比单纯的OBB检测有所提高,特别是在场景中模型数量比较多时,效果更为明显。本文的研究成果,对于碰撞检测算法的优化有一定的实验依据。