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

孔 森，張立強，李宇昊

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

0 引言

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

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

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

1 OBB 包圍盒與鏡像銑模型構(gòu)建

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

1.1 OBB 包圍盒模型構(gòu)建

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

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

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

其中，E 代表數(shù)學(xué)期望。

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

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

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

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

1.2 鏡像銑模型構(gòu)建

鏡像銑加工機床由支撐端和銑削端構(gòu)成，如圖2 所示，在兩端存在旋轉(zhuǎn)位置變化。

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

構(gòu)建鏡像銑兩端的包圍盒時，將支撐端和銑削端的三角面片網(wǎng)格化，提取三角面片上的網(wǎng)格節(jié)點坐標(biāo)，構(gòu)建包圍盒模型。在對銑削端和支撐端的包圍盒進(jìn)行運動狀態(tài)變換時，需要建立鏡像銑機床坐標(biāo)系，如圖3 所示。

Fig.3 Mirror milling coordinates at both ends圖3 鏡像銑兩端坐標(biāo)

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

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

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

其中，α代表點P1繞x1軸旋轉(zhuǎn)的角度，β代表點P1繞y1軸旋轉(zhuǎn)的角度，則坐標(biāo)系o1經(jīng)平移、旋轉(zhuǎn)后變換如下：

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

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

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

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

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

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

Fig.5 Build the projection axis圖5 構(gòu)建投影軸

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

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

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

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

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

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

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

3 仿真分析

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

Fig.9 Algorithm flow圖9 算法流程

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

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

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

4 結(jié)語

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

Fig.11 Collision test圖11 碰撞測試