基于Vega的碰撞检测算法研究

霍光　李中英

摘要：虚拟环境下的碰撞检测问题是当今计算机图形学研究的热点之一。针对复杂场景实时漫游过程中的碰撞检测本文提出了一种将分割过滤法与包围盒技术相融合的碰撞检测方法，在Vega平台下，应用本算法成功实现了桌面级非沉浸式虚拟漫游系统，在检测精度和检测速度上都取得了满意的效果。

关键词：分割过滤 实时漫游

引言

在虚拟环境中，为了模拟真实世界，让用户获得高度的沉浸感，就必须为用户提供具有关键交互作用的虚拟环境。虚拟现实系统一个最重要功能，就是能快速进行虚拟世界中物体间的碰撞检测。精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感起着至关重要的作用，而虚拟环境自身的复杂性和实时性对碰撞检测提出了更高的要求[1]。

1为观察者建立碰撞检测模型

漫游者在漫游过程中会与地面、障碍物发生碰撞。虽然Vega 有对地面碰撞检测的定义，但对于自定义的运动模型根本起不到实质的作用，因此本文采用基于视线的BUMP算法进行碰撞检测。

该方法使用6段线段，包括x,y的正负方向和由相交矢量的位置和方向定义的z轴正负方向。线段长度分别由相对于x,y,z轴线段的3个属性VGIS-_BUMP_WIDTH、VGIS_BUMP_LENGTH和VGIS_BUMP_HEIGHT控制。通常情况下，该方法比其它方法代价更高，但是却更为灵活适用。这是因为在该方法中有6段线段而不是3段线段，其线段不仅有长度，还有方向。但缺点是在碰撞实体选择时，往往不知道视线应与哪一个多边形求交，如果每次都要对整个场景中所有表面多边形全部都遍历一遍，势必产生巨大运算量，造成无谓的浪费。因此，在实现基于视线的碰撞检测算法时，可以考虑借助包围盒来简化碰撞的模型，以提高碰撞检测的效率。

（2）包围球

包围球被定义为包含该对象的最小的球体，计算给定对象E的包围球，首先需分别确定被包围几何对象中各个顶点的x，y，z坐标均值以确定包围球的球心c，再由球心与三个最大值坐标所确定的点间的距离计算半径r，包围球的计算时间略多于AABB，但存储一个包围球只需两个浮点数。

包围球的紧密性在所有包围盒中是比较差的，它除了对在三个坐标轴上分布得比较均匀的几何体外，几乎都会留下很大的空隙。但包围球有一个比较优秀的特性，就是对于旋转运动来说，包围球不需要做任何更新，因而当对象进行频繁的旋转运动时，采用包围球可能的到较好的结果。

3包围盒的改进

前面提到的几种现在比较常用的碰撞检测方法都各有其有缺点。比如：包围球的紧密性较差，但是它的相交测试十分简单；与之相反，方向包围盒紧密性较好，可是相交测试相对困难。

本系统是一个基于视点的漫游系统，因此，对碰撞效果的真实感要求相对要高一点，而影响碰撞检测精度的直接因素就是对相交检测对象所建立的包围盒的精度。因此本文选用的包围盒是一种简化的OBB。这种简化包围盒具有近似OBB的紧密度，同时，也为后面的碰撞检测提供了一种相对简单的检测模型。具体简化过程如下：

（1）降维

由于建模的场景是校园，所以大多数的楼体的基面都是与地面平行的，这就为OBB中最佳方向的计算提供了一个约束条件。即最佳方向只可能是与地面水平或垂直的。这样一来，就可以把三维的OBB计算简化为（对建筑物的垂直投影的）二维计算。得到二维的最小包围矩形后，对每条边进行垂直提拉就可以恢复到三维的包围盒了。

（2）收缩

由于本系统所选用的漫游模式是步行，碰撞检测的高度不会超过3米，因此在建立包围盒时没必要把高过3米的物体或物体的某一部分包含在内。例如：像房屋的屋檐、大树的树冠这类物体一般都是只对其下部的楼体、树干建立包围盒即可。这样做的优点是：

?誗 减少了包围盒的数量；

?誗 缩小包围盒的范围；

?誗 提高包围盒的紧密度。

（3）选建

对于像马路沿、台阶这种有一定高度的实体不建立包围盒。因为这类物体虽然也有碰撞，但它们是可以跨域的，碰撞瞬间的现象主要表现为漫游者视点高度的增加或减少，而不像楼房那样碰撞后无法前进，所以只要是高度小于跨越高度（zoffset）物体，都不对其建立包围盒，而是通过修改其视点高度来实现其碰撞的效果。

4 碰撞检测优化方法

对于范围较大的场景，且场景中景物繁多的情况，在漫游的过程中实时的对场景中的每一个物体都进行碰撞检测，无疑将给系统带来巨大的计算开销，降低系统的性能。为此，人们提出了空间分解法[2]和层级包围盒法[3]。本文采用的分割过滤法也属于空间分解法一种，因此原理也是通过滤去不需要的数据，以减少不必要的计算。所谓分割过滤法就是将漫游场景分割成规则网格，以此将场景中的物体分割成小的群组。并对规则网格建立对应的平面索引表。如图2所示：

此方法的目的是为了在系统进行碰撞检测时，较少实体比较的次数。在漫游的过程中，只需根据视点所在位置的坐标，就可以确定视点所在的网格，然后，再与该网格内的物体进行碰撞检测即可。从而大大的较少了碰撞检测的计算量，提高了碰撞检测的速度。对于包含有大量地物的模型，效果尤为明显。

场景平面索引表中的地物数据可能有重复的现象，这是由于有些地物横跨两个或两个以上的地形块，如图3所示，A只属于地形块1，对应平面索引表的一行。C，D也是如此它们也只属于地形块2，不同的只是在一行中有两条记录而已。而B则不同，它横跨4个地形块（5,6,9,10），如果只在地形块5中为其建立一条记录，那么当视点漫游到6,9,10中并与B发生碰撞时，由于没有B的记录，B也不会被列入检测的范围，进而被检测所遗漏。为了避免遗漏现象的出现，本文在平面索引表5,6,9,10四行中，都建立B的记录，这样无论在这四块中的哪一块碰到B，系统都能检测到。

5 实验结果

本算法是将整个场景分割为若干个小空间，对每个小空间的对象用一个较为简单的形体（包围盒）进行描述，再对该包围盒进行宏观检测，检测方法简单、精确，检测速度快，能够满足大范围场景中实时交互的要求。

当然，BUMP检测方法也有它的局限性，如它的视线方向始终是保持水平的，就象人行走在起伏的路面上，人的视线基本保持水平一样，因此，它可以较好的模拟人的行走。

参考文献

[1] Kamat V.A survey of techniques for simulation of dynamic collsion detection and response[J], Computer&Graphics,1993,17(4):379-385

[2] 陈华斌 王彤，虚拟建筑环境实时漫游系统的设计和实现，西南交通大学学报，2001

[3] 胡艳 陈蒙蒙， 一种基于等距线的碰撞检测算法，电子科技，2009

[4] 支剑锋 韩长红，虚拟景区中层次碰撞检测方法的研究，电脑知识与技术，2011