碰撞检测技术在视景仿真中的设计和应用碰撞检测技术在视景仿真中的设计和应用
通过优化轴向包围盒算法(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节点的更新也远比其他算法简单,当几何体对象发生变形后,对变形叶节点部分自底向上重新选