基于改進(jìn)OBB包圍盒的碰撞檢測(cè)算法

史旭升+喬立紅+朱作為

文章編號(hào)：16742974(2014)05002606

收稿日期：20130925

基金項(xiàng)目：國(guó)家科技重大專項(xiàng)項(xiàng)目（2011ZX04016-021）；北京市教育委員會(huì)共建資助項(xiàng)目

作者簡(jiǎn)介：史旭升（1983-），男，陜西蒲城人，北京航空航天大學(xué)博士研究生

通訊聯(lián)系人，E-mail: lhqiao@buaa.edu.cn 

摘 要： 針對(duì)車銑復(fù)合數(shù)控加工仿真碰撞檢測(cè)精確度低的問(wèn)題，提出了一種基于改進(jìn)OBB包圍盒的快速碰撞檢測(cè)算法.該算法基于改進(jìn)的OBB包圍盒算法，利用車銑復(fù)合加工仿真碰撞檢測(cè)的結(jié)果，創(chuàng)建碰撞單元組的包圍盒及層次包圍盒樹；通過(guò)粗檢階段計(jì)算出包圍盒樹的相交節(jié)點(diǎn)集合，計(jì)算得到發(fā)生碰撞的三角形面片集合；應(yīng)用回退技術(shù)，解得初始碰撞時(shí)間及位置.實(shí)例驗(yàn)證結(jié)果表明，該算法有效提高了車銑復(fù)合數(shù)控加工碰撞檢測(cè)的精確度.

關(guān)鍵詞：車銑復(fù)合；碰撞檢測(cè)；OBB（Oriented Bounding Box）包圍盒；分離軸定理；三角面片

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

Algorithm of Collision Detection Based 

on Improved Oriented Bounding Box



SHI Xusheng，QIAO Lihong，ZHU Zuowei

(Advanced Manufacturing Technology and Systems Research Center, School of Manufacturing 

Engineering and Automation,Beihang University, Beijing 100191, China)

Abstract:To solve the problem of the low precision of collision detection in the turnmill combined machining simulation, a rapid collision detection algorithm based on the improved theory of Oriented Bounding Box was proposed. This algorithm, based on the improved oriented bounding box, and using the collision detection result as the input, creates the oriented bounding box and hierarchical bounding box tree of the collision unit group. During the rough detection phase, the intersecting nodes are detected. In the following precise detection phase, the triangular patches of the objects in collision are detected. With the application of feedback technology, the initial time and position of the collision are calculated. A case study shows that this algorithm increases the efficiency and precision of the collision detection in numerical control simulation.

Key words: turnmilling; collision detection; OBB(Oriented Bounding Box); SAT(Separating Axis Theorem);triangular patches



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

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

1 問(wèn)題描述

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

2 碰撞檢測(cè)算法

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

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

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

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

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

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

Mk=Tkab,Ak,∑Aki,νka,Bk,∑Bkj,νkb（1）

Tkab為第k對(duì)碰撞單元組發(fā)生碰撞的時(shí)間；Ak為碰撞單元組的對(duì)象1，νka為Ak的運(yùn)動(dòng)速度, ∑Aki表示Ak所包含的三角面片集合∑Akipi,qi,ri；Bk為碰撞單元組的對(duì)象2，νkb為Bk的運(yùn)動(dòng)速度，∑Bki為Bk包含的三角面片集合∑Bkjpj,qj,rj.則車銑復(fù)合加工仿真碰撞組信息集合可表示為：

M=M1,M2,…,Mk（2）

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

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

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

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

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

2.2 基于分離軸定理的初始碰撞檢測(cè)

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

WkOBB_Ani,OBB_Bmj （3）

其中OBB_Ani是指層次包圍盒A的第i層第n個(gè)子節(jié)點(diǎn)，OBB_Bmj是指層次包圍盒B的第j層第m個(gè)子節(jié)點(diǎn)，Wk表示第k對(duì)發(fā)生相交的子節(jié)點(diǎn)組.層次包圍盒OBB_A和OBB_B所有相交子節(jié)點(diǎn)組集合可表示為：

W=W1,W2,…,Wk（4）

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



圖1 分離軸定理示意圖

Fig.1 Separating axis theorem diagram

2.3 基于三角面片的精確碰撞檢測(cè)

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

已知在粗檢階段計(jì)算得到相交包圍盒節(jié)點(diǎn)集合：W=W1,W2,…,Wk.設(shè)Wk1是包圍盒節(jié)點(diǎn)集合W的第k個(gè)元素中層次包圍盒OBB_A的節(jié)點(diǎn)，Wk2是包圍盒節(jié)點(diǎn)集合W的第k個(gè)元素中層次包圍盒OBB_B的節(jié)點(diǎn).應(yīng)用分離軸定理考查11個(gè)分離軸（平行于兩個(gè)三角形面法線的兩個(gè)軸，兩個(gè)三角形之間的9種邊邊組合）.若兩個(gè)三角形在任一分離軸上的投影區(qū)間不相交，則兩個(gè)三角形分離；若投影區(qū)間在所有分離軸上都相交，則兩個(gè)三角形必定相交.把發(fā)生相交的三角形組記為：

QnSki,Skj （5）

其中Ski是指相交包圍盒節(jié)點(diǎn)集合中的第k個(gè)元素對(duì)中層次包圍盒OBB_A的節(jié)點(diǎn)包含的第i個(gè)三角面片信息；Skj是指相交包圍盒節(jié)點(diǎn)集合中的第k個(gè)元素對(duì)中層次包圍盒OBB_B的節(jié)點(diǎn)包含的第j個(gè)三角面片信息.Qn表示第n對(duì)發(fā)生相交的三角面片.層次包圍盒OBB_A和OBB_B所有相交三角面片對(duì)集合表示為：

QQ1,Q2,…,Qn （6）

關(guān)于初始時(shí)間及位置的計(jì)算和改進(jìn)方法將在第4節(jié)進(jìn)行詳細(xì)闡述.

3 改進(jìn)的OBB包圍盒算法

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

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

m=13n∑ni=1(pi+qi+ri)（7）

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

3.2 改進(jìn)的OBB包圍盒算法

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

m=∑i1mii （8）

其中mi=13∑ji=1(pj+qj+rj)，協(xié)方差矩陣元素為：

Cjk=13n∑ni=1(pijpik +qijqik+rijrik)（9）

其中1≤j,k≤3，pi=pi-m, qi=qi-m和 ri=ri-m都是3×1階向量，例如qi=(qi1,qi2,qi3)T.其次，計(jì)算協(xié)方差矩陣C［Cjk］的特征向量并單位化，作為包圍盒的方向軸，幾何體頂點(diǎn)在各方向軸上的投影區(qū)間長(zhǎng)度就是相應(yīng)的包圍盒尺寸.

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

（a)改進(jìn)前

(b)區(qū)域劃分

(c)改進(jìn)后

圖2 OBB包圍盒改進(jìn)效果對(duì)比圖

Fig.2 Comparison chartof improved OBB

4 初始碰撞時(shí)間及位置的計(jì)算

4.1 初始碰撞時(shí)間的計(jì)算

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

設(shè)兩個(gè)三角面片在某個(gè)臨近時(shí)間t=T0時(shí)未發(fā)生相交，則第一次發(fā)生碰撞的時(shí)間為t=TT0

T0是三角面片相交之前的某個(gè)時(shí)間，如何選擇T0直接影響初始時(shí)間的計(jì)算效率.假設(shè)在Tk時(shí)刻兩個(gè)三角面片相交，則回退的最大時(shí)間差表示為Δt，則Δt=N/va－vb?L，其中N表示兩個(gè)三角形中最長(zhǎng)的邊，va和vb分別表示兩個(gè)三角面片的運(yùn)動(dòng)速度，L是三角形的分離軸，則T0=T－Δt.在區(qū)間t∈T0,T內(nèi)做回退處理，回退次數(shù)是可控的，可以通過(guò)增大三角形剖分的精度來(lái)減少回退次數(shù).設(shè)時(shí)間t的步長(zhǎng)為0.02 s，在測(cè)試中發(fā)現(xiàn)，回退次數(shù)一般不大于5.

在應(yīng)用回退技術(shù)的過(guò)程中，需要推導(dǎo)出時(shí)間區(qū)間t∈T0,T內(nèi)每個(gè)回退點(diǎn)的位置信息.這里應(yīng)用洛倫茲變換理論，根據(jù)三角面片的頂點(diǎn)坐標(biāo)和運(yùn)動(dòng)狀態(tài)v，可以計(jì)算出任意時(shí)刻的三角面片位置信息.

通過(guò)遍歷集合QQ1,Q2,…,Qn包含的所有元素，并應(yīng)用回退技術(shù)計(jì)算出每對(duì)相交三角面片的初始相交時(shí)間，得出集合：

TT1,T2,…,Tn （10）

比較集合T中的元素，則最小時(shí)間為檢測(cè)對(duì)象初始碰撞時(shí)間記為Tmin .

4.2 初始碰撞位置的計(jì)算

兩個(gè)三角形初次相交時(shí)，必交于一點(diǎn)或者一條線段.若Tmin 對(duì)應(yīng)的三角面片對(duì)數(shù)目大于1，則三角形相交于一條線段.

設(shè)△ABC和△DEF是Tmin 時(shí)相交的一對(duì)三角形.設(shè)E1=B－A,E2=C－A和E3=E2－E1為△ABC的三條邊，N1=E1×E2為法線，{A+x1E1+x2E2}表示△ABC包含的點(diǎn)，其中(0≤x1≤1, 0≤x2≤1, x1+x2≤1).L1=E－D，L2=F－D和L3=L2－L1為△DEF三條邊，N2=L1×L2為法線，△DEF包含的點(diǎn)記為：{D+y1L1+y2L2}，其中(0≤y1≤1, 0≤y2≤1, y1+y2≤1).

則初始碰撞位置就轉(zhuǎn)換為計(jì)算Tmin 時(shí)兩個(gè)三角形交點(diǎn)P的問(wèn)題，即求解:

A+x1E1+x2E2－Tva=

D+y1L1+y2L2－Tvb（11）

其中T=Tk－Tmin ，va是碰撞檢測(cè)對(duì)象A的運(yùn)動(dòng)速度，vb是碰撞檢測(cè)對(duì)象B的運(yùn)動(dòng)速度.

設(shè)初始相交位置在△DEF的任意一條邊上，則有y1=0,y2=0;y1=1,y2=0和y1=0,y2=1三種情況.篩選出滿足條件(0≤x1≤1,0≤x2≤1)的x1和x2.如果x1或x2不在[0,1]范圍內(nèi)，則假設(shè)不成立.重新假設(shè)初始相交點(diǎn)的位置在△ABC的任意一條邊上，同理，根據(jù)x1=0,x2=0;x1=1,x2=0和x1=0,x2=1三種情況，篩選出滿足條件(0≤y1≤1,0≤y2≤1)的y1和y2.因?yàn)槿切蜗嘟唬砸欢苡?jì)算出滿足條件的系數(shù)x1，x2或系數(shù)y1，y2.

若計(jì)算出滿足條件的(0≤x1≤1,0≤x2≤1)的x1和x2.則把相應(yīng)的y1和y2代入D+y1L1+y2L2－Tvb得交點(diǎn)P的坐標(biāo).反之，則把x1和x2代入A+x1E1+x2E2－Tva得交點(diǎn)P的坐標(biāo).

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

常用基于分離軸的測(cè)試方案[10]，分別計(jì)算11個(gè)分離軸情況下，每一類分離軸有不同的3種情況（詳細(xì)內(nèi)容見文獻(xiàn)［10］），計(jì)算出相應(yīng)的x1和x2的系數(shù)，滿足條件時(shí)，則根據(jù)系數(shù)計(jì)算出P點(diǎn)的坐標(biāo).計(jì)算11×3次.

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

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

5 實(shí)例驗(yàn)證

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

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

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

M1={0:45 min ,刀架1,∑A1i,2 mm/s,刀架2,∑B1j,0.8 mm/s}

其中“0:45 min”是指某工步在45 s時(shí)發(fā)生碰撞現(xiàn)象，“刀架1”是碰撞對(duì)象1，∑Aki表示刀架1的幾何信息，“2 mm/s”刀架1沿碰撞方向的加工參數(shù)；“刀架2”是碰撞對(duì)象2，∑Bkj表示刀架2的幾何信息，“0.8 mm/s”是刀架2沿碰撞方向的加工參數(shù)；應(yīng)用CAD軟件導(dǎo)出stl文件的功能，選擇公差為0.08 mm，則導(dǎo)出發(fā)生碰撞的兩個(gè)對(duì)象的三角面片數(shù)量分別為864個(gè)和13 632個(gè).

應(yīng)用改進(jìn)的OBB包圍盒算法得出：刀架1上車刀的包圍盒中心坐標(biāo)Oa(91.5,151.5,0)，半軸長(zhǎng)分別為(71,67.5,50)，方向軸坐標(biāo)為（保留小數(shù)點(diǎn)后兩位）(－0.48,－0.72,－0.50;0.68,－0.67,0.31;－0.56,－0.19,0.81)；刀架2上鉆刀刀座的包圍盒中心坐標(biāo)Ob(217.5,0,0)，半軸長(zhǎng)分別為(55,170,170)，(1,0,0;0,1,0;0,0,1)為方向軸坐標(biāo).根據(jù)八叉樹空間分割法，可以計(jì)算出OBB層次包圍盒樹的每一個(gè)節(jié)點(diǎn)和子節(jié)點(diǎn)的包圍盒中心坐標(biāo)及半長(zhǎng)軸尺寸.

5.2 計(jì)算結(jié)果

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

W=W1,W2,W3,W4,W5

其中：

W1OBB_A135,OBB_B116

W2OBB_A155,OBB_B86

W3OBB_A235,OBB_B146

W4OBB_A135,OBB_B156

W5OBB_A76,OBB_B146.

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

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

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

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



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

Fig.3 The graph of collision in NC simulation

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

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

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



圖4 碰撞檢測(cè)計(jì)算流程圖

Fig.4Flow chart of collision detection algorithm

6 結(jié) 論

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

參考文獻(xiàn)

［1］ 吳寶海,嚴(yán)亞楠,羅明,等.車銑復(fù)合加工的關(guān)鍵技術(shù)與應(yīng)用前景[J].航空制造技術(shù),2010（19）:42-45. 

WU Baohai, YAN Yanan, LUO Ming, et al. 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, et al. Collision detection: a survey[C]//IEEE International Conference on Systems, Man and Cybernetics. Montreal Canada:IEEE, 2007:4046-4051.

［3］ 鄭錦銅,江銘鴻.剛性基礎(chǔ)上搖晃橋柱系統(tǒng)地震反應(yīng)研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版, 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］ 孟志強(qiáng),何濤,尹望吾,等.六角彈簧管汽車碰撞吸能裝置的效能研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版, 2011,38 (11):43-46. 

MENG Zhiqiang,HE Tao,YIN Wangwu,et al. 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, et al. 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ù)碰撞檢測(cè)算法[J].浙江大學(xué)學(xué)報(bào):工學(xué)版,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］ 康勇,熊岳山,費(fèi)先宏,等.基于空間分解和包圍盒層次的混合碰撞檢測(cè)算法[J].計(jì)算機(jī)仿真,2010（6）:191-193. 

KANG Yong, XIONG Yueshan, FEI Xianhong, et al.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/.

5.2 計(jì)算結(jié)果

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

W=W1,W2,W3,W4,W5

其中：

W1OBB_A135,OBB_B116

W2OBB_A155,OBB_B86

W3OBB_A235,OBB_B146

W4OBB_A135,OBB_B156

W5OBB_A76,OBB_B146.

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

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

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

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



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

Fig.3 The graph of collision in NC simulation

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

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

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



圖4 碰撞檢測(cè)計(jì)算流程圖

Fig.4Flow chart of collision detection algorithm

6 結(jié) 論

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

參考文獻(xiàn)

［1］ 吳寶海,嚴(yán)亞楠,羅明,等.車銑復(fù)合加工的關(guān)鍵技術(shù)與應(yīng)用前景[J].航空制造技術(shù),2010（19）:42-45. 

WU Baohai, YAN Yanan, LUO Ming, et al. 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, et al. Collision detection: a survey[C]//IEEE International Conference on Systems, Man and Cybernetics. Montreal Canada:IEEE, 2007:4046-4051.

［3］ 鄭錦銅,江銘鴻.剛性基礎(chǔ)上搖晃橋柱系統(tǒng)地震反應(yīng)研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版, 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］ 孟志強(qiáng),何濤,尹望吾,等.六角彈簧管汽車碰撞吸能裝置的效能研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版, 2011,38 (11):43-46. 

MENG Zhiqiang,HE Tao,YIN Wangwu,et al. 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, et al. 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ù)碰撞檢測(cè)算法[J].浙江大學(xué)學(xué)報(bào):工學(xué)版,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］ 康勇,熊岳山,費(fèi)先宏,等.基于空間分解和包圍盒層次的混合碰撞檢測(cè)算法[J].計(jì)算機(jī)仿真,2010（6）:191-193. 

KANG Yong, XIONG Yueshan, FEI Xianhong, et al.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/.

5.2 計(jì)算結(jié)果

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

W=W1,W2,W3,W4,W5

其中：

W1OBB_A135,OBB_B116

W2OBB_A155,OBB_B86

W3OBB_A235,OBB_B146

W4OBB_A135,OBB_B156

W5OBB_A76,OBB_B146.

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

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

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

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



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

Fig.3 The graph of collision in NC simulation

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

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

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



圖4 碰撞檢測(cè)計(jì)算流程圖

Fig.4Flow chart of collision detection algorithm

6 結(jié) 論

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

參考文獻(xiàn)

［1］ 吳寶海,嚴(yán)亞楠,羅明,等.車銑復(fù)合加工的關(guān)鍵技術(shù)與應(yīng)用前景[J].航空制造技術(shù),2010（19）:42-45. 

WU Baohai, YAN Yanan, LUO Ming, et al. 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, et al. Collision detection: a survey[C]//IEEE International Conference on Systems, Man and Cybernetics. Montreal Canada:IEEE, 2007:4046-4051.

［3］ 鄭錦銅,江銘鴻.剛性基礎(chǔ)上搖晃橋柱系統(tǒng)地震反應(yīng)研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版, 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］ 孟志強(qiáng),何濤,尹望吾,等.六角彈簧管汽車碰撞吸能裝置的效能研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版, 2011,38 (11):43-46. 

MENG Zhiqiang,HE Tao,YIN Wangwu,et al. 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, et al. 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ù)碰撞檢測(cè)算法[J].浙江大學(xué)學(xué)報(bào):工學(xué)版,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］ 康勇,熊岳山,費(fèi)先宏,等.基于空間分解和包圍盒層次的混合碰撞檢測(cè)算法[J].計(jì)算機(jī)仿真,2010（6）:191-193. 

KANG Yong, XIONG Yueshan, FEI Xianhong, et al.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/.