3D游戏中碰撞检测技术研究

叶丽娜

摘要：本文首先介绍了碰撞检测的基本原理及常用的几种碰撞检测方法，并对它们做出比较，指出其优缺点，最后提出基于包围球的快速碰撞检测优化算法，并在此基础上实现了一个简单的应用碰撞检测技术的实例Demo。

关键词：碰撞检测；轴向包围盒；方向包围盒；离散方向多面体

中图分类号：TP37 文献标识码：A 文章编号：1009-3044（2015）07-0220-02

Abstract： This paper first introduces the basic principle of collision detection and collision of several commonly used detection method， and make comparison of them， and point out the advantages and disadvantages， finally put forward a fast collision detection algorithm based on optimal bounding sphere， and on this basis， the realization of a simple application of collision detection technology is an instance of Demo.

Key words：Collision detection；AABB；OBB；K-DOP

技术的进步以及人们对游戏体验的不断苛求和升级，对游戏环境尤其是三维场景的构建提出了更大的挑战。在现实生活中，碰撞总是自然而然的发生着，比如踢足球、打篮球的时候，我们总是需要控制球的方向和力度等。自从3D游戏出现以来，程序员就不断为模拟更精确的现实世界而努力。为了更加逼真地模拟真实环境，开发出现场感体验感更强的优质游戏，就必须要将客观实际中存在的各种物理规律现象融入到整个游戏开发过程中，在这其中大部分的游戏离不开碰撞检测，这其中不管是物体与场景之间的碰撞检测，还是物体与物体之间的碰撞检测，碰撞检测技术便是诸多最为关键的问题之一。当我们在游戏进行中出现飞向墙壁的小球穿墙而过，或是是驾驶的汽车与障碍物出现干涉时，就会大大降低游戏体验的真实感，由此可见，碰撞检测技术确实成为游戏场景开发中的一项重要课题，而针对该项技术国外多家知名游戏开发商早已着手开展了相关技术的探索工作。

1 碰撞检测的基本原理

碰撞检测是检测虚拟物体之间是否发生干涉，是虚拟现实技术中的关键问题之一，它是判断图形连同虚拟场景满足时空的一致性定律的条件，即对游戏场景中的出现对象间的相对关系进行判定以决定是否触发新的相应游戏事件，简单来讲，就是多面体间的相交测试问题。而3D游戏中的碰撞检测比2D游戏中的碰撞检测要复杂得多。

在3D游戏开发过程中最常见的情况是一个或一些在静态环境中运动的物体。以下三种情况一般由碰撞检测所描述：检测碰撞连接点和对碰撞响应建模；检测两个物体之间的碰撞；检测碰撞发生和连接点的精确度。

从渲染角度来说，第一种描述需要一个动态模型，若两个物体渲染的位置重叠，即发生了碰撞；而后面两种情况则属于几何操作。

2 基于层次包围盒的碰撞检测法

2.2.1轴向包围盒（AABB）检测法的基本原理

一个3D的AABB就是简单的六面体，每一边都平行于一个坐标平面，而矩形边界框不一定都是立方体，它的长、宽、高可以彼此不同。这种方法相对简单，从二维的碰撞检测降到一维空间操作，当两个AABB包围盒相交时，当且仅当它们在X轴、Y轴和Z轴上的投影均重叠，只要存在一个方向上的投影不重叠，那么它们就不相交。AABB间的相交测试和包围体的更新速度是最快的，因此使用最广泛，尤其适用于多物体运动的大规模环境和变形体碰撞检测。

2.2.2方向包围盒（OBB）检测法的基本原理

OBB的相交测试是基于分离轴的理论的，它被定义为包含该对象且相对于坐标轴方向任意的正六面体。它的最佳方向必须保证在该方向上包围盒的尺寸最小，这样就形成了一个物内划分。由于其方向的任意性，较好的紧密性，在执行碰撞查询时，可能只需要遍历更少的树层次，其重叠检测速度更快，大大提高了算法的效率。

2.2.3 离散方向多面体（k-DOP）检测法的基本原理

k-DOP的概念最早由Kajiya和Kay二人提出，使用k/2对的平行平面来包围物体，它是AABB的推广。这种方法的优势在于增加AABB的包围效率，与此同时保留它相对于OBB的优势。通过调整k的取值，可以在简单性、紧密性中达到一定的折衷，从而提高碰撞检测的效率，这样就能满足一个高效的场景层次结构应具有的条件。

2.2.4 AABB、OBB、K-DOP检测方法比较

AABB法被用作模型的包围盒时，虽然相交测试较简单但紧密性差，且跟随性差，运算量大，这将极大的减慢应用的速度，此外该方法仍面临着精度的问题。OBB法同样需要进行大量的计算，且速度慢，不适用于动态对象的检测。采用OBB方法的另一个缺点是需要进行大量的矩阵运算。K-DOP方法则介于前述两种方法之间的一种方法，其特点是只要合理地选取平行平面对的个数和方向，就可以在检测的简单性和包裹物体的紧密性之间灵活取舍，但计算量仍然很大，且对于平行平面对的选取更是一个难点问题，在使用该方法对于动态环境下复杂虚拟场景中多虚拟对象之间的碰撞检测问题还是显得效率低下。

3 算法优化及其运行结果

鉴于对以上各种包围盒体测试方法的比较，本文的做法是在对多面体进行碰撞检测时采用一个球体包裹每一对象或对象的一部分，然后检测这些球体是否相交。此方法计算的代价较低。包围球法虽然算法简单，但是在遇到动态环境下复杂虚拟游戏场景中多虚拟对象之间的碰撞检测问题时同样给该处理器带来了不小的计算负荷。基于此本文对该方法进行了如下优化：

1）过滤法：

此种优化是逻辑上的，即使用检测范围的概念。本文在开发引擎代码时在为不同多面体包围球设计数据结构时在其中加入了一个布尔型标志位，首先在帧与帧之间检测该包围球体的空间位置是否发生了变化，这种检测只需通过计算包围球体的三维坐标是否发生了变化，仅涉及到加法、减法的计算并不会给处理器带来较大的额外负担，但却十分有效。

2）公式优化法：

以二维图形为例，如图1所示在A物体的外围画一个圆，作为检测碰撞的边线，任何物体是否与其发生了碰撞，都用圆心与圆心的距离来判断，当两个圆心的距离等于或者小于2个物体碰撞圆周的半径之和时，就说明这两个物体发生了碰撞。如B和C两个物体，当它们圆心的距离等于两个半径的和的时候，也就是两个碰撞检测的圆相切的时候，这时我们判断这两个物体碰撞了。

参考文献：

[1] Earnshaw R A， Gigante M A， Jones H. Virtual Reality Systems [M].Academic Press Limited 24/28，Oval Road London NW1 7DX，1993，135-237.

[2] 王志强等. 碰撞检测问题研究综述[J]. 软件学报，1999，10（5）：545-551.

[3] ChristerEricson实时碰撞检测算法技术[M].刘天慧译.北京：清华大学出版社，2010

[4] 赵伟，谭睿璞，李勇.复杂虚拟环境下的实时碰撞检测算法[J].系统仿真学报，2010