虚拟现实中包围盒碰撞检测算法优化研究

陈秋菊

摘要：碰撞检测的实现是虚拟现实技术中的关键环节，其主要任务就是使得多个物体在发生接触时避免发生穿透现象，能够实现实时的、精确度高的连续碰撞检测对于增强虚拟现实场景的沉浸感和真实感是十分重要的。文章以三维虚拟校园漫游系统的开发为例，针对各种包围盒碰撞检测技术的缺陷，分析描述了基于包围球和有向包围盒的混合层次包围盒碰撞检测算法的优点和构建方法。最后将该算法在VC和Unity3d开发引擎中进行测试，得到了较好的效果。

关键词：虚拟现实技术；包围盒；碰撞检测；Unity3d

中图分类：TP3 文献标识码：A 文章编号：1009-3044（2018）19-0236-03

虚拟现实技术是一种集合了计算机图形学，多媒体技术等多种技术为一体的综合性技术，其目的是模拟现实中的场景[1]。为保证环境的真实感，场景中的物体就必须具有相应的物理属性，这就要求用户在进行各种操作时，身体不会穿透物体，并且能够真实感觉到碰撞的发生，所以碰撞检测技术在VR技术中就有了相当重要的地位[2]。

碰撞检测技术不断发展，一些经典的碰撞检测算法应用亦十分广泛，包括经典的轴向包围盒法AABB（Aligned Axis Bounding Box）、包围球法（Spheres）、有向包围盒法OBB（Oriented Bounding Box）等，这些方法适用于不同几何特征的物体，所以检测的简洁性不是十分理想。故而，一些学者提出了混合包围盒算法，形成了类似OBB-Spheres的算法。

本文从虚拟校园漫游系统的开发要求出发，针对系统的真实感，交互性问题，研究了碰撞检测技术在Unity开发引擎中的应用方法与优化方案。

1 碰撞检测基本原理

虚拟校园漫游系统的构件运用了碰撞检测技术、实时渲染技术、环境建模技术等技术手段完成了系统的开发。其中碰撞检测技术保证了整个系统的真实感，同时构成了用户体验的基础，赋予了用户在虚拟场景中的沉浸感。

碰撞检测技术就是在场景当中的物体上增加碰撞体，增加真实感，防止出现人物穿墙而过，人物的一部分和场景中的物体重合等显然与现实生活中的逻辑不相符的现象[3]。其基本原理可定义如下：在一个具有[n]个物体的虚拟三维空间中，其三维几何坐标系统加上时间变量构成一个四维坐标系统，表示为[Cw]，第[i]个物体运动形成的轨迹就构成了一个[Cw]的子集，标记为[Ci]（[1≤i≤n]）。碰撞检测就是判断第[i1]个物体是否与第[i2]个物体相交，也就是判断[Ci1?Ci2]是否为空。

对于物体碰撞的检测，Unity提供了一个很好的测试平台，在该平台下可以建立两个虚拟几何体，给它们赋予碰撞器，然后检测它们之间的碰撞效果。

2 基于包围球和有向包围盒的混合层次包围盒

2.1 包围盒技术

包围盒技术有很多类型，一些经典方法主要有包围球（Spheres）、轴向包围盒法AABB、有向包围盒法OBB等。这里主要介绍包围球与有向包围盒的基本原理。

1） 包围球（Spheres）是一种构造起来相对比较简单但紧密型却较差的包围盒。作为一个几何物体的外接球体，对于凹面较多的物体来说，就会产生过多的冗余空间，从而碰撞时会产生没有碰到物体而碰到了包围球的现象。为了便于说明其构建过程，这里假设几何物体为E，用SE表示该物体中所有最基本的几何元素（如三角形、圆）的集合。包围球的计算方式相比其它包围盒较为简单：集合SE中的所有元素的三个坐标值（三角形为角平分线交点坐标值，圆为圆心坐标值）的平均值就是包围球的球心，记为c（x， y， z）。然后对球心到物体E中每个基本几何元素距离进行比较，得出的最大值就是包围球的半径，记为R。由此可以看出，记录一个包围球所需的参数相对其他包围盒要少很多，得到一个球体只需要给出其球心的坐标和半径。

包围球之间的相交测试方法也相对比较简单，只需将两个球体的圆心距离和它们的半径之和进行比较即可，其具体方法如下：

设两个包围球的球心和半径分别为：s1（x1， y1， z1）、R1和s2（ x2， y2， z2）、R2。若[s1-s22≤R1+R2]，则两个包围球相交，否则两包围球不相交。此不等式的详细表述为：

由于球体无论朝哪个方向旋转，表述其属性的参数都不会发生变化，因此无论被包围的几何物体如何进行旋转，它都不会跑出包围球外，所以对于一个固定形状的物体来说，当其发生运动时，包围球无须对半径进行重新计算，而只需要对圆心坐标进行相应的平移即可。但对于一个形状不断改变的物体来说，就只有对该物体的包围球的球心和半径进行连续的重新计算了。因此包围球碰撞检测算法的实时性与连续性较差。

2） 有向包围盒OBB。它是一种包含了几何物体且在坐标系中具有任意方向的最小长方体。在构造OBB时如何找到该长方体的最佳方向，并且确定其长宽高的可达最小数值是构造的关键。相比包围球来说，OBB的构造也就显得十分困难，其具体构造方法如下：

给定一个几何物体记为G，用SG表示该物体中所有最基本的几何元素（如三角形、圆）的集合。為了描述的简洁，假定构成该物体的所有基本元素均为三角形，设共有n三角形，其中第i（i >0）个三角形的三个顶点记为ai、bi和ci，则集合SG的均值μ和协方差C的求值方法分别如下（ai、bi、ci均为一维向量）：

其中μ为一维向量，Cjk为一个数值，将由矩阵元素Cjk组成的对称矩阵记为C。由于得到的矩阵C为实对称矩阵且具有三个不同的特征值，因此三个特征值所对应的特征向量是相互正交的，对得到的三个特征向量进行单位化处理也就得到了一组基，这组基也就构成了OBB的三个方向轴，这就确定了OBB的最佳方向，剩下的就是确定OBB的最小长宽高。找到这三个最小数只需将SG中每个基本几何元素的顶点在刚刚得到的三个方向轴上进行投影，每个轴上的投影所得最小数值就是所需的长宽高。

根据以上构造方法的描述，可以知道OBB的构造十分复杂，描述一个OBB也十分麻烦，所需参数较多，共需要15个数来进行描述，其中9个数用来描述三个方向轴，每个轴由一个由三个参数构成的一维向量表示，剩余的6个数表示OBB长宽高的长度大小与对应方向轴。

由上述方法构造的OBB因其基底的任意性，从而具有较高的紧密性，并且能够跟随物体形状的改变而快速做出方向长度的变化，不需要进行重新计算。

2.2 模型搭建

虚拟校园的三维建模主要是对校园内和校园周边的地形、道路、建筑、植物等物体进行三维建模。三维建模主要的工作为对需要进行建模的物体进行基础地理信息的采集、整理、分类和预处理。涉及的基础技术为多边形建模和纹理映射[4]。

在传统的三维场景搭建方式中，场景中的各种物体因其形状，精度等要求的不同而具有多种几何表示方法，目前用得较多的为曲面模型和多边形网格模型。在校园漫游系统中，由于场景中的物体多为棱角分明的建筑，所以多采用多边形网格模型来构建。多边形模型由最基本的点和线构成模型的形状，然后对物体表面赋予相应的材质，并通过添加光照模型来增加物体的真实感。其中材质的添加使用了纹理映射技术，也就是将表示物体表面纹理的二维图像映射到三维物体的表面。其基本思想就是把纹理图案的坐标按一定方式映射到三维模型表面的顶点几何坐标，然后再将几何对象上的点映射到屏幕上，最终进行显示，如图1所示。

2.3 层次包围盒树的构建

漫游系统是一个连续循环的过程，不断通过逻辑判断绘制展示给用户的每一帧。为了提高碰撞检测的速度与实时性，传统的包围盒碰撞检测算法无法得到理想的效果，而混合层次包围盒算法解决了这一问题[5]。

层次包围盒树，就是由包围盒所构成树節点组成的树结构。根据前面的介绍，OBB包围盒算法具有较好的紧密型，物体发生位移或旋转时更新速度也较快，但相交测试难度较大，速度也较慢，而包围球算法虽然紧密性差，但相交测试简单快速，并且具有比OBB算法更快的更新速度。结合两种算法的优点，这里选用这两种算法。

包围球算法由于相交测试的简单速度可以作为包围盒树的根节点，用来排除大量很容易判断的不相交物体。在构造包围盒树时，所用方法主要有两种，一种为自底向下的方式，也就是将构成一个物体的一个个基本的几何元素作为叶节点，然后进行不断的递归，逐步形成最终的一个根节点，也就是该物体。还有一种就是完全相反的自顶向下的方法，即从根节点开始递归划分，最终到叶节点。由于目前构造技术的成熟性和使用的广泛度，这里选用了自顶向下的方法来构造层次包围盒树，如图2所示。

在构建包围盒树时还要考虑是采用动态方式构建还是采用静态的方式来构建[6]。使用静态结构建立时，一旦物体发生形状改变或移动，就需要重新构建包围盒树。而使用动态结构时，则不需要随着物体的改变而重新建立。动态结构虽然灵活性相比静态结构较好，但需要实时修改节点数据，稳定性较弱，更新的实时性较难解决。由于虚拟校园漫游系统中的物体多为静态物体，碰撞时不会发生变化，所以这里采用稳定性较高的静态结构来构建包围盒树。

3 系统应用及测试结果

为了验证该算法能够很好地实现不同几何特征物体之间的碰撞检测，首先进行初步的测试，即用一个茶壶和一个圆柱体进行碰撞测试，茶壶是由8680个三角形、17500个顶点组成的，而圆柱体由8064个三角形、16256个顶点组成的，其复杂度可满足测试要求。在两个物体的包围二叉树顶点构造双重包围盒，节点外层构造包围球，节点内层分别构造OBB和sphere包围盒。将其与基于OBB包围盒的碰撞检测算法RAPID进行对比，根据碰撞检测算法的评价函数：

对该算法与RAPID算法进行对比分析。

实验在得到相同且正确的检测结果的前提下，对同一碰撞场景中两种算法的碰撞检测时间进行了对比。根据碰撞检测评价函数，两种算法进行碰撞检测时参与检测的基本几何图元对的数目Np 相同，一对几何图元求交的代价Cp相同。对比实验使用同一场景，物体的运动轨迹一致，物体运动后两种算法需要更新的节点数目Nu相同，本文算法更新一个双重包围盒的代价Cu即为更新一个内层包围盒的代价。因此，两种算法的总代价T与包围盒重叠测试的代价Nv*Cv和更新一个包围盒的代价Cu相关。

该算法为茶壶和圆柱体的包围盒二叉树节点内层分别构造sphere和OBB。sphere与OBB相交测试类似于OBB算法，但测试更加快速简捷，最多只需判断三次，sphere包围盒比OBB的更新代价小，因此该算法比RAPID算法更新一个包围盒的代价更小。两种算法的实验结果如表1所示，算法效率对比如图3所示。

实验结果表明，在三角形重叠数目相同时，该算法相对于RAPID算法大大缩短了碰撞检测的时间，物体间的碰撞响应得到加快，进而提高了物体实时碰撞时场景显现的真实感。

在Unity3d开发引擎中具有基于各种层次包围盒碰撞检测算法开发出来的碰撞器，软件系统开发人员只需要对物体添加不同的碰撞器就可以完成相应算法的碰撞检测测试，而不需要编写相应的碰撞检测算法，这就有效地提高了软件开发的效率[7]。Unity中，主要有Box Collider、Sphere Collider、Capsule Collider、Wheel Collider等静态碰撞器和用于动态物体的刚体碰撞器。在该系统中，对漫游角色添加了刚体碰撞器，对建筑、花木、地面等物体添加各种静态碰撞器。碰撞的信息处理通过脚本中的OnCollisionEnter（碰撞发生）、OnCollisionExit（碰撞消失）、OnCollisionStay（碰撞保持）函数实现，在碰撞发生函数中添加一个弹出GUI界面的函数来弹出特定GUI界面[8]。本文算法同时可通过Unity中的Game界面，完成系统的碰撞功能测试。

当角色和某一个建筑物发生了碰撞时，由于给特定的建筑物附件添加了碰撞体，当用户和这个碰撞体发生了碰撞则触发了碰撞检测，通过脚本触发一个碰撞事件，则会弹出一个信息窗口来介绍相应的建筑物。

通过该测试，可以知道基于包围球和OBB包围盒的混合层次包围盒碰撞检测算法在开发系统的过程中也得到了非常好的效果。不仅增强了场景的真实感，而且通过碰撞事件的检测完成了窗口弹出事件的触发，增强了交互性。

4 结论

本文从虚拟现实技术基本理论及碰撞检测关键技术出发，对基于虚拟现实技术的虚拟校园漫游系统进行研究。通过系统的整个开发过程，着重对系统的碰撞检测技术的实现原理以及基于包围球与有向包围盒的混合层次包围盒算法进行了介绍，同时对本文算法和开发系统的碰撞检测功能进行了测试，该技术在系统中得到了较好的使用效果，使校园的风光得到了更好的展示。

参考文献：

[1] 唐翠芳.基于虚拟现实技术的校园漫游系统设计与实现[J].科技创新导报，2016，（20）：87-88.

[2] 韩蕾.基于Unity 3D的虚拟楼盘漫游和碰撞检测研究[J].电脑知识与技术，2016，（19）：194-195+197.

[3] 王瑜.虚拟漫游系统中碰撞检测技术的研究与应用[J].电子设计工程，2016，（13）：155-156+160.

[4] 王爽，陈永当，孔繁锦，杨斌. 虚拟现实技术概论[J].科技视界，2016，（11）：129+153.

[5] 张少波. 沉浸式虚拟现实中人机交互关键技术研究[D].重庆邮电大学，2016.

[6] 张佳佳. 三维虚拟环境中的碰撞检测技术优化仿真[J].计算机仿真，2016，（3）：359-362.

[7] 来全，查木嘎，金额尔德木吐，金呼格吉乐吐.基于Unity3D平台的三维可视化校园系统开发研究[J].图书情报导刊，2016，（01）：124-127.

[8] 王磊.基于混合型包围盒碰撞检测技术的研究及其在Web3D漫游中的应用[D].上海大学，2015.