基于網(wǎng)格包絡(luò)的工業(yè)機(jī)器人仿真碰撞檢測(cè)算法

趙 亮 張義德 胡旭曉

1.浙江大學(xué)機(jī)械工程學(xué)院，杭州，3100272．浙江理工大學(xué)機(jī)械與自動(dòng)控制學(xué)院，杭州，310018

基于網(wǎng)格包絡(luò)的工業(yè)機(jī)器人仿真碰撞檢測(cè)算法

趙 亮1張義德1胡旭曉2

1.浙江大學(xué)機(jī)械工程學(xué)院，杭州，3100272．浙江理工大學(xué)機(jī)械與自動(dòng)控制學(xué)院，杭州，310018

為提高工業(yè)機(jī)器人在復(fù)雜作業(yè)環(huán)境下的碰撞檢測(cè)效率，提出了一種網(wǎng)格包絡(luò)的碰撞檢測(cè)算法，以大量等尺寸的立方體網(wǎng)格來包絡(luò)模型本身，并在網(wǎng)格內(nèi)部建立網(wǎng)格子模型的AABB樹結(jié)構(gòu)。該算法在建模過程中將網(wǎng)格的空間坐標(biāo)進(jìn)行有序存儲(chǔ)，在遍歷階段可快速搜索到相交的網(wǎng)格，之后遍歷網(wǎng)格內(nèi)部的樹結(jié)構(gòu)來進(jìn)一步判斷模型是否碰撞。該算法網(wǎng)格內(nèi)部的子模型幾何數(shù)據(jù)量遠(yuǎn)小于整體模型幾何數(shù)據(jù)量，其網(wǎng)格內(nèi)的檢測(cè)速度遠(yuǎn)快于以整體模型建模的傳統(tǒng)層次包圍盒方法的檢測(cè)速度。實(shí)驗(yàn)結(jié)果表明，在大型復(fù)雜模型碰撞檢測(cè)仿真中，該算法在不同網(wǎng)格數(shù)量下的檢測(cè)效率比傳統(tǒng)的Solid算法的檢測(cè)效率快數(shù)倍到數(shù)十倍。

碰撞檢測(cè)；網(wǎng)格包絡(luò)；軸對(duì)齊包圍盒；工業(yè)機(jī)器人

0 引言

碰撞檢測(cè)技術(shù)應(yīng)用在機(jī)器人路徑規(guī)劃[1]、醫(yī)學(xué)仿真[2]、3D游戲等虛擬現(xiàn)實(shí)領(lǐng)域，在工業(yè)機(jī)器人仿真中，碰撞檢測(cè)技術(shù)提供對(duì)工業(yè)機(jī)器人路徑規(guī)劃的技術(shù)支持，如車架的點(diǎn)焊、零件的裝配、復(fù)雜環(huán)境下物料的搬運(yùn)等。潘海鷗等[3]研究了多機(jī)器人系統(tǒng)下的碰撞檢測(cè)算法；金明杰等[4]研究了工業(yè)機(jī)器人運(yùn)動(dòng)規(guī)劃中的自適應(yīng)碰撞檢測(cè)算法。

碰撞檢測(cè)技術(shù)主要有層次包圍盒技術(shù)、空間劃分技術(shù)和基于GPU[5-6]的碰撞檢測(cè)技術(shù)等。層次包圍盒技術(shù)主要有球包圍盒樹[7]、AABB層次樹[8]、OBB層次樹[9]、K-DOPs樹[10]等?？臻g劃分技術(shù)包括均勻網(wǎng)格、八叉樹[11]和BSP樹[12]等。其中，層次包圍盒技術(shù)因建模方便、檢測(cè)效率高而得到廣泛的應(yīng)用和研究[13]。層次包圍盒檢測(cè)技術(shù)中較為成熟的有基于AABB包圍盒層次樹結(jié)構(gòu)的Solid[8]算法和基于OBB包圍盒層次樹結(jié)構(gòu)的RAPID[9]算法，由于其高效的檢測(cè)性能，被廣泛用于對(duì)比和作為改進(jìn)對(duì)象。

機(jī)器人仿真中的碰撞檢測(cè)技術(shù)研究大多對(duì)機(jī)器人模型進(jìn)行了簡(jiǎn)化，模型的幾何數(shù)據(jù)量較小。工業(yè)機(jī)器人的機(jī)械手和作業(yè)環(huán)境的三維模型結(jié)構(gòu)復(fù)雜，包含幾何數(shù)據(jù)量大，作業(yè)精度要求高，使用傳統(tǒng)的包圍盒碰撞檢測(cè)技術(shù)檢測(cè)效率不高。本文提出了一種網(wǎng)格包絡(luò)算法，將三維模型離散化成大量整齊排列的均勻網(wǎng)格，在建模階段對(duì)網(wǎng)格內(nèi)的子模型建立AABB層次樹，在碰撞檢測(cè)階段快速定位發(fā)生相交的網(wǎng)格區(qū)域。該網(wǎng)格以模型本身為建?；鶞?zhǔn)而不以整個(gè)空間為建?；鶞?zhǔn)，通過遍歷相交網(wǎng)格內(nèi)的AABB層次樹來進(jìn)一步準(zhǔn)確判斷碰撞情況。

1 網(wǎng)格包絡(luò)模型的建立

1.1 仿真系統(tǒng)的搭建

圖1為6軸工業(yè)機(jī)器人點(diǎn)焊作業(yè)的三維顯示圖，焊接夾具模型含有約694×103個(gè)三角形面片，汽車側(cè)門模型含有約286×103個(gè)三角形面片，點(diǎn)焊機(jī)含有約12.5×103個(gè)三角形面片。在仿真環(huán)境中實(shí)現(xiàn)工業(yè)機(jī)器人的運(yùn)動(dòng)控制，通過求解軌跡運(yùn)動(dòng)中的碰撞檢測(cè)情況，可以在仿真中實(shí)現(xiàn)運(yùn)動(dòng)軌跡曲線的調(diào)整。

圖1 工業(yè)機(jī)器人點(diǎn)焊汽車側(cè)門仿真Fig.1 Simulation of a industrial robot spot-welding door frame

1.2 網(wǎng)格包絡(luò)層的建立

以模型的最外層的軸向包圍盒為邊界，采用等大小的立方體網(wǎng)格層覆蓋模型，網(wǎng)格的建立以Z、Y、X坐標(biāo)軸為優(yōu)先級(jí)順序并以最外層包圍盒為邊界依次建立。模型由大量三角形面片構(gòu)成，檢測(cè)網(wǎng)格內(nèi)是否包含屬于模型的三角形面片來判斷網(wǎng)格是否包絡(luò)模型。當(dāng)網(wǎng)格內(nèi)含有三角形面片時(shí)，則存儲(chǔ)該網(wǎng)格的中心點(diǎn)坐標(biāo)和三角形數(shù)據(jù)索引；當(dāng)網(wǎng)格內(nèi)不包含模型的三角形面片時(shí)，則舍棄該網(wǎng)格節(jié)點(diǎn)，直至建完所有網(wǎng)格。網(wǎng)格包絡(luò)法的建模偽代碼如下：

for(Xi=Xmin；Xi

for(Yi=Ymin；Yi

for(Zi=Zmin；Zi

if (有三角形在網(wǎng)格i內(nèi)或與網(wǎng)格i相交) {創(chuàng)建該網(wǎng)格節(jié)點(diǎn)i并記錄中心點(diǎn)坐標(biāo)(Xi，Yi，Zi)；對(duì)網(wǎng)格節(jié)點(diǎn)i創(chuàng)建AABBi樹結(jié)構(gòu)；}

else {舍棄該網(wǎng)格節(jié)點(diǎn)；}

其中，(Xmin，Ymin，Zmin)為最外層長(zhǎng)方體包圍盒頂點(diǎn)的最小點(diǎn)坐標(biāo)；(Xmax，Ymax，Zmax)為最大點(diǎn)坐標(biāo)，i為網(wǎng)格節(jié)點(diǎn)序號(hào)，(Xi，Yi，Zi)為網(wǎng)格i的中心點(diǎn)坐標(biāo)，r為網(wǎng)格半邊長(zhǎng)。AABBi為網(wǎng)格i的內(nèi)部AABB樹，即對(duì)網(wǎng)格內(nèi)所有三角形進(jìn)行AABB建模。以最外層軸向包圍盒為邊界，以網(wǎng)格邊長(zhǎng)為移動(dòng)單位，以Z、Y、X坐標(biāo)軸為優(yōu)先級(jí)順序依次建立網(wǎng)格，若有三角形在網(wǎng)格內(nèi)或與網(wǎng)格相交，則存儲(chǔ)該網(wǎng)格的中心點(diǎn)坐標(biāo)；否則刪除該網(wǎng)格。

在二維平面中，網(wǎng)格包絡(luò)算法的建模方法與AABB層次樹的建模方法的對(duì)比如圖2所示。以模型的最外層軸向包圍長(zhǎng)方形為邊界建立正方形網(wǎng)格層，遍歷所有網(wǎng)格并檢測(cè)網(wǎng)格是否和模型相交，若網(wǎng)格與模型相交則標(biāo)記該網(wǎng)格并存儲(chǔ)相交的模型數(shù)據(jù)，圖2中陰影網(wǎng)格為所有被標(biāo)記的網(wǎng)格。網(wǎng)格的建立順序如下：以第一列網(wǎng)格最底端為起點(diǎn)(即左下角網(wǎng)格)，以網(wǎng)格邊長(zhǎng)為單位向上移動(dòng)，當(dāng)網(wǎng)格超出長(zhǎng)方形頂端界限，則從第二列網(wǎng)格底端繼續(xù)向上移動(dòng)，如此往復(fù)直至長(zhǎng)方形內(nèi)所有網(wǎng)格遍歷完畢。

圖2 AABB樹和網(wǎng)格包絡(luò)的建模方法對(duì)比Fig.2 Comparison of modeling methods between AABB and grids covering algorithm

圖3所示為網(wǎng)格包絡(luò)下的焊接夾具模型，網(wǎng)格數(shù)量為2256，網(wǎng)格尺寸越小，網(wǎng)格數(shù)越多，網(wǎng)格內(nèi)部包含的模型特征量越少。

圖3 網(wǎng)格包絡(luò)下的焊接夾具模型Fig.3 Model of grids covering welding fixture

1.3 網(wǎng)格與三角形位置關(guān)系的快速判斷

如圖4所示，點(diǎn)P為網(wǎng)格中心點(diǎn)，點(diǎn)Q為三角形ABC上與點(diǎn)P相距最近的點(diǎn)，三角形ABC上距點(diǎn)P的最近點(diǎn)Q采用Voronoi特征域法可快速求解得到。若線段PQ在X、Y、Z軸上的投影值都小于或等于網(wǎng)格半邊長(zhǎng)r，則表明三角形ABC在網(wǎng)格內(nèi)或與網(wǎng)格相交；若PQ在X、Y、Z軸上的任一投影值大于網(wǎng)格半邊長(zhǎng)r，則說明三角形在網(wǎng)格外，快速求解三角形與包圍盒的位置關(guān)系可加速建模過程。網(wǎng)格不僅存儲(chǔ)網(wǎng)格內(nèi)部的三角形索引數(shù)據(jù)，而且需存儲(chǔ)與網(wǎng)格邊界相交的三角形索引數(shù)據(jù)，與網(wǎng)格相交的三角形會(huì)被多個(gè)相鄰網(wǎng)格存儲(chǔ)。

圖4 三角形與網(wǎng)格位置關(guān)系判斷Fig.4 Judging of the position relation between triangle and grid

1.4 分層加速建模

當(dāng)模型含有大量三角形面片時(shí)，為每個(gè)網(wǎng)格循環(huán)檢索模型的所有三角形索引數(shù)據(jù)耗時(shí)情況嚴(yán)重。為加速檢索網(wǎng)格內(nèi)是否含有模型三角形面片，采用建立多層不同尺寸網(wǎng)格的預(yù)處理方法。每層網(wǎng)格存儲(chǔ)屬于該網(wǎng)格的所有三角形索引，第N層網(wǎng)格從第N-1層網(wǎng)格獲取三角形索引而無需檢索根模型的所有三角形索引。

如圖5所示，先建立較大尺寸的網(wǎng)格，網(wǎng)格內(nèi)存儲(chǔ)屬于該網(wǎng)格的模型數(shù)據(jù)，然后以較大網(wǎng)格尺寸的一半作為下一層網(wǎng)格尺寸。在三維空間中，多層網(wǎng)格以八叉樹結(jié)構(gòu)形式存在，在二維空間中以四叉樹結(jié)構(gòu)來表示。

圖5 分層加速建立網(wǎng)格層Fig.5 Layered acceleration to build grid layer

如圖6所示，第N層網(wǎng)格尺寸為第N-1層網(wǎng)格的一半，當(dāng)網(wǎng)格尺寸降到目標(biāo)尺寸r時(shí)，建立最后一層網(wǎng)格。為節(jié)省存儲(chǔ)消耗，建完第N層網(wǎng)格后立即刪除N-1層網(wǎng)格存儲(chǔ)的三角形索引數(shù)據(jù)，只在最后一層存儲(chǔ)模型的三角形索引。

圖6 分層建模流程圖Fig.6 Flow chart of layered modeling

為節(jié)省內(nèi)存消耗，網(wǎng)格按Z、Y、X坐標(biāo)軸為優(yōu)先級(jí)先后順序，采用一維線性存儲(chǔ)方式依次進(jìn)行存儲(chǔ)來記錄三維空間位置信息。

1.5 網(wǎng)格內(nèi)部建立AABB樹結(jié)構(gòu)

每個(gè)網(wǎng)格不僅存儲(chǔ)該網(wǎng)格的坐標(biāo)位置，同時(shí)存儲(chǔ)了在網(wǎng)格內(nèi)部或與網(wǎng)格相交的三角形數(shù)據(jù)，在網(wǎng)格建立的同時(shí)對(duì)網(wǎng)格內(nèi)部的網(wǎng)格子模型建立AABB層次樹結(jié)構(gòu)，在后續(xù)的碰撞檢測(cè)中可以實(shí)時(shí)調(diào)用網(wǎng)格內(nèi)部的樹結(jié)構(gòu)檢測(cè)三角形碰撞情況。如圖7所示，在建立網(wǎng)格的同時(shí)在網(wǎng)格內(nèi)部建立網(wǎng)格子模型的AABB層次樹結(jié)構(gòu)，將所有網(wǎng)格內(nèi)的樹結(jié)構(gòu)存入堆棧，在檢測(cè)階段可實(shí)時(shí)讀取，網(wǎng)格內(nèi)部AABB樹用Solid算法進(jìn)行建模。

圖7 網(wǎng)格內(nèi)部建立AABB樹結(jié)構(gòu)Fig.7 AABB trees structure established in the grid

網(wǎng)格尺寸大小對(duì)算法的影響主要在整體網(wǎng)格建模和碰撞檢測(cè)兩個(gè)階段。在建模階段：網(wǎng)格越小，網(wǎng)格數(shù)越多，計(jì)算所有網(wǎng)格的位置和存儲(chǔ)網(wǎng)格內(nèi)部的三角形數(shù)據(jù)越耗時(shí)。在碰撞檢測(cè)階段：網(wǎng)格越小，網(wǎng)格對(duì)模型的覆蓋越緊密，同時(shí)網(wǎng)格平均包含的模型數(shù)據(jù)量越小，網(wǎng)格內(nèi)樹結(jié)構(gòu)的遍歷速度越快。

2 碰撞檢測(cè)

2.1 網(wǎng)格遍歷檢測(cè)

設(shè)模型A、B分別含有網(wǎng)格數(shù)n、m，遍歷模型A的所有網(wǎng)格，判斷模型B中是否有網(wǎng)格與模型A 中的網(wǎng)格相交來初步判斷兩模型是否碰撞。網(wǎng)格的相交判斷采用 “分離軸法”以適應(yīng)旋轉(zhuǎn)更新變換。

本文算法采用一維線性存儲(chǔ)，使用二分法進(jìn)行快速查找來定位可能相交區(qū)域。對(duì)于模型A中的網(wǎng)格i，在模型B中以X、Y、Z坐標(biāo)軸為先后順序采用二分法進(jìn)行搜索，檢索模型B中是否有網(wǎng)格j與網(wǎng)格i相交，時(shí)間復(fù)雜度為Ο(nlog2m)。根據(jù)時(shí)間復(fù)雜度公式，應(yīng)以網(wǎng)格數(shù)少的模型作為遍歷對(duì)象(即模型A)，網(wǎng)格數(shù)多的模型作為二分法檢索對(duì)象(即模型B)。

當(dāng)檢測(cè)到A中的網(wǎng)格i與B中的網(wǎng)格j相交時(shí)，遍歷網(wǎng)格i、j內(nèi)存儲(chǔ)的子模型的AABB層次包圍盒樹結(jié)構(gòu)，檢測(cè)網(wǎng)格i、j內(nèi)的三角形面片是否發(fā)生碰撞。圖8為本文算法碰撞檢測(cè)判斷流程圖。

圖8 碰撞檢測(cè)流程圖Fig.8 Flow chart of collision detection

如圖9所示，對(duì)于圖中左邊的每一個(gè)網(wǎng)格，循環(huán)檢測(cè)右邊所有網(wǎng)格是否與之相交。圖9中黑色部分網(wǎng)格為相交網(wǎng)格，之后對(duì)黑色網(wǎng)格內(nèi)部進(jìn)行精確檢測(cè)。

圖9 網(wǎng)格相交遍歷檢索Fig.9 Grid intersection traversal search

2.2 分層碰撞檢測(cè)

為加速網(wǎng)格相交的檢測(cè)判斷，采用網(wǎng)格最小外接球代替網(wǎng)格進(jìn)行初步判斷。如圖10所示，模型采用三層結(jié)構(gòu)進(jìn)行建模。圖10中由上到下，最外層為軸向包圍盒，中間層為網(wǎng)格外接球?qū)?，?nèi)層為網(wǎng)格層。當(dāng)兩個(gè)模型相距較遠(yuǎn)時(shí)，用最外層判斷可快速檢測(cè)而省去大量遍歷過程；當(dāng)兩個(gè)模型相距較近時(shí)，以中間層遍歷判斷為主。

圖10 點(diǎn)焊夾具模型三層包絡(luò)結(jié)構(gòu)Fig.10 Three layer structure of spot-welding fixture modle

設(shè)模型A中網(wǎng)格i的坐標(biāo)為(Xi，Yi，Zi)，模型B中的網(wǎng)格j的坐標(biāo)為(Xj，Yj，Zj)，網(wǎng)格外接球的半徑為R。當(dāng)兩坐標(biāo)之間的距離D>2R時(shí)，則表示兩網(wǎng)格最小外接球不相交，即網(wǎng)格i與網(wǎng)格j不相交。當(dāng)兩坐標(biāo)之間的距離D≤2R時(shí)，采用OBB包圍盒檢測(cè)方法中的“分離軸法”繼續(xù)判斷兩網(wǎng)格是否相交。

當(dāng)模型旋轉(zhuǎn)時(shí)，網(wǎng)格需要進(jìn)行坐標(biāo)更新和方向更新，而網(wǎng)格外接球只需更新坐標(biāo)。由于采用網(wǎng)格外接球代替網(wǎng)格進(jìn)行初步判斷，故無需對(duì)所有網(wǎng)格進(jìn)行旋轉(zhuǎn)更新而只需更新外接球相交的網(wǎng)格。

2.3 網(wǎng)格內(nèi)部相交檢測(cè)

遍歷兩模型網(wǎng)格，檢測(cè)是否有相交網(wǎng)格，當(dāng)檢測(cè)到分別屬于不同模型的網(wǎng)格相交時(shí)，對(duì)相交的網(wǎng)格內(nèi)部的子模型AABB層次樹深度遍歷，進(jìn)行網(wǎng)格碰撞區(qū)域的AABB層次樹的碰撞判斷。網(wǎng)格內(nèi)部的子模型AABB層次樹的檢測(cè)速度主要與網(wǎng)格內(nèi)部的三角形數(shù)量有關(guān)，三角形數(shù)量越多，則檢測(cè)時(shí)間越長(zhǎng)。

網(wǎng)格尺寸越小，則網(wǎng)格內(nèi)包含的三角形數(shù)量越少，網(wǎng)格內(nèi)的相交檢測(cè)越快。但網(wǎng)格數(shù)量越多，網(wǎng)格層建立越慢，因此，網(wǎng)格尺寸不宜過小。如圖11所示，遍歷兩模型的網(wǎng)格外接球，計(jì)算網(wǎng)格外接球是否相交，若相交則繼續(xù)檢測(cè)網(wǎng)格是否相交，若網(wǎng)格也相交則檢測(cè)網(wǎng)格內(nèi)部的三角形面片是否相交，圖11中兩模型的非碰撞狀態(tài)將在網(wǎng)格內(nèi)部的AABB層次樹遍歷階段被檢測(cè)出。

圖11 網(wǎng)格包絡(luò)模型碰撞情況Fig.11 Collision situation of the grids covering models

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

3.1 仿真系統(tǒng)的搭建

本文對(duì)算法的性能進(jìn)行了實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)的硬件環(huán)境如下：CPU為Corei5-4210H(2.9G)、內(nèi)存8GB，顯卡為NVIDIAGT960；軟件環(huán)境為VisualStudio2010和DXSDK_Jun10。在三維建模軟件中將模型導(dǎo)出為STL格式，并使用3DSMAX將模型導(dǎo)出為“.X”類型文件。在3DSMAX中將模型的位置和姿態(tài)調(diào)整正確，在仿真環(huán)境中建立6軸工業(yè)機(jī)器人運(yùn)動(dòng)控制模塊，實(shí)現(xiàn)末端位置的準(zhǔn)確定位。圖12為點(diǎn)焊汽車側(cè)門仿真作業(yè)的三維顯示圖。

圖12 點(diǎn)焊汽車側(cè)門仿真圖Fig.12 Welding Simulation of a car door

3.2 兩種方法檢測(cè)速度的對(duì)比

在兩模型最外層包圍盒相交的情況下，對(duì)點(diǎn)焊機(jī)分別與焊接夾具模型、汽車側(cè)門模型10×103個(gè)不同相對(duì)姿態(tài)、位置，用不同算法計(jì)算碰撞檢測(cè)時(shí)間。焊接夾具模型含有約694×103個(gè)三角形面片，汽車側(cè)門模型含有約286×103個(gè)三角形面片，點(diǎn)焊機(jī)含有約12.5×103個(gè)三角形面片。

如表1所示，在Solid算法下，點(diǎn)焊機(jī)與焊接夾具碰撞狀態(tài)平均每個(gè)點(diǎn)的檢測(cè)時(shí)間約323.5ms，最慢位置為8.22s。網(wǎng)格包絡(luò)算法在不同網(wǎng)格尺寸下，檢測(cè)速度和建模速度有所差異。網(wǎng)格尺寸越小，建模時(shí)間越長(zhǎng)，但平均檢測(cè)時(shí)間和最慢位置檢測(cè)時(shí)間越短。網(wǎng)格包絡(luò)算法在焊接夾具網(wǎng)格數(shù)為2256的情況下，碰撞的平均檢測(cè)時(shí)間約11ms，最慢位置約492ms。對(duì)比傳統(tǒng)基于AABB層次樹結(jié)構(gòu)的Solid算法，網(wǎng)格包絡(luò)算法在檢測(cè)速度上提高了數(shù)十倍。

表1 點(diǎn)焊機(jī)與焊接夾具模型碰撞檢測(cè)時(shí)間

如表2所示，由于汽車側(cè)門的結(jié)構(gòu)比焊接夾具簡(jiǎn)單，所以點(diǎn)焊機(jī)與汽車側(cè)門的碰撞檢測(cè)速度較快。在Solid算法下，點(diǎn)焊機(jī)與汽車側(cè)門的碰撞狀態(tài)的平均檢測(cè)時(shí)間約為10.5 ms，網(wǎng)格包絡(luò)算法在網(wǎng)格數(shù)為1616時(shí)的平均檢測(cè)時(shí)間約為2.6 ms，網(wǎng)格包絡(luò)算法比Solid算法快數(shù)倍。

表2 點(diǎn)焊機(jī)與汽車側(cè)門模型碰撞檢測(cè)時(shí)間

網(wǎng)格包絡(luò)算法在建模時(shí)間上比Solid算法慢，網(wǎng)格數(shù)越多，建模時(shí)間越長(zhǎng)，但檢測(cè)效率越高。由于工業(yè)機(jī)器人仿真中模型較為固定，模型更新少，故可將碰撞檢測(cè)的建模數(shù)據(jù)輸出為文本文件。因此，每次運(yùn)行仿真軟件讀取建模數(shù)據(jù)的文本文件即可，無需重復(fù)建模過程。

4 結(jié)論

(1)網(wǎng)格包絡(luò)算法以大量等尺寸的立方體網(wǎng)格包絡(luò)模型，并在網(wǎng)格內(nèi)部建立子模型AABB樹結(jié)構(gòu)，網(wǎng)格與模型同步運(yùn)動(dòng)。在檢測(cè)階段，遍歷兩模型的網(wǎng)格可以快速定位碰撞區(qū)域，在網(wǎng)格碰撞區(qū)域?qū)υ摼W(wǎng)格內(nèi)部子模型的AABB樹結(jié)構(gòu)進(jìn)行遍歷檢測(cè)，從三角形層面判斷是否發(fā)生碰撞。

(2)將大模型拆解為大量網(wǎng)格子模型，由于子模型含有的三角形數(shù)據(jù)量小，故其檢測(cè)速度遠(yuǎn)快于以整體模型為檢測(cè)對(duì)象的傳統(tǒng)方法的檢測(cè)速度。通過細(xì)化網(wǎng)格可以減少網(wǎng)格內(nèi)的數(shù)據(jù)量，但網(wǎng)格數(shù)量過大會(huì)導(dǎo)致初次建模時(shí)間的延長(zhǎng)，可以根據(jù)模型的復(fù)雜程度以及對(duì)檢測(cè)速度的要求來確定網(wǎng)格尺寸。

(3)相比傳統(tǒng)包圍盒算法，網(wǎng)格包絡(luò)算法針對(duì)大型模型的碰撞檢測(cè)速度快數(shù)倍至數(shù)十倍。在工業(yè)機(jī)器人的作業(yè)和路徑規(guī)劃仿真中，三維模型的結(jié)構(gòu)復(fù)雜且包含的三角形數(shù)量多，網(wǎng)格包絡(luò)算法在工業(yè)機(jī)器人作業(yè)和路徑規(guī)劃仿真中能夠提供穩(wěn)定快速的碰撞檢測(cè)。

[1] 劉忠，曹其新，朱笑笑，等．基于VRML節(jié)點(diǎn)樹的雙臂移動(dòng)機(jī)器人碰撞檢測(cè)及優(yōu)化[J]．上海交通大學(xué)學(xué)報(bào)，2011, 45(7): 985-989. LIU Zhong, CAO Qixin, ZHU Xiaoxiao, et al. Collision Detection and Optimization of Dual-arm Mobile Robot Based on Node Tree of VRML[J]. Journal of Shanghai Jiaotong University, 2011, 45(7): 985-989.

[2] GAO Baofeng, HU Kangqi, GUO Shuxiang. Collision Detection Algorithm Based on AABB for Minimally Invasive Surgery[C]//Proceedings of 2014 IEEE International Conference on Mechatronics and Automation. Tianjin,2014:315-320.

[3] 潘海鴻，戴駿，陳琳，等．多機(jī)器人并行動(dòng)態(tài)包圍盒層次樹碰撞檢測(cè)算法[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2014，26(11)：1948-1956. PAN Haihong, DAI Jun, CHEN Lin, et al. Multi-robot Parallel Dynamic Bounding Volume Hierarchy Tree Collision Detection Algorithm[J]. Journal of Computers Aided Design & Computer Graphic, 2014, 26(11):1948-1956.

[4] 金明杰，樓云江，劉冠峰，等．基于自適應(yīng)動(dòng)態(tài)碰撞檢測(cè)的工業(yè)機(jī)器人運(yùn)動(dòng)規(guī)劃算法研究[J]．中國(guó)科技大學(xué)學(xué)報(bào)，2012，42(6)：448-455. JIN Mingjie, LOU Yunjiang, LIU Guanfeng, et al. A Novel Motion Planning Algorithm with Adaptive Dynamic Collision Detection for Industrial Robot[J]. Journal of University of Science and Technology of China,2012, 42(6): 448-455.

[5] 唐敏，林江，童若鋒．圖形硬件加速的柔性物體連續(xù)碰撞檢測(cè)[J]．計(jì)算機(jī)學(xué)報(bào)，2010，33(10)：2022-2030 TANG Min, LIN Jiang, TONG Ruofeng. Graphics Hardware Accelerated Continuous Collision Detection Between Deformable Objects[J]. Chinese Journal of Computers, 2010, 33(10):2022-2030.

[6] 印桂生，王海玲, 張菁，等. 快速高效的碰撞檢測(cè)算法[J]．上海交通大學(xué)學(xué)報(bào)，2012, 46(6)：962-971 YIN Guisheng, WANG Hailing, ZHANG Jing, et al. Fast Efficient Collision Detection[J]. Journal of Shanghai Jiaotong University,2012,42(6):962-971.

[7] PALMERI J, GRIMSDALE R L. Collision Detection for Animation Using Sphere-trees[J]. Computer Graphics Forum, 1995, 14(2):105-116.

[8] van den BERGEN G. Efficient Collision Detection of Complex Deformable Models Using AABB Trees[J]. Journal of Graphics Tools, 1997, 2(4):1-14.

[9] GOTTSCHALK S, LIN M, MANOCHA D. OBB Tree: A Hierarchical Structure for Rapid Interference Detection[C]// Proceedings of the SIGGRAPH. New York, 1996 :171-180.

[10] KLOSOWSKI J, HELD M, MITCHELL J, et al. Efficient Collision Detection Using Bounding Volume Hierarchies of K-DOPs[J]. IEEE Transactions on Visualization and Computer Graphics,1998, 4(1):21-37.

[11] NAYLORB F. Interactive Solid Geometry via Partitioning Trees[C]//Conference on Graphics Interface. Toronto, 1992:11-18.

[12] 鮑義東，吳冬梅．自適應(yīng)細(xì)分及優(yōu)化編碼八叉樹碰撞檢測(cè)算法[J]．上海交通大學(xué)學(xué)報(bào)，2015，49(8)：1114-1122. BAO Yidong, WU Dongmei. A Novel Algorithm for Collision Detection Based on Octree of Adaptive Subdivision and Encoding[J]. Journal of Shanghai Jiaotong University, 2015, 49(8):1114-1122.

[13] 唐勇，楊偲偲，呂夢(mèng)雅，等. 自適應(yīng)橢球包圍盒改進(jìn)織物碰撞檢測(cè)方法[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2013， 25(10)：1589-1596. TANG Yong, YANG Sisi, LYU Mengya, et al. Collision Detection for Cloth Based on Adaptive Enclosing Ellipsoids[J]. Journal of Computer-Aided Design & Computer Graphic, 2013, 25(10)：1589-1596.

(編輯 陳 勇)

A Novel Collision Detection Algorithm Based on Grids Enveloping for Industrial Robot Simulations

ZHAO Liang1ZHANG Yide1HU Xuxiao2

1.College of Mechanical Engineering, Zhejiang University, Hangzhou, 310027 2.College of Mechanical and Automatic Control, Zhejiang Sci-Tech University, Hangzhou, 310018

To speed up the collision detection efficiency of industrial robots in the complex working environments, a novel collision detection algorithm was proposed using equal-sized cubic grids to cover the model and building tree structure of AABB in the grid. The space coordinates of these grids were stored orderly in the modeling progresses so as to determine whether there were grids intersecting in the traversal periods. Then traverse the hierarchical structure in the intersecting grids to detect collision precisely. Due to the grids had far less model data than the whole model, the detection speeds in the grids were far more fast than the traditional hierarchical bounding volume method where the building model was based on the whole model. The experimental results show that the detection efficiency in the novel algorithm is several times to dozes times (which depends on the size of grids) more than that in the traditional SOLID method for the large complex model environments.

collision detection; grids enveloping; axis aligned bounding box (AABB); industrial robot

2016-03-28

浙江省自然科學(xué)基金資助項(xiàng)目(LZ14E050003)

TP391.9DOI：10.3969/j.issn.1004-132X.2017.03.011

趙 亮，男，1976年生。浙江大學(xué)機(jī)械工程學(xué)院副教授。主要研究方向?yàn)楣I(yè)機(jī)器人和智能檢測(cè)設(shè)備。E-mail:mezl@zju.edu.cn。張義德，男，1988年生。浙江大學(xué)機(jī)械工程學(xué)院碩士研究生。胡旭曉，男，1965年生。浙江理工大學(xué)機(jī)械與自動(dòng)控制學(xué)院教授。