摘 要：通过优化轴向包围盒算法（AABB），改进并完善了视景仿真软件VEGA的碰撞检测功能。同时提供了一种在VEGA环境下通过Performer直接访问和修改物体三维模型的方法。
关键词：碰撞检测 视景仿真 VEGA 轴向包围盒 Performer
随着计算机、图形处理和图形生成等技术的迅速发展，视景仿真已经成为现代仿真技术的一个新的研究领域。它通过构建逼真的视觉、听觉和触觉等三维感觉环境的人机交互系统，改变了传统的以数据和曲线表示实验结果的仿真形式，使实验人员以更加直观、交互的形式观察并参与仿真过程，评估仿真实验结果。因此，视景仿真在军事模拟训练、航空航天、城市规划仿真、影视娱乐以及教育培训等诸多领域得到了广泛应用。
在众多的视景仿真应用中，碰撞检测及其相关问题是最基本也是最重要的组成部分。实时、精确的碰撞检测技术对于提高虚拟环境的真实性，增强虚拟环境的沉浸感起着至关重要的作用。本文通过改进的轴向包围盒碰撞检测算法，对业界广泛使用的视景仿真开发平台VEGA的碰撞检测部分进行了改进。改进后的系统不仅显著提高了碰撞检测的速度，并且可以便捷地得到更为详细的碰撞检测信息，满足了进一步进行碰撞响应处理的需要。
1 VEGA软件及其碰撞功能简介
在现有的视景仿真开发工具中，美国MULTIGEN-PARADIGM公司推出的VEGA平台是实现虚拟现实、实时视景仿真和可视化计算应用最广的解决方案。VEGA基于GL图形库，是在SGI Performer视景软件开发包基础上发展而来。VEGA软件专门设计了Isector类处理各种碰撞检测问题，并提供八种碰撞检测算法供开发者进行选择(VOLUME，Z，HAT，ZPR，TRIPOD，LOS，XYZHPR，BUMP)。其中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提供的其他检测方式都不能满足这些要求。因此，设计使用了一种基于层次包围体的碰撞检测算法，改进了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 Tomas Akenine-Moler，Haines E.实时计算机图形学(第2 版).北京：北京大学出版社，2004
2 王志强.碰撞检测问题研究综述.软件学报，1999；10(5)
3 康凤举.现代仿真技术与应用.北京：国防工业出版社，2001
4 Multigen_Paradigm Inc. Vega Programmer's Guide Version 3.7 for Windows NT and Windows 2000.http：//www. multigenparadigm.com，2001
5 Eckel G，Jones K.OpenGL PerformerTM programmers guide. Englewood Cliffs：Prentice-Hill，2000