王建民，殷 宏，许继恒，黄 瑛，田 凌，李 宁

(解放军理工大学工程兵工程学院信息技术系军事仿真教研室，江苏南京，210007)

在虚拟场景漫游中，由于用户与物体的移动，物体之间经常会发生碰撞。为了保持虚拟场景漫游的真实性，需要及时检测这些碰撞的发生。碰撞检测是指空间中任意两个不可刺穿的物体，不能存在于相同位置的空间区域［1］。精确的碰撞检测对于提高虚拟场景漫游的拟真度和速度有着很重要的作用。虚拟漫游碰撞检测的关键问题是如何在有着大量复杂实体的虚拟环境中，达到一种实时和精确的碰撞检测，提高虚拟漫游的效率。近几年，一些快速碰撞算法逐渐应用于虚拟环境下的碰撞检测问题取得了很好的效果，其中运用较为广泛的是包围盒层次法和空间分解法。李苗［2］对常见的包围盒层次法进行了分析比较，针对虚拟环境中比较多的是凸型模型的特点提出了OBB包围盒算法理论上的改进。冯波等［3］提出一种面向路径规划的连续碰撞检测算法。运用层次包围盒中的AABB包围盒和投影技术相结合，显著降低了虚拟环境路径规划中计算复杂度，但是AABB包围盒在每次物体转向时必须重构，增加了系统的负担。康勇等［4］提出基于空间分解和包围盒层次的混合碰撞检测算法，但是碰撞检测主要针对可变性的物体，对含有大量刚性实体的虚拟场景具有一定局限性。

虚拟漫游中的碰撞检测技术主要涉及以人或者车辆等动态视线载体与虚拟静态实体之间的碰撞检测，防止漫游过程中发生动态视线载体穿过虚拟静态实体的现象发生，大部分虚拟场景中虚拟漫游视线的唯一性就决定了动态物体的唯一性。针对这些特点和上述的一些方法，笔者提出了一种混合碰撞检测算法，综合运用空间分解法、包围盒层次法和投影技术，在某虚拟场景漫游中取得了良好的效果。

1 碰撞算法预处理

在本次研究中，针对虚拟场景的特点首先进行场景空间的分割，然后进行包围盒的构造，最后综合利用包围盒和投影技术进行碰撞检测。

1.1 虚拟场景空间的分割

空间分割的方法有很多种，其中一类有效的方法就是用均匀网格对空间实施覆盖，将空间划分成多个均等的局域，其中每个网格单元与其中的对象相关联。这样就把碰撞检测局限到了一个网格之中，减少个碰撞检测的数量。

设虚拟空间为S，把S划分为边长均为一定的空间网格。同时对虚拟场景静态实体基于空间网格进行均匀划分，如果某实体同时位于几个网格之中，则对实体按照网格边进行分割(图1)。在划分结束后，只需要利用世界坐标值除以单元网格长度就可获得网格单元的坐标。

虚拟场景均匀分解作为混合碰撞检测的子过程，它的分解深度的确定需要衡量以下2个因素［5］:

(1)网格空间不易过小，加速其构建以及遍历的过程。

(2)网格空间包含的实体尽可能少，以加速混合包围盒的构建，以及每一步碰撞的检测。

空间网格划分不能过大或者过小，过大的每一步的空间碰撞检测中检测物体过多。划分过小，则使减缓算法的遍历，这些都会加大算法的复杂度。

1.2 混合包围盒构建

针对虚拟场景漫游和场景中实体特点，在此选择构建基于包围球［6］和OBB包围盒［7］的混合包围盒。

OBB包围盒和包围球在物体转向重新建立坐标系的时候，不需要对包围盒进行重构，同时利用包围球相交测试复杂度低和OBB包围盒紧密性好的特点，可以大大提高算法的有效性和实时性。

图1 虚拟场景空间分割

首先针对实体形状构建OBB包围盒，然后在OBB包围盒的外层再构造一个球体包围盒，其球体包围盒的球心直接采用OBB包围盒的中心，半径则根据OBB包围盒的大小来确定。

对于OBB包围盒的中心位置和方向利用均值μ和协方差矩阵C来确定［8］。设第i个三角形的顶点是pi，qi，ri，则有包围盒中心位置:

协方差矩阵:

其中，n是三角片的个数，每一个都是3×1矩阵。

将C的3个特征根归一化，由于3个特征根是正交的，可作为一个基底，也就确定了包围盒的方向。把将要包围的几何体顶点向方向轴上投影，找出各方向轴的投影区间，各投影区间的长度即为包围盒的尺寸(图2)。

图2 混合包围盒

2 碰撞检测算法描述

2.1 虚拟环境投影检测原理

三维环境中投影检测原理可以描述为:在三维空间的直线运动中，如果在运动区间内物体与障碍物发生碰撞，则两物体在运动方向的投影一定相交。如果物体与运动区间内的障碍物在运动方向的投影相交，则在运动区间内两物体一定发生碰撞［3］。投影检测的核心将三维空间的对象相交转化为二维空间来处理，通过降低纬度来提高检测的效率。

2.2 算法描述

步骤1 投影坐标系的确立。在碰撞检测中，首先将空间单元中的物体投影到投影坐标系，然后进行逐步的碰撞检测分析。所以必须首先确立坐标系。在本次研究中以运动实体的运动方向为Z轴，以Z轴与空间单元交点处确定坐标原点O，然后确定垂直于Z轴的XOY平面(图3)。

图3 碰撞检测中的投影坐标系

步骤2 建立待检测物体序列表。所有物体的包围球首先投影到XOY平面，按照被投影的顺序，为待检测物体建立序列。

步骤3 待检测物体序列检测。按照序列进行检测，可以在最先发生的碰撞的物体之间进行规避，防止不必要的碰撞检测。设定序列初值为i=1，序列表最大值为j。如果i≤j，则转入下一步，否则则证明进入下一空间，转入步骤1。

步骤4 包围球碰撞检测。按照待检测物体序列表，对物体逐个进行碰撞检测(图4)。首先计算包围球与运动实体包围球的中心点距离，如果

则不发生碰撞，继续前进，进入步骤3。否则则进行OBB包围盒碰撞检测。

步骤5 OBB包围盒碰撞检测。OBB包围盒碰撞在XOY平面上的投影必为矩形，如果两个矩形的中心点在X方向距离的绝对值小于等于矩形宽度之和的二分之一，并且Y方向距离的绝对值小于等于矩形高度之和的二分之一，那么包围盒发生碰撞(图5)。如果不发生碰撞，继续前进，对下一物体进行检测，否则则进行精确碰撞。

步骤6 基于等分线的精确碰撞检测。将多边形投影到XOY平面，得到一个平面多边形。如果多边形相交，必然有一条直线同时与两个多边形都相交。根据这个原理，基于两个中心点投影点做两条平行的轴线，如果相交则必然发生在两条轴线之间。由于能十分准确的得到相交点算法难度多大，就可以设一个误差值ρ。在此设定当两个多边形的距离小于ρ时，发生碰撞(图6)。在两条轴线做n条等分线，如果存在第m条等分线与其中两个多边形相交于点(X1，Y1)和点(X1，Y2)。如果|Y1－Y2|＜ρ，则发生碰撞，需要进行障碍物规避。否则不发生碰撞，继续前进，转入步骤3。

步骤7 障碍物的规避。如果会发生碰撞，则在第一个碰撞实体之前，按照预定的设定距离、方向角进行转向。然后转入步骤1。

图4 包围球碰撞

图5 OBB包围盒碰撞

图6 基于等分线的精确碰撞

3 应用实例与分析

将算法运用与虚拟设备巡检之中，测试内容主要包括:不同场景规模对算法性能的影响、不同相交率下的算法平稳性的影响(图7)。并与经典的OBB算法和k-dops算法进行比较。

图7 虚拟设备巡检下的碰撞检测

使用本次研究提出的混合碰撞算法在虚拟场景实体模型较少的时候，算法效能并不突出(图8)。但是随着模型的增多效能逐渐提高，而且虚拟场景实体模型越多，算法性能得到较大的提高。在算法的平稳性上，虽然相交的三角形对数在提高，但是混合碰撞算法仍然表现出了很大的平稳性(图9)。

图8 场景规模对算法性能的影响

图9 相交率对算法性能的影响

4 结论与讨论

针对大多数情况下虚拟场景漫游视点的唯一性，笔者提出一种混合碰撞检测算法。通过引入空间分割缩小了碰撞检测的空间，同时运用包围盒层次法和投影技术来简化碰撞检测的复杂度。实例表明，该算法能够有效地支持虚拟环境下场景漫游中的碰撞检测。

当然混合碰撞算法也存在着一些不足，以下两点是下一步研究的重点:

①在场景空间分割上，如何随着场景模型的变化，达到划分深度与网格空间体积的平衡。

②等分线和误差值的运用上使得碰撞检测存在一定的误差，如何使得算法在精确性和实时性上更进一步也是研究的重点。

［1］ 魏迎梅，王涌，吴泉源，等.碰撞检测中的固定方向凸包包围盒的研究［J］.软件学报，2001，12(7):1 056-1 063.

［2］ 李苗.实时碰撞检测算法分析与比较［J］.计算机与现代化，2011(6):88-90.

［3］ 冯波，贾晓亮，王佩，等.面向路径规划的碰撞检测算法研究［J］.机械设计与制造，2011(2):44-46.

［4］ 康勇，熊岳山，费先宏，等.基于空间分解和包围盒层次的混合碰撞检测算法［J］.计算机仿真，2010，27(6):191-194.

［5］ TURK G.Interactive collision detection for molecular graphics.Technical Report TR90-014［R］.University of North Carolina at Chapel Hill，1990.

［6］ SPLLMANN J，BECKER M，TESCHNER M.Efficient updates of bounding sphere hierarchies for geometrically deformable models［C］//The 3rd Workshop in Virtual Reality Interactions and Physical Simulation.Madrid:［s.n.］，2008:53-60.

［7］ CHANG J-W，WANGWENPING，KIMM-S.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy［J］.Computer-Aided Design，2008，42(1):50-57.

［8］ CHRISTER Ericson.实时碰撞检测算法［M］.刘天慧，译.北京:清华大学出版社，2010.