許 榮 張為民②

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

近年來，隨著虛擬現(xiàn)實(shí)、計(jì)算機(jī)仿真等技術(shù)的蓬勃發(fā)展，對(duì)碰撞檢測(cè)的實(shí)時(shí)性和精確性要求逐漸提高。在數(shù)控機(jī)床進(jìn)行加工前，刀具與夾具以及工件的碰撞需要運(yùn)用計(jì)算機(jī)仿真技術(shù)進(jìn)行在線實(shí)時(shí)碰撞檢測(cè)，防止加工中由于碰撞對(duì)機(jī)床造成損害［1］。所以實(shí)時(shí)碰撞檢測(cè)技術(shù)成為機(jī)床在線仿真當(dāng)中的關(guān)鍵技術(shù)。隨著機(jī)床三維幾何模型形狀越來越復(fù)雜，碰撞檢測(cè)成為一件很耗時(shí)的工作，因此在盡可能保證實(shí)時(shí)性和場(chǎng)景真實(shí)性的前提下，提高碰撞檢測(cè)算法的效率，成為研究人員面前一項(xiàng)迫切的任務(wù)，從而使得實(shí)時(shí)碰撞檢測(cè)再次成為研究的熱點(diǎn)。本文主要介紹了基于層次包圍盒的碰撞檢測(cè)算法在機(jī)床碰撞檢測(cè)系統(tǒng)中的應(yīng)用并對(duì)算法提出了優(yōu)化。

1 碰撞檢測(cè)算法概述

目前，國內(nèi)外許多學(xué)者對(duì)實(shí)時(shí)碰撞檢測(cè)技術(shù)進(jìn)行了廣泛深入的研究和探索，提出了距離跟蹤法、空間分解法、時(shí)空包圍盒法和層次包圍盒法等許多檢測(cè)算法。其中，主要有空間分解法和層次包圍盒法兩類算法。

空間分解法首先將對(duì)整個(gè)空間進(jìn)行體積相等的網(wǎng)格化剖分，然后僅僅對(duì)同一網(wǎng)格中的幾何對(duì)象進(jìn)行碰撞檢測(cè)［3］。典型的空間分解法有八叉樹法和二叉樹法。

而如今虛擬現(xiàn)實(shí)技術(shù)中比較通用的是層次包圍盒法，其核心思想是使用體積略大但幾何特性簡(jiǎn)單的包圍盒來近似描述復(fù)雜的對(duì)象，通過構(gòu)造樹狀層次結(jié)構(gòu)可以不斷逼近真實(shí)模型的幾何形狀，最后通過對(duì)包圍盒的相交計(jì)算來實(shí)現(xiàn)幾何物體的碰撞檢測(cè)。典型方法有軸向?qū)哟伟鼑?Axis－Aligned Bounding Boxes，AABB)、方向?qū)哟伟鼑?盒 (Oriented Bounding Boxes，OBB)、包 圍 球(Sphere)和離散方向多面體(8－Direction Orientation Polytopes，8 －DOP)等［2］，如圖1 所示。

這兩類算法都使用了層次結(jié)構(gòu)模型，其思想都是通過減少需要相交測(cè)試的對(duì)象或基本幾何元素的數(shù)目來提高碰撞檢測(cè)的效率?？臻g分解法由于存儲(chǔ)量大、靈活性差，一般適用于稀疏的環(huán)境中較均勻分布的幾何物體之間的碰撞檢測(cè);而層次包圍盒方法則應(yīng)用比較廣泛，尤其適用于復(fù)雜環(huán)境中的碰撞檢測(cè)。

2 機(jī)床碰撞檢測(cè)系統(tǒng)中包圍盒算法及其改進(jìn)

2.1 OBB方向包圍盒的定義及檢測(cè)方法

包圍盒OBB被定義為包含該對(duì)象且相對(duì)于坐標(biāo)軸方向的任意最小的正六面體。它的最大特點(diǎn)是方向任意性，可以根據(jù)被包圍對(duì)象的形狀特點(diǎn)盡可能緊密地包圍對(duì)象［4］。但是關(guān)鍵在于尋找包圍盒的最佳方向，然后確定在該方向上包圍盒的最小尺寸。假設(shè)模型中的基本幾何元素是三角形，設(shè)第i個(gè)三角形的頂點(diǎn)矢量為pi、qi和ri，則均值μ和協(xié)方差矩陣C計(jì)算式為

式中:n為包圍盒所包圍的三角形面元的數(shù)目;μ確定了包圍盒的中心位置;p－i=pi－μ，q－i=qi－ μ 和 r－i=ri－μ是所包圍區(qū)域內(nèi)的向量。協(xié)方差矩陣C的三個(gè)特征向量是正交的，正規(guī)化后可作為一個(gè)基底，確定包圍盒的方向軸，最后將所有的頂點(diǎn)投影到這條方向軸上，計(jì)算出在軸上的最大值和最小值，以此來確定包圍盒的大小。為了快速地判斷相交性，OBB檢測(cè)使用分離軸方法進(jìn)行檢測(cè)。在空間中，若存在一個(gè)向量，使兩個(gè)OBB在該向量上的投影不相交，那么這個(gè)向量即為一條分離軸。若一對(duì)OBB間存在一條分離軸，那么可判定這兩個(gè)OBB是不相交的。一對(duì)OBB包圍盒之間最多有15條潛在的分離軸，分別是每個(gè)OBB的3個(gè)面方向有3×2=6條潛在分離軸，每個(gè)OBB的3條邊方向的兩兩叉乘有3×3=9條潛在分離軸，一共是15條潛在分離軸。對(duì)每一條潛在分離軸分別采取區(qū)間檢測(cè)方法，計(jì)算出包圍盒八個(gè)頂點(diǎn)的坐標(biāo)值、每個(gè)頂點(diǎn)在分離軸上的投影，比較他們的大小。方法如圖2。

假設(shè)兩個(gè)OBB分別為A和B，ai和bi表示A、B邊長的一半，Ai和Bi表示A、B軸向的單位向量(i=1，2，3);T是A、B中心點(diǎn)的距離，L是當(dāng)前的分離軸向量。有如下公式(2):

如果滿足前者大于后者，那么兩個(gè)物體不相交;否則按此公式繼續(xù)計(jì)算A、B在其他14條分離軸上的投影。在最多進(jìn)行15次計(jì)算之后如果還不能把兩個(gè)OBB分開，可以判定這兩個(gè)物體是相交的。由此可見，創(chuàng)建階段和比較階段都很復(fù)雜，過程包括了大量的運(yùn)算。

2.2 基于OBB包圍盒算法的機(jī)床碰撞檢測(cè)系統(tǒng)

采用基于層次包圍盒樹的碰撞檢測(cè)算法，在機(jī)床上建立有效的碰撞檢測(cè)系統(tǒng)，實(shí)現(xiàn)實(shí)時(shí)加工碰撞的檢測(cè)。

首先是機(jī)床、刀具和工件的實(shí)體建模階段。即準(zhǔn)確描述機(jī)床、工件和刀具的運(yùn)動(dòng)狀態(tài)，在OpenGL軟件環(huán)境下建立模型，實(shí)現(xiàn)機(jī)床模型和工件模型的三角面片化，為后面層次包圍盒二叉樹建模做準(zhǔn)備，另外實(shí)現(xiàn)G代碼的解析工作，將G代碼解析后生成指令來驅(qū)動(dòng)模型運(yùn)動(dòng)。

其次在機(jī)床幾何模型基礎(chǔ)上建立OBB包圍盒樹模型，實(shí)現(xiàn)碰撞檢測(cè)。結(jié)合機(jī)床的結(jié)構(gòu)，銑刀頭運(yùn)動(dòng)方式(轉(zhuǎn)角范圍、刀具尺寸及形狀等)以及工件的建模來確定可能發(fā)生碰撞的系統(tǒng)部件，對(duì)其進(jìn)行包圍盒樹的構(gòu)建，運(yùn)用分離軸理論，實(shí)現(xiàn)基于包圍盒樹算法的碰撞檢測(cè)。另外，應(yīng)用西門子的OEM開發(fā)包，實(shí)現(xiàn)碰撞檢測(cè)系統(tǒng)與機(jī)床數(shù)控系統(tǒng)的嵌入集成。圖3為虛擬環(huán)境中應(yīng)用OpenGL建立的機(jī)床三維幾何模型;圖4為機(jī)床碰撞檢測(cè)系統(tǒng)的顯示界面。

2.3 包圍盒算法優(yōu)化

由于OBB包圍盒的中心位置是各三角形面片頂點(diǎn)簡(jiǎn)單的平均，當(dāng)模型存在弧度或凹凸時(shí)，構(gòu)成模型表面的三角形面片尺寸就會(huì)不均勻，有的尺寸大而分散，有的尺寸小且密集，這樣計(jì)算出來的包圍盒整體就會(huì)向著三角形尺寸小且密集的部分偏移。這種情況對(duì)最后碰撞檢測(cè)的結(jié)果存在不利影響，可能會(huì)出現(xiàn)誤判。因?yàn)橛幸徊糠秩切蚊嫫诎鼑械耐饷?，同時(shí)包圍盒有一個(gè)與包圍盒平行的較小的長方體空隙，這樣就使得包圍盒緊密性變差，而且會(huì)使構(gòu)造的包圍盒樹不平衡，影響到碰撞檢測(cè)的效率。尤為嚴(yán)重的是存在某些情況，即那些在包圍盒外面的三角形已經(jīng)與其他物體接觸了，但包圍盒檢測(cè)時(shí)沒有檢測(cè)出接觸，于是錯(cuò)誤地?cái)喽ㄋ鼑娜切尾唤佑|，導(dǎo)致錯(cuò)誤的檢測(cè)結(jié)果。此外，這對(duì)協(xié)方差矩陣也有影響，導(dǎo)致包圍盒方向向量的計(jì)算不準(zhǔn)確，對(duì)包圍盒的緊密性造成影響。這樣就需要對(duì)傳統(tǒng)的OBB包圍盒算法提出優(yōu)化的解決方法。

優(yōu)化方法是給每一個(gè)三角形加權(quán)，選擇三角形的面積作為權(quán)值。設(shè)第i個(gè)三角形的面積用Si表示，包圍盒所包圍的物體表面積用S表示，第i個(gè)三角形的中心用ni表示，包圍盒所包圍的三角形帶權(quán)中心用n表示，則公式如下:

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

3 實(shí)驗(yàn)測(cè)試

實(shí)驗(yàn)環(huán)境是在西門子840D數(shù)控系統(tǒng)的機(jī)床碰撞檢測(cè)系統(tǒng)中，實(shí)現(xiàn)了本文優(yōu)化的OBB碰撞檢測(cè)算法。分別測(cè)試了兩個(gè)場(chǎng)景的碰撞檢測(cè)的時(shí)間，兩個(gè)場(chǎng)景中機(jī)床模型分別在不同G代碼的驅(qū)動(dòng)下，完成碰撞檢測(cè)。場(chǎng)景1中為圓柱面刀具與長方體刀架的碰撞，場(chǎng)景2為圓環(huán)面刀具與機(jī)床尾架的碰撞。圖5為碰撞發(fā)生時(shí)機(jī)床的響應(yīng)結(jié)果，圖6為兩種算法的耗時(shí)結(jié)果對(duì)比。

由實(shí)驗(yàn)結(jié)果可以看出，采用優(yōu)化的碰撞檢測(cè)算法較之原始算法有大約20%的性能上的改進(jìn)，并且當(dāng)場(chǎng)景的規(guī)模越大時(shí)，算法改進(jìn)的效率也越高。

4 結(jié)語

OBB層次包圍盒廣泛應(yīng)用于數(shù)控機(jī)床的碰撞檢測(cè)中，且緊密性較好，但存在一些誤檢測(cè)情況。本文根據(jù)OBB的算法特點(diǎn)，提出并實(shí)現(xiàn)了優(yōu)化的OBB碰撞檢測(cè)算法。實(shí)驗(yàn)結(jié)果證明，本文的優(yōu)化算法能較大幅度地提高碰撞檢測(cè)的實(shí)時(shí)性能，且效果明顯。

［1］許瑋，張為民，金致富.基于西門子840D數(shù)控系統(tǒng)的防碰撞技術(shù)研究［J］.制造技術(shù)與機(jī)床，2010(11):33－36.

［2］何偉，李勇，蘇虎.碰撞檢測(cè)中的包圍盒方法［J］.重慶工學(xué)院學(xué)報(bào)，2007(12).

［3］龍春國，史耀耀，程剛，等.基于OpenGL五軸聯(lián)動(dòng)數(shù)控仿真系統(tǒng)碰撞干涉檢驗(yàn)實(shí)時(shí)仿真技術(shù)及算法研究［J］.機(jī)床與液壓，2006(2).

［4］Christer Ericson.Real－ time collision detection［M］.Elsevier Science Ltd.，2005.