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

史旭升，喬立紅，朱作為

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

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

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

1 問題描述

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

2 碰撞檢測算法

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

2.1 創建OBB包圍盒及層次包圍盒樹

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

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

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

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

(1)

M={M1,M2,…,Mk]

(2)

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

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

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

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

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

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

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

(3)

W={W1,W2,…,Wk}

(4)

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

圖1 分離軸定理示意圖

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

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

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

(5)

Q{Q1,Q2,…,Qn}

(6)

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

3 改進的OBB包圍盒算法

3.1 傳統OBB包圍盒算法

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

(7)

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

3.2 改進的OBB包圍盒算法

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

(8)

(9)

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

(a)改進前

(b)區域劃分

(c)改進后

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

4.1 初始碰撞時間的計算

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

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

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

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

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

T{T1,T2,…,Tn}

(10)

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

4.2 初始碰撞位置的計算

兩個三角形初次相交時，必交于一點或者一條線段.若Tmin對應的三角面片對數目大于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).

則初始碰撞位置就轉換為計算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]范圍內，則假設不成立.重新假設初始相交點的位置在△ABC的任意一條邊上，同理，根據x1=0,x2=0;x1=1,x2=0和x1=0,x2=1三種情況，篩選出滿足條件(0≤y1≤1,0≤y2≤1)的y1和y2.因為三角形相交，所以一定能計算出滿足條件的系數x1，x2或系數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種情況(詳細內容見文獻[10])，計算出相應的x1和x2的系數，滿足條件時，則根據系數計算出P點的坐標.計算11×3次.

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

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

5 實例驗證

5.1 OBB包圍盒的創建

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

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

應用改進的OBB包圍盒算法得出：刀架1上車刀的包圍盒中心坐標Oa(91.5,151.5,0)，半軸長分別為(71,67.5,50)，方向軸坐標為(保留小數點后兩位)(-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)為方向軸坐標.根據八叉樹空間分割法，可以計算出OBB層次包圍盒樹的每一個節點和子節點的包圍盒中心坐標及半長軸尺寸.

5.2 計算結果

通過粗檢階段得出，發生相交的子節點集合：

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

其中：

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

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

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

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

圖3 數控加工仿真碰撞示意圖

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

方案4.調整工藝方案.將車削加工與鉆削加工分開加工.

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

圖4 碰撞檢測計算流程圖

6 結 論

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

[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]鄭錦銅,江銘鴻.剛性基礎上搖晃橋柱系統地震反應研究[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]黃通浪,唐敏,董金祥.一種快速精確的連續碰撞檢測算法[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/.