虛擬裝配中基于層次包圍盒的空間快速驗證

方舟，易朋興*，杜玉嬌，李陽

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 中開發出了對應的可直接使用的功能模塊，并對較復雜模型的空間碰撞、距離驗證進行了實例驗證與分析。本文所做工作在工程應用中具有一定的使用價值。