海战场环境中基于射线的碰撞检测算法研究＊

许宏泉 明 芳

（武汉市74223信箱1） 武汉 430074）（武汉数字工程研究所2） 武汉 430074）

1 引言

在海战场环境中，相对运动的物体之间可能会发生碰撞，通常分为有目标的碰撞和无目标的碰撞两类［1］。有目标的碰撞检测，例如射击导弹通常是针对某个目标的，需要判断目标与导弹等是否发生碰撞以及后果如何。无目标的碰撞检测，例如低空飞行的飞机需要判断飞机与地形、地物、舰艇是否发生碰撞。实时性、精确性是检验碰撞检测成败的两个关键因素。包围盒是广泛应用的碰撞检测技术，本文根据海战场环境中运动物体的特点选择不同包围盒，对基于射线的相交测试方法进行研究。

2 碰撞检测算法的分类

碰撞检测算法种类繁多，主要是从时间域的角度和空间域的角度来进行划分。

从时间域的角度，碰撞检测算法可分为静态碰撞检测算法、离散碰撞检测算法和连续碰撞检测算法三类［2］。

基于空间域的碰撞检测算法可分为基于物体空间的碰撞检测算法和基于图像空间的碰撞检测算法。

基于物体空间的碰撞检测算法又可以进一步划分为：基于物体的不同表示模型；基于不同的空间结构。物体空间的碰撞检测算法可采用不同的空间结构来提高效率，根据所用空间结构的不同可将它们分为两类：空间剖分法（Space Decomposition）和层次包围体树法（Hierarchical Bounding Volume Trees）。空间剖分法采用对整个场景的层次剖分技术来实现，而层次包围体树法则是通过对场景中每个物体建构合理的层次包围体树来实现。

空间剖分法：场景的层次剖分方法主要有均匀剖分、BSP树、k-dop树和八叉树（Octree）等。在处理不同的场景和具有不同形状及复杂度的物体时，这类算法较难保持比较一致的检测效率。

层次包围体树法：物体的层次包围体树可以根据其所采用包围体类型的不同来加以区分，包围体类型主要包括包围球、AABB、OBB、k-dop等等。

3 包围盒的选择原则

判断两个多面体物体间是否发生碰撞，实质上是判断一个物体的一边是否穿过另一个物体的一个面。这种算法对N个物体测试的平均计算时间是O（N2EF），其中E和F分别是物体平均的边数和面数，并且随着物体的数量和复杂性的增加，测试量成平方的增加。因此包围盒的选择是提高检测精度、降低计算量的关键。

3.1 运动物体的分类

从空间分布角度进行划分，海战场环境可以分为空中环境和水面环境，相应的运动物体可以分为空中物体和水面物体。

·海战场中的空中物体主要是指各类作战飞机。空中物体一般都形状不规则，表面特征复杂，具有范围很广的立体作战领域，且运动速度快，机动性高。

·海战场中的水面物体主要是指舰艇、潜艇等武器的运载和发射工具。水面物体一般形状较为规则，近似于立方体，作战领域为平面，且范围相对较小，运动速度慢，机动性较低。

3.2 包围盒的选择

常用的包围盒有四种：包围球、AABB轴向包围盒、OBB轴向包围盒、k-dop包围盒。

包围球是包围物体的最小球体。此类包围盒简单，易于计算，非常易于做重叠测试和节点修改，但是与物体的逼近程度较差。

AABB轴向包围盒是一个六面盒状长方体，且其面方向性划分按如下方式进行：面法线皆平行于给定的坐标轴，最大的特点是能够实现快速的相交测试。

OBB轴向包围盒是三维空间的一个任意方向的长方体包围盒。此类包围盒可提供非常紧凑的逼近效果，修改OBB轴向包围盒较为简单，只需将两个变换矩阵相乘，但是重叠测试的耗费比AABB高一个数量级。

k-dop包围盒是一种凸多面体，它的面由一些半空间所确定，这些半空间的外法向是从k个固定方向选取的。与包围球和AABB包围盒相比，kdop包围盒对物体的逼近程度相对较好，与OBB包围盒相比，k-dop包围盒的重叠测试和节点修改耗费相对较低。

空中物体形状不规则，表面特征复杂，但是其速度快，机动性高，因此可以选择简单的包围盒进行碰撞检测，如包围球或AABB轴向包围盒。

形状规则，表面特征复杂的水面物体，特别是具有较为突出的可活动组件的水面物体，例如载有雷达、炮弹的舰艇，可选择复杂的包围盒，如OBB包围盒或k-dop包围盒。

4 基于射线的相交测试

4.1 “射线／体”相交测试

海战场环境中物体数量多，采用两两相交测试的方法进行碰撞检测，计算量庞大。本文采用基于“射线／体”相交测试的方法进行碰撞检测，运动物体起点即是射线的起点，物体的运动方向即是射线的方向。体即是海战场环境中某一区域中物体的包围体，通常用包围盒或包围球作为该区域的包围体。在相交测试的过程中，如果射线与包围体发生相交，则认为射线与包围体发生了碰撞。

碰撞检测的基本原理就是利用相交检测的方法判断空间物体是否相交，某些情况下还需要求出相交的部分。在实际情况中，相对位置较远的两个物体在很长一段时间内可能都是不会相交的，两个相对静止的物体也不可能相交。碰撞检测流程图如图1所示。

图1 碰撞检测流程图

为了提高碰撞检测效率，快速排除不相交的物体，采用的加速算法通常有以下几种：

1）背向剔除［3］：背向运动的物体基本不可能发生碰撞。

2）区域剔除［4］：相隔较远的物体不可能发生碰撞。

3）类型剔除：地面上的物体不可能与水下的物体发生碰撞。

4）阈值剔除［5］：检测导弹与地物是否发生碰撞时，设置高度或距离阈值，当导弹高度或距离到达阈值以内时，才进行碰撞检测。

4.2 相交测试分类

海战场环境中的所有物体分为两种：静态物体和动态物体。静态物体的位置是固定不变的，因此不需要对静态物体间进行碰撞检测。动态物体在三维地形场景中进行旋转或平移运动时可能与场景中的物体发生相交的情况，因此，本文碰撞检测分为两种情况：运动物体和静止物体之间碰撞检测、运动物体之间碰撞检测［6］。

1）运动物体和静止物体相交测试

如图2所示的原理，黑色三角形代表对象运动之前的起始位置，白色五边形代表对象以一定速度方向运动之后的新位置，然后通过连接这两个点产生一条线段，通过判断线段与包围体是否有交点。如果这个包围体代表的是地面，如果物体运动后的新位置与地面有一个交点，则该运动不能执行，只能保持在原地，否则会穿过地面到达地底下去；如果这个包围体代表的是场景物体，则该运动会发生碰撞。

图2 运动物体和静止物体相交测试示意图

2）运动物体之间相交测试

海战场环境中通常需要判断是两个动态物体间是否发生碰撞检测的问题，例如飞行的导弹能否命中运动的目标。动态相交测试是判断两个运动的物体是否相交，以及相交的时间点。两个物体都有自己的运动参数，从单个物体的角度处理问题，相对而言比较简单。通常情况下物体可假定为分段性运动［7］，即在两点间实现位移，并在初始点或终点即刻进行旋转操作。因此对于两个物体A和B，可从A的运动中“减去”物体B的运动，则物体B相对静止，且相交测试可视作运动的物体A与静止的物体B之间的计算，即两物体之间的彼此相对运动［8］。最后，如果交点已计算完毕，需要将B的运动状态最终作用于交点之上，从而获取正确的世界坐标而非物体的相对坐标。

图3 采用区间二分法计算运动球体与静止球体碰撞测试步骤示意图

通常采用基于递归的二分搜索算法［10］计算碰撞时刻（若存在），即对物体的运动路径实施采样，并在位移过程中执行多次静态物体测试。如果在运动路径上测试全部n个采样点，即时间复杂度为O（n）。球体S高速掠过一个静止物体，S的初始位置为A且运动方向以向量v表示。首先，构造一个包围球且完全包含位置A及位置A＋v的球体，并利用该包围球与其他物体执行碰撞测试。若不存在碰撞，则S直接到达终点。然而，若其中未检测到碰撞，则二分计算位移量并以同一方式递归地测试前半部分。如果其中未检测到碰撞，则对后半部分执行相同的递归测试。若受测位移量在趋于某个最小预定值时碰撞检测过程仍未结束，则可假定该碰撞存在且递归结束。

图3（a）显示了区间二分法的测试过程［11］，其中，根据总位移量构造了一个球体，并在某一点处检测到与另一物体发生碰撞。这里需要计算位移的中点，而后分别对各半部分执行递归调用。在首次递归调用过程中，由起始点至中点形成的球体B1中并未发现任何碰撞，且该递归调用退出并返回“未碰撞”信息；该过程继续执行并开始第二次递归调用，同时，检测到包围后半程的球体B2与物体发生碰撞。因此，在当前二分区间内生成新的中点并针对该二分区间再次执行递归计算，如图3（b）所示。同理，球体B3中发生且执行递归调用。在本例中，由于产生了碰撞相交，因而递归调用最终退出，算法如下：

5 结语

在海战场环境中，对各种运动物体进行碰撞检测要兼顾效率和精度。本文采用的基于射线的碰撞检测技术可以通过碰撞检测加速算法排除大部分明显不可能发生碰撞的物体，减少参与碰撞检测的物体数量，从而提高碰撞检测的效率。对可能发生碰撞的物体，则采用较为复杂的OBB包围盒或k-dop包围盒进行碰撞检测，从而提高碰撞检测的精度。

［1］万刚，夏青，武志强.虚拟视景仿真中实体行为建模技术的研究［J］.信息工程大学测绘学院学报，2002，19（3）：3～4

［2］范昭炜.实时碰撞检测技术研究［D］.杭州：浙江大学，2003：30～40

［3］Akenine-Moller T，Haines E.实时计算机图形学［M］.普建涛，译.北京：北京大学出版社，2004：50～60

［4］王海.林木场景漫游关键技术的研究与实现［D］.北京：北京林业大学硕士学位论文，2007，6：42

［5］李芙玲，张谨.碰撞检测技术研究［J］.华北科技学院学报，2004，1（2）：71～73

［6］高丽娜，马尧海.虚拟漫游中的碰撞检测问题的解决方法［J］.计算机仿真，2006，23（2）：189～191

［7］魏迎梅.虚拟环境中碰撞检测问题的研究［D］.长沙：国防科学技术大学，2000：80～90

［8］王海.林木场景漫游关键技术的研究与实现［D］.北京林业大学大学，2007：40～42

［9］宗美玲，童小念.虚拟现实环境下的碰撞检测实现［J］.计算机与数字工程，2011，39（4）

［10］Jeschke S.Wimmer M，Purgathofer W.Image-based Representations for Accelerated Rendering of Complex Scenes［C］／／Proceedings of EUROGRAPHICS，Dublin，2005：1～20

［11］Mantler S，Robert F，Tobler，et al.The State of the Art in Realtime Rendering of Vegetation［R］.Vienna：VRVis Research Center for Virtual Reality and Visualization，2003：20～30