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

孔 森，張立強(qiáng)，李宇昊

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

0 引言

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

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

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

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

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

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

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

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

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

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

通過(guò)協(xié)方差計(jì)算公式，可得到物體所有頂點(diǎn)的協(xié)方差矩陣：

其中，當(dāng)變量相同時(shí)，如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)造控制，形成了西南高北東低，似簸箕狀地貌景觀，東部為牛首山、山前臺(tái)地及丘陵地區(qū)；北部屬于銀川平原南部，中部為衛(wèi)寧平原北端和青銅峽庫(kù)區(qū)，地勢(shì)平坦；南部、西部為衛(wèi)寧北山東端及山前臺(tái)地，地面起伏較大[6]。全市土壤偏堿性(pH為7.67～9.70)，主要土壤類型為灌淤土、灰鈣土、新積土和潮土等，其中灌淤土為主要農(nóng)耕土壤類型。

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

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

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

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

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

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

雙五軸鏡像銑機(jī)床由兩個(gè)五軸構(gòu)成，分解成單五軸來(lái)看，如圖3 的銑削端，在銑削端進(jìn)行平移運(yùn)動(dòng)時(shí)，可分解為沿x1、y1、z1的分運(yùn)動(dòng)。若一點(diǎn)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)運(yùn)動(dòng)時(shí)，可分解為沿x1、y1的分運(yùn)動(dòng)。若一點(diǎn)P1(X1,Y1,Z1)經(jīng)旋轉(zhuǎn)變換得到P2(X2,Y2,Z2)，則坐標(biāo)系o1的坐標(biāo)變換如下：

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

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

2 基于分離軸算法的碰撞檢測(cè)

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

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

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

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

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

步驟三：搜尋多邊形頂點(diǎn)，并將頂點(diǎn)從檢測(cè)軸方向投影到移動(dòng)后的投影軸線上，如圖6 所示。

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

步驟四：獲取另一個(gè)多邊形頂點(diǎn)，將頂點(diǎn)投影到軸上，如圖7 所示。

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

Fig.8 Collision distance detection圖8 碰撞距離檢測(cè)

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

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

3 仿真分析

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

Fig.9 Algorithm flow圖9 算法流程

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

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

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

4 結(jié)語(yǔ)

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

Fig.11 Collision test圖11 碰撞測(cè)試