一種利用Delaunay三角剖分的碰撞檢測(cè)算法

朱二喜， 徐 敏， 何援軍

(1. 江蘇信息職業(yè)技術(shù)學(xué)院物聯(lián)網(wǎng)工程系，江蘇 無錫 214153；2. 上海交通大學(xué)計(jì)算機(jī)工程系，上海 200240)

一種利用Delaunay三角剖分的碰撞檢測(cè)算法

朱二喜1， 徐 敏1， 何援軍2

(1. 江蘇信息職業(yè)技術(shù)學(xué)院物聯(lián)網(wǎng)工程系，江蘇 無錫 214153；2. 上海交通大學(xué)計(jì)算機(jī)工程系，上海 200240)

虛擬現(xiàn)實(shí)中物體對(duì)象分布及運(yùn)動(dòng)情況呈現(xiàn)復(fù)雜多樣，碰撞檢測(cè)算法很難達(dá)到實(shí)時(shí)性和準(zhǔn)確性的要求。提出了一種基于Delaunay三角剖分的多物體碰撞檢測(cè)實(shí)時(shí)算法。該算法運(yùn)用包圍體緊密擬合物體對(duì)象，以包圍體的中心構(gòu)建離散數(shù)據(jù)點(diǎn)集，生成Delaunay三角網(wǎng)格，實(shí)施碰撞檢測(cè)，避免層次包圍盒和空間劃分的不利因素，物體的更新等操作限定在局部的三角形內(nèi)。實(shí)驗(yàn)表明在多物體的碰撞檢測(cè)中，即使存在若干移動(dòng)物體，算法能夠滿足實(shí)時(shí)性和準(zhǔn)確性的要求。

空間劃分；層次包圍盒；Delaunay三角剖分；碰撞檢測(cè)

碰撞檢測(cè)技術(shù)是虛擬游戲、物理仿真[1]、機(jī)器人技術(shù)[2]、虛擬樣機(jī)技術(shù)等應(yīng)用程序的基礎(chǔ)。目前碰撞檢測(cè)算法的研究方法主要有：基于物體空間的碰撞檢測(cè)算法和基于圖像空間的碰撞檢測(cè)算法[3]。后者通過降低空間維數(shù)，將3D投影轉(zhuǎn)到2D平面上，后分析2D圖像空間中的緩存信息，依次判斷兩物體之間碰撞情況；前者通過數(shù)學(xué)、幾何原理對(duì)虛擬物體的空間關(guān)系進(jìn)行計(jì)算，判斷物體碰撞與

否，此類算法分為層次包圍體[4]和空間劃分[5]。

層次包圍體是用簡(jiǎn)單的包圍體近似擬合復(fù)雜物體對(duì)象，后將包圍體整合到層次樹中，物體之間的碰撞檢測(cè)轉(zhuǎn)換成相應(yīng)樹葉節(jié)點(diǎn)的包圍體之間的碰撞檢測(cè)。典型的包圍體有球體[6]、AABB[7]、OBB[8]以及k-DOP[9]等。空間劃分技術(shù)是將整個(gè)虛擬空間劃分成多個(gè)子空間，碰撞檢測(cè)的物體范圍限定在同一空間或者相鄰子空間?？臻g劃分手段有均勻劃分、八叉樹、k-d樹、BSP樹等。文獻(xiàn)[6-9]介紹了優(yōu)秀的層次包圍體和空間劃分的實(shí)現(xiàn)算法，但其算法也存在很多的問題和困難。從衡量性能公式[10]來看層次包圍體，想得到較高的效率，必須構(gòu)造緊湊的包圍體，但構(gòu)造緊湊包圍體將會(huì)耗費(fèi)更多時(shí)間；層次包圍體也困于選擇劃分方法形成樹結(jié)構(gòu)，包含n個(gè)元素的集合共存在2n–1–1種方案可以將其劃分為兩個(gè)非空子集，顯然，只有少數(shù)方案真實(shí)可行；在劃分過程中會(huì)出現(xiàn)所選分割面跨越圖元，須采用何種方式加以正確處理跨越？如何確定樹的度數(shù)和分支系數(shù)？層次包圍體處理過程只能在運(yùn)行期間處理且相關(guān)數(shù)據(jù)結(jié)構(gòu)占據(jù)大量?jī)?nèi)存空間。而空間劃分技術(shù)雖然大大地減少組合測(cè)試的數(shù)量，但主要適用于物體分布較均勻的稀疏的場(chǎng)景中；如果處理形狀不同的物體之間的碰撞檢測(cè)時(shí)，很難保持一致的碰撞檢測(cè)效率；網(wǎng)格相對(duì)于對(duì)象尺寸的疏密程度，影響到對(duì)象關(guān)聯(lián)信息進(jìn)行更新、對(duì)象定位以及網(wǎng)格內(nèi)組合測(cè)試的數(shù)量；網(wǎng)格計(jì)算的開銷都是十分巨大的。

碰撞檢測(cè)的目的是盡早將不會(huì)發(fā)生碰撞的對(duì)象從計(jì)算過程中剔除，使得處理過程專注于可能存在碰撞的物體之間的計(jì)算?？紤]到層次包圍體和空間劃分所存在的局限性，結(jié)合Delaunay三角網(wǎng)格[11]的結(jié)構(gòu)特性及穩(wěn)定性，本文提出了一種利用Delaunay三角剖分的碰撞檢測(cè)算法。該算法在減少兩兩組合測(cè)試數(shù)量的同時(shí)，也利于新物體對(duì)象的插入與退出，也適合于系統(tǒng)中存在少量移動(dòng)物體，算法時(shí)間效率滿足現(xiàn)實(shí)應(yīng)用的需要。

1 算法的基本原理

碰撞檢測(cè)算法的優(yōu)越性體現(xiàn)在算法盡可能減少系統(tǒng)中兩兩組合碰撞檢測(cè)數(shù)量。在構(gòu)建層次包圍體形成樹結(jié)構(gòu)時(shí)，很難有一個(gè)好地劃分方案，特別是當(dāng)物體對(duì)象數(shù)量比較大時(shí)，層次包圍體局限性更加明顯；而在空間劃分技術(shù)中對(duì)象尺寸差異比較大，或者對(duì)象形狀比較特殊，分布不均勻，都會(huì)對(duì)碰撞檢測(cè)過程造成很大影響。在系統(tǒng)中，如果明確物體對(duì)象的相對(duì)位置，物體對(duì)象只與它最鄰近的物體進(jìn)行測(cè)試，兩兩組合測(cè)試的數(shù)量就會(huì)大大減少，據(jù)此，如果將系統(tǒng)中的物體對(duì)象集合看成點(diǎn)集，進(jìn)行三角剖分，那么物體對(duì)象在系統(tǒng)中相對(duì)位置就比較明確了。

如圖1(a)所示平面上多個(gè)物體對(duì)象，假設(shè)不存在碰撞，對(duì)多個(gè)物體已經(jīng)進(jìn)行了三角剖分，當(dāng)有一個(gè)物體對(duì)象進(jìn)入平面，所插入的位置如圖 1(b)所示，則只需對(duì)該對(duì)象與其相鄰物體兩兩組合測(cè)試即可。Delaunay三角剖分正是Voronoi圖的對(duì)偶圖，有Voronoi圖的定義可知，選擇Delaunay三角剖分能夠使碰撞檢測(cè)更具有效性。

三角剖分實(shí)質(zhì)是用三角形表示點(diǎn)集合中的各點(diǎn)與其相鄰點(diǎn)之間連接的拓?fù)潢P(guān)系。在一個(gè)點(diǎn)集合中，可能存在很多種的三角剖分，但Delaunay三角剖分是唯一的，也是最優(yōu)的。Delaunay三角剖分存在許多的優(yōu)化準(zhǔn)則，其中空外接球準(zhǔn)則和最小角最大準(zhǔn)則就是確保三角剖分中盡可能避免出現(xiàn)病態(tài)的三角形。在3D點(diǎn)集中，如果不存在五點(diǎn)共球現(xiàn)象，則該點(diǎn)集的 Voronoi結(jié)構(gòu)中每個(gè)面是 2個(gè)Voronoi多面體的公共面，每條邊恰好是 3個(gè)

Voronoi多面體的公共邊，并且每個(gè)頂點(diǎn)是 4個(gè)Voronoi多面體的公共點(diǎn)。將共一個(gè)Voronoi頂點(diǎn)的4個(gè) Voronoi多面體所對(duì)應(yīng)的點(diǎn)集中的點(diǎn)連成的四面體稱為該點(diǎn)集的Delaunay四面體。

在Delaunay三角剖分性質(zhì)中，區(qū)域性對(duì)移動(dòng)物體的碰撞檢測(cè)有著十分重要的意義。在 Delaunay三角網(wǎng)格中，區(qū)域性是指新增、刪除、移動(dòng)某一個(gè)數(shù)據(jù)點(diǎn)時(shí)只會(huì)影響鄰近的三角形。如圖2所示，當(dāng)物體由A移至B的過程中，在三角形234中進(jìn)行碰撞檢測(cè)，當(dāng)跨越三角形234的邊界24時(shí)要考慮與其相關(guān)B位置所在的三角形124的碰撞可能，所以必須與1物體進(jìn)行測(cè)試，當(dāng)完全到達(dá)三角形124內(nèi)，只需要三角形124中的碰撞測(cè)試。

圖2 移動(dòng)物體的碰撞過程

由此可見，Delaunay三角網(wǎng)格的區(qū)域性對(duì)物體移動(dòng)的碰撞檢測(cè)帶來非常高的效率，首先，整個(gè)網(wǎng)格結(jié)構(gòu)無需大地變化，只需對(duì)新物體插入的相關(guān)三角形進(jìn)行跟進(jìn)優(yōu)化；其次，在局部范圍內(nèi)兩兩組合碰撞測(cè)試的數(shù)量沒有太大變化，而層次包圍盒和空間劃分中樹型結(jié)構(gòu)的更新將會(huì)耗費(fèi)大量的時(shí)間，甚至在空間劃分中增加了兩兩組合測(cè)試的數(shù)量。

2 算法的具體實(shí)現(xiàn)

在三角剖分前，為了提高算法效率，對(duì)復(fù)雜物體對(duì)象進(jìn)行包圍體處理，加快物體兩兩組合測(cè)試。在2D空間中，以復(fù)雜物體包圍盒的中心點(diǎn)作為數(shù)據(jù)點(diǎn)集，進(jìn)行平面的三角剖分；在3D空間中，以復(fù)雜物體的包圍體的中心點(diǎn)作為數(shù)據(jù)集，進(jìn)行空間的三角剖分。進(jìn)行 Delaunay三角剖分的算法非常多，按照其實(shí)現(xiàn)過程分為分治算法、貪心算法、逐點(diǎn)插入算法、三角網(wǎng)生長(zhǎng)法。以插入算法為例實(shí)現(xiàn)碰撞檢測(cè)，步驟如下：

(1) 對(duì)復(fù)雜物體對(duì)象集合進(jìn)行包圍盒預(yù)處理，獲取各物體對(duì)象包圍盒的中心點(diǎn)；

(2) 以中心點(diǎn)作為點(diǎn)集合，獲取容納集合中全部點(diǎn)最合適的初始三角形，將其放入三角形集合中，以三角形的3個(gè)頂點(diǎn)為中心構(gòu)建3個(gè)互不相交的3個(gè)包圍盒，這3個(gè)包圍盒的距離適當(dāng)遠(yuǎn)，以致復(fù)雜物體集合的任意一個(gè)都不與它們相交；

(3) 依次將點(diǎn)集合中的中心點(diǎn)進(jìn)行插入。在三角形集合中找出其外接圓包含插入點(diǎn)的影響三角形，刪除該點(diǎn)的影響三角形的公共邊，將插入點(diǎn)同三角形的3個(gè)頂點(diǎn)連線，將新插入的物體的包圍盒與影響三角形的3個(gè)包圍盒進(jìn)行兩兩組合測(cè)試，若有相交，則算法退出；若無，繼續(xù)步驟(4)；

(4) 對(duì)局部新形成的三角形依據(jù)優(yōu)化準(zhǔn)則進(jìn)行優(yōu)化（如互換對(duì)角線等）。將形成的三角形置于三角形集合；

(5) 不斷循環(huán)執(zhí)行步驟(3)，直至插入所有點(diǎn)。

如果系統(tǒng)需要查詢哪些對(duì)象之間存在碰撞，在步驟(3)中依次標(biāo)記碰撞物體的組合，不要退出程序，繼續(xù)進(jìn)行步驟(4)即可。

3 對(duì)象組合測(cè)試的優(yōu)化

在碰撞系統(tǒng)完成物體對(duì)象剔除操作之后，對(duì)兩物體直接進(jìn)行底層的基本圖元測(cè)試，系統(tǒng)效率定會(huì)大打折扣，選擇一種有效的方法繼續(xù)判斷兩個(gè)物體對(duì)象存在碰撞，這將進(jìn)一步提高碰撞檢測(cè)的效率。在整個(gè)碰撞過程中，所有算法實(shí)現(xiàn)的策略都是盡量避免發(fā)生底層測(cè)試或者在發(fā)生底層測(cè)試時(shí)減少基本圖元測(cè)試的數(shù)量。Larcombe給出了一種成本低廉的分離軸測(cè)試方法，提高了兩兩組合碰撞測(cè)試的效率。由于凸體的特性，凸體間若不相交，則必存在可以插入一個(gè)平面的間隙，從而可以判斷兩個(gè)凸體不存在碰撞可能。物體對(duì)象間若存在凹體，有必要采用相應(yīng)的曲面判斷對(duì)象間是否存在碰撞可能。若物體對(duì)象已為碰撞狀態(tài)，則無論平面還是曲面都無法實(shí)現(xiàn)對(duì)象間的分離。

采用分離軸測(cè)試方法可以快速判斷兩個(gè)組合

物體的包圍體相交狀態(tài)。如果包圍體已經(jīng)處于相交狀態(tài)，下一步工作就是進(jìn)行底層的圖元測(cè)試。若將物體的全部圖元表述都參與測(cè)試，計(jì)算測(cè)試量是非常巨大的，可以采用針對(duì)發(fā)生重疊的兩個(gè)包圍體的重疊部分確定兩個(gè)對(duì)象的發(fā)生底層測(cè)試的基本圖元的數(shù)量。

由于三角形具有很好的穩(wěn)定性，它經(jīng)常被用來表示物體對(duì)象表面，物體對(duì)象碰撞測(cè)試的底層圖元測(cè)試就轉(zhuǎn)化為了空間三角形的位置關(guān)系計(jì)算。兩個(gè)空間三角形之間位置關(guān)系可采用文獻(xiàn)[12]所述的改進(jìn)算法。

4 算法的實(shí)驗(yàn)及分析

算法采用2.5 GHz CPU主頻、內(nèi)存4 G的筆記本，為了測(cè)試方便，選擇幾個(gè)凸體樣本作為測(cè)試對(duì)象，如圖3所示，選擇數(shù)量為100、300、500、800、1 000、2 000、3 000，這些凸體的位置隨機(jī)分布在世界坐標(biāo)系中，在凸體位置確定后，采用OBB進(jìn)行擬合，利用直接插入法對(duì)樣本凸體包圍體中心進(jìn)行三角剖分。

圖3 凸體樣本和碰撞場(chǎng)景

當(dāng)物體對(duì)象直接插入三角網(wǎng)格時(shí)，有可能在插入過程就產(chǎn)生碰撞，碰撞提早退出，這里，以平均的碰撞檢測(cè)時(shí)間來衡量。表1為多次隨機(jī)分布所得的平均碰撞檢測(cè)時(shí)間；表2、圖4所示，相同條件環(huán)境下，采用Delaunay三角剖分的碰撞檢測(cè)與傳統(tǒng)的層次包圍盒和空間劃分技術(shù)算法時(shí)間效率的比較，為了比較的統(tǒng)一和快捷，此處采用AABB作為物體對(duì)象包圍體。

由此可見，采用Delaunay三角剖分的碰撞檢測(cè)技術(shù)時(shí)間效率能夠達(dá)到實(shí)際應(yīng)用水平；算法實(shí)現(xiàn)比較方便，其并可對(duì)整個(gè)碰撞檢測(cè)過程實(shí)施檢測(cè)；此算法最適合用于在系統(tǒng)中少量物體存在的移動(dòng)的場(chǎng)景，因?yàn)椋矬w對(duì)象的移動(dòng)只會(huì)影響局部的三角剖分，而不影響全局物體對(duì)象。

表1 多次隨機(jī)分布對(duì)象的碰撞檢測(cè)平均時(shí)間

表2 相同環(huán)境條件下新算法與傳統(tǒng)算法的時(shí)間效率比較(ms)

圖4 時(shí)間效率比較

5 總 結(jié)

本文算法的優(yōu)點(diǎn)在于物體對(duì)象在系統(tǒng)中的相對(duì)位置比較明確，兩兩組合碰撞測(cè)試的數(shù)量大大減少；其次避免了空間劃分技術(shù)中網(wǎng)格與對(duì)象尺寸的糾結(jié)，不需要考慮網(wǎng)格的疏密程度，省去了對(duì)象歸入空間以及空間重疊的對(duì)象與相鄰空間的碰撞檢測(cè)；再次避免了層次包圍體中選擇超平面對(duì)象的劃分與樹形結(jié)構(gòu)的深度和廣度問題，以及分隔軸和分割處的選擇問題；最后，在系統(tǒng)中對(duì)物體對(duì)象的插入、刪除、更新或者移動(dòng)，得到非常好地處理，因?yàn)樵?Delaunay三角剖分中這些操作只會(huì)影響與之關(guān)聯(lián)的三角形，而不會(huì)對(duì)整個(gè)系統(tǒng)產(chǎn)生影響。雖然層次包圍體能夠使多物體碰撞檢測(cè)的時(shí)間效率降至log級(jí)別，但在預(yù)處理階段，平方級(jí)劃分對(duì)象的復(fù)雜性，使得該技術(shù)的預(yù)計(jì)算不容忽視，而該算法將包圍體整合至Delaunay三角網(wǎng)格中，其時(shí)間復(fù)雜度可降至O(n)，此外在系統(tǒng)中對(duì)單物體對(duì)象的碰撞檢測(cè)的時(shí)間效率只有O(1)，因?yàn)樵诰W(wǎng)格中單物體只有與其相鄰的點(diǎn)有碰撞的可能。

[1] 于凌濤, 王 濤, 宋華建, 等. 面向虛擬手術(shù)的碰撞檢測(cè)優(yōu)化算法[J]. 哈爾濱工程大學(xué)學(xué)報(bào), 2014, 35(9)：1164-1170.

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

[3] 王 磊, 王毅剛. 基于GPU加速的多物體碰撞檢測(cè)方法[J]. 計(jì)算機(jī)工程與科學(xué), 2009, 31(12)： 52-55.

[4] 熊 濤, 付鶴崗. 蒙皮骨骼動(dòng)畫的碰撞檢測(cè)研究[J].計(jì)算機(jī)應(yīng)用, 2008, 28(3)： 683-685.

[5] 高玉琴, 何云峰, 于俊清. 改進(jìn)的基于AABB包圍盒的碰撞檢測(cè)算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2007, 28(16)：3815-3817.

[6] O? Sullivan C, Dingliana J. Real-time collision detection and response using sphere-trees [C]//Proceedings of the Spring Conference on Computer Graphics. Bratislava, Slovakia, 1999： 83-92.

[7] Larsson T, Akenine-M?ller L. Collision detection for continuously eforming bodies [J]. Eurographics, 2001, 24：325-333.

[8] Gottschalk S, Lin M C, Manocha D. OBBTree： a hierarchical structure for rapid interference detection [C]//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New York, USA, 1996： 171-180.

[9] Zachmann G. Rapid collision detection by dynamically aligned DOP-Trees [C]//Proceedings of IEEE, VRAIS?98, Atlanta, USA, 1998： 90-97.

[10] He Taosong. Fast collision detection using QuOSPO trees [C]//Proceedings of the 1999 Symposium on Interactive 3D Graphics. New York, USA, 1999：55-62.

[11] 孫繼忠, 胡 艷, 馬永強(qiáng). 基于Delaunay三角剖分生成Voronoi圖算法[J]. 計(jì)算機(jī)應(yīng)用, 2010, 30(1)： 75-79.

[12] 于海燕, 何援軍. 空間兩三角形的相交問題[J]. 圖學(xué)學(xué)報(bào), 2013, 34(4)： 54-62.

A Collision Detection Algorithm Using Delaunay Triangulation

Zhu Erxi1, Xu Min1, He Yuanjun2
(1. Department of Internet of Things & Engineering, Jiangsu Institute of Information Technology, Wuxi Jiangsu 214153, China; 2. Department of Computer Science & Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

The distribution and movement of objects in virtual reality show varied complications, so that the real-time and accuracy of collision detection algorithms are difficult to meet the requirements. A real-time algorithm is presented for multi-body collision detection based on Delaunay triangulation. The algorithm uses bounding volume close fitting objects, constructs discrete aggregates using centers of bounding volume, generate Delaunay triangular mesh, implements collision detection. This algorithm avoids the unfavorable factors of bounding volume hierarchy and space division. The update operation of objects is defined in the local triangles. The experiments show that the algorithm can meet the real-time and accuracy requirements in the multi objects detection system in the presence of several moving objects.

space division; bounding volume hierarchy; Delaunay triangulation; collision detection

TP 391.72

A

2095-302X(2015)04-0516-05

2014-12-03；定稿日期：2015-01-03

國家自然科學(xué)基金資助項(xiàng)目(61073083)

朱二喜(1981–)，男，江蘇無錫人，講師，碩士。主要研究方向?yàn)閳D形圖像處理、信息技術(shù)。E-mail：erxi666@163.com