基于OBB包围盒的碰撞检测算法改进

摘要

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