碰撞检测技术在视景仿真中的解决方案

 

　　视景仿真（VisualSimulation）是一种基于可计算信息的沉浸式交互环境，具体地说，就是采用以计算机技术为的现代高科技生成逼真的视、听、触觉一体化的特定范围的虚拟环境，用户借助必要的设备以自然的方式与虚拟环境中的对象进行交互作用、相互影响，从而产生"沉浸"于等同真实环境的感受和体验。其作为计算机技术中为前沿的应用领域之一，它已经广泛应用于虚拟现实、模拟驾驶、场景再现、城市规划及其它应用领域。

　　在众多的视景仿真应用中，碰撞检测及其相关问题是基本也是重要的组成部分。实时、的碰撞检测技术对于提高虚拟环境的真实性，增强虚拟环境的沉浸感起着至关重要的作用。本文通过改进的轴向包围盒碰撞检测算法，对业界广泛使用的视景仿真开发平台VEGA的碰撞检测部分进行了改进。改进后的系统不仅显着提高了碰撞检测的速度，并且可以便捷地得到更为详细的碰撞检测信息，满足了进一步进行碰撞响应处理的需要。

　　1  VEGA软件及其碰撞功能简介

　　Vega是MultiGen-Paradigm公司主要的工业软件环境，用于实时视觉模拟、虚拟现实和普通视觉应用。Vega将先进的模拟功能和易用工具相结合，对于复杂的应用，能够提供便捷的创建、编辑和驱动工具。Vega能显着地提高工作效率，同时大幅度减少源代码开发时间。Paradigm还提供和Vega紧密结合的特殊应用模块，这些模块使Vega很容易满足特殊模拟要求，例如航海、红外线、雷达、照明系统、动画人物、大面积地形数据库管理、CAD数据输入和DIS分布应用等等。Vega对于程序员和非程序员都是称心如意的。其中VOLUME方法用于用户指定的体与目标场景的碰撞检测；Z、HAT、ZPR、TRIPOD方法用于高程查询（功能略有不同）；XYZHPR方法用于非平面地球坐标系交点及姿态计算；LOS方法用于射线交点和距离查询；BUMP方法可以用于物体间的碰撞检测计算。

　　BUMP定义了一个由六条线段组成的Segment类型内部体，沿物体体坐标系的X、Y、Z三个坐标轴正负六个方向延伸，长度受参数Width、Length、Height控制。如果其中的线段与其他物体相交，则BUMP方法将碰撞结果保存于result[24]的浮点数组中，按照固定格式，从中仅可以提取三个轴向的碰撞点坐标和物体相应轴向长度的碰撞信息。而且BUMP方法非常消耗系统资源，以两个由3 072个三角形组成的物体相交测试为例，BUMP方法的平均检测时间多达6ms.

　　在大多数需要进一步进行碰撞响应处理的仿真应用中，要求得到一些基本的碰撞部位的几何信息（点、面等），进而对这些碰撞部位进行处理或保存试验结果进行分析，如物体变形、确定破片散布等。而BUMP方法以及VEGA提供的其他检测方式都不能满足这些要求。

　　2  碰撞检测系统设计

　　几何模型间的碰撞检测算法大致可分为空间分解法和层次包围盒两类。层次包围盒的方法应用较为广泛，适用于复杂环境的物体间碰撞检测。其基本思想是通过体积略大而几何特征简单的包围盒来近似表示复杂的几何对象，从而减少基本几何元素（通常是三角形）两两相交的测试数目，提高碰撞检测的效率。

　　基于层次包围盒的碰撞检测算法的性能可以使用公式（1）进行评估：

 

　　目前常用的包围盒类型有包围球（SPHERE）、轴对齐包围盒（AABB）、方向包围盒（OBB）和离散有向多面体（K-DOP）。包围球由于紧密性差，基本很少使用。OBB和K-DOP（为K=18）具有较好的拟合效果，相交测试速度快，但需要较多的存储空间，构造和更新包围体都比较慢。轴对齐包围盒（AABB）虽然对几何体的拟合效果和相交测试速度不如OBB和K-DOP,但其在构造、所需存储空间、AABB间的相交测试和包围体的更新速度方面都比其他算法效率高，因此也是使用为广泛的碰撞算法，尤其适用于多物体运动的大规模环境。特别是对于需要动态创建包围树的情况，构建时间成为重要因素。

　　2.1算法描述

　　轴向包围盒定义：包含给定几何体且边平行于坐标轴的正六面体。

　　轴向包围盒的构造：采用递归的方式分别计算几何体中各元素顶点x,y,z的值和值，即可构造出该几何体的层次包围体。

　　轴向包围盒的相交测试：两个AABB相交当且仅当它们在三个坐标轴上的投影分别重叠。根据AABB定义的六个值和值在三个轴向的投影，其两个子树节点多仅需六次比较运算。

　　伪代码如下：

　　AABB_intersect（A,B）

　　for  each  i∈{X,Y,Z}

　　if（aimin>bimax  or bimin>aimax） return false;

　　return true;

　　轴向包围盒的旋转和更新：根据AABB定义的六个值和值进行组合，对得到的八个顶点进行相应旋转后，选出值和值即可。而AABB节点的更新也远比其他算法简单，当几何体对象发生变形后，对变形叶节点部分自底向上重新选择值和值，仅需六次比较运算即可完成一个节点的更新。

　　2.2 算法改进

　　（1）AABB树由2×N-1个节点组成，其中N是几何体中基本图元（通常是三角形）的数目。完全AABB树有N个叶节点和N-1个内部节点，每一个叶节点包含一个指向基本图元的指针和包围基本图元的包围体。在进行碰撞检测时，遇到测试两个叶节点的情况，需要首先进行包围体间（BV/BV）的相交测试。如果包围体相交测试成立，则可进行基本图元的相交测试，确定位置。

　　改进算法的基本思想是舍弃AABB树的叶节点，即无需进行包围体间的相交测试，直接进行基本图元间的测试。因为如果基本图元相交，则包围体间的相交测试就可以省略；如果基本图元不相交，则改进所付出的代价就是测试包围体比测试基本图元节省的时间。由于AABB树没有叶节点，由更的基本图元（三角形）与包围体间的相交测试取代较粗糙的包围体间的测试，使得总体上进行相交测试的次数减少。

　　碰撞检测查询伪代码如下：

　　

 

　　程序中三角形和AABB的重叠检测采用Akenine-Moler的算法。该算法基于分离轴定理，对13条轴线进行测试，即AABB的三条法线。三角形的法线n,aij=ei×fj,i,j∈{0,1,2},其中ei为AABB的三条法线，fj为三角形边向量。三角形与三角形的相交测试使用经典ERIT算法，这两种算法在参考文献[1]中有详细描述。

　　完整的AABB树有2×N-1个节点，现在省略了N个叶节点，仅需N-1个节点，节省了大量的存储空间。在许多视景仿真应用中，一个场景可能存在许多复杂物体，从而占用大量系统内存，导致系统性能下降。与OBB和K-dop算法相比，改进的AABB算法节省了近70%的存储空间，显着改善了系统效率。

　　（2）虚拟环境中可能包含成百上千个运动物体。如果场景中包含N个运动物体和M个固定物体，则穷举的处理方法需要执行的碰撞测试次数为：。显然，其中包含了大量无效测试。随着N和M数量的增加，计算的开销会越来越大。为了尽可能减少进行碰撞检测的物体对数量，本文采用扫描-修剪算法进行筛选处理。

　　扫描-修剪算法利用虚拟环境中的时间相关性，即两幅连续画面之间物体的位置与方向变化较小，通过动态分离轴测试方法，计算可能发生碰撞的物体对，减少进行碰撞检测的次数。其基本原理是：如果两个物体重叠，则它们在三个主轴方向上的所有一维时间间隔必定也相互重叠。

　　假设Si、Ei分别表示在某主轴（X,Y,Z）上的一定时间间隔，Ii表示物体i在此时间间隔[Si,Ei]内投影到主轴上的运动区间。将[Si,Ei]存入一个排序列表中，然后对此列表进行扫描，当遇到起始点Si时，将其相应的时间间隔放入一个活动列表；当遇到结束点Ei时，将相应的时间间隔从活动列表中清除。如果在活动列表中存在多个时间间隔事件，则它们一定重叠。如图1所示：当S2进入活动列表后，S3进入，当遇到E2结束点时，S3仍然在活动列表中，因此可以确定，此刻物体运动区间I2、I3在该主轴上发生重叠。考虑到随后进行的碰撞检测调用中包围盒测试也使用投影方式确定是否重叠，因此在算法程序实现上只需要在X、Y轴上进行排序和投影。在碰撞检测的包围盒测试中则先对Z轴投影，这样可以省略在一个主轴方向上的投影和排序，提高算法的效率。

 

 

　　3  VEGA程序中轴向包围盒（AABB）的建立

　　构造AABB树，必须获得几何模型的点、面信息。VEGA开发环境下是以OpenFlight文件加载模型的。因此，可以根据已经公开的Flt文件格式，通过直接读取Flt文件获得几何模型信息，进而构建包围树。但是这种方式速度较慢，只能在程序初始化时加载所有需要碰撞检测的模型，这极大地影响了程序的灵活性。

　　本文提供一种方式，可以在程序中根据需要动态获取模型几何信息。由于封装的原因，VEGA没有直接提供访问基本几何元素（三角形）的功能，但是VEGA是在SGI Performer基础上发展起来的，可以通过嵌入Performer函数调用，获取所需信息。如果处理时间允许，也可以对模型进行修改。

　　（1）通过调用vgGetObjPfNode（VgObj?鄢obj）获得物体的Pfnode句柄。

　　（2）遍历Pfnode子树，利用pfIsOfType（pfnode,pfGetGeodeClassType（ ））得到pfGeode节点。

　　（3）在Performer中，模型的点、面存储于pfGeoSet节点。调用pfGetGSet（ ）函数可以得到pfGeoSet句柄。

　　（4）调用函数pfGetGSetAttrLists（ ）获得模型的点信息列表。通过pfGetGSetPrimType（ ）确定列表信息的存储顺序。可以使用pfGSetAttr（ ）修改几何模型。

　　基本代码如下：

　　

 

　　由于这种方式是在程序中动态读取场景中模型信息，所以读取时间将直接影响显示的帧频。一般情况下，正常显示所需的刷新频率在25帧/秒以上，VEGA平台下开发的程序帧频因场景及物体复杂度的不同而变化。以一个由7万多个三角形、132个物体组成的场景为例，稳定的帧频在19.0ms至20.3ms之间。经过多组试验比对，这种在程序中动态读取场景模型信息的方式，通常情况下不会超过2ms.如表1数据所示，比较复杂的模型（模型3和模型4）的读取时间都小于2ms,且独立部件越多，时间越长。如果模型过于复杂，可以考虑在程序初始化时加载。当然，CREATOR不提倡通过增加模型复杂度的方式达到提高逼真度的效果。正确的建模方式应该是对纹理技术、LOD以及BILLBORD技术合理搭配地运用，使模型尽量具有真实感，进而达到在视景驱动时减少内存使用、提高渲染速度的目的。

　　4  实验结果及分析

　　实验运行环境为：CPU主频--AMD2400+,内存--1GB DDR,显卡--128MB,VEGA版本为3.7.

　　首先对VEGA的Bump算法进行测试，为了屏蔽地形及场景等其他因素对实验结果的影响，场景中只放置三个运动物体（三角形数：3 072），结果如表2.

　　由实验数据分析可知：Bump方法没有进行优化处理，所以无论是否发生碰撞，所需的检测时间几乎相同，因而非常耗费系统资源。

　　对于相同场景，采用轴向包围盒方法对两个运动物体进行检测，结果如图2.其峰值检测时间仅为0.4ms,平均检测时间为0.063ms.对于多物体的情况，采用扫描-修剪算法对运动物体进行排序后再进行检测，所需时间也有显着减少。

　　通过上述数据对比可以证明，在VEGA下使用改进AABB算法处理物体间碰撞处理可以极大地缩短检测时间，系统性能也获得了显着提高。

　　碰撞检测是视景仿真软件重要的组成部分。本文就VEGA软件中关于物体间碰撞检测算法进行改进，将其应用于车辆碰撞仿真试验、某武器系统杀伤效果评估等项目，均取得了良好的效果。必须说明，由于仿真场景的高度复杂性和仿真要求的不同，处理场景中物体间碰撞的方式也不尽相同，许多情况下需要多种方法结合使用。因此，灵活地选取不同碰撞算法组合，才能取得较好的仿真效果。

　　同时，本文提供了一种在VEGA环境下调用Performer访问、修改场景中物体三维模型的方法，对于希望在VEGA下进行底层操作的开发者具有一定的借鉴意义。

 

 

  

参考文献:

[1]. VEGA datasheet https://www.dzsc.com/datasheet/VEGA_1117503.html.
[2]. N-1 datasheet https://www.dzsc.com/datasheet/N-1_1997158.html.
[3]. Flt datasheet https://www.dzsc.com/datasheet/Flt_329018.html.