融合包围盒智能算法的虚拟场景碰撞检测研究

惠学武，孟祥宇

(海军大连舰艇学院，辽宁 大连 116013)

1 引言

由于图像处理和虚拟技术的快速进步，推动了虚拟仿真的应用普及[1]。对于场景复杂，规模庞大的现实模型，利用虚拟仿真便可以轻松获得其各项参数指标与性能验证。在虚拟仿真技术领域，碰撞检测是影响其性能的关键技术，会影响到虚拟仿真执行的精度与实时性。随着虚拟场景中模型规模和复杂度的升高，以及场景的动态变换，给碰撞检测提出了更高的要求。当前针对碰撞检测，比较常见且有效的方法是GPU加速[2]和HBV[3]。其中GPU加速虽然能够摆脱对CPU的消耗，提升图像处理效果，但是成本较高，且灵活性和扩展性受限。HBV是层次包围盒，它可以从策略和算法角度提高碰撞检测的适应性，所以受到更多的关注。如文献[4]设计了AABB轴对称包围盒；文献[5]设计了OBB质点变换包围盒；文献[6]设计了混合AABB-OBB包围盒。这些算法普遍缺乏对三角形面片和分布情况的深入分析，在性能上还有提升空间，同时还缺乏对碰撞检测整体性能的均衡考量。

当虚拟场景具有动态变换特征时，单一的HBV不能很好的保证检测性能均衡，为此，本文提出了一种融合包围盒智能算法，可以根据不同场景选择合适的包围盒策略。对于较为简单的虚拟场景，采用AABB优化包围盒，快速进行非碰撞排除。对于较为复杂的虚拟场景，采用OBB优化包围盒，通过带有方向的分离轴实现碰撞检测。考虑到包围盒的本质是特征点的优化，将包围盒与粒子群算法进行融合，从而把立体碰撞变换成最优解搜索，通过收敛计算进一步提高算法性能。

2 包围盒碰撞检测算法

2.1 包围盒策略

虚拟场景变换是一个复杂的过程，很多情况对碰撞检测算法的性能要求也不同，一些简单场景下只需简单算法即可满足，而一些复杂场景下则对算法具有较高要求。另外，并非全部场景都必须采取碰撞检测。考虑到碰撞检测性能均衡，尽可能提高碰撞算法的场景适应性，本文把模型向xyz坐标平面内投影，根据虚拟场景内模型的倾斜角来调整包围盒策略。通过矢量夹角求解确定场景内模型倾斜状态。针对投影至xoy面分析，如果x对应的最大和最小值点分别是P1(x1，y1)、P2(x2，y2)，那么可以得到P1P2和x轴夹角为

(1)

设定矢量夹角阈值为θ0，当夹角在[0，θ0]范围内时，采取AABB优化包围盒；当夹角超过θ0时，采取OBB优化包围盒。

2.2 AABB优化包围盒

图1 AABB优化包围盒模型

(2)

r=max(|(xc,yc,zc)-P1|，|(xc，yc，zc)-P2|，

|(xc，yc，zc)-P3|)

(3)

此时，圆形的法线表示为

(4)

假定AABB包围盒中任意两圆形中心依次为Oi、Oj，半径依次为ri、rj，对应的法线依次为ni、nj。则通过对ni、nj和圆心向量计算点积，可以得到如下结果

(5)

如果，α=±1，且β=0成立，则意味着|Oi-Oj|超过了ri+rj，此时一定不相交。如果β≠0时，进一步判断两圆是否相交。将两圆所处平面依次标记为πi、πj，为避免构建πi、πj耗时，本文采用圆心到相交线距离方式求交。先计算πi和πj的交线L，其计算式描述如下

L=2(rinj-rjni)×n/(n·n)

(6)

其中，n=ni×nj。再分别计算出Oi、Oj至交线L的距离di和dj，如下

(7)

当di>ri，且dj>rj成立时，代表两圆相交；否则代表不相交。

2.3 OBB优化包围盒

OBB包围盒较AABB包围盒具有方向优势[7]，但是当前针对OBB方向的确定大多基于三角面片计算，且缺乏对三角分布的考虑，导致产生方向倾斜，进而影响碰撞检测精度。为此，本文针对OBB包围盒的分布问题进行优化。

首先需要确定模型中所有三角形形心。将模型上的任意三角形表示为Ti，设定Ti所在面为xoy，Ti法线为z轴方向。通过构造的Ti区域坐标，即可得到三角形Ti形心为

(8)

然后根据所有三角形形心确定整体形心。把Ti区域坐标向世界坐标变换，Ti形心变换后表示为Wi(xci，yci，zci)。模型整体形心计算式如下

(9)

最后得到(xc，yc，zc)即是OBB包围盒中心。此时模型三角面片信息描述如下

(10)

其中，Sall代表模型全部三角面片面积和；C代表模型协方差。

假定三角形Ti与圆Tj所处平面依次标记为fi、fj，则在判断Ti与Tj是否相交时，传统方法需要构建fi、fj平面，而本文为了提高相交检测速度，根据两点可确定一条直线理论，先求解三角形Ti与Tj是否具有交线Li。如果没有交线，则代表三角形Ti与Tj一定不相交；如果有交线，则进一步确定交线Li是否有落在Tj上的部分。如果Li没有有落在Tj上的部分，则代表三角形Ti与Tj一定不相交；否则代表三角形Ti与Tj相交。

2.4 包围盒紧密度

在采取矢量夹角调整包围盒策略时，可能出现两夹角冲突情况，从而无法确定使用AABB还是OBB包围盒。于是，针对这种情况采用紧密度来进一步判断。紧密度可以通过体积计算得到，式表示为

(|zmin|+|max|))

(11)

其中，V0表示模型体积。将包围盒在矢量夹角阈值为θ0时的紧密度标记为η0，如果η>η0，表示使用AABB包围盒是有效的；如果η<η0，表示使用OBB包围盒是有效的。

对于任意两个包围盒，假定它们的中心依次是Oi(xi，yi，zi)和Oj(xj，yj，zj)，则可以计算出它们的中心距离

(12)

2.5 树结构优化

现有AABB包围盒算法中，一般会在最上层采取Sphere等检测方式[8]，来分离不存在相交的模型。再在下层采取AABB检测来处理距离较近模型。对于相交深度大的情况而言，由于遍历深度增加，这种算法的复杂度将急剧上升。另外，当把AABB与OBB融合之后，具有差异的包围盒间遍历也会显著拉低效率。为了提高包围盒的检测速度，这里设计了双层二叉树结构，如图2所示。其中x层为AABB，主要用于区分非碰撞模型，y层为OBB，主要用于近距离碰撞检测更新。同时考虑到划分层较少会降低检测精度，将x层和y层内又划分成2个子层。

图2 树遍历结构

3 融合智能算法

(13)

其中，(ai,x,ai,y,ai,z)、(bi,x,bi,y,bi,z)分别代表模型a、b内特征点i和j的坐标位置。粒子群算法采用式(13)的计算来衡量特征对适应性。于是，整个算法的碰撞检测流程描述如下：

1)根据模型投影角度确定包围盒策略，并根据几何特征构造对应的AABB或者OBB包围盒。

2)按层遍历树结构，同时根据AABB或OBB完成各自的相交判断。

3)当判断出存在碰撞时，通过随机方式采集模型样本。构造特征点对，并依据包围盒确定寻优解范围。

4)通过粒子群迭代计算最优解。此外，还需要确定最优解所在的包围盒相交情况。

5)如果本次没有搜索得到最优解，或者所在包围盒没有检测到相交，则继续执行4)。

6)得到碰撞位置信息，完成碰撞检测。

4 仿真与结果分析

实验平台系统采用Windows10，内存16GB，CPU为Inter Core i7-7700。仿真环境基于OpenGL和Visual Studio 2017实现。

实验首先分析特征点对与碰撞检测效果的关系。给定粒子群算法的初始规模为50，迭代计算上限为80。针对图3所示的待测试虚拟场景，改变特征点对的规模，利用包围盒面片规模代替特征采样规模，通过仿真得到不同检测率所需的时间，结果如图4所示，其中分别描述了特征点对为1000、3000、5000时对应的检测效果曲线。根据结果分析可得，碰撞检测时间受特征点对规模影响。特征点对规模增加，有助于碰撞检测的精细，但是会损失检测时间。当检测率要达到50%，特征点对为1000、3000和5000对应的检测时间分别是7.5ms、13.4ms和19.6ms；当检测率要达到90%，特征点对为1000、3000和5000对应的检测时间分别是13.5ms、19.9ms和26.1ms。显然特征点对的影响还是很严重的，所以在实际应用中，需要根据待测试虚拟场景的复杂程度，灵活调整包围盒面片的规模，从而确保获得最佳检测性能。

图3 待测试场景

图4 特征点对与检测性能关系曲线

为了更好的体现融合包围盒智能算法碰撞检测的有效性，引入文献[6]和文献[7]中算法作为性能对比。变换待测试虚拟场景，通过10次实验得到碰撞检测时间。表1为三种方法的检测时间曲线。根据实验结果可得，本文算法的碰撞检测平均时间为15.69ms，而文献[6]和文献[7]的平均时间分别为23.64ms和23.77ms。本文算法的检测效率显著提高，较文献[6]和文献[7]分别缩短了33.62%和33.98%。

表1 不同算法的碰撞检测时间

针对不同的碰撞检测算法，仿真得到检测率与检测效率间的关系，结果如图5所示。根据对比，在初始阶段三种算法的检测效率和检测精度差别不大，但是后期本文算法的碰撞检测时间和检测率表现出明显的优势。这是因为本文算法针对不同的投影夹角采取不同的包围盒算法，优化了相交检测及遍历树结构，结合智能算法后增强了算法的寻优能力，所以显著提高了碰撞检测的速度和精度。

图5 碰撞检测率与检测时间关系曲线

表2描述了三种碰撞检测方法对应的检测数据。经过对比，由于都采用了混合包围盒算法，各方法在平均帧计算与更新比例上基本相似。但是本文算法的单位帧树节点明显少于其它方法，仅为文献[6]的35.46%，文献[7]的37.47%，显著缩小了算法的空间和时间消耗。

表2 碰撞检测数据对比

5 结束语

为了实现虚拟场景碰撞的快速准确检测，提出了融合包围盒智能算法。根据虚拟场景中模型的投影角度确定包围盒策略，针对每种包围盒分别采取相应优化处理，并引入粒子群算法对包围盒模型采样进行寻优计算。通过仿真可得，当检测率达到50%时，算法的碰撞检测时间仅为8.45ms；当检测率达到90%时，算法的碰撞检测时间也仅为15.43ms；10次碰撞检测的平均时间为15.69ms。实验结果充分验证了融合包围盒智能算法具有良好的碰撞检测效率与准确度，适用于大规模复杂虚拟场景下的碰撞检测。