Volume 16 Issue 2
Apr.  2021
Turn off MathJax
Article Contents

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 doi: 10.19693/j.issn.1673-3185.01906
Citation: 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 doi: 10.19693/j.issn.1673-3185.01906

Fast verification of space based on hierarchical bounding boxes in virtual assembly

doi: 10.19693/j.issn.1673-3185.01906
  • Received Date: 2020-03-22
  • Rev Recd Date: 2020-06-05
  • Available Online: 2021-03-16
  • Publish Date: 2021-04-01
  •   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 of the algorithm.   Results   The examples show that in models of different levels of complexity with more than 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.
  • [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. doi: 10.1007/s11804-011-1090-1
    [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. doi: 10.1108/AA-03-2013-023
    [5] LIU M T, GAI M, LAI S N. Simulating unmanned aerial vehicle flight control and collision detection[J]. Visual Computing for Industry, Biomedicine, and Art, 2019, 2(1): 1–7. doi: 10.1186/s42492-019-0012-y
    [6] QI B B, PANG M Y. An enhanced sweep and prune algorithm for multi-body continuous collision detection[J]. The Visual Computer, 2019, 35(11): 1503–1515. doi: 10.1007/s00371-019-01718-2
    [7] 王达鹏, 罗显光, 闭业宾, 等. 分布式碰撞检测在装配仿真中的应用[J]. 机械科学与技术, 2015, 34(9): 1394–1398.

    WANG D P, LUO X G, BI Y B, et al. Application of distributed collision detection in assembly simulation[J]. Mechanical Science and Technology for Aerospace Engineering, 2015, 34(9): 1394–1398 (in Chinese).
    [8] 李普. 虚拟装配中基于分离距离的快速碰撞检测算法研究[D]. 大连: 大连海事大学, 2018.

    LI P. Research on fast collision detection algorithm based on separation distance in virtual asssembly[D]. Dalian: Dalian Maritime University, 2018 (in Chinese).
    [9] 李普, 孙长乐, 熊伟, 等. 一种基于半透明颜色叠加与深度值的碰撞检测算法[J]. 计算机科学, 2018, 45(增刊 1): 193–197, 233.

    LI P, SUN C L, XIONG W, et al. Collision detection algorithm based on semi-transparent color overlay and depth value[J]. Computer Science, 2018, 45(Supp 1): 193–197, 233 (in Chinese).
    [10] 杜群. 基于蚁群算法的碰撞检测在虚拟装配中的应用[D]. 北京: 华北电力大学, 2019.

    DU Q. Application of collision detection based on ant colony algorithm in virtual assembly[D]. Beijing: North China Electric Power University, 2019 (in Chinese).
    [11] 卢江, 钱德英, 周伟中, 等. 基于观察坐标与混合包围盒的装配碰撞检测方法[J]. 船舶工程, 2019, 41(9): 12–16, 51.

    LU J, QIAN D Y, ZHOU W Z, et al. Assembly collision detection method based on observation coordinates and hybrid bounding box[J]. Ship Engineering, 2019, 41(9): 12–16, 51 (in Chinese).
    [12] GOTTSCHALK S, LIN M C, MANOCHA D. OBBTree: a hierarchical structure for rapid interference detection[C]//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New Orleans, LA, USA: ACM, 1996.
    [13] HELD M. ERIT—a collection of efficient and reliable intersection tests[J]. Journal of Graphics Tools, 1997, 2(4): 25–44. doi: 10.1080/10867651.1997.10487482
    [14] 田富君, 张红旗, 张祥祥, 等. 基于轻量化模型的三维装配工艺文件生成技术[J]. 制造业自动化, 2013, 35(10): 46–50.

    TIAN F J, ZHANG H Q, ZHANG X X, et al. Three-dimensional assembly process file generate technology based on lightweight model[J]. Manufacturing Automation, 2013, 35(10): 46–50 (in Chinese).
  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(10)  / Tables(2)

Article Metrics

Article views(17) PDF downloads(2) Cited by()

Proportional views
Related

Fast verification of space based on hierarchical bounding boxes in virtual assembly

doi: 10.19693/j.issn.1673-3185.01906

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 of the algorithm.   Results   The examples show that in models of different levels of complexity with more than 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.

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

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

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

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

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

      Figure 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个方向上是否有重叠来判断是否相交。

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

      Figure 2.  The triangular patch representation of the model

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

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

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

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

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

      1) 根据两模型XY内部的三角形顶点,求出XY的OBB,记为AB,并根据分离轴定理判断AB是否相交。

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

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

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

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

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

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

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

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

      Figure 3.  Overall process

    • 装配体由不同层次的子装配体组成,零件是最小的子装配体,称为最小子部件,在不同层次装配体中有不同的装配坐标系$Axi{s_{{A_i}}}$$i$为子装配体编号),零件在建模时有着自己的零件坐标系$Axi{s_{{P_i}}}$$i$为零件编号)。$Axi{s_{{P_i}}}$可以看作是特殊的$Axi{s_{{A_i}}}$

      给定一个部件的移动方向$D_{\rm{M}}$以及移动距离$h$,以$D_{\rm{M}}$z轴建立方向坐标系$Axi{s_{D_{\rm{M}}}}$。此时,存在2种坐标系:$Axi{s_{{A_i}}}$$Axi{s_{D_{\rm{M}}}}$,不同坐标系间可通过坐标系转换矩阵转换。由于被研究部件会有一个移动方向并且此方向为任意方向,为便于计算,包围盒与三角面片的空间验证需在$Axi{s_{D_{\rm{M}}}}$下进行。以最外层装配体的坐标系为全局坐标系$Axi{s_{{A_0}}}$,则各$Axi{s_{{A_i}}}$$Axi{s_{{A_0}}}$的转换矩阵为${{\mathit{\boldsymbol{A}}}_i}$$Axi{s_{D_{\rm{M}}}}$$Axi{s_{{A_0}}}$的转换矩阵为${\mathit{\boldsymbol{D}}}$$Axi{s_{{A_0}}}$$Axi{s_{D_{\rm{M}}}}$的转换矩阵为${{\mathit{\boldsymbol{D}}}^{ - 1}}$。从$Axi{s_{{A_i}}}$$Axi{s_{D_{\rm{M}}}}$的转换矩阵为

      $${{\mathit{\boldsymbol{T}}}_i} = {{\mathit{\boldsymbol{D}}}^{ - 1}}{{\mathit{\boldsymbol{A}}}_i}$$ (1)

      左乘${{\mathit{\boldsymbol{T}}}_i}$可将$Axi{s_{{A_i}}}$下的点转换到$Axi{s_{D_{\rm{M}}}}$

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

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

      Figure 4.  AABB bounding box in assembly coordinate system

      包围盒空间验证算法如图5所示。图中:OBB为OBB包围盒;$\otimes $的定义见式(4)。算法第1步需要在$Axi{s_{D_{\rm{M}}}}$中将选定部件${P_{{\rm{select}}}}$中的OBB先转换为AABB,称为$AAB{B_{{\rm{trans}}}}$,因为若以OBB形式拉伸,拉伸的包围盒形状可能不是一个OBB,不便于相交检测,而AABB沿z轴拉伸后依然为AABB。OBB的8个顶点记为${V_i}$($i$=1,2,···,8),则$AAB{B_{{\rm{trans}}}}$的最小点${V_{\min }}$与最大点${V_{\max }}$分别为:

      Figure 5.  Bounding box space verification algorithm

      $$\begin{split} & {V_{\min }} = ( \min ({V_i}.x),\;\min ({V_i}.y),\; \min ({V_i}.{\textit{z}}) ), \\&\qquad\quad\; i = 1,\;2,\cdots,8 \end{split}$$ (2)
      $$\begin{split} & {V_{\max }} = ( \max ({V_i}.x),\;\max ({V_i}.y),\; \max ({V_i}.{\textit{z}}) ),\\&\qquad\quad\; i = 1,\;2,\cdots,8 \end{split}$$ (3)

      ${V_{\min }}$${V_{\max }}$的坐标值必定分别小于和大于该包围盒内所有三角形的顶点坐标。然后将$AAB{B_{{\rm{trans}}}}$拉伸后得到$AAB{B_{{\rm{stretch}}}}$。拉伸方法为:在$Axi{s_{{{D_{\rm{M}}}}}}$中沿代表验证方向$D_{\rm{M}}$z轴将$AAB{B_{{\rm{trans}}}}$${V_{\max }}$z坐标增加验证距离$h$的值,即可将其拉伸为$AAB{B_{{\rm{stretch}}}}$,拉伸效果如图6所示。

      Figure 6.  Bounding box stretch

      算法中存在栈ST,SS与SC,其中ST存放选定部件中的$AAB{B_{{\rm{trans}}}}$,SS存放$AAB{B_{{\rm{trans}}}}$拉伸后的包围盒$AAB{B_{{\rm{stretch}}}}$,SC存放其他部件中的OBB

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

      种类说 明
      部件包围盒子部件的包围盒
      内部包围盒不包含子部件且包含超过1个三角面片的包围盒
      叶子包围盒只包含1个三角面片的非部件包围盒

      Table 1.  Types of bounding box

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

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

      2) 选定部件的$AAB{B_{{\rm{stretch}}}}$划分。转换方法与1)中类似,不同之处在于,在划分为2个子AABB后,将其转换为$Axi{s_{{\rm{D_{\rm{M}}}}}}$中的2个子$AAB{B_{{\rm{trans}}}}$,再拉伸为2个子$AAB{B_{{\rm{stretch}}}}$

      表2所示为不同部件各包围盒在$Axi{s_{D_{\rm{M}}}}$中的符号。表中,i为层数,第i层包围盒有0个或多个i+1层对应同类包围盒,第0层部件包围盒为最大外层部件包围盒,第0层内部包围盒为最小的部件包围盒。

      产品符 号
      部件包围盒内部包围盒叶子包围盒
      选定部件$AABB_{{\rm{stretch}}}^i$$AABB_{{\rm{stretchInside}}}^i$$AAB{B_{{\rm{stretchLeaf}}}}$
      其他部件$OBB_{{\rm{other}}}^i$$OBB_{{\rm{otherInside}}}^i$$OB{B_{{\rm{otherLeaf}}}}$

      Table 2.  The symbol in $Axi{s_{{{D_{\rm{M}}}}}}$ for each bounding box of different parts

      定义$ \otimes $操作为2个OBB利用分离轴定理进行相交检测,其运算过程如式(4)所示。

      $${R_{{OBB}}} = OB{B_1} \otimes OB{B_2}$$ (4)

      式中:OBB1OBB2均为OBB包围盒;${R_{{OBB}}}$为相交检测结果,${R_{{OBB}}}$=1代表相交,${R_{{OBB}}}$=0代表不相交。包围盒空间验证算法的步骤如下:

      1) 将$AAB{B}_{{\rm{stretch}}}^0$$OB{B}_{{\rm{other}}}^0$分别推入栈SS与栈SC中。

      2) 若SC中无元素,则2个部件不发生碰撞;若SC中有元素,则分别从SS与SC中弹出栈顶元素$AAB{B_{{\rm{stretch}}}}$$OBB$进行$AAB{B_{{\rm{stretch}}}} \otimes OBB$计算。根据不同的计算结果,分别转步骤3)~步骤8)。

      3) 若计算结果为0,将$AAB{B_{{\rm{stretch}}}}$重新推入SS,回到步骤2)。

      4) 若计算结果为1,同时$OBB$$OBB_{{\rm{other}}}^k$(其中k为某层数)且包含$OBB_{{\rm{other}}}^{k{\rm{ + }}1}$,则将$AAB{B_{{\rm{stretch}}}}$与全部$OBB_{{\rm{other}}}^{k{\rm{ + }}1}$分别推入SS与SC中,回到步骤2)。

      5) 若计算结果为1同时$OBB$$OBB_{{\rm{otherInside}}}^k$,则将$AAB{B_{{\rm{stretch}}}}$重新推入SS,同时将$OBB_{{\rm{otherInside}}}^k$划分为2个子包围盒$OBB_{{\rm{otherInside}}}^{k{\rm{ + 1}}}$$OB{B_{{\rm{otherLeaf}}}}$,然后将2个子包围盒推入SC,回到步骤2)。

      6) 若计算结果为1同时$OBB$$OB{B_{{\rm{otherLeaf}}}}$$AAB{B_{{\rm{stretch}}}}$是一个$AABB_{{\rm{stretchInside}}}^k$且包含$AABB_{{\rm{stretchInside}}}^{k + 1}$,则将全部$AABB_{{\rm{stretchInside}}}^{k + 1}$$OBB$分别推入SS与SC中,回到步骤2)。

      7) 若计算结果为1同时$OBB$$OB{B_{{\rm{otherLeaf}}}}$$AAB{B_{{\rm{stretch}}}}$$AABB_{{\rm{stretchInside}}}^k$,则将$OBB$重新推入SC,同时划分$AABB_{{\rm{stretchInside}}}^k$为2个子包围盒$AABB_{{\rm{stretchInside}}}^{k{\rm{ + 1}}}$$OB{B_{{\rm{otherLeaf}}}}$,然后将2个子包围盒推入SS,回到步骤2)。

      8) 若$AAB{B_{{\rm{stretch}}}}$$OBB$均是叶子包围盒,则进行三角面片空间验证。

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

      $${R_{Tri}} = Tr{i_1} \bullet Tr{i_2}$$ (5)

      式中:$Tr{i_1}$$Tr{i_2}$为三角面片;${R_{Tri}}$=1代表三角面片相交,${R_{Tri}}$=0代表不相交。具体算法在1.2中已描述。

      定义$ \odot $操作为2个三角面片的空间验证过程,记2个三角面片的空间验证为

      $${R_{Tri{\rm{Space}}}} = Tr{i_1} \odot Tr{i_2}$$ (6)

      式中:$Tr{i_1}$$AAB{B}_{{\rm{stretchLeaf}}}$中的三角面片;$Tr{i_2}$$OB{B_{{\rm{otherLeaf}}}}$中的三角面片;${R_{Tri{\rm{Space}}}}$=1代表三角面片相交,${R_{Tri{\rm{Space}}}}$=0代表不相交。${R_{Tri{\rm{Space}}}}$的具体算法如图7所示。

      Figure 7.  Triangular patch space verification algorithm

      $Axi{s_{D_{\rm{M}}}}$中将$Tr{i_1}$的3个顶点的z坐标增大$h$后得到$Tr{i}_1^2$,以$Tr{i_1}$$Tr{i}_1^2$为两底面构造出三棱柱$Pri$,其3个侧面均为平行四边形,可分别构造出2个三角面片,加上2个底面共8个三角面片$Tr{i}_1^i$$i = 1,2,\cdots,8$),如图8所示。判断是否存在$k$使得$Tr{i}_1^k \bullet Tr{i_2}$=1,若存在则空间验证为碰撞,若不存在可能是未碰撞或$Tr{i_2}$$Pri$内部。

      Figure 8.  Triangle stretch

      判断$Tr{i_2}$$Pri$内部的方法为:在$Axi{s_{D_{\rm{M}}}}$中过$Tr{i_2}$的3个顶点并且平行于z轴的3条直线与${Tri}_1^1$$Tr{i}_1^2$的交点分别为$Point_j^1$$Point_j^2$$j = 1,2,3$),$Point_j^1$都在$Tr{i}_1^1$内部,同时$Tr{i_2}$的3个顶点的z坐标分别不小于$Point_j^1$z坐标并且不大于$Point _j^2$z坐标。若$Tr{i_2}$不在$Pri$内部,则可判定为未碰撞。

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

      采用二分法与递进法配合来计算碰撞距离。从$S$中取出一零部件$X$,计算$X$的OBB,记为$OB{B_X}$,在$Axi{s_{{{D_{\rm{M}}}}}}$下的最大、最小z坐标记为${{\textit{z}}_{\max }}$${{\textit{z}}_{\min }}$。若${{\textit{z}}_{\min }} > {V_{\min }}.{\textit{z}}$,则以${{\textit{z}}_{\min }}$$X$的最小估计碰撞坐标${{\textit{z}}_{\min }'}$,否则${{\textit{z}}_{\min }'} = {V_{\min }}.{\textit{z}}$;若${{\textit{z}}_{\max }} < {V_{\max }}.{\textit{z}}$,则以${{\textit{z}}_{\max }}$$X$的最大估计碰撞坐标${{\textit{z}}}_{\max }'$,否则${{\textit{z}}_{\max }'} = {V_{\max }}.{\textit{z}}$。将$AAB{B}_{{\rm{select}}}^0$拉升至$({{\textit{z}}_{\min }'} + {z_{\max }'})/2$得到${B_2'}$,若${B_2'} \otimes OB{B_X} = 1$,则${{\textit{z}}_{\max }'}{\rm{ = }}({{\textit{z}}_{\min } '}+ {{\textit{z}}_{\max }'})/2$,否则${{\textit{z}}_{\min }'}{\rm{ = }}({{\textit{z}}_{\min }'} + {{\textit{z}}_{\max }'})/2$。再将$AAB{B}_{{\rm{select}}}^0$拉升至$({{\textit{z}}_{\min } '}+ {{\textit{z}}_{\max }'})/2$进行${R_{OBB}}$测试,直到${{\textit{z}}_{\max }'} - {{\textit{z}}_{\min }'} < \varepsilon$($\varepsilon $为给定的精度)时以$({{\textit{z}}_{\min }'} + {{\textit{z}}_{\max }'})/2$作为碰撞距离。

      上述为纯二分法计算,在$Tr{i_1} \odot Tr{i_2}$中最多会进行8次$Tr{i_1} \bullet Tr{i_2}$运算以及1次判定$Tr{i_2}$是否在$Pri$内部的计算,最少会进行1次$Tr{i_1} \bullet Tr{i_2}$运算。所以平均每次$Tr{i_1} \odot Tr{i_2}$会进行5次$Tr{i_1} \bullet Tr{i_2}$运算,故在${{\textit{z}}_{\max }'} - {{\textit{z}}_{\min }'} < (k*\varepsilon )$($k$为系数)时仍采用二分法,计算次数会比按递进法(每次$AAB{B}_{{\rm{select}}}^0$$+ {\textit{z}}$方向移动$\varepsilon $)更多。$k$可由函数(式(7))求极大值计算出。

      $$f(x) = 5*{\log _2}k - k$$ (7)

      最终求得$k$=7.2。

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

      Figure 9.  Space fast verification module

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

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

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

    • 实例测试在一台笔记本电脑上进行,该机的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。

      Figure 10.  Example verification

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

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

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

Reference (14)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return