基于OBB-SAT 算法的雙五軸加工路徑碰撞檢測方法

孔 森，張立強，李宇昊

（1.上海工程技術大學 機械與汽車工程學院，上海 201620；2.上海拓璞數控科技股份有限公司，上海 201111）

0 引言

隨著航空航天事業的快速發展，鏡像銑加工設備成為了航空航天大型薄壁件成型制造技術最新的發展方向之一。雙五軸鏡像銑用來加工航天飛機，以及衛星上大型的蒙皮和壁板，因此如何實現加工的高效、穩定和精確是目前的研究熱點。相較于普通五軸機床，鏡像銑機床多出一個五軸支撐裝置，雙五軸的協調同步運動是工件加工的基礎，所以支撐端與銑削端的接觸碰撞是不可避免的。

在大量碰撞檢測算法中，包圍盒算法是最常用的一種算法，其包含AABB 包圍盒、OBB 包圍盒、包圍球、K-DOP包圍盒等［1-4］。如何方便、快速、有效地進行干涉性判斷是影響系統效率的一個關鍵因素［5］，因此許多學者對包圍盒算法進行了深入研究。如王立文等［6］提出一種改進的AABB 包圍盒碰撞檢測算法，提高了碰撞檢測速度，并得到更詳細的碰撞檢測信息；尹艷艷等［7］提出一種基于OBB 的矩形碰撞檢測算法，對機器臂進行空間建模與碰撞檢測，以實現機器臂的碰撞預警與安全停機；唐勇等［8］提出一種改進的軸向包圍盒碰撞檢測算法，通過壓縮儲存對AABB包圍盒進行改進，提高了AABB 包圍盒的緊密性；唐源皓等［9］提出基于質點轉換的混合碰撞檢測算法，把物體最外層OBB 包圍盒當作三維空間中的點，計算兩點之間的距離，從而提高了碰撞檢測效率；陳秋菊［10］提出虛擬現實中的包圍盒碰撞檢測算法，分析并描述了基于包圍球和有向包圍盒的混合層次包圍盒碰撞檢測算法的優點及構建方法，實現了實時、高精度的連續碰撞檢測；陳志華等［11］提出一種將包圍球模型與GJK 算法相結合的算法，實現了鏡像銑的快速碰撞檢測；李玉虎等［12］提出一種混合層次包圍盒碰撞算法，引入了形心概念，并改進包圍盒的樹形結構，使算法精度和效率得到一定程度提升；趙鑫［13］將傳統粒子群算法融入到碰撞檢測中，以OBB 包圍盒為特征對象，實現了對復雜剛體的碰撞檢測；趙偉等［14］提出一種快速的基于球體混合重建的碰撞檢測算法，將從線性到球形混合的構造變換方法進行擴展，實現了快速碰撞檢測；譚睿璞等［15］提出一種快速的可變形物體碰撞檢測算法，采用多線程技術，在多核設備上實現了并行碰撞檢測算法；孫殿柱等［16］提出一種將遺傳算法與O·Rourke 算法相融合的最小包圍盒求解算法，實現了對離散點云數據包圍盒的快速求解；胡志剛等［17］通過枚舉凸包中邊的所有可能組合，唯一確定包圍盒的最優方向，實現了包圍盒的緊密構造；張琪等［18］提出一種基于三角片分割的改進包圍盒樹構造方法，通過控制三角片分割粒度和葉子節點包圍盒中的三角片個數，驗證了算法的有效性；孫敬榮等［19］提出基于混合包圍盒的碰撞檢測優化算法，構造新的計算坐標系，對空間幾何三角形進行投影降維，在二維平面上解決空間問題，從而大大提升了計算速度；于瑞云等［20］提出結合軸對齊包圍盒與空間劃分的碰撞檢測算法，采用分步檢測方法，利用碰撞檢測的時空相關性，對時空相關部分進行相交測試，在減少碰撞檢測所需時間的同時，提高了碰撞檢測的準確性。

本文以OBB 包圍盒為模型基礎，建立支撐端和銑削端的包圍盒模型，并解析了雙五軸鏡像銑的運動學模型，之后通過分離軸算法（SAT）進行碰撞檢測，最后通過MAT?LAB 進行碰撞仿真驗證。

1 OBB 包圍盒與鏡像銑模型構建

包圍盒是根據包圍物體形狀而建立的簡單的盒型空間。為了實現更快速的碰撞檢測以及更精確的碰撞距離，構建包圍體成為了主流研究方法。當包圍盒之間發生碰撞后，才能進一步對碰撞進行檢測與處理。包圍盒類型繁多，主要包含球體包圍盒、軸對齊包圍盒（AABB）、有向包圍盒（OBB）、8-DOP 以及凸殼等。不同形狀的物體擁有不同包圍盒，因為包圍盒一般為規則物體，因此用其代替該物體進行計算，會比直接利用物體本身更加高效、簡單。在3D 模型碰撞算法中，AABB 包圍盒和OBB 包圍盒都得到了廣泛應用，其中AABB 包圍盒的構建方法簡單，并且是軸對齊的，所以在碰撞檢測中更為常見。在鏡像銑加工過程中存在旋轉變換的情況，但AABB 包圍盒在旋轉狀態下需要重建包圍盒模型，導致檢測效率降低。此時OBB 包圍盒有其獨特優勢，OBB 包圍盒是通過分析物體頂點得到一個最小包圍體，并且其形狀不隨物體的運動變化而變化，可作為存在旋轉變換的鏡像銑碰撞檢測模型。

1.1 OBB 包圍盒模型構建

如圖1 所示，圖1（a）為AABB 包圍盒模型，其完全按照坐標軸方向構建模型，而且在旋轉時，物體坐標變化會造成包圍盒的形狀變化，需要對AABB 包圍盒進行重建，且模型不緊湊、效率不高。從圖1（b）中可以看出，OBB 包圍盒模型不存在旋轉變換后重構模型的過程，并且比AABB 包圍盒更加緊湊。

Fig.1 Bounding box model圖1 包圍盒模型

生成OBB 包圍盒時，首先要獲得物體頂點，然后根據主成分分析法得到物體相關頂點下的特征向量。對于三維物體而言，3 個特征向量即為OBB 包圍盒的3 個空間主軸。在進行主成分分析時，協方差矩陣計算很關鍵。變量之間的協方差越小，說明變量之間相關性越小，變量呈現更加獨立的狀態。協方差計算公式為：

其中，E 代表數學期望。

通過協方差計算公式，可得到物體所有頂點的協方差矩陣：

其中，當變量相同時，如cov(xi,xi)、cov(yi,yi)、cov(zi,zi)又可表示為變量的方差。

青銅峽市位于西北內陸，屬于中溫帶大陸性氣候區。地理坐標為東經105°21′～106°21′、北緯37°36′～38°15′。青銅峽市地貌受構造控制，形成了西南高北東低，似簸箕狀地貌景觀，東部為牛首山、山前臺地及丘陵地區；北部屬于銀川平原南部，中部為衛寧平原北端和青銅峽庫區，地勢平坦；南部、西部為衛寧北山東端及山前臺地，地面起伏較大[6]。全市土壤偏堿性(pH為7.67～9.70)，主要土壤類型為灌淤土、灰鈣土、新積土和潮土等，其中灌淤土為主要農耕土壤類型。

通過式（2）可得到一個對稱矩陣B，求得矩陣B 的特征向量后，使特征向量正規化，包圍盒的3 條軸線用正規化后的3 個向量表示。軸線確定后，物體所有頂點向3 條軸線方向投影，每個軸線方向最大值與最小值的連線可作為包圍盒的三邊之一，包圍盒建立完成。

1.2 鏡像銑模型構建

鏡像銑加工機床由支撐端和銑削端構成，如圖2 所示，在兩端存在旋轉位置變化。

Fig.2 Mirrored milling model圖2 鏡像銑模型

構建鏡像銑兩端的包圍盒時，將支撐端和銑削端的三角面片網格化，提取三角面片上的網格節點坐標，構建包圍盒模型。在對銑削端和支撐端的包圍盒進行運動狀態變換時，需要建立鏡像銑機床坐標系，如圖3 所示。

Fig.3 Mirror milling coordinates at both ends圖3 鏡像銑兩端坐標

雙五軸鏡像銑機床由兩個五軸構成，分解成單五軸來看，如圖3 的銑削端，在銑削端進行平移運動時，可分解為沿x1、y1、z1的分運動。若一點P1(X1,Y1,Z1)經平移變換得到P2(X2,Y2,Z2)，則坐標系o1的坐標變換如下：

其中，x、y、z代表在軸x1、y1、z1方向的平移距離。

在銑削端進行旋轉運動時，可分解為沿x1、y1的分運動。若一點P1(X1,Y1,Z1)經旋轉變換得到P2(X2,Y2,Z2)，則坐標系o1的坐標變換如下：

其中，α代表點P1繞x1軸旋轉的角度，β代表點P1繞y1軸旋轉的角度，則坐標系o1經平移、旋轉后變換如下：

由OBB 包圍盒特性可知，其位置變化后不需要再進行重建，包圍盒頂點可直接代入上式進行計算得到變換后的位置，進而得到包圍盒。建模過程比較簡單，有利于提高系統檢測效率。支撐端的建模計算同上。

2 基于分離軸算法的碰撞檢測

在二維模型中，分離軸算法的核心思想是判斷兩個二位圖形之間有無間隙，如果不存在間隙，則物體發生碰撞，相反，物體不會發生碰撞。針對OBB 包圍盒模型的三維凸體碰撞檢測，本文設置以下計算步驟：

步驟一：根據分離軸定理，支撐端和銑削端的OBB 包圍盒模型建立完成后，得到12 個面，如圖4 所示。投影平面為兩包圍盒某一個面的垂直面，將兩包圍盒向投影平面投影，可以把三維碰撞檢測轉化成二維碰撞檢測。由于包圍盒相對面兩兩平行，所以一個包圍盒存在3 個相互垂直的面，每一個包圍盒需要進行3 次投影，兩個包圍盒總投影次數為6 次。

Fig.4 3D projection圖4 三維投影

步驟二：某次投影結束后，得到兩個二維多邊形，如圖5 所示。計算所需檢測邊的法向量，即是需要投影的原始軸，實際投影軸為移動后的投影軸，檢測邊則為投影方向。

Fig.5 Build the projection axis圖5 構建投影軸

步驟三：搜尋多邊形頂點，并將頂點從檢測軸方向投影到移動后的投影軸線上，如圖6 所示。

Fig.6 Projection of the first polygon圖6 第一個多邊形投影

步驟四：獲取另一個多邊形頂點，將頂點投影到軸上，如圖7 所示。

Fig.7 Projection of the second polygon圖7 第二個多邊形投影

Fig.8 Collision distance detection圖8 碰撞距離檢測

步驟六：待檢測邊的搜尋。由于投影得到的多邊形為凸多邊形，根據多邊形頂點坐標計算得到最近的兩個頂點，連線得到第一條檢測邊。投影計算完成后，計算離其中一個頂點最近的頂點，上一步得到的頂點除外，將兩頂點連線得到第二條檢測邊，迭代循環得到所有待檢測的邊及其頂點。

步驟七：完成支撐端包圍盒和銑削端包圍盒其中一個面的投影后，依次在5 個面的法平面方向進行投影，一共得到2×6 個參數，其中最大負值的絕對值為包圍盒重疊的最大值。若使碰撞分離，則將兩端分開相應距離，其中最小非負值為兩端未發生碰撞時的安全距離。本文算法流程如圖9 所示。

3 仿真分析

通過MATLAB2018b 對雙五軸支撐端和銑削端進行碰撞檢測。當雙五軸鏡像銑機床的支撐端和銑削端發生旋轉與平移變化時，將本文提出的OBB 包圍盒算法與AABB包圍盒算法進行對比，采取離散碰撞檢測法，兩個包圍盒算法運行時間如圖10 所示。

Fig.9 Algorithm flow圖9 算法流程

Fig.10 Comparison of modeling time between two bounding box algorithms圖10 兩種包圍盒算法建模時間對比

通過圖10 可以看出，在同一個采樣點，OBB 包圍盒算法的運行時間明顯少于AABB 包圍盒算法。所以OBB 包圍盒算法在構建模型時更加高效，建模平均速度提高了25%。

設計碰撞仿真時，設置安全距離為0，當包圍盒之間距離大于0 時則為安全距離，當包圍盒之間距離小于等于0時，發出警告并停止運動。本文通過分離軸算法進行實時測距，在Z 方向的碰撞測試如圖11 所示。

4 結語

本文分析OBB 包圍盒的建立方法及其優勢，并建立機床支撐端和銑削端的包圍盒模型。通過分離軸算法判斷支撐端與銑削端是否碰撞，最后通過MATLAB 進行仿真。仿真結果表明，該算法可適用于鏡像銑加工碰撞檢測。此外，本文主要研究離散碰撞相關內容，針對復雜的連續碰撞還需作進一步研究。

Fig.11 Collision test圖11 碰撞測試