虚拟装配中基于层次包围盒的空间快速验证

方舟，易朋兴*，杜玉娇，李阳

1 华中科技大学 机械科学与工程学院，湖北 武汉 430074

2 武汉第二船舶设计研究所，湖北 武汉 430205

0 引 言

船舶建造需要庞大而复杂的工程系统在有限的空间和资源内完成各种类型的工作，若设计时考虑周到，便能合理利用空间与资源[1]。虚拟装配有助于对产品组件进行虚拟分析和设计，在设计阶段进行必要的虚拟装配既能缩短产品开发时间、降低生产成本，又能优化产品性能[2]。碰撞检测是虚拟装配中的关键技术，直接影响装配仿真是否为“真”的问题[3]。空间快速验证是一种碰撞检测技术，用于验证部件在空间运动过程中（主要考虑平动）是否会发生干涉，能对虚拟装配中装配性能的好坏进行评定，从而改善装配性能。

Gonzalez-Badillo 等[4]开发了基于物理和约束的触觉虚拟装配系统，但未针对碰撞检测性能的瓶颈问题开展深入研究。Liu 等[5]采用网格与k维树结合的方法在虚拟环境中模拟了无人机的碰撞检测问题，但是只能在某一时刻进行静态的碰撞检测。Qi 等[6]提出了基于动态扫描与修剪技术和事件驱动机制的碰撞检测算法，在大规模多体虚拟场景中具有很高的鲁棒性与稳定性。王达鹏等[7]考虑到面片模型碰撞检测速度虽快但精度不足而实体模型速度慢但精度较高等问题，采用分布式碰撞检测，在主机上完成面片检测、从机上完成实体检测，提高了精度与速度，但实例验证不够深入。李普等[8-9]改进了基于图像空间的算法，即利用半透明颜色叠加快速剔除无碰撞零件，然后配合像素深度值求出最小分离距离，该算法弥补了基于图像空间算法不能求距的缺点，但其将三维降为二维，在深度方向缺失了一定的精度。杜群[10]将碰撞问题转化为二维平面上的优化问题，并提出了一种改进的蚁群算法，在基于Unity 的虚拟装配系统中有较好的仿真效果，但二维平面会使精度降低。卢江等[11]利用四元数法设计鹰眼观察坐标系，建立物体模型的对应关系，结合轴向包围盒（AABB）与离散方向多面体包围盒（KDOP）检测算法进行碰撞检测，具有较高的精度与速度。上述研究中仅有李普等提出的算法涉及到空间快速验证问题，其余算法均为静态检测，不能满足实际装配需求。

在舰船三维模型装配过程中存在部分零部件需要以平动方式进行拆卸或在维修过程中需要将工具平动到维修点的情况，而现有平动碰撞检测算法略有不足，在实际情况中针对平动碰撞检测问题只能采取实地人工测量。本文根据上述文献中的算法，针对现有空间快速验证算法存在的问题，拟提出一种基于包围盒与三角面片的空间快速验证算法，然后结合CATIA 二次开发技术完成模块的设计、开发并进行实例验证。

1 基于层次包围盒与三角面片的碰撞检测

本文以方向层次包围盒（OBB）[12]和三角形对相交检测算法[13]为基础进行算法改进。

1.1 层次包围盒相交检测

层次包围盒一般分为AABB 包围盒、OBB 包围盒、球包围盒和K-DOP 包围盒等，如图1 所示，它们各有优缺点。

图1 4 种类型包围盒Fig. 1 Four types of bounding box

1) AABB 包围盒：构造简单，相交测试方法为通过3 个坐标轴上的最大值、最小值得到最大点与最小点后比较2 个包围盒的最大点与最小点是否有重合，算法简单、速度快，但由于紧密性较低，相交测试次数会更多。

2) OBB 包围盒：构造较复杂，是通过三角形顶点的均值与方差来计算最佳方向，计算量偏大，但紧密性较好，计算精度比AABB 更高，测试次数较少。具体方法为通过分离轴定理[12]，计算出15 条分离轴，比较2 个包围盒在每条分离轴上的投影是否重叠进行相交测试。

3) 球包围盒：构造简单，可根据AABB 或OBB包围盒直接求出外接球构造，但其紧密性最低，相交计算次数最多。通过直接比较2 个包围盒的球心距与半径和的关系即可判断是否相交，且不需转换坐标系。

4)K-DOP 包围盒：构造复杂，是根据K的值构造K/2 来对平行平面进行构造，紧密性最高，测试次数较少，但单次测试速度较慢，需找到合适的法向量个数以确保最佳速度。根据在2 个包围盒K/2 个方向上是否有重叠来判断是否相交。

1.2 三角面片相交检测

在CATIA 中存在许多轻量化模型，例如由.cgr等格式[14]转换而来的模型或由部分管道等复杂曲面表示、不含拓扑与特征的模型，同时，在CATIA中模型的可视化也是轻量化显示的。轻量化模型一般由多个曲面组成，而曲面则由成百上千个三角面片组成。如图2 所示，CATIA 中曲面的可视化均是由三角面片组成，并以此来统一不同格式的文件与不同类型的模型。为便于软件开发，做到适应不同类型的模型，选择三角面片相交对模型是否碰撞进行判断。

图2 模型的三角面片表示Fig. 2 The triangular patch representation of the model

2 个空间三角形相交检测的步骤如下：

1) 判断2 个三角形a，b所在平面是否平行，是则不相交，否则转到步骤2）。

2) 判断a的3 个顶点是否均在b所在平面的同侧，是则不相交，否则转到步骤3)。

3) 求出a与b所在平面的交线段l，判断l是否在b的内部或与b的边线相交，是则a与b相交，否则不相交。

1.3 模型的碰撞检测

结合OBB 相交测试与三角面片相交测试，即可得到模型的碰撞检测算法：

1) 根据两模型X，Y内部的三角形顶点，求出X与Y的OBB，记为A，B，并根据分离轴定理判断A与B是否相交。

2) 若A与B相交，则根据B内部三角形顶点坐标的加权值将B一分为二得到2 个子包围盒B1，B2，若A与B1相 交，则将B1一 分 为 二，否则，使A与B2进行相交检测。直到B的某子包围盒中只含1 个三角形时开始划分A。最后，当A的子包围盒中同样只有1 个三角形时进行三角形相交检测。

3) 若三角形相交，则模型碰撞，否则选取A，B的子包围盒中未进行相交检测的包围盒对进行检测，直到模型碰撞或包围盒对全部选完。

采用包围盒+三角面片进行碰撞检测具有如下优点：

1) 包围盒构造简单，计算速度快，当有大量零件时，亦可采用并行计算。

2) 与轻量化模型的三角面片化表示融洽度高，可直接读取。

3) 包围盒划分可重用，从而减少了划分次数。

2 基于层次包围盒−三角面片的空间碰撞和空间距离快速验证

在进行虚拟装配时，需要知道某部件附近的空间范围，从而判断零件是否合理；在进行虚拟维修时也需要知道被维修部件附近的空间距离，从而判断维修工具是否能够进入或者正常操作。考虑到实际需求，往往需要知道某零部件沿某方向移动一定距离的过程中，与该零部件碰撞的其他零件或该零部件与其他零件在该方向上的距离值，如果手动测量，效率会非常低。根据此需求，提出空间碰撞快速验证与空间距离快速验证算法，分别简称为碰撞验证与距离验证。

算法总体流程如图3 所示。流程分为3 部分：坐标系转换、碰撞验证与距离验证，前2 个部分是必需的，距离验证根据需求考虑是否应用。

2.1 坐标系转换

装配体由不同层次的子装配体组成，零件是最小的子装配体，称为最小子部件，在不同层次装配体中有不同的装配坐标系AxisAi（i为子装配体编号），零件在建模时有着自己的零件坐标系AxisPi（i为 零件编号）。AxisPi可以看作是特殊的AxisAi。

图3 总体流程Fig. 3 Overall process

给定一个部件的移动方向DM以及移动距离h， 以DM为z轴建立方向坐标系AxisDM。此时，存在2 种坐标系：AxisAi和AxisDM，不同坐标系间可通过坐标系转换矩阵转换。由于被研究部件会有一个移动方向并且此方向为任意方向，为便于计算，包围盒与三角面片的空间验证需在AxisDM下进行。以最外层装配体的坐标系为全局坐标系AxisA0，则 各AxisAi到AxisA0的 转 换矩 阵 为Ai，AxisDM到AxisA0的转换矩阵为D，AxisA0到AxisDM的 转 换 矩阵为D−1。 从AxisAi到AxisDM的转换矩阵为

左乘Ti可 将AxisAi下的点转换到AxisDM。

2.2 空间碰撞快速验证

碰撞验证分为2 个部分：层次包围盒空间验证和三角面片空间验证。通过2 步空间验证，可计算出所有会发生碰撞的最小零部件。当三角面片碰撞时，可判定2 个零件碰撞。

2.2.1 层次包围盒空间验证

考虑到AABB 与OBB 具有构造简单、相交检测计算较为容易的特点，本文采用AABB 和OBB 混合形式的包围盒。由于零件通常是按照轴向建模，所以在零件坐标系中采用AABB，其与零件坐标系下的OBB 紧密性基本一致。而在装配坐标系中零件可能会发生旋转，此时的AABB在装配坐标系下为OBB。不同层次的装配体在自身装配坐标系下均有一个AABB，如图4 所示。

图4 装配坐标系下的AABB 包围盒Fig. 4 AABB bounding box in assembly coordinate system

包围盒空间验证算法如图5 所示。图中：OBB为OBB 包围盒； ⊗的定义见式（4）。算法第1 步 需 要 在AxisDM中 将 选 定 部 件Pselect中 的OBB 先转换为AABB，称为AABBtrans，因为若以OBB 形式拉伸，拉伸的包围盒形状可能不是一个OBB，不便于相交检测，而AABB 沿z轴拉伸后依然为AABB。OBB 的8 个顶点记为Vi(i= 1，2，···，8)，则AABBtrans的最小 点Vmin与最大点Vmax分 别为：

图5 包围盒空间验证算法Fig. 5 Bounding box space verification algorithm

Vmin与Vmax的坐标值必定分别小于和大于该包围盒内所有三角形的顶点坐标。然后将AABBtrans拉 伸 后 得 到AABBstretch。拉 伸 方 法 为：在AxisDM中沿代表验证方向DM的z轴将AABBtrans的Vmax的z坐标增加验证距离h的值，即可将其拉伸为AABBstretch，拉伸效果如图6 所示。

图6 包围盒拉伸Fig. 6 Bounding box stretch

算法中存在栈ST，SS 与SC，其中ST 存放选定部件 中 的AABBtrans， SS 存放AABBtrans拉 伸后的 包围盒AABBstretch，SC 存放其他部件中的OBB。

算法中存在3 种包围盒，如表1 所示。部件包围盒不包含子部件时是内部包围盒，部件包围盒的子包围盒是部件包围盒、内部包围盒、叶子包围盒中的一种，子包围盒是内部包围盒或叶子包围盒时需要划分。内部包围盒的子包围盒是内部包围盒与叶子包围盒，子包围盒同样需要进行包围盒划分。叶子包围盒没有子包围盒。

表1 包围盒种类Table 1 Types of bounding box

划分子包围盒的方法有 2 种：

1) 其他部件的OBB划分。首先，选择划分基准轴：在AxisPk中，以该OBB对应的AABB 包含的三角形顶点在坐标轴上的跨度最大的轴为基准轴。然后，计算基准轴上所有三角形顶点坐标的算术平均值µ，三角形几何中心在基准轴上的坐标值比 µ大属于上包围盒，比 µ小属于下包围盒，从而将AABB 划分为上、下2 个子AABB，再转换到AxisDM中得到2 个子OBB。

2) 选定部件的AABBstretch划分。转换方法与1)中类似，不同之处在于，在划分为2 个子AABB后，将 其 转 换 为AxisDM中 的2 个 子AABBtrans，再 拉伸为2 个子AABBstretch。

表2 所示为不同部件各包围盒在AxisDM中的符号。表中，i为层数，第i层包围盒有0 个或多个i+1 层对应同类包围盒，第0 层部件包围盒为最大外层部件包围盒，第0 层内部包围盒为最小的部件包围盒。

表2 不同部件各包围盒在 AxisDM 中的符号Table 2 The symbol in A xisDM for each bounding box of different parts

定义 ⊗操作为2 个OBB利用分离轴定理进行相交检测，其运算过程如式（4）所示。

式中：OBB1和OBB2均 为OBB 包围 盒；ROBB为相交 检 测 结 果，ROBB= 1 代 表 相 交，ROBB=0 代 表 不 相交。包围盒空间验证算法的步骤如下：8) 若AABBstretch与OBB均是叶 子 包围盒，则进行三角面片空间验证。

2.2.2 三角面片空间验证

定义•操作为2 个三角面片的相交测试，其运算过程如式（5）所示。

式中：Tri1，Tri2为 三角 面 片；RTri=1 代 表 三 角 面片相交，RTri=0 代表不相交。具体算法在1.2 中已描述。

定义 ⊙操作为2 个三角面片的空间验证过程，记2 个三角面片的空间验证为

式 中：Tri1为AABBstretchLeaf中 的 三 角 面 片；Tri2为OBBotherLeaf中的三角面片；RTriSpace=1 代表三角面片相 交，RTriSpace=0 代 表 不 相 交。RTriSpace的 具 体 算 法如图7 所示。

图7 三角面片空间验证算法Fig. 7 Triangular patch space verification algorithm

图8 三角面片拉伸Fig. 8 Triangle stretch

2.3 空间距离快速验证

通过2.2 节给出的方法可计算出给定方向给定距离下所有会发生碰撞的最小零部件，记该集合为S。只要计算出S中每个最小零部件的碰撞距离，即可完成距离验证。

3 功能模块的设计、开发与案例验证

3.1 功能模块的设计与开发

功能模块的开发采用CATIA 的组件应用架构 (component application architecture，CAA)和C++语言对CATIA 进行二次开发，将算法编译为对应的动态链接库(.dll)并在CATIA 应用程序中调用实现。其主要功能包括输入信息、进行空间快速验证计算、输出结果，程序界面如图9 所示。

图9 空间快速验证模块Fig. 9 Space fast verification module

1） 输入信息。选择一个Product 类型的子部件作为研究对象，根产品下除该Product 以外的其他子部件均参与碰撞计算。选择一个面或一条直线确定验证方向，选择面则以面的外法向方向为验证方向，选择线则根据实际情况判断。当选定研究对象以及方向后会在模型中出现代表验证方向的红色箭头，可根据实际情况选择正向或反向。输入一个验证距离，单位为mm。

2） 空间快速验证计算。包括模型曲面顶点的读取、包围盒的划分、三角面片的生成、研究对象与其他子部件的包围盒空间验证以及三角面片的空间验证计算。

3） 输出结果。显示计算结果与研究对象在该方向、距离下发生碰撞的最小子部件以及碰撞的距离值，并在图形界面中高亮显示碰撞的最小子部件。

3.2 实例验证与分析

实例测试在一台笔记本电脑上进行，该机的CPU 为I7-4710MQ，显卡为GTX 850M D5。以一个最小子部件−储气罐为研究对象，验证方向为图9 中红色箭头所指方向，验证距离为5 000 mm，内置计算精度为0.5 mm。根产品中一共有2 100个最小子装配体，最大装配体层数为6 层，如图10所示。计算结果为一共有78 个最小子装配体与研究对象碰撞；在包围盒未划分时空间碰撞验证计算所需时间共为0.058 s，平均每个最小子装配体耗时为0.000 028 s，空间距离验证耗时0.534 s，平均每个最小子装配体耗时为0.006 8 s；在包围盒已划分后验证计算时间减少为0.014 s，平均每个最小子装配体耗时为0.000 007 s，空间距离验证耗时为0.518 s，平均每个最小子装配体耗时为0.006 6 s。

图10 实例验证Fig. 10 Example verification

从计算结果来看，在未划分包围盒时计算时间很短，平均每个零件的计算时间在纳秒级，在划分完包围盒后，平均空间碰撞验证时间约缩短了75.9%，平均空间距离验证时间缩短了2.9%。在不需要考虑距离时结果几乎是瞬间计算完成，在需要考虑距离时速度会较慢，这主要由碰撞部件的个数决定，在碰撞部件较少时也能在几秒之内完成，能够提高验证速度。

可以看出，计算单个距离的时间是计算单个碰撞时间的243 倍，距离的计算速度较碰撞慢。后续改进方式可针对包围盒的形式、三角面片拉伸后的相交算法以及距离验证算法进行改进。例如，在进行距离验证时，由于每个碰撞最小子产品的距离计算是独立的并且共享研究对象的数据，故可对每个碰撞最小子产品利用GPU 并行计算距离，以缩短计算时间。

4 结 语

本文以提高虚拟装配、虚拟维修效率为目标，利用层次包围盒和三角面片碰撞算法，提出了一种在虚拟模型中对模型进行空间快速验证的算法；在CATIA 中开发出了对应的可直接使用的功能模块，并对较复杂模型的空间碰撞、距离验证进行了实例验证与分析。本文所做工作在工程应用中具有一定的使用价值。