Chinese Journal of Ship Research
虚拟装配中基于层次包围盒的空间快速验证
引用格式：方舟,易朋兴,杜玉娇, 等.虚拟装配中基于层次包围盒的空间快速验证[J]. 中国舰船研究, 2021, 16(2): 64–70, 77. FANG Z, YI P X, DU Y J, et al. Fast verification of space based on hierarchical bounding boxes in virtual assembly[J]. Chinese Journal of Ship Research, 2021, 16(2): 64–70, 77.
方舟1，易朋兴*1，杜玉娇2，李阳1 1华中科技大学机械科学与工程学院，湖北武汉 430074 2武汉第二船舶设计研究所，湖北武汉 430205
摘 要: ［目的］ 针对现有虚拟装配与维修中可移动空间计算的算法精度、效率较低，甚至缺少算法的问题，结合舰船虚拟装配、维修的实际需求，提出一种能够快速、准确计算零部件在移动空间中碰撞验证的算法。［方法］ 首先，以层次包围盒与三角面片相交检测算法为基础，改进层次包围盒与三角面片在移动空间中进行变换的方法；然后，根据二分法与递增法求得干涉距离，提出一种空间碰撞验证与空间距离验证的算法；最后，利用 CATIA二次开发技术设计并开发空间快速验证模块，验证算法的合理性与准确性。［结果］实例结果表明，在复杂程度不同的2 000多个零件模型中，计算空间碰撞的时间在100 ms以内，计算空间距离的时间约为 0.5 s。 ［结论］ 该算法在舰船设计人员考虑装配与维修空间时可起到较大的辅助作用，能够有效缩短舰船设计周期、生产周期与维护周期。
关键词：虚拟装配；碰撞检测；移动空间；空间快速验证；层次包围盒；CATIA二次开发
中图分类号: U662.3 文献标志码:A DOI：10.19693/j.issn.1673-3185.01906
Fast verification of space based on hierarchical bounding boxes in virtual assembly
FANG Zhou1, YI Pengxing*1, DU Yujiao2, LI Yang1
1 School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China 2 Wuhan Second Ship Design and Research Institute, Wuhan 430205, China
Abstract: ［Objectives ］ Aiming at problems such as low accuracy, low efficiency and even a lack of algorithms in the calculation of moving spaces in existing virtual assembly and maintenance, and combined with the actual needs of the virtual assembly and maintenance of the ship, this paper puts forward a method for quickly and accurately calculating parts in a moving space for the purpose of spatial collision verification. ［Methods ］ Based on the intersection detection algorithm of a hierarchical bounding box and triangular patches, we improve the transformation method of the box and triangular patches in a moving space, then obtain the interference distance according to the method of dichotomy and increment, thus proposing an algorithm for spatial collision verification and distance verification. Finally, CATIA secondary development technology is used to design and develop a rapid space verification module that can verify the rationality and accuracy ofthealgorithm.［Results］Theexamplesshowthatinmodelsofdifferentlevelsofcomplexitywithmorethan 2 000 parts, the calculation time of spatial collision is less than 100 ms and that of spatial distance is about 0.5 s. ［Conclusions］This algorithm can have a significant auxiliary effect on the design of ships when designers consider assembly and maintenance space, thus effectively reducing the ship design cycle, production cycle and maintenance cycle. Key words: virtual assembly； collision detection； moving space； rapid space verification；hierarchical bounding box；secondary development of CATIA
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个空间三角形相交检测的步骤如下： 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。给定一个部件的移动方向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所示。
包围盒空间验证算法如图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分别为：
Vmin与Vmax的坐标值必定分别小于和大于该包围盒内所有三角形的顶点坐标。然后将AABBtrans拉伸后得到AABBstretch。拉伸方法为：在AxisDM中沿代表验证方向DM的 z 轴将AABBtrans的Vmax的z坐标增加验证距离h的值，即可将其拉伸为AABBstretch ，拉伸效果如图6所示。
算法中存在栈ST，SS 与 SC，其中 ST 存放选定部件中的AABBtrans，SS 存放AABBtrans拉伸后的包围盒AABBstretch ，SC存放其他部件中的OBB。算法中存在3 种包围盒，如表1 所示。部件包围盒不包含子部件时是内部包围盒，部件包围盒的子包围盒是部件包围盒、内部包围盒、叶子包围盒中的一种，子包围盒是内部包围盒或叶子包围盒时需要划分。内部包围盒的子包围盒是内部包围盒与叶子包围盒，子包围盒同样需要进行包围盒划分。叶子包围盒没有子包围盒。
划分子包围盒的方法有 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 个 OBB利用分离轴定理进行相交检测，其运算过程如式（4）所示。
式中： OBB1 和 OBB2 均为OBB 包围盒； ROBB为相交检测结果， ROBB=1 代表相交， ROBB=0 代表不相交。包围盒空间验证算法的步骤如下： 1) 将AABB0 与OBB0 分别推入栈SS 与栈stretch other SC 中。2) 若 SC 中无元素，则2 个部件不发生碰撞；若 SC 中有元素，则分别从SS 与 SC 中弹出栈顶元素 AABBstretch与OBB进行 AABBstretch ⊗ OBB计算。根据不同的计算结果，分别转步骤3)~步骤 8)。3) 若计算结果为0 ，将AABBstretch重新推入 SS，回到步骤2)。4) 若计算结果为1，同时OBB是OBBother k （其中k 为某层数）且包含OBBother k+1 ，则将AABBstretch与全部OBBk+1 分别推入SS 与 SC中，回到步骤2)。other 5) 若计算结果为1 同时OBB是OBBotherInside，则k将 AABBstretch重新推入SS ，同时将OBBotherInside k 划分为 2 个子包围盒OBBotherInside k+1 或 OBBotherLeaf ，然后将2个子包围盒推入SC，回到步骤 2)。6) 若计算结果为1 同时OBB是 OBBotherLeaf ， AABBstretch是一个AABBk 且包含AABBk+1 stretchInside， stretchInside则将全部 AABBstretchInside k+1 与OBB分别推入SS 与 SC中，回到步骤2)。7) 若计算结果为1 同时OBB是 OBBotherLeaf ， AABBstretch是AABBk ，则将OBB重新推入SC， stretchInside同时划分AABBstretchInside k 为 2个子包围盒AABBk+1 stretchInside或OBBotherLeaf ，然后将 2个子包围盒推入 SS，回到步骤 2)。8) 若AABBstretch与OBB均是叶子包围盒，则进
行三角面片空间验证。
2.2.2 三角面片空间验证
定义•操作为2个三角面片的相交测试，其运算过程如式（5）所示。
式中：T ri ， T ri 为三角面片； RTri =1代表三角面片1 2相交， RTri =0代表不相交。具体算法在1.2中已描述。定义⊙操作为2个三角面片的空间验证过程，记 2个三角面片的空间验证为
式中： T ri 1为 AABBstretchLeaf中的三角面片； Tri 2为OBBotherLeaf中的三角面片； RTri =1代表三角面片Space相交， RTri =0代表不相交。RTri 的具体算法Space Space如图7所示。
在 AxisDM中将T ri 1的 3 个顶点的z 坐标增大h后得到Tri 2 ，以T ri 1和Tri 2为两底面构造出三棱柱1 1 Pri ，其 3个侧面均为平行四边形，可分别构造出2个三角面片，加上2 个底面共8 个三角面片Tri i （ i = 1, 2, ··· , 8 ），如图 8 所示。判断是否存在1 k使得Tri k • Tri =1，若存在则空间验证为碰撞，若1 2不存在可能是未碰撞或T ri 在Pri内部。2
判断T ri 在Pri内部的方法为：在AxisDM中过2 T ri 的 3 个顶点并且平行于z 轴的3 条直线与2 Tri 1与T ri 2的交点分别为Point 1， Point 2（ j = 1 , 2 , 3 ）， 1 1 j j Point 1都在Tri 1内部，同时Tri 的 3个顶点的z 坐标j 1 2分别不小于Point 1的 z 坐标并且不大于Point2 j的j z 坐标。若Tri 不在Pri内部，则可判定为未碰撞。2
2.3 空间距离快速验证
通过 2.2节给出的方法可计算出给定方向给定距离下所有会发生碰撞的最小零部件，记该集合为S。只要计算出S中每个最小零部件的碰撞距离，即可完成距离验证。采用二分法与递进法配合来计算碰撞距离。从S中取出一零部件X，计算X的 OBB，记为OBBX，在AxisDM下的最大、最小z 坐标记为zmax ， zmin。若zmin > Vmin .z，则以zmin为X的最小估计碰撞坐标z ′ ， min否则z ′ = Vmin .z ；若zmax < Vmax .z ，则以zmax为X的最min大估计碰撞坐标z ′ ，否则z ′ = Vmax .z。将AABB0 max max select拉升至( z ′ + z ′ )/2得到B ′ ，若B ′ ⊗ OBBX = 1 ，则min max 2 2 z ′ =( z ′ + z ′ )/2 ，否则z ′ =( z ′ + z ′ )/2。再将max min max min min max AABB0 拉升至( z ′ + z ′ )/2进行ROBB测试，直到select min max z ′ − z ′ <ε (ε为给定的精度) 时以( z ′ + z ′ )/2作max min min max为碰撞距离。
上述为纯二分法计算，在Tri ⊙ T ri 2中最多会1
进行8 次Tri • T ri 运算以及1 次判定Tri 是否在1 2 2 Pri内部的计算，最少会进行1 次T ri • T ri 运算。1 2所以平均每次Tri ⊙ T ri 会进行5 次 T ri • Tri2 1 2 1运算，故在z ′ − z ′ < (k ∗ ε)(k为系数) 时仍采用二max min分法，计算次数会比按递进法(每次AABB0 往select +z方向移动ε) 更多。k可由函数（式（7））求极大值计算出。
3 功能模块的设计、开发与案例验证3.1 功能模块的设计与开发
功能模块的开发采用CATIA 的组件应用架构 (component application architecture，CAA) 和C++语言对 CATIA 进行二次开发，将算法编译为对应的动态链接库 (.dll) 并在 CATIA 应用程序中调用实现。其主要功能包括输入信息、进行空间快速验证计算、输出结果，程序界面如图9所示。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。
从计算结果来看，在未划分包围盒时计算时间很短，平均每个零件的计算时间在纳秒级，在划分完包围盒后，平均空间碰撞验证时间约缩短了 75.9% ，平均空间距离验证时间缩短了2.9%。在不需要考虑距离时结果几乎是瞬间计算完成，在需要考虑距离时速度会较慢，这主要由碰撞部件的个数决定，在碰撞部件较少时也能在几秒之内完成，能够提高验证速度。可以看出，计算单个距离的时间是计算单个碰撞时间的243 倍，距离的计算速度较碰撞慢。后续改进方式可针对包围盒的形式、三角面片拉伸后的相交算法以及距离验证算法进行改进。例如，在进行距离验证时，由于每个碰撞最小子产品的距离计算是独立的并且共享研究对象的数据，故可对每个碰撞最小子产品利用GPU 并行计算距离，以缩短计算时间。
4 结 语
本文以提高虚拟装配、虚拟维修效率为目标，利用层次包围盒和三角面片碰撞算法，提出了一种在虚拟模型中对模型进行空间快速验证的算法；在 CATIA中开发出了对应的可直接使用的功能模块，并对较复杂模型的空间碰撞、距离验证进行了实例验证与分析。本文所做工作在工程应用中具有一定的使用价值。
参考文献：
[1] YUAN H, ZHAO Y, YAN J. Research on an integrated modeling method of virtual ship assembly[J]. Journal of Marine Science and Application, 2011, 10(4): 447–455. [2] CUILING LI. Research on knowledge discovery system for ship virtual assembly[C]//Proceedings of 2010 the 3rd International Conference on Power Electronics and Intelligent Transportation System. Shenzhen: Intelligent Information Technology Application Research Association, 2013, 3: 470-473. [3] 潘仁宇, 孙长乐, 熊伟, 等.虚拟装配环境中碰撞检测算法的研究综述与展望 [J]. 计算机科学, 2016, 43(增刊 2): 136–139. PAN R Y, SUN C L, XIONG W, et al. Survey and prospect of collision detection based on virtual assembly environment[J]. Computer Science, 2016, 43(Supp 2): 136–139 (in Chinese). [4] GONZALEZ-BADILLO G, MEDELLIN-CASTILLO H, LIM T, et al. The development of a physics and constraint-based haptic virtual assembly system[J]. Assembly Automation, 2014, 34(1): 41–55.