钟淑平

（长江工程职业技术学院 湖北 武汉 430212）

0 引言

碰撞检测是三维场景中交互事件触发最主要的方式，通过碰撞检测技术可以为三维场景中的虚拟物体添加物理模拟属性，使虚拟物体具有实体，当实体之间发生碰撞被检测到以后，就可以动态触发交互事件。三维场景最初的应用主要是在游戏和娱乐领域，场景结构较为简单，对碰撞检测的精度和响应时延等需求也较低，3D 开发引擎的内置组件就可以满足一般性的碰撞检测需求[1]。而随着三维技术的快速发展和应用普及，在很多的专业领域也需要应用三维交互技术，例如工业流程的模拟作业、医疗器械设备的模拟操作等，这些三维场景对交互的响应时延和精准度都具有很高的要求，而原有的碰撞检测技术只能实现简单场景下规则模型的边界检测，无法满足更高精度的检测，为了提高检测精度，算法设计过于复杂又难以保证检测的响应[2]。因此，本研究尝试采用混合分层式包围盒算法改进策略，以提高复杂场景下的碰撞检测精度和实时性。

1 碰撞检测技术的包围盒算法概述

碰撞检测技术的算法有很多，其中包围盒是应用最为广泛的一类算法[3]。包围盒算法是典型的基于几何体空间检测的算法，其核心思路是通过构建规则几何体网格对三维模型进行包裹，通过检测几何体网格之间的相交情况来判断是否产生碰撞。主流的包围盒检测算法包括：轴对齐包围盒（Axis-aligned Bounding Box,AABB）、方向包围盒（Oriented Bounding Box,OBB）、k-DOPs包围盒等算法[4]。

1.1 AABB 算法

AABB 包围盒主要是通过构建规则长方体网格对三维模型进行逼近，即构建能够包裹住待检测模型的最小长方体。在公式中可以通过三维空间坐标上的六个坐标值进行描绘，称为最大值、最小值表示法。公式如下：

式中xmin、xmax、ymin、ymax、zmin、zmax 表示三维模型在坐标空间中顶点投影的最大值和最小值。

此外，还可以通过中心－半径表示法和长度表示法进行描绘，公式如下：

式中xc、yc、zc表示三维模型在坐标空间中的中心坐标投影；rx、ry、rz表示三维模型在坐标空间中的投影半径，可由式（4）获取；WX、Wy、Wz表示三维模型在坐标空间中的投影长度，可由式（5）获取。

AABB 包围盒结构简单、算法易于实现，且执行效率较高[5]。针对外观较为规则的模型来说，AABB 包围盒的空间利用率非常高，一般性的相交检测都能够实现。但AABB包围盒的算法设计并未考虑到方向问题，因此三维物体动态平移、旋转的情况下，会大大降低算法的检测精度，同时该算法也不适用于不规则形态模型的精确检测。

1.2 OBB 算法

OBB 包围盒可以理解为带有方向的AABB 包围盒，采用OBB 算法构建的包围盒可以适配任意旋转角度的三维模型检测。OBB 包围盒的构建，可以由式（6）表示：

式中O 表示包围盒的中心点坐标；r1、r2、r3表示包围盒三个轴向上的半径；v1、v2、v3表示正交向量，用于来描绘包围盒的方向，可由协方差公式获取[6]。首先假设待检测的三维模型的所有面片均为三角形面片，其中单个三角形面片j 的顶点坐标可以表示为Aj（Ajx，Ajy，Ajz）、Bj（Bjx，Bjy，Bjz）、Cj（Cjx，Cjy，Cjz），三角形面片总数为n，中心点O 的公式表示如下：

OBB 包围盒相较于AABB 包围盒，对于任意方向变化的模型检测效果更好，且算法开销适中，在提高检测质量的同时还能很好的兼顾执行效率。缺点与AABB 包围盒一样，采用规则的长方几何体构造，对边界复杂的模型包裹紧密度较差，无法实现细节化的碰撞检测。

1.3 k-DOPs 包围盒

k-DOPs 包围盒是一种多面不规则几何体包围盒，也称为离散型包围盒[7]。k-DOPs 包围盒所有面的法线向量由方向集合k决定，k的值越大，包围盒的面数构建越复杂，对模型的逼近度也就越高，而AABB 与OBB 包围盒也是属于k-DOPs 的一个特例6-DOPs。构建k-DOPs 包围盒的算法设计与OBB 包围盒相类似，但首先需要基于固定方向k 集合进行三维空间的分离，构成半空间，再选择k/2 个方向进行法向量的中心点和协方差计算。这是因为另外k/2 方向的法向量选取的是基于共线的相反向量，构建的半空间只需对称过去即可构成完整的包围盒。计算法线向量的协方差是一个三阶对称式矩阵，其公式如下：

k-DOPs 包围盒检测精度的高低取决于k值的大小，k值越大，精度越高、算法开销越大、执行效率也就越低。

2 层次包围盒的构建

上述三种包围盒算法在检测的精度与执行效率等方面各有优势，因此可以通过层次包围盒的构建，以实现这些算法优势的有效融合。

2.1 层次包围盒的构建思路和检测流程的设计

层次包围盒的主要构建思路是通过对三维模型的细化和分割，以实现对其更加精确的检测，并采用层次式树状结构对模型细化的完整过程进行管理，依据不同层级上的检测需求选择适当的包围盒算法实现检测[8]。检测流程设计如图1所示：

图1 基于层次包围盒的算法检测流程

层次包围盒首先通过递归将待检测模型进行图元分割，并将其结构信息以BVH 节点树进行存储，根节点表示模型本身，中间节点表示模型分割后的局部信息，叶节点表示分割模型的最小单位——图元的信息。检测流程首先对根节点进行检测，当根节点未与其他包围盒发生相交，则可以直接判定模型未发生碰撞；当根节点检测到相交，则按照节点树的层次结构逐层递归遍历所有的内部节点，直到锁定相交节点，并通过该节点上的图元信息获知模型碰撞的具体位置。

2.2 层次包围盒的构建

层次包围盒的构建包括三个关键因素，即树结构的选择、构造方式的选择和包围盒算法的选择[9]。

（1）树结构的选择是指树的节点结构选择，树的节点结构主要分为二叉树、三叉树、四叉树和八叉树[10]。树的横向节点分叉值越大，纵向深度节点就会减少，层次间的迭代次数也会减少，可以节省更多的内存空间，同时检测精度也会更准确，但在模型的相交检测过程中，会成倍增加相交的节点数，检测流程的判断次数也会成倍增长，算法开销较大，因此树结构的选择还需要结合具体的三维场景需求进行。

（2）BVH 树按照树的构造层级划分包括三种构造方式：从根节点划分、从叶节点合并、层级渐进插入。

从根节点划分构造方式，首先对待检测模型构造一个完整包围盒，将其信息存储在根节点中，再将其逐层进行子树划分，产生的子节点中会包含若干图元信息，并以节点为单位构造包围盒，然后继续分割子节点，直到包含单一图元信息的叶节点。该构造方式的核心是子树的划分，可以采用超平面分割法，通过平面对模型进行左右对称式分割。

从叶节点合并构造方式，先分割待检测模型的基本图元，构建叶节点，每个基本图元对应一个叶节点，并构造相应的包围盒，逐层向上对相邻的节点进行两两合并，直至根节点对应完整模型的包围盒信息。相较于从根节点划分的构造方式，该方法实现过程相对复杂，但构造的BVH树结构更为优化。

层级渐进插入方式是一种动态构造方式，初始状态下先构建一个只包含根节点的空树，动态构建包围盒的过程中不断将新产生的节点插入到根节点下。在插入新的节点之前，需要先将节点包围盒与根节点包围盒进行比对，当节点包围盒体积大于根节点包围盒时，则尤其替换根节点；反之则插入根节点的下层。当BVH 树包含两个层级以上，需要通过递归将新的节点逐层向下比对，并插入到适当位置。

（3）包围盒算法的选择

常用的包围盒算法中，AABB 轴对齐包围盒结构最为简单、测试难度小、执行效率高，但动态检测效果差，模型包裹紧密度差；OBB 方向包围盒增加了法向量属性，能够更好地逼近模型，但检测效果依然存在较大误差，且算法复杂度要高于AABB 包围盒；k-DOPs 包围盒的构造最为复杂，紧密度最高，但在物体运动过程中，算法更新较慢，执行效率较低。综合这三种算法的自身特点，考虑在BVH树的根节点层级可以选择AABB 算法，用于实现待检测物体的快速检测，通过粗糙检测首先判断物体是否存在相交，如果存在，再做进一步的精确检测；在BVH 树的中间可以选择紧密性更好的OBB 算法，以判断是物体的哪个局部发生相交；锁定局部区域后，在BVH 树的底部叶节点处采用k-DOPs 算法对物体的基本图元依次进行相交检测，以最终确定模型的相交部位。这种基于混合算法的层次包围盒构建策略，能够大大提高碰撞检测的精准度，同时还能保证检测效率。

3 基于混合算法的层次包围盒构建

基于混合算法层次包围盒——BVH 树的构建结构如图2所示：

图2 基于混合层次包围盒的BVH 树结构

由上图可知，BVH 树构建采用二叉树结构，自顶向下从根节点开始进行模型分割，顶层根节点选择AABB 包围盒，中间节点选择OBB 包围盒，底部叶节点选择k-DOPs包围盒。

首先是根节点层级对模型整体进行包围盒的构造，通过模型顶点的最大值与最小值采集，确定模型的中心点与半径，即可依据公式2.2 构造AABB 包围盒。再以AABB 包围盒的最长边为分割轴对模型进行左右子集的分割，若最长边分割难以实现，递归调用最短轴分割法，以包围盒最短轴为分割轴进行分割。其次分割后图元子集作为中间节点，采用OBB 算法构建子集包围盒，图元子集作为模型的局部区域，采用带有方向包围盒，能够具有更好的紧密性。针对OBB 包围盒的分割，可以采用平面分割法进行分割，即在包围盒中确定一个平面作为超平面，依据图元子集相对于平面的位置进行二叉树的子集划分。如果存在基本图元横跨平面的现象，则以图元的质心与平面的相对位置为依据进行划分。最后当划分的子集仅包含单一图元时，表示为BVH 树的叶节点层，叶节点采用k-DOPs 算法构建包围盒，对基本图元实现紧密包裹，且不再进行分割。该层级主要用于实现精确级别的碰撞检测，因此除了基于包围盒的相交检测，还增加了基于图元的检测步骤。基本图元大都以三角形面片为主，判断三角形面片是否相交，可以通过点与点、线段与线段、点与三角形面的相交测试等方式来确定。

4 结论

随着虚拟仿真技术在各行各业的广泛应用，用户对三维场景的交互体验要求越来越高，需求也日趋复杂。在此背景前提下，本研究对三维场景交互实现的关键技术——碰撞检测技术的核心算法设计进行了深入研究和探讨，详细分析了AABB、OBB、k-DOPs 三种包围盒算法的设计思路与实现过程，结合三种包围盒算法的优缺点，提出了基于混合包围盒算法构建BVH 层次树的碰撞检测策略，一方面能够有效提高碰撞检测技术的精度，另一方面能够确保在精确检测环节中算法的执行效率和响应速度。