鄭尊鵬

青島科技大學(xué)，山東青島 266042

機(jī)器人仿真系統(tǒng)中碰撞檢測(cè)算法的優(yōu)化

鄭尊鵬

青島科技大學(xué)，山東青島 266042

碰撞檢測(cè)是機(jī)器人仿真系統(tǒng)中的重要問題之一。本文介紹了碰撞檢測(cè)算法的基本分類，對(duì)層次包圍盒的幾種基本算法進(jìn)行了分析比較，重點(diǎn)闡述了混合包圍盒法，并將其應(yīng)用于仿真系統(tǒng)中碰撞檢測(cè)問題的解決，提高了檢測(cè)速度、優(yōu)化了檢測(cè)算法。

仿真系統(tǒng)；碰撞檢測(cè)；層次包圍盒；混合包圍盒

0 引言

在物理模型中檢測(cè)運(yùn)動(dòng)物體是否相互碰撞的過程稱為碰撞檢測(cè)（Collision Detection,CD），也稱為干涉檢測(cè)或接觸檢測(cè)。碰撞檢測(cè)是基于現(xiàn)實(shí)生活中一個(gè)普遍存在的事實(shí)：兩個(gè)不可穿透的對(duì)象不可能共享相同的空間區(qū)域。

在機(jī)器人仿真系統(tǒng)中，經(jīng)常需要對(duì)多個(gè)機(jī)器人在同一工作單元中的協(xié)同作業(yè)進(jìn)行仿真。為避免因機(jī)器人的工作空間之間存在重疊交叉區(qū)域而發(fā)生相互干涉的問題，要引入碰撞檢測(cè)來判定多個(gè)機(jī)器人在給定時(shí)間域內(nèi)的同一時(shí)刻是否占有相同區(qū)域。碰撞檢測(cè)是機(jī)器人仿真系統(tǒng)不可回避的問題之一，快速而有效的碰撞檢測(cè)功能是仿真系統(tǒng)成功的關(guān)鍵。

1 碰撞檢測(cè)算法

由于碰撞檢測(cè)問題由來已久，在不同領(lǐng)域涌現(xiàn)出了許多碰撞檢測(cè)算法。在這些算法中比較經(jīng)典的研究成果包括空間分割法（space decomposition）和層次包圍盒法（hierarchical bounding bolumes）及其一系列改進(jìn)算法等。

空間分割法是將包含物體的虛擬空間分割為多個(gè)體積相等的小單元格，每個(gè)物體對(duì)應(yīng)于一個(gè)或多個(gè)小單元中，碰撞檢測(cè)時(shí)只需對(duì)占據(jù)同一單元格或相鄰單元格的幾何對(duì)象進(jìn)行相交測(cè)試。比較典型的方法有k-d樹、八叉樹、BSP（binary space partitioning）樹、四面體網(wǎng)和規(guī)則網(wǎng)格等。層次包圍盒法是用幾何特性簡(jiǎn)單的包圍盒近似地描述虛擬場(chǎng)景中復(fù)雜的幾何對(duì)象，進(jìn)而通過構(gòu)造樹狀層次結(jié)構(gòu)逐步逼近對(duì)象的幾何模型，直到幾乎完全獲得對(duì)象的幾何特性。典型的類型有沿坐標(biāo)軸包圍盒AABB（axis-aligned bounding box）、包圍球（spheres）、方向包圍盒 OBB（oriented bounding box）、離散方向多面體k-DOP（k-discrete orientation polytopes）等。前者適用于對(duì)象較少且均勻分布的空間；后者適用于復(fù)雜環(huán)境中的碰撞檢測(cè)，且應(yīng)用廣泛。

2 層次包圍盒類型

2.1 AABB

AABB是指一個(gè)包含給定對(duì)象且各邊平行于坐標(biāo)軸的最小六面體，它需要6個(gè)標(biāo)量來描述，即組成物體基本幾何元素的頂點(diǎn)x、y、z坐標(biāo)的最大值和最小值。AABB的緊密性相對(duì)較差，但計(jì)算十分簡(jiǎn)單。AABB的相交測(cè)試是比較簡(jiǎn)單的，兩個(gè)對(duì)象當(dāng)且僅當(dāng)它們?cè)?個(gè)坐標(biāo)軸上的投影區(qū)間均重疊即相交；也是最快的，最多只需要6次比較運(yùn)算。AABB間的相交測(cè)試和包圍盒的更新速度比其他算法效率高，因此使用也最廣泛。

2.2 包圍球

包圍球被定義為包含該對(duì)象的最小的球體，僅需兩個(gè)標(biāo)量描述，即球心和半徑。包圍球的計(jì)算時(shí)間多于AABB，但存儲(chǔ)一個(gè)包圍球只需兩個(gè)浮點(diǎn)數(shù)，縮小了包圍盒所需的存儲(chǔ)空間。包圍球的相交測(cè)試比較簡(jiǎn)單，是用球體包圍整個(gè)幾何體。包圍球緊密性最差，故使用較少。

2.3 OBB

一個(gè)給定對(duì)象的OBB被定義為包含該對(duì)象且相對(duì)于坐標(biāo)軸方向任意的最小的正六面體。OBB的緊密性最好，因其方向的任意性使它可以根據(jù)被包圍對(duì)象的形狀特點(diǎn)盡可能緊密地包圍對(duì)象，大大提高了算法的效率。但這也使其相交測(cè)試變得復(fù)雜，不能有效處理變形體的碰撞檢測(cè)。一般來說，OBB的總體性能優(yōu)于前兩種方法，并且實(shí)時(shí)性較高。

2.4 k-DOP

由于AABB和包圍球的緊密性較差，而OBB的重疊測(cè)試和節(jié)點(diǎn)修改耗費(fèi)又較高，所以提出了一種折中的k-DOP算法。k-DOP是一個(gè)凸多面體，它使用k/2對(duì)平行平面來包圍物體。當(dāng)k值取足夠大時(shí)，k-DOP就發(fā)展成物體的凸包。

K的取值要根據(jù)碰撞檢測(cè)的不同需要而定，通過調(diào)整k值，k-DOP可以在碰撞檢測(cè)的簡(jiǎn)單性和包裹物體的緊密性之間靈活取舍，以滿足特定的要求。k-DOP的緊密性要優(yōu)于AABB，相交測(cè)試的復(fù)雜度要小于OBB，從而提高了碰撞檢測(cè)的效率。

3 混合包圍盒

對(duì)層次包圍盒法來說，其自身的簡(jiǎn)單性和所包圍物體的緊密性是相互矛盾的。簡(jiǎn)單性是指包圍盒要比被包圍的幾何對(duì)象簡(jiǎn)單，既要求幾何形狀簡(jiǎn)單易于計(jì)算，又要求相交測(cè)試算法簡(jiǎn)單運(yùn)算快速；緊密性則要求包圍盒盡可能貼近被包圍的對(duì)象。事實(shí)上，一種包圍盒的簡(jiǎn)單性越高則緊密性越差，反之亦然，很難達(dá)到一定的平衡。

一般來說，AABB較適合于橢長形但與坐標(biāo)軸夾角不大的物體，OBB則適合于橢長形且與坐標(biāo)軸有一定夾角的物體；而包圍球較適合于三個(gè)坐標(biāo)軸上分布比較均勻或經(jīng)常發(fā)生旋轉(zhuǎn)運(yùn)動(dòng)的物體，k-DOP則適合用在表面結(jié)構(gòu)比較復(fù)雜但不發(fā)生旋轉(zhuǎn)的物體上。

為了既能利用包圍盒的優(yōu)點(diǎn)，又能避免它們的不足，可以采用混合包圍盒法。即根據(jù)同一物體上不同的幾何特征選用不同的包圍盒，縮減可能發(fā)生碰撞的范圍，并通過包圍盒之間的求交運(yùn)算，優(yōu)化碰撞檢測(cè)算法，提高碰撞檢測(cè)的時(shí)效性。

4 結(jié)論

檢測(cè)速度的提高是機(jī)器人仿真系統(tǒng)碰撞檢測(cè)的核心問題。我們?cè)谄咦杂啥葯C(jī)器人仿真控制系統(tǒng)中，結(jié)合機(jī)器人動(dòng)作的軌跡采用了AABB-OBB混合包圍盒法。在包圍盒樹的頂層采用AABB，在樹的其他層次采用OBB，使AABB簡(jiǎn)單性好和OBB緊密性好的優(yōu)點(diǎn)有效結(jié)合。從而實(shí)現(xiàn)了碰撞檢測(cè)算法的優(yōu)化，加快了檢測(cè)的速度，提高了檢測(cè)的實(shí)時(shí)性和可靠性。實(shí)驗(yàn)結(jié)果表明，比OBB算法提高了大約10%～15%。此算法可應(yīng)用于形狀復(fù)雜剛體的實(shí)時(shí)碰撞檢測(cè)，并且場(chǎng)景規(guī)模越大，算法改進(jìn)的效果越明顯。

[1]崔漢國，陳軍，王大宇.虛擬環(huán)境中優(yōu)化的OBB碰撞檢測(cè)算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007(11)：2524-2526.

[2]申玉斌，蔡勇，華才健.虛擬環(huán)境中的碰撞檢測(cè)技術(shù)的研究與應(yīng)用[J].交通與計(jì)算機(jī)，2005(1)：23.

[3]蔡文軍，陳虎.基于混合模型的碰撞檢測(cè)優(yōu)化算法研究[J].計(jì)算機(jī)與現(xiàn)代化，2006(7)：49-52.

TP24

A

1674-6708（2011）48-0191-01