基于三維物體特征圖的動(dòng)態(tài)碰撞檢測方法

馬 禮1，王 強(qiáng)1，楊銀剛2，馬東超1，張永梅1

（1.北方工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，北京 100144；2.北京信息高技術(shù)研究所，北京 100094）

基于三維物體特征圖的動(dòng)態(tài)碰撞檢測方法

馬 禮1，王 強(qiáng)1，楊銀剛2，馬東超1，張永梅1

（1.北方工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，北京 100144；2.北京信息高技術(shù)研究所，北京 100094）

碰撞是多機(jī)器人系統(tǒng)作業(yè)過程中一定要避免的關(guān)鍵問題，碰撞檢測對(duì)系統(tǒng)安全、避障策略至關(guān)重要；針對(duì)現(xiàn)有碰撞檢測方法在結(jié)構(gòu)復(fù)雜的多機(jī)器人系統(tǒng)，特別是高精度作業(yè)中檢測精度不能滿足實(shí)際的問題，提出了一種基于物體特征圖的碰撞檢測方法；該方法根據(jù)不同物體的結(jié)構(gòu)特征，構(gòu)造出能夠緊密包裹該物體的特征圖，以遍歷特征圖的方式檢測物體間的碰撞；同時(shí)，結(jié)合使用碰撞檢測掩碼方法實(shí)現(xiàn)動(dòng)態(tài)碰撞檢測，以提高碰撞檢測效率；通過實(shí)驗(yàn)分析表明，該方法比傳統(tǒng)的碰撞檢測方法擁有更高的碰撞檢測精度以及檢測效率。

多機(jī)器人；碰撞檢測；特征圖檢測；精度動(dòng)態(tài)檢測

0 引言

碰撞檢測是檢測空間中的運(yùn)動(dòng)物體是否發(fā)生接觸以及干涉的重要技術(shù)，所以也是多機(jī)器人系統(tǒng)開發(fā)過程中最為重要的研究內(nèi)容之一。隨著多機(jī)器人仿真場景中物體數(shù)目的增多以及三維模型復(fù)雜度的不斷增加，對(duì)場景中碰撞檢測功能的實(shí)時(shí)性、精確性以及真實(shí)性等提出了越來越大的挑戰(zhàn)。當(dāng)今主要的虛擬環(huán)境碰撞檢測方法分為基于圖形的碰撞檢測方法和基于圖像的碰撞檢測方法，而基于圖形的碰撞檢測方法由于其不需要過多依賴機(jī)器硬件的性能而得到了越來越廣泛的重視和研究。到目前為止，已經(jīng)有許多學(xué)者包括商業(yè)公司對(duì)虛擬場景中的碰撞檢測做了大量的研究，也得出了一些非常實(shí)用的碰撞檢測方法，如空間分割法和包圍盒法。

針對(duì)傳統(tǒng)的碰撞檢測方法存在的檢測精度低以及檢測效率低等問題并結(jié)合模型構(gòu)造復(fù)雜的多機(jī)器人仿真研究的實(shí)際，提出一種新型的基于模型特征圖的動(dòng)態(tài)碰撞檢測方法。通過實(shí)驗(yàn)表明該方法相比傳統(tǒng)的碰撞檢測方法具有更高的檢測效率以及更高的檢測精度，能夠極大增強(qiáng)多機(jī)器人仿真系統(tǒng)的真實(shí)感。

1 新型碰撞檢測方法的提出

1.1 空間分割方法

空間分割方法是將整個(gè)仿真場景分割成為一個(gè)個(gè)更小的區(qū)域，而每一次運(yùn)動(dòng)物體只檢測所在運(yùn)動(dòng)區(qū)域內(nèi)的對(duì)象物體。該方法可以減少每一次碰撞檢測的檢測對(duì)象，從而獲得較高的檢測效率，因?yàn)槊看味贾恍枰獧z測運(yùn)動(dòng)物體所在的網(wǎng)格范圍內(nèi)的物體。張振華等［1］對(duì)基于空間域的碰撞檢測算法作了詳細(xì)的介紹和分析；張國飚等［2］利用物體空間分布特性以及實(shí)時(shí)碰撞的局部性，使用空間剖分的方法并結(jié)合包圍盒檢測方法，完成了場景布局相對(duì)簡單的運(yùn)動(dòng)物體模型的碰撞檢測，得到了較好的運(yùn)行效率；Johannes Schauer［3］等使用空間分割的K－D樹方法實(shí)現(xiàn)了點(diǎn)云模型的碰撞檢測，獲得了很高的檢測效率和準(zhǔn)確度。

1.2 包圍盒方法

包圍盒方法是通過使用簡單的幾何模型來虛擬外形復(fù)雜的物體，然后使用簡單的幾何模型來進(jìn)行碰撞檢測，如果包圍盒之間發(fā)生干涉，則說明發(fā)生碰撞，如果包圍盒沒有發(fā)生干涉，則說明沒有發(fā)生碰撞。包圍盒方法可以簡化原有模型的結(jié)構(gòu)復(fù)雜度，從而極大減少碰撞檢測計(jì)算量，加快系統(tǒng)的執(zhí)行效率。Yao Wang等［4］使用包圍盒方法完成了數(shù)控機(jī)床仿真中的碰撞檢測，因?yàn)閿?shù)控機(jī)床中的物體模型相對(duì)簡單，而且流程也相對(duì)固定；陳琳［5］等使用層次包圍盒方法實(shí)現(xiàn)了多機(jī)器人系統(tǒng)的碰撞檢測，該方法能夠獲得較高的碰撞檢測效率，但是只是適用于物體外形相對(duì)規(guī)則的連桿機(jī)器人，針對(duì)結(jié)構(gòu)造型復(fù)雜的物體卻難以實(shí)現(xiàn)高精度的碰撞檢測；姜光焱［6］使用OBB和AABB層次包圍盒，實(shí)現(xiàn)的碰撞檢測方法相比RAPID方法有了更高的檢測效率。

空間分割方法對(duì)于處于兩個(gè)或者多個(gè)網(wǎng)格之間的物體的不會(huì)被納入檢測目標(biāo)，所以該方法比較適合場景中物體分部比較均勻的場合，這樣可以使得劃分的網(wǎng)格盡量包含所有的物體。但是對(duì)于場景復(fù)雜的多機(jī)器人系統(tǒng)，可能由于各個(gè)網(wǎng)格不能完全包括所有的物體而出現(xiàn)漏檢情況。對(duì)于復(fù)雜構(gòu)型的機(jī)器人結(jié)構(gòu)，簡單的立方體或者圓柱體等集合模型往往難以近似的表示其外形，而且會(huì)過多擴(kuò)大原有物體的輪廓，特別是針對(duì)凹多面體而言，包圍盒方法更加會(huì)放大原有物體的外表輪廓，從而會(huì)出現(xiàn)過檢的情況。

同時(shí)，傳統(tǒng)的碰撞檢測方法往往需要多種檢測方法的配合使用才能完成較好的碰撞檢測效果。比如包圍盒和空間分割的混合碰撞檢測方法［7］，然而這樣的碰撞檢測方法需要經(jīng)過至少一次初步檢以及至少一次再檢測，使得算法復(fù)雜度極高，檢測效率和精度都難以達(dá)到要求。

基于以上分析，提出一種基于物體模型特征圖的碰撞檢測方法。該方法通過提取物體表面的特征點(diǎn)，然后依據(jù)特征點(diǎn)構(gòu)造一個(gè)能夠緊密包圍物體模型的特征圖，最后使用特征圖的邊與碰撞檢測目標(biāo)的表面進(jìn)行干涉檢測以完成碰撞檢測，這樣可以提高碰撞檢測的精確度。同時(shí)，依據(jù)運(yùn)動(dòng)物體的運(yùn)動(dòng)路徑，以及物體運(yùn)動(dòng)的時(shí)間及空間局部性，使用掩碼方法，動(dòng)態(tài)的設(shè)置碰撞檢測的目標(biāo)，使得運(yùn)動(dòng)物體只需要檢測處于運(yùn)動(dòng)路徑周圍的物體，從而減少了每一次碰撞檢測的檢測對(duì)象數(shù)量，可以使碰撞檢測的效率得到極大提高。

2 基于特征圖的碰撞檢測方法

基于物體模型特征圖的碰撞檢測方法能夠極大限度的接近物體外形，從而可以實(shí)現(xiàn)高精度的碰撞檢測。依據(jù)物體表面特征點(diǎn)構(gòu)造特征圖，再用特征圖的邊來檢測碰撞情況，將以往的面面求交算法簡化為了線面求交。此外，根據(jù)物體的運(yùn)動(dòng)路徑，使用掩碼方法實(shí)現(xiàn)了碰撞檢測目標(biāo)的動(dòng)態(tài)設(shè)置，也極大提高了系統(tǒng)中碰撞檢測算法的執(zhí)行效率。該方法需要完成的工作有：

1）提取物體模型特征點(diǎn)；

2）根據(jù)體征點(diǎn)生成物體特征圖；

3）根據(jù)路徑獲取物體的運(yùn)動(dòng)范圍；

4）設(shè)置碰撞掩碼，以實(shí)現(xiàn)動(dòng)態(tài)設(shè)置檢測目標(biāo)。

2.1 提取物體模型特征點(diǎn)

為了實(shí)現(xiàn)基于物體特征圖的碰撞檢測功能，需要先提取運(yùn)動(dòng)物體的表面特征點(diǎn)。根據(jù)仿真系統(tǒng)中模型的構(gòu)建過程可以知道，場景中的物體模型都是由多個(gè)面片構(gòu)成，所以可以依據(jù)面片之間的鄰接線端點(diǎn)來選取特征點(diǎn)。依據(jù)鄰接面所構(gòu)成的夾角，鄰接線存在谷線和脊線兩種情況，以下對(duì)兩種情況的特征點(diǎn)提取做進(jìn)一步分析。

1）谷線特征點(diǎn)：如圖1所示，物體模型的面片α與β的法線分別是，l是α與β的鄰接線。由于α與β構(gòu)成了山谷形狀，所以l就是谷線。設(shè)定θ為二面角α－l－β的大小，則θ＝π，若θ＜ε（ε為設(shè)定的角度閾值），則鄰接線l的端點(diǎn)A、B為運(yùn)動(dòng)物體的兩個(gè)特征點(diǎn)。

2）脊線特征點(diǎn)：如圖2所示，物體模型的面片α與β的法線分別是n■，l是α與β的鄰接線。由于α與β構(gòu)成了山脊形狀，所以l就是脊線。設(shè)定θ為二面角α－l－β的大小，則，若θ＞ε（ε為設(shè)定的角度閾值），則鄰接線l的端點(diǎn)A、B為運(yùn)動(dòng)物體的兩個(gè)特征點(diǎn)。

根據(jù)以上的基礎(chǔ)算法分析，通過依次遍歷運(yùn)動(dòng)物體模型的各個(gè)面片，分別對(duì)相鄰面片的夾角進(jìn)行計(jì)算，就可以提取得到運(yùn)動(dòng)物體模型表面的所有特征點(diǎn)。針對(duì)不同復(fù)雜度的運(yùn)動(dòng)物體模型，可以通過設(shè)置ε的值來限制提取到的特征點(diǎn)數(shù)目。在提取特征點(diǎn)的同時(shí)，將特征點(diǎn)存入物體的特征點(diǎn)集合V。成功提取出特征點(diǎn)的物體模型如圖3所示。

圖1 谷線特征點(diǎn)

圖2 脊線特征點(diǎn)

2.2 根據(jù)物體特征點(diǎn)生成特征圖

由于碰撞檢測精度的要求，最理想的情況就是使用運(yùn)動(dòng)物體的表面輪廓線進(jìn)行檢測，如果運(yùn)動(dòng)物體的表面輪廓線與被檢測對(duì)象物體的表面發(fā)生相交，就說明發(fā)生了碰撞。在3.1節(jié)中，已經(jīng)成功提取出了物體表面的特征點(diǎn)，此處就以這些特征點(diǎn)作為特征圖的頂點(diǎn)構(gòu)造一個(gè)運(yùn)動(dòng)物體特征圖的簡單回路，該圖就是最接近物體輪廓的一個(gè)網(wǎng)狀結(jié)構(gòu)。

此處假設(shè)提取出的特征點(diǎn)集合V＝｛v1，v2，v3...vn｝（n為特征點(diǎn)的個(gè)數(shù)）。為了表示生成的圖，需要用到式（1）所示的鄰接矩陣。

式中，n表示圖中節(jié)點(diǎn)的個(gè)數(shù)，也就是提取出的運(yùn)動(dòng)物體特征點(diǎn)的數(shù)目。若aij＝0（i，j∈［1，n］），表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間沒有連線；反之，若aij＝1，則表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間有連線。

初始化的鄰接矩陣G中每個(gè)元素的值都為0，夠造簡單回路的同時(shí)需要修改G中元素的值，由于連接頂點(diǎn)的線段不需要有方向及代價(jià)信息，所以構(gòu)造的是一個(gè)無向圖。若提取4個(gè)特征點(diǎn)，則構(gòu)造的特征圖的鄰接矩陣就該如式（2）所示。由于無向圖的鄰接矩陣是對(duì)稱矩陣，所以可以采取壓縮存儲(chǔ)來存儲(chǔ)鄰接矩陣。

由于特征圖的節(jié)點(diǎn)信息已經(jīng)存放在特征點(diǎn)集合V中，所以只需要根據(jù)V中的節(jié)點(diǎn)構(gòu)造簡單回路。通過對(duì)運(yùn)動(dòng)物體模型特征點(diǎn)集合中的特征點(diǎn)進(jìn)行首尾相連，構(gòu)造無向圖的簡單回路，該無向圖的簡單回路則構(gòu)成了最接近物體外形的輪廓線。特征圖構(gòu)造完成之后，將其存儲(chǔ)在運(yùn)動(dòng)物體結(jié)構(gòu)體的特征圖指針中。特征圖構(gòu)造完成的效果如圖4所示。

2.3 根據(jù)路徑獲取物體的運(yùn)動(dòng)范圍

傳統(tǒng)的碰撞檢測方法在運(yùn)行時(shí)的檢測對(duì)象都是整個(gè)場景中的所有物體，然而這些檢測目標(biāo)中有三分之二以上的檢測對(duì)象都是不需要在當(dāng)前的運(yùn)行步驟中檢測的，因?yàn)橛泻艽笠徊糠值奈矬w并不在機(jī)器人的運(yùn)動(dòng)路徑上。為了減少運(yùn)動(dòng)物體單步運(yùn)動(dòng)時(shí)的碰撞檢測運(yùn)算量，提高碰撞檢測效率，需要根據(jù)機(jī)器人的運(yùn)動(dòng)路徑來動(dòng)態(tài)設(shè)置碰撞檢測的目標(biāo)。

運(yùn)動(dòng)物體的每一次運(yùn)動(dòng)，必然有一個(gè)運(yùn)動(dòng)起點(diǎn)和終點(diǎn)，通過對(duì)該運(yùn)動(dòng)物體運(yùn)動(dòng)路徑的起點(diǎn)和終點(diǎn)進(jìn)行坐標(biāo)投影，就可以獲得物體的運(yùn)動(dòng)區(qū)間。再將處于運(yùn)動(dòng)物體運(yùn)動(dòng)區(qū)間中的可能產(chǎn)生碰撞的其他障礙性物體構(gòu)造為可能碰撞的集合vi＝｛（i，j）| j∈Cn，j≠i｝，其中Cn＝｛1，2，3...n｝是場景中的所有物體，在運(yùn)動(dòng)物體的單步運(yùn)動(dòng)過程中，只需要檢測是否和可能碰撞集合中的物體是否碰撞，而不需要檢測場景中的其他物體。如圖5為坐標(biāo)投影法的效果圖。

圖3 特征點(diǎn)提取效果

圖4 生成圖所構(gòu)成的物體外表輪廓

圖5 坐標(biāo)投影法的效果圖

在圖5中，運(yùn)動(dòng)物體R從原點(diǎn)O出發(fā)到達(dá)目標(biāo)點(diǎn)T，折線為所規(guī)劃的運(yùn)動(dòng)物體R的運(yùn)動(dòng)路徑，所得虛線立方體為R的運(yùn)動(dòng)路徑區(qū)間。在場景中有機(jī)器人R以及A、B、C三個(gè)物體，其中物體A和B在R的路徑坐標(biāo)投影區(qū)間中，而物體C在之外。

2.4 設(shè)置碰撞掩碼

為了實(shí)現(xiàn)根據(jù)路徑進(jìn)行動(dòng)態(tài)的碰撞檢測，引入碰撞檢測掩碼方法。該方法為每一個(gè)檢測對(duì)象分配一個(gè)掩碼屬性。初始掩碼都配置為0，若運(yùn)動(dòng)物體開始運(yùn)動(dòng)，則運(yùn)動(dòng)物體的碰撞檢測掩碼置1，同時(shí)根據(jù)運(yùn)動(dòng)物體的運(yùn)動(dòng)路徑，通過3.3節(jié)的方法會(huì)獲得一個(gè)可能碰撞的集合v，然后再將集合v中的物體的碰撞掩碼置為1。在每一次碰撞檢測之前，先將物體的掩碼相與，若結(jié)果不為0，則該物體是機(jī)器人的碰撞檢測目標(biāo)，需要進(jìn)行碰撞檢測，否則不需要進(jìn)一步檢測。在運(yùn)動(dòng)完成之后，需要將設(shè)置的掩碼重新清0。如果在當(dāng)前步驟中沒有發(fā)生碰撞事件，運(yùn)動(dòng)物體又進(jìn)行了一次新的路徑規(guī)劃，那么在下一次的運(yùn)動(dòng)之前，需要再一次投影物體的運(yùn)動(dòng)區(qū)間，再一次設(shè)置碰撞掩碼。

在圖5中，物體A、B在運(yùn)動(dòng)物體R的運(yùn)動(dòng)路徑投影區(qū)間之中，則A、B及R的掩碼應(yīng)該都設(shè)置為1，即mask＝1，而物體C不在R的運(yùn)動(dòng)路徑投影區(qū)間中，則R在當(dāng)前步驟中不會(huì)與物體C發(fā)生碰撞，所以物體C的mask＝0。在進(jìn)行碰撞檢測之前，先將物體的mask相與，則R只需檢測A、B是否碰撞即可。

2.5 碰撞檢測方法實(shí)現(xiàn)

對(duì)模型結(jié)構(gòu)相對(duì)復(fù)雜的多機(jī)器人仿真系統(tǒng)，通過提取出模型的表面特征點(diǎn)，進(jìn)而構(gòu)成一個(gè)可以緊密包圍模型的特征圖，使用特征圖的各個(gè)邊來檢測模型之間是否碰撞，可以簡化以往的面面檢測方法；此外再使用碰撞掩碼方法動(dòng)態(tài)添加碰撞檢測對(duì)象，使得碰撞檢測效率得到較大提高。實(shí)現(xiàn)本文所提出的碰撞檢測方法需要完成以下工作。

1）將建立完成的模型按初始狀態(tài)需求布局到仿真場景中，布局物體的同時(shí)，記錄下場景中的物體以及每個(gè)物體所在位置等信息，所以需要建立模型鏈表modle_List，modle_List中的每個(gè)節(jié)點(diǎn)Node是物體模型信息的數(shù)據(jù)結(jié)構(gòu)。模型鏈表節(jié)點(diǎn)Node的結(jié)構(gòu)設(shè)計(jì)如下：

其中ID、Name、Position和Collion_mask需要在布局物體時(shí)進(jìn)行初始化，Collion_mask初始化都為0，默認(rèn)都不進(jìn)行碰撞檢測。特征點(diǎn)集合指針以及特征圖指針需要待特征點(diǎn)提取完成和特征圖生成之后才能賦值。

2）針對(duì)已經(jīng)初始化完成的場景，遍歷模型鏈表并依次對(duì)每一個(gè)物體提取特征點(diǎn)。為了存儲(chǔ)提取到的特征點(diǎn)，需要為每一個(gè)物體建立特征點(diǎn)集合V，然后使用3.2節(jié)所提方法提取出物體模型的特征點(diǎn)，最后生成特征點(diǎn)集合V＝｛v1，v2，v3... vn｝（n為特征點(diǎn)的個(gè)數(shù)）并將集合地址賦值給物體鏈表節(jié)點(diǎn)的Sp_point指針。

3）根據(jù)生成的物體模型特征點(diǎn)集合構(gòu)造特征圖。首先根據(jù)特征點(diǎn)集合中元素的個(gè)數(shù)n定義圖的鄰接矩陣G并初始化G中元素aij＝0｛i∈（0，n），j∈（0，n）｝；然后對(duì)特征點(diǎn)集合中的特征點(diǎn)使用首尾相連的方法構(gòu)造特征圖，同時(shí)修改特征圖的鄰接矩陣，最后得到包圍物體模型的特征圖G。

4）根據(jù)物體運(yùn)動(dòng)的路徑修改物體的碰撞檢測掩碼。首先根據(jù)機(jī)器人的當(dāng)前位置O的坐標(biāo)和目標(biāo)位置T的坐標(biāo)，使用3.3節(jié)所提的坐標(biāo)投影法獲得機(jī)器人的運(yùn)動(dòng)包圍盒；然后遍歷場景物體模型鏈表modle_List，如果物體的position∈（O，T）則修改物體的Collion_mask為1，最后再修改運(yùn)動(dòng)機(jī)器人的Collion_mask為1。

5）運(yùn)動(dòng)物體開始運(yùn)動(dòng)之后，首先對(duì)運(yùn)動(dòng)物體和場景中其他物體的Collion_mask相與，若結(jié)果不為0，則需要對(duì)二者進(jìn)行碰撞檢測。

當(dāng)物體開始運(yùn)動(dòng)時(shí)，就需要進(jìn)行碰撞檢測，先對(duì)運(yùn)動(dòng)物體模型的特征圖進(jìn)行遍歷，由于特征圖是一個(gè)無向循環(huán)圖，所以進(jìn)行深度遍歷，若鄰接矩陣G中的元素值為1，則說明對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)之間存在邊，所以需要獲取兩個(gè)頂點(diǎn)的坐標(biāo)并依據(jù)其坐標(biāo)構(gòu)成一條線段，設(shè)遍歷所得的兩個(gè)點(diǎn)為P1（x1，y1，z1）和P2（x2，y2，z2），則線段公式如式（3）所示：

其中：（x ∈［x1，x2］，y∈［y1，y2］，z∈［z1，z2］）。

使用該線段與目標(biāo)物體的各個(gè)面片進(jìn)行干涉檢測。首先求解線段與目標(biāo)物體的其中一個(gè)面片所在平面是否存在交點(diǎn)，若不存在，則與該面片不干涉，檢測目標(biāo)物體的下一個(gè)面片；若存在，判斷該交點(diǎn)是否位于該面片中，若不在該目標(biāo)面片中，則不干涉，檢測下一個(gè)面片；否則線段與該面片相交，即發(fā)生碰撞，進(jìn)入碰撞處理程序；如果特征圖的每一條邊都不與目標(biāo)物體的任何面相交，則說明沒有碰撞，繼續(xù)運(yùn)動(dòng)。

程序的運(yùn)行流程如圖6所示。

圖6 碰撞檢測方法流程圖

3 仿真驗(yàn)證

3.1 仿真驗(yàn)證平臺(tái)

1）在進(jìn)行多機(jī)器人仿真之前，需要對(duì)多機(jī)器人場景中的物體建模。當(dāng)今世面上存在許多優(yōu)秀的計(jì)算機(jī)建模軟件，如AutoCAD、Inventor、Solid Works以及Creator等。由于 Multigen－Paradigm公司的Creator軟件具有針對(duì)實(shí)時(shí)應(yīng)用優(yōu)化的OpenFlight數(shù)據(jù)格式，強(qiáng)大的多邊形建模、矢量建模等功能，能高效、最優(yōu)化地生成實(shí)時(shí)三維（RT3D）數(shù)據(jù)庫，所以本實(shí)驗(yàn)采用Creator作為多機(jī)器人系統(tǒng)的模型建立軟件。

2）在完成建模工作之后，還需要模型驅(qū)動(dòng)引擎以呈現(xiàn)仿真效果。如同建模軟件，當(dāng)今同樣存在多款模型驅(qū)動(dòng)引擎軟件，比如Direct X和OpenGL等。本試驗(yàn)為了方便展開試驗(yàn)，減少由于平臺(tái)不同而帶來的影響，所以同樣采用Multigen－Paradigm公司的圖形引擎軟件Vega Prime。通過Vega Prime可以進(jìn)行場景初始化以及設(shè)置模型位置和狀態(tài)信息。

3）使用MFC框架，以及Vega Prime的API驅(qū)動(dòng)多機(jī)器人場景中的模型實(shí)現(xiàn)實(shí)時(shí)三維運(yùn)動(dòng)仿真。在運(yùn)動(dòng)仿真的過程中使用上文提出的碰撞檢測方法，可以觀察到仿真過程流暢，模型之間發(fā)生碰撞事件時(shí)可以得到實(shí)時(shí)提醒。

3.2 仿真實(shí)驗(yàn)結(jié)果

為了使用本文所提碰撞檢測方法來驗(yàn)證仿真環(huán)境中物體間的碰撞檢測情況，設(shè)計(jì)了如圖7所示的仿真運(yùn)行環(huán)境。該場景中包含了一個(gè)運(yùn)動(dòng)物體以及3個(gè)罐體障礙物，實(shí)驗(yàn)希望運(yùn)動(dòng)物體可以從圖（a）的位置以最短路徑運(yùn)動(dòng)到圖（b）中的位置。

圖7 仿真實(shí)驗(yàn)場景

在物體運(yùn)動(dòng)之前，已經(jīng)使用以上方法完成了特征圖的構(gòu)建，并且使用坐標(biāo)投影方法計(jì)算出2號(hào)和3號(hào)罐體在運(yùn)動(dòng)物體的路徑包圍盒之中，所以2號(hào)和3號(hào)罐體都是運(yùn)動(dòng)物體的碰撞檢測目標(biāo)，而1號(hào)罐體并不需要檢測。當(dāng)物體運(yùn)動(dòng)時(shí)與2號(hào)罐體發(fā)生碰撞并且成功檢測到碰撞發(fā)生的情況，如圖8所示。

圖8 碰撞檢測效果

4 結(jié)論

針對(duì)多機(jī)器人仿真系統(tǒng)中傳統(tǒng)碰撞檢測方法存在的漏檢、過檢，以及在大規(guī)模場景中檢測效率低下等問題，本文提出一種基于物體模型特征圖的碰撞檢測方法。通過提取物體表面特征點(diǎn)，并進(jìn)一步生成緊密包裹模型表面的特征圖，使用該特征圖的邊檢測碰撞可以完成高精度的碰撞檢測。又使用掩碼方法依據(jù)物體運(yùn)動(dòng)路徑完成碰撞檢測目標(biāo)的動(dòng)態(tài)添加，使得在大規(guī)模場景中的碰撞檢測效率得到極大提高。最后，通過實(shí)驗(yàn)驗(yàn)證了該方法的可行性。

［1］張振華，周文理，等.虛擬場景中基于空間域的碰撞檢測算法研究［J］.計(jì)算機(jī)應(yīng)用，2012，32（S2）：151-153.

［2］張國飚，張 華，劉滿祿，等.基于空間剖分的碰撞檢測算法研究［J］.計(jì)算機(jī)工程與應(yīng)用，2014，50（7）：46-55.

［3］Schauer J，Nuchter A.Collision detection between point clouds using efficient k－d tree implementation［J］.Advantage Engineering Informatics，2015，29（3）：440-458.

［4］Wang Y，Hu Y Y，F(xiàn)an J C.Collision detection based on bounding box for NC machining simulation［A］.2012 International Conference on Applied Physics and Industrial Engineering［C］.2012，24：247-252.

［5］陳 琳，付 兵，潘海鴻，等.一種適用于多機(jī)器人的動(dòng)態(tài)包圍體層次樹碰撞檢測方法［J］.組合機(jī)床與自動(dòng)加工技術(shù)，2014 （7）：73-76.

［6］姜光焱.基于包圍盒的碰撞檢測算法及應(yīng)用［D］.成都：電子科技大學(xué)，2012.

［7］沈?qū)W利，吳 瓊.基于包圍盒和空間分割的混合碰撞檢測算法［J］.計(jì)算機(jī)工程，2012，38（6）：256-258.

［8］潘 翔，章國棟，陳啟華.三維可變形物體的特征點(diǎn)層次提?。跩］.計(jì)算機(jī)科學(xué)，2014，41（4）：292-296.

［9］郭凌云，鄭延斌，劉晶晶.基于時(shí)空相關(guān)性的快速碰撞檢測算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2013，30（5）：174-176.

［10］邵曉東，高 巍，劉煥玲.基于自適應(yīng)檢測線的碰撞檢測算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2013，19（12）：3148-3154.

［11］Yang J D，Shang S Y.An Improved collision detection algorithm based on K－DOPS［A］.International Conference on Computer Science andNetworkTechnology，2012［C］.2012（2）：842 -846.

［12］Yang S M，Guo W，Tang W.Simulation of collision resolution algorithm based on self－similar traffic model［J］.IEEE，2009，182-186.

Dynamic Collision Detection Method Based on Figure Graph of 3D Models

Ma Li1，Wang Qiang1，Yang Yingang2，Ma Dongchao1，Zhang Yongmei2

（1.North China University of Technology，Beijing 100144，China；2.Institute of Beijing High Information Technology，Beijing 100094，China）

Collision problem is a key issue in multi－robot system which must be solved，and the collision detection method is important for system security and avoidance strategy.In the multi－robot systems which have a complex structure，existing collision detection methods cannot meet the actual accuracy needs，especially in high－precision operation system，raise a new collision detection way based on the feature graph of objects.According to the structure characteristics of different objects，construct the feature graph which tightly wrapped the object，and the collision can be detected by traversing the feature graph.At the same time，in order to improve the efficiency of the detection method，in combination with the detection masks method.Through experimental analysis shows that this method has a higher collision detection accuracy and detection efficiency than the traditional method of collision detection.

multi－robot；collision detection；feature graph detection；accuracy dynamic detection

1671-4598（2016）08-0059-04

10.16526／j.cnki.11－4762／tp.2016.08.016

：TP391.9

：A

2016-01-30；

：2016-02-29。

部委預(yù)研項(xiàng)目（513060803）；國家自然科學(xué)基金項(xiàng)目（61300171，61371143）。

馬 禮（1968-），男，博士，教授，碩士生導(dǎo)師，主要從事分布式系統(tǒng)，多agent機(jī)器人系統(tǒng)方向的研究。