基于改進OBB包圍盒的碰撞檢測算法*

史旭升，喬立紅，朱作為

(北京航空航天大學 機械工程及自動化學院先進制造技術與系統(tǒng)研究中心，北京 100191)

車銑復合加工作為一種先進的加工技術，在加工復雜的高精密零件和異形零件等領域都有不可替代的地位.車銑復合加工機床包含多主軸多刀架結(jié)構(gòu)，在精密微小零件的高速加工過程中，多把刀架在狹小的空間中同時加工零件，刀架之間極易發(fā)生干涉碰撞現(xiàn)象[1].

隨著計算機技術的發(fā)展，虛擬仿真技術在降低成本、提高效率方面都有顯著優(yōu)勢.碰撞檢測算法主要有空間分解法和層次包圍盒法兩種算法，其核心思想都是盡可能減少相交測試對象的數(shù)目來提高檢測速度.空間分解法適用于在稀疏的環(huán)境中分布比較均勻的幾何對象間的檢測，層次包圍盒法則應用更為廣泛，適應復雜環(huán)境中的碰撞檢測[2].車銑復合加工環(huán)境復雜，運動對象多，因此，在本研究中選用了基于層次包圍盒的方法.傳統(tǒng)檢測方法是進行一次或多次試切、不斷調(diào)試，直到確認能夠完成預定的加工要求，該方法效率低、周期長、成本高.為了提高檢測效率，基于虛擬仿真技術的碰撞檢測算法[3-7]，為數(shù)控加工方案的修正提供了依據(jù)，但是在修正過程中需要工藝人員根據(jù)經(jīng)驗預估修正方式，由預估引起的不確定性和偶然性，給生產(chǎn)計劃帶來一定風險，如果不能及時解決可能影響生產(chǎn)進度.為了避免盲目預估，減少反復修正的次數(shù)，提高準確率，保證精度，本文提出了基于改進OBB包圍盒的快速碰撞檢測算法.

1 問題描述

現(xiàn)有研究傾向于通過碰撞檢測確定發(fā)生碰撞的對象，沒有考慮具體的交點信息.數(shù)控加工仿真軟件給出的碰撞檢測結(jié)果是加工過程中發(fā)生碰撞的對象，這些碰撞檢測數(shù)據(jù)可以基本滿足數(shù)控加工仿真的需求[1].但是由于碰撞結(jié)果比較籠統(tǒng)，需要反復調(diào)整或校正加工速度、切削量或刀具伸長量等方式來修正.為了避免盲目的參數(shù)預估，減少反復修正的次數(shù)，提高準確率保證精度，準確計算出三角面的初始碰撞時間和碰撞位置顯得尤其重要[8].針對車銑復合數(shù)控加工仿真碰撞檢測精確度低的問題，本文提出了一種基于改進OBB包圍盒的碰撞檢測算法.

2 碰撞檢測算法

碰撞檢測算法分為3個部分：預處理階段、粗檢階段和精檢階段.該算法以車銑復合加工仿真碰撞檢測信息作為輸入，計算出碰撞單元組之間發(fā)生的初始碰撞時間和位置.

2.1 創(chuàng)建OBB包圍盒及層次包圍盒樹

車銑復合加工碰撞檢測預處理階段的主要內(nèi)容是創(chuàng)建碰撞單元組對象的包圍盒及層次包圍盒樹.具體步驟如下：

步驟1創(chuàng)建車銑復合加工仿真環(huán)境.主要是車銑復合加工機床組件的創(chuàng)建，如刀具、刀架、主軸等，根據(jù)機床的運動學關系，建立機床運動學模型.

步驟2車銑復合加工仿真碰撞檢測.通過創(chuàng)建加工方法和加工操作，利用數(shù)控仿真軟件進行車銑復合加工仿真，并進行碰撞檢測.

步驟3獲取車銑復合加工仿真過程中發(fā)生碰撞的碰撞組信息.設碰撞單元組信息表示為:

(1)

M={M1,M2,…,Mk]

(2)

步驟4創(chuàng)建OBB包圍盒.根據(jù)碰撞單元組對象所包含的三角面片信息，創(chuàng)建相應的OBB包圍盒，分別標記為包圍盒A和包圍盒B.

步驟5創(chuàng)建OBB層次包圍盒樹.以八叉樹的形式進行空間劃分，按照“自上而下”的方法創(chuàng)建層次包圍盒樹，分別標記為OBB_A和OBB_B.

層次包圍盒樹子節(jié)點主要分為3種類型，即實節(jié)點、空節(jié)點和灰節(jié)點.當葉子節(jié)點與幾何對象實體完全重合時用實節(jié)點表示，當葉子節(jié)點與幾何對象實體部分重合時用灰節(jié)點表示，當葉子節(jié)點與幾何對象實體分離時用空節(jié)點表示.這樣葉子節(jié)點中就儲存了離散表面所包含的三角面片數(shù)據(jù)，用于精確碰撞檢測.

其中空節(jié)點不包含幾何實體，在計算中被剔除，減少運算節(jié)點數(shù)目；實節(jié)點與幾何對象完全重合，認為該節(jié)點是最末端子節(jié)點，不需要再分割，可直接用于下一步進行精確碰撞檢測計算；灰節(jié)點包含幾何對象以外的空間，直接用于精確碰撞檢測可能引起偽碰撞現(xiàn)象，所以如果灰節(jié)點存在碰撞現(xiàn)象，需要進一步分割，直到滿足設定的層次包圍盒深度或者所有葉子節(jié)點都是空節(jié)點或?qū)嵐?jié)點為止，如果灰節(jié)點不存在碰撞現(xiàn)象，則不需要進一步分割，減少不必要的節(jié)點數(shù)目和存儲數(shù)據(jù).

在建立層次結(jié)構(gòu)時，層次結(jié)構(gòu)樹深度的確定需要遵循兩個原則：劃分深度不宜太大，從而在遍歷時，只需很少的步數(shù)，就能完成從根節(jié)點到葉子節(jié)點的搜索；劃分深度不宜太小，否則每個子節(jié)點內(nèi)包含的三角面片數(shù)量太多,加重了精確檢測的計算壓力.層次包圍盒樹子節(jié)點的深度與幾何模型及其精度相關[9]，本文結(jié)合檢測對象的幾何模型及精度，設層次包圍盒樹子節(jié)點最大深度為6.

2.2 基于分離軸定理的初始碰撞檢測

碰撞檢測的粗檢階段是基于分離軸定理，通過廣度優(yōu)先搜索的策略遍歷層次包圍盒樹子節(jié)點，快速剔除不發(fā)生碰撞的子節(jié)點，當發(fā)生碰撞的節(jié)點不可分割時，則記為：

(3)

W={W1,W2,…,Wk}

(4)

對于一對OBB，需測試15條可能的分離軸(每個OBB的3個面方向，每個OBB的3條邊方向的兩兩組合)，只要找到一條這樣的分離軸，就可以判定這兩個OBB是不相交的.如圖1所示為分離軸定理示意圖，其中L表示兩個包圍盒的某一分離軸，Oa和Ob分別表示兩個包圍盒的中心位置，S是包圍盒中心位置在分離軸上投影的距離，ra和rb是包圍盒在分離軸上投影的距離，當存在分離軸使S>ra+rb時，則OBB處于分離狀態(tài)，反之則視為相交.在某些情況下，該算法會將分離的盒體報告為相交，但不會遺漏相應的碰撞結(jié)果，在初始碰撞檢測階段該算法計算簡單，能夠快速剔除不發(fā)生碰撞的包圍盒.

圖1 分離軸定理示意圖

2.3 基于三角面片的精確碰撞檢測

碰撞檢測的精檢階段是應用分離軸定理，判斷碰撞節(jié)點所包含的三角面片之間的相交情況，然后應用回退技術，計算出三角面片發(fā)生碰撞的初始碰撞時間和碰撞位置.

已知在粗檢階段計算得到相交包圍盒節(jié)點集合：W={W1,W2,…,Wk}.設Wk1是包圍盒節(jié)點集合W的第k個元素中層次包圍盒OBB_A的節(jié)點，Wk2是包圍盒節(jié)點集合W的第k個元素中層次包圍盒OBB_B的節(jié)點.應用分離軸定理考查11個分離軸(平行于兩個三角形面法線的兩個軸，兩個三角形之間的9種邊邊組合).若兩個三角形在任一分離軸上的投影區(qū)間不相交，則兩個三角形分離；若投影區(qū)間在所有分離軸上都相交，則兩個三角形必定相交.把發(fā)生相交的三角形組記為：

(5)

Q{Q1,Q2,…,Qn}

(6)

關于初始時間及位置的計算和改進方法將在第4節(jié)進行詳細闡述.

3 改進的OBB包圍盒算法

3.1 傳統(tǒng)OBB包圍盒算法

創(chuàng)建OBB包圍盒時，確定包圍盒的中心位置和最佳方向是關鍵.傳統(tǒng)算法是根據(jù)幾何模型的三角面片信息，利用均值和單位化協(xié)方差矩陣的統(tǒng)計量來計算包圍盒的位置和方向.已知組成幾何對象的基本幾何元素為三角形，設包含的三角面片數(shù)為n，且第i個三角形的頂點坐標為(pi,qi,ri)，則包圍盒的中心位置為：

(7)

由于該算法是各三角形頂點的簡單平均，如果幾何體結(jié)構(gòu)不均勻，在體積相等的區(qū)域，有的部分三角面片數(shù)量多，有的部分三角面片數(shù)量少，這樣計算出來的包圍盒就會向三角面片數(shù)量多的部分偏移(如圖2(a)所示).顯然這將導致一部分包圍盒在幾何體外面，使碰撞檢測出現(xiàn)誤檢的現(xiàn)象.

3.2 改進的OBB包圍盒算法

為了解決傳統(tǒng)包圍盒算法計算結(jié)果不準確的問題，本文提出區(qū)域加權(quán)的改進算法，該算法的核心思想是把幾何對象劃分為表面積相近的i個區(qū)域，分別計算每個區(qū)域的中心坐標mi，再求這幾個區(qū)域中心坐標的平均值：

(8)

(9)

碰撞單元組對象的結(jié)構(gòu)存在很大不確定性，無法采用統(tǒng)一的表面積劃分方法.本文采用人機交互的方式，借助CAD軟件的“分析-測量面”獲取幾何形面表面積的功能，把產(chǎn)品劃分為幾個相近的區(qū)域，根據(jù)產(chǎn)品結(jié)構(gòu)可劃分為3～5個區(qū)域.本文把萬向節(jié)零件劃分為3個表面積相近的區(qū)域(如圖2(b)所示)，通過采用改進的OBB包圍盒算法，使矯正之后的包圍盒緊緊地包圍物體(如圖2(c)所示).

(a)改進前

(b)區(qū)域劃分

(c)改進后

4 初始碰撞時間及位置的計算

4.1 初始碰撞時間的計算

設在t=Tk時刻車銑復合加工發(fā)生碰撞現(xiàn)象，由于仿真精度和系統(tǒng)反應時間的問題無法保證Tk就是物體之間的初始碰撞時間.本文應用回退技術計算初始碰撞時間.

設兩個三角面片在某個臨近時間t=T0時未發(fā)生相交，則第一次發(fā)生碰撞的時間為t=T(T0

T0是三角面片相交之前的某個時間，如何選擇T0直接影響初始時間的計算效率.假設在Tk時刻兩個三角面片相交，則回退的最大時間差表示為Δt，則Δt={N/(|va-vb|·L)}，其中N表示兩個三角形中最長的邊，va和vb分別表示兩個三角面片的運動速度，L是三角形的分離軸，則T0=T-Δt.在區(qū)間t∈[T0,T)內(nèi)做回退處理，回退次數(shù)是可控的，可以通過增大三角形剖分的精度來減少回退次數(shù).設時間t的步長為0.02 s，在測試中發(fā)現(xiàn)，回退次數(shù)一般不大于5.

在應用回退技術的過程中，需要推導出時間區(qū)間t∈[T0,T)內(nèi)每個回退點的位置信息.這里應用洛倫茲變換理論，根據(jù)三角面片的頂點坐標和運動狀態(tài)v，可以計算出任意時刻的三角面片位置信息.

通過遍歷集合Q{Q1,Q2,…,Qn}包含的所有元素，并應用回退技術計算出每對相交三角面片的初始相交時間，得出集合：

T{T1,T2,…,Tn}

(10)

比較集合T中的元素，則最小時間為檢測對象初始碰撞時間記為Tmin.

4.2 初始碰撞位置的計算

兩個三角形初次相交時，必交于一點或者一條線段.若Tmin對應的三角面片對數(shù)目大于1，則三角形相交于一條線段.

設△ABC和△DEF是Tmin時相交的一對三角形.設E1=B-A,E2=C-A和E3=E2-E1為△ABC的三條邊，N1=E1×E2為法線，{A+x1E1+x2E2}表示△ABC包含的點，其中(0≤x1≤1,0≤x2≤1,x1+x2≤1).L1=E-D，L2=F-D和L3=L2-L1為△DEF三條邊，N2=L1×L2為法線，△DEF包含的點記為：{D+y1L1+y2L2}，其中(0≤y1≤1,0≤y2≤1,y1+y2≤1).

則初始碰撞位置就轉(zhuǎn)換為計算Tmin時兩個三角形交點P的問題，即求解:

A+x1E1+x2E2-Tva=

D+y1L1+y2L2-Tvb

(11)

其中T=Tk-Tmin，va是碰撞檢測對象A的運動速度，vb是碰撞檢測對象B的運動速度.

設初始相交位置在△DEF的任意一條邊上，則有y1=0,y2=0;y1=1,y2=0和y1=0,y2=1三種情況.篩選出滿足條件(0≤x1≤1,0≤x2≤1)的x1和x2.如果x1或x2不在[0,1]范圍內(nèi)，則假設不成立.重新假設初始相交點的位置在△ABC的任意一條邊上，同理，根據(jù)x1=0,x2=0;x1=1,x2=0和x1=0,x2=1三種情況，篩選出滿足條件(0≤y1≤1,0≤y2≤1)的y1和y2.因為三角形相交，所以一定能計算出滿足條件的系數(shù)x1，x2或系數(shù)y1，y2.

若計算出滿足條件的(0≤x1≤1,0≤x2≤1)的x1和x2.則把相應的y1和y2代入D+y1L1+y2L2-Tvb得交點P的坐標.反之，則把x1和x2代入A+x1E1+x2E2-Tva得交點P的坐標.

如果以每種假設為計算單元，本文提出的假設算法總共需要計算3+3=6次.

常用基于分離軸的測試方案[10]，分別計算11個分離軸情況下，每一類分離軸有不同的3種情況(詳細內(nèi)容見文獻[10])，計算出相應的x1和x2的系數(shù)，滿足條件時，則根據(jù)系數(shù)計算出P點的坐標.計算11×3次.

區(qū)間相交算法是一種類似于分離軸測試的改進方案[6].該算法先計算出兩個三角形所在平面的交線，然后比較分離軸中與交線L最接近平行的一條分離軸，測試在3種假設情況下滿足條件的系數(shù)，再計算出P點的坐標.計算11+3次.

綜上所述，本文關于三角面片相交位置的計算次數(shù)比分離軸算法的計算次數(shù)少了80%，比區(qū)間相交算法的計算次數(shù)少了50%，明顯提升了計算效率.

5 實例驗證

5.1 OBB包圍盒的創(chuàng)建

本文以某型號萬向節(jié)零件的車銑復合加工為例，進行碰撞檢測算法實例驗證.以CAD軟件為仿真平臺，創(chuàng)建了用于車銑復合加工仿真的機床、刀具、工件和夾緊裝置等三維模型，配置機床的運動學關系，選擇數(shù)控系統(tǒng)為simens840D.仿真碰撞檢測結(jié)果顯示共發(fā)生碰撞次數(shù)為15次.

本文以數(shù)控加工3分12秒時刀架1與刀架2發(fā)生的碰撞為例.由發(fā)生碰撞的時間和工藝過程推算得出，刀架1車削萬向節(jié)外圓和刀架2鉆削萬向節(jié)軸向孔時刀架1的刀具和刀架2的刀座發(fā)生了碰撞.相應的碰撞信息描述為：

應用改進的OBB包圍盒算法得出：刀架1上車刀的包圍盒中心坐標Oa(91.5,151.5,0)，半軸長分別為(71,67.5,50)，方向軸坐標為(保留小數(shù)點后兩位)(-0.48,-0.72,-0.50;0.68,-0.67,0.31;-0.56,-0.19,0.81)；刀架2上鉆刀刀座的包圍盒中心坐標Ob(217.5,0,0)，半軸長分別為(55,170,170)，(1,0,0;0,1,0;0,0,1)為方向軸坐標.根據(jù)八叉樹空間分割法，可以計算出OBB層次包圍盒樹的每一個節(jié)點和子節(jié)點的包圍盒中心坐標及半長軸尺寸.

5.2 計算結(jié)果

通過粗檢階段得出，發(fā)生相交的子節(jié)點集合：

W={W1,W2,W3,W4,W5}

其中：

通過精檢階段得出，發(fā)生相交的三角面片有93對.初始碰撞時間為工步2加工運行到17.83 s，初始碰撞位置為P(132.5,36.4,0).圖3為數(shù)控加工仿真碰撞示意圖.其中碰撞對象A為車刀，運動速度為va，碰撞對象B為鉆刀刀座,運動速度為vb，加工對象W為工件，A沿著工件徑向豎直向下做直線運動，B沿著工件軸線方法向左做直線運動.在局部放大示意圖中，相交區(qū)域用C表示，點P為發(fā)生初始碰撞的位置.

在車削外圓與鉆削軸向孔時，刀架1的車刀與刀架2的鉆刀刀座發(fā)生碰撞.有以下4種修正方案：

方案1.增加鉆刀的伸長量.把鉆刀的伸長量由50 mm調(diào)整到56.2 mm以上，使鉆刀刀座與車刀距離增加，有可能避免碰撞現(xiàn)象；

方案2.增加車削加工車削速度.把車刀的切削速度增加到2.5 mm/s以上，使鉆刀與車刀在碰撞區(qū)域的運動軌跡產(chǎn)生時間差；

圖3 數(shù)控加工仿真碰撞示意圖

方案3.減小鉆削速度.鉆刀的切削速度減小到0.7 mm/s以下，使鉆刀與車刀在碰撞區(qū)域的運動軌跡產(chǎn)生時間差；

方案4.調(diào)整工藝方案.將車削加工與鉆削加工分開加工.

以上4種方案中，方案1最方便快捷，且能保證切削效率和精度.方案2和方案3分別通過增加和減小加工參數(shù)避免干涉碰撞發(fā)生.如果參數(shù)修改幅度太大，會影響到加工效率和精度.方案4如果只是將車削加工與鉆削加工分為兩個工步進行加工，將影響加工效率.由于碰撞現(xiàn)象發(fā)生的情況各異，暫時還無法用統(tǒng)一的標準規(guī)定修正方案，詳細修正計算過程這里不展開論述.本文采用方案1修正碰撞現(xiàn)象.經(jīng)驗證有效避免了碰撞現(xiàn)象.如圖4所示為車銑復合加工碰撞檢測流程示意圖.

圖4 碰撞檢測計算流程圖

6 結(jié) 論

本文創(chuàng)建的車銑復合加工仿真環(huán)境比CAM軟件通過刀位文件仿真更真實，更接近實際加工情況，提供了可靠的碰撞檢測信息.在預處理階段，建立了改進的OBB包圍盒及其層次包圍盒樹；在粗檢階段和精檢階段，基于分離軸定理和回退技術，計算出了初始碰撞時間及位置.實例驗證結(jié)果表明，計算結(jié)果準確，為操作人員進行加工修正提供了可靠的依據(jù)，避免了盲目的參數(shù)預估，減少反復修正的次數(shù)，提高了效率，對車銑復合加工和制造也具有很重要的意義.

[1]吳寶海,嚴亞楠,羅明,等.車銑復合加工的關鍵技術與應用前景[J].航空制造技術,2010(19):42-45.

WU Bao-hai,YAN Ya-nan,LUO Ming,etal.Key technology and application prospect of turning/milling machining [J].Aeronautical Manufacturing Technology,2010(19):42-45.(In Chinese)

[2]KOCKARA S,HALIC T,IQBAL K,etal.Collision detection: a survey[C]//IEEE International Conference on Systems,Man and Cybernetics.Montreal Canada:IEEE,2007:4046-4051.

[3]鄭錦銅,江銘鴻.剛性基礎上搖晃橋柱系統(tǒng)地震反應研究[J].湖南大學學報：自然科學版,2013,40(4):32-41.

ZHENG Jin-tong,JIANG Ming-hong.Seismic response of rocking pier system on rigid foundation[J].Jounral of Hunan University: Natural Sciences,2013,40(4):32-41.(In Chinese)

[4]孟志強,何濤,尹望吾,等.六角彈簧管汽車碰撞吸能裝置的效能研究[J].湖南大學學報：自然科學版,2011,38 (11):43-46.

MENG Zhi-qiang,HE Tao,YIN Wang-wu,etal.Research on the performances of hexagonal spring tube energy-absorbing device for car crash[J].Jounral of Hunan University: Natural Sciences,2011,38(11):43-46.(In Chinese)

[5]PAZOUKI A,MAZHAR H,NEGRUT D.Parallel collision detection of ellipsoids with applications in large scale multi body dynamics[J].Mathematics and Computers in Simulation,2012,82:879-894.

[6]JIA Xiao-hong,CHOI Yi-king,BERNARD Mourrain,etal.An algebraic approach to continuous collision detection for ellipsoids[J].Computer Aided Geometric Design,2011,28: 164-176.

[7]CHANG Jung-woo,WANG Wen-ping,KIM Myung-soo.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J].Computer-Aided Design,2010,42(1): 50-57.

[8]黃通浪,唐敏,董金祥.一種快速精確的連續(xù)碰撞檢測算法[J].浙江大學學報:工學版,2006,40(6):1051-1055.

HUANG Tong-lang,TANG Min,DONG Jin-xiang.Fast and accurate continuous collision detection between rigid bodies[J].Journal of Zhejiang University: Engineering Science,2006,40(6):1051-1055.(In Chinese)

[9]康勇,熊岳山,費先宏,等.基于空間分解和包圍盒層次的混合碰撞檢測算法[J].計算機仿真,2010(6):191-193.

KANG Yong,XIONG Yue-shan,FEI Xian-hong,etal.A hybrid collision detection algorithm based on spatial partitioning and bounding volume hierarchy[J].Computer Simulation,2010(6):191-193.(In Chinese)

[10]David eberly geometric tool LLC.Dynamic collision detection using oriented bounding boxes[EB/OL].[2013-09-21].http://www.geometrictools.com/.