陳 晨 張為民 褚 寧

(①同濟(jì)大學(xué)中德學(xué)院，上海 200092;②同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院，上海 201804)

五軸數(shù)控機(jī)床相比普通三軸機(jī)床多出兩個(gè)旋轉(zhuǎn)自由度，因此更容易發(fā)生各部件之間的碰撞干涉，其碰撞干涉檢測一直都是五軸數(shù)控加工中的關(guān)鍵難題之一［1］。在各種碰撞算法中，層次包圍盒法近年來得到了廣泛的應(yīng)用，它的設(shè)計(jì)思想是用體積稍大而特征比較簡單的包圍盒來描述待測的幾何實(shí)體，并將包圍盒與某種樹型結(jié)構(gòu)結(jié)合起來，從而形成層次結(jié)構(gòu)來逐步逼近幾何實(shí)體，根據(jù)包圍盒層次結(jié)構(gòu)建立層次包圍體樹，再遍歷兩個(gè)模型的包圍體樹來逐漸縮小模型的檢測區(qū)域，以此減少整體的檢測次數(shù)［2］。由于包圍盒與幾何實(shí)體之間通常存在一定的間隙，所以當(dāng)檢測到葉節(jié)點(diǎn)的包圍盒相交時(shí)，需進(jìn)一步進(jìn)行基于三角形面片相交測試的精檢測算法。傳統(tǒng)的OBB包圍盒和三角形相交算法存在精度和實(shí)時(shí)性上的不足，本文針對五軸機(jī)床的運(yùn)動(dòng)特性，對算法進(jìn)行了改進(jìn)。

1 基于層次包圍盒的碰撞干涉粗檢測

常用的包圍盒包括:包圍球(Sphere)，沿坐標(biāo)軸的包圍盒AABB(Axis－Aligned Bounding Boxes)，固定方向包圍盒 FDH(Fixed Directions Hulls)，方向包圍盒OBB(Oriented Bounding Box)［3］。其中 OBB 包圍盒曾一度作為評價(jià)碰撞檢測算法的標(biāo)準(zhǔn)，它的計(jì)算相對復(fù)雜，但緊密性是最好的。在大多數(shù)情況下，OBB包圍盒的總體性能比AABB和包圍球要好很多［4］。

1.1 OBB包圍盒樹存儲(chǔ)方式的優(yōu)化

當(dāng)兩個(gè)幾何實(shí)體的OBB層次包圍盒樹建立后，通過遍歷兩棵包圍盒樹對兩個(gè)包圍盒進(jìn)行相交測試:當(dāng)兩個(gè)包圍盒不相交時(shí)，以該包圍盒為根節(jié)點(diǎn)的子樹停止檢測;當(dāng)兩個(gè)包圍盒相交時(shí)，則對該節(jié)點(diǎn)的葉子節(jié)點(diǎn)進(jìn)行相交檢測;當(dāng)檢測到葉子結(jié)點(diǎn)的包圍盒相交時(shí)，則執(zhí)行基于三角形面片相交測試的精檢測，其流程圖如圖1所示。

采用二叉樹來構(gòu)造包圍盒樹時(shí)，用遞歸的方法劃分包圍盒，根據(jù)子節(jié)點(diǎn)相對于分裂軸的空間位置將父節(jié)點(diǎn)劃分為兩個(gè)子集，直至每個(gè)葉結(jié)點(diǎn)只包含一個(gè)三角形面片為止。每個(gè)節(jié)點(diǎn)里存儲(chǔ)了所對應(yīng)的包圍盒信息，而葉子節(jié)點(diǎn)里還包括三角形的幾何信息，如圖2a所示。對于含有N個(gè)葉子節(jié)點(diǎn)的包圍盒樹來說，其需要存儲(chǔ)的節(jié)點(diǎn)數(shù)目為2N－1個(gè)，如果將原葉子節(jié)點(diǎn)的三角形信息放在其父節(jié)點(diǎn)里，跳過葉子節(jié)點(diǎn)包圍盒間的相交測試，直接進(jìn)行基本幾何元素間的相交測試，這樣只需要存儲(chǔ)N－1個(gè)節(jié)點(diǎn)，基本去掉了一半的節(jié)點(diǎn)，從而節(jié)省了存儲(chǔ)空間。在進(jìn)行檢測的時(shí)候，需要遍歷的節(jié)點(diǎn)數(shù)目也明顯減少，優(yōu)化后的包圍盒存儲(chǔ)結(jié)構(gòu)如圖2b所示。

1.2 傳統(tǒng)OBB包圍盒構(gòu)造算法分析

本文中待測對象的存儲(chǔ)方式是基于三角形網(wǎng)格模型的STL格式，三角形的頂點(diǎn)集合可以看作是三變量的概率分布函數(shù)，則OBB包圍盒的中心位置和方向可以利用三角形頂點(diǎn)的均值和協(xié)方差矩陣來計(jì)算。若第i個(gè)三角形頂點(diǎn)矢量為 pi，qi和 ri，三角面片的總數(shù)為n，則包圍盒中心位置為:

其協(xié)方差矩陣元素為:

求解Cjk的特征向量并單位化。因?yàn)镃jk是一個(gè)實(shí)對稱矩陣，所以其特征向量相互垂直，令它們作為包圍盒的方向軸。將所有頂點(diǎn)投影到這3條方向軸上，計(jì)算出在軸上的最大和最小值，以此來確定包圍盒的大小。

包圍盒的中心位置是各個(gè)三角形頂點(diǎn)的簡單平均，所以當(dāng)構(gòu)成幾何實(shí)體的三角形的尺寸不均勻時(shí)，包圍盒就會(huì)偏向三角形尺寸較小、分布較密的部分。這樣就會(huì)導(dǎo)致包圍盒和幾何實(shí)體發(fā)生錯(cuò)位，顯然這樣會(huì)使包圍盒的緊密性變差，并且使構(gòu)造的包圍盒樹不平衡，從而影響到碰撞檢測的效率和準(zhǔn)確性。

1.3 OBB包圍盒構(gòu)造算法優(yōu)化

選擇三角形的面積作為權(quán)值，給每個(gè)三角形進(jìn)行加權(quán)。設(shè)第i個(gè)三角形的面積為Si，則:

三角形面片表示的幾何實(shí)體表面積為S，則:

第i個(gè)三角形的中心為Mi，則:

包圍盒所包圍的三角形帶權(quán)中心為M，則:

協(xié)方差矩陣C的元素為:

以此得到更精確緊密的OBB包圍盒，包圍盒間的相交測試可以看成某一個(gè)盒體是否完全位于另一個(gè)盒體某一面之外，凸塊OBB包圍盒的相交檢測采用了Gottschalk［5］等基于分離軸定理提出的檢測方法。如果包圍盒間存在一條分離軸，那么可以判定它們是不相交的。

2 基于三角形面片的碰撞干涉精檢測

2.1 三角形圖元之間相交測試

提高碰撞檢測的實(shí)時(shí)性一般從兩方面入手:一是減少整體的檢測次數(shù)，例如采用上文的層次樹;二是減少圖元之間相交檢測的時(shí)間，因此研究快速的三角形相交檢測算法有著十分重要的意義。

三角形快速相交檢測算法主要可以分為標(biāo)量判別型算法和矢量判別型算法。標(biāo)量判別型算法是通過準(zhǔn)確計(jì)算來獲知兩個(gè)三角形相交關(guān)系的一類算法，典型的有M?ller、Held和Tropp算法;矢量判別型算法是通過三角形各頂點(diǎn)構(gòu)成的行列式的正負(fù)幾何意義來判斷三角形中點(diǎn)、線、面間的相對位置關(guān)系，進(jìn)而判斷兩個(gè)三角形是否相交，典型的有Devillers＆Guigue算法和Shen算法［6］。本文在前面幾種算法的分析基礎(chǔ)上，提出了一種優(yōu)化算法，該算法可以在判斷三角形是否相交的同時(shí)，得到相交的具體位置及深度信息，避免了復(fù)雜的三角形所在平面的計(jì)算，從而加快了計(jì)算速度，保證了系統(tǒng)的實(shí)時(shí)性。

2.2 空間三角形快速檢測算法優(yōu)化

如圖3所示:邊Q1Q2所在的直線方程可以表示為L(t)=Q1+tD，其中 D=Q1－Q2。

設(shè)I(u，v)為ΔP1P2P3內(nèi)任意一點(diǎn)，則其可以表示為:

其中:u≥0，v≥0 且 u+v≤1。

求直線L(t)和ΔP1P2P3所在平面的交點(diǎn)可以等價(jià)于求解 L(t)=I(u，v)，即:

其中:t即為點(diǎn)Q1到三角形平面的距離。整理方程得:

令 D0=Q1－P1，D1=P2－P1，D2=P3－P1，則方程可以轉(zhuǎn)換為:

又由|X Y Z|=－(X×Z)·Y=－(Z×Y)·X可將方程進(jìn)一步轉(zhuǎn)換為:

為了提高算法效率，首先計(jì)算u的值，若0≤u≤1，再計(jì)算v，以此求出交點(diǎn)I的坐標(biāo)，比較Q1、Q2及I任意一軸向方向上的值，便可判斷 Q1、Q2兩點(diǎn)是否在ΔP1P2P3的兩側(cè);若 u＜0或 u＞0，則不再計(jì)算 v，轉(zhuǎn)而計(jì)算ΔQ1Q2Q3的其他兩條邊是否穿過ΔP1P2P3。當(dāng)確定兩個(gè)三角形已經(jīng)相交時(shí)，計(jì)算t的值，即為Q1點(diǎn)離ΔP1P2P3所在平面的值。

2.3 三角形相交檢測算法計(jì)算量比較

檢測算法的時(shí)間消耗主要取決于開辟內(nèi)存和數(shù)學(xué)運(yùn)算兩部分，開辟內(nèi)存又取決于算法中所使用的變量數(shù)，而數(shù)學(xué)運(yùn)算包括四則運(yùn)算、比較運(yùn)算、絕對值運(yùn)算和賦值運(yùn)算。目前主流的PC與數(shù)控系統(tǒng)中，加、減、乘和比較的計(jì)算時(shí)間可以認(rèn)為是相同的，賦值運(yùn)算的計(jì)算時(shí)間相對而言可以忽略，除法的計(jì)算時(shí)間大約是加法的4～8倍［7］。表1是檢測如圖3所示兩個(gè)三角形相交時(shí)各種算法所使用的變量數(shù)以及計(jì)算量的比較［8］:

表1 各種三角形相交檢測算法使用變量數(shù)及計(jì)算量比較

經(jīng)過比較可以發(fā)現(xiàn)，優(yōu)化算法所需的變量數(shù)較少，而且盡管提出的優(yōu)化算法里有3個(gè)除法運(yùn)算，但是加減法和乘法運(yùn)算較其他幾種算法明顯減少，所以總的計(jì)算量得以大幅度減小，從而提高了算法的效率。而且待檢測物體和參與運(yùn)算的圖元數(shù)量越多，優(yōu)化算法的優(yōu)越性就越明顯。

3 仿真實(shí)驗(yàn)

首先用Solidworks作圖軟件建立某車銑復(fù)合加工中數(shù)控機(jī)床的簡化模型，使用OpenGL圖形庫對機(jī)床工作場景進(jìn)行描述，并導(dǎo)出為基于三角形網(wǎng)格模型的STL格式。機(jī)床各部件所包含面片個(gè)數(shù)如表2所示。

表2 機(jī)床各部件所含三角形面片數(shù)

模擬兩種情況下的進(jìn)給運(yùn)動(dòng):(1)令刀具沿Z軸方向靠近工件和三爪卡盤，進(jìn)給速度為100 mm/min;(2)令刀具作A旋轉(zhuǎn)軸上的運(yùn)動(dòng)，進(jìn)給速度為270°/min，如圖4所示。仿真運(yùn)行環(huán)境為:Pentium(R)Dual－ Core CPU E5400 2.70 GHz，內(nèi)存2.0 GB，Windows 7系統(tǒng)，測試用VC++語言實(shí)現(xiàn)。

令刀具在兩種運(yùn)動(dòng)形式中依次與工件和三爪卡盤發(fā)生碰撞干涉，分別使用包圍盒樹未經(jīng)優(yōu)化情況下的Tropp算法，Shen算法和三角形優(yōu)化算法，以及包圍盒樹和三角形都經(jīng)優(yōu)化過的算法進(jìn)行碰撞檢測，并采集檢測算法所需時(shí)間，耗時(shí)結(jié)果如表3所示。

表3 算法優(yōu)化前后耗時(shí)結(jié)果對比 ms

結(jié)果表明優(yōu)化算法有效地加快了碰撞檢測的速度，而且待檢測三角形數(shù)目越多，效果越明顯。

4 結(jié)語

本文將基于OBB包圍盒的碰撞干涉檢測優(yōu)化為粗檢測和精檢測兩部分，粗檢測采用改進(jìn)的OBB層次包圍盒算法，精檢測采用基于三角形面片相交檢測的優(yōu)化算法，在保證運(yùn)算精度的情況下提高了檢測速度。在粗檢測部分通過省去二叉樹結(jié)構(gòu)中葉子節(jié)點(diǎn)，直接進(jìn)行基本圖元間的相交測試，從而改善了包圍盒樹的存儲(chǔ)結(jié)構(gòu)，采用改進(jìn)的OBB包圍盒構(gòu)造算法保證了包圍盒的緊密性和準(zhǔn)確性。在精檢測部分提出了一種基于三角形面片相交檢測的優(yōu)化算法。該算法不僅能夠快速有效地判斷出兩個(gè)三角形面片之間是否存在相交情況，而且能夠快速地計(jì)算出交點(diǎn)的具體位置以及相交的深度值，從而提高了碰撞檢測的精度。通過仿真實(shí)驗(yàn)，驗(yàn)證了該優(yōu)化算法的有效性。

［1］Ding S，Mannan Ma，Poo An.Oriented bounding box and octree based global interference detection in 5－axis machining of free－form surfaces［J］.Computer－ Aided Design，2004，36:1281 －1294.

［2］朱曉耀.數(shù)控系統(tǒng)在線防碰撞系統(tǒng)的碰撞檢測算法的設(shè)計(jì)與實(shí)現(xiàn)［D］.上海:同濟(jì)大學(xué)，2011:20 －21.

［3］石教英.虛擬現(xiàn)實(shí)基礎(chǔ)及使用算法［M］.北京:科學(xué)出版社，2002.

［4］趙呈浩.數(shù)控機(jī)床仿真系統(tǒng)的碰撞檢測算法［D］.天津:天津大學(xué)，2010:9－10.

［5］Gottschalk S，Lin M C，Manocha D.OBBTrees:A hierarchical structure for rapid interference detection［C］.New York:SIGGRAPH ＇96 Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques，1996:171－180.

［6］門曉鵬，呂曉峰，馬登武，等.虛擬場景中基本幾何元素相交測試技術(shù)［J］.海軍航空工程學(xué)院學(xué)報(bào)，2006，21(3):379 －382.

［7］Devillers O，Guigue P.Faster triangle － triangle intersection tests，TR 4488［R］.［S.I.］:INRIA，2002.

［8］鄒益勝，丁國富，何邕，等.空間三角形快速相交檢測算法［J］.計(jì)算機(jī)應(yīng)用研究，2008，25(10):2906 －2910.