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

朱二喜， 徐 敏， 何援軍

(1. 江蘇信息職業技術學院物聯網工程系，江蘇 無錫 214153；2. 上海交通大學計算機工程系，上海 200240)

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

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

(1. 江蘇信息職業技術學院物聯網工程系，江蘇 無錫 214153；2. 上海交通大學計算機工程系，上海 200240)

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

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

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

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

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

碰撞檢測的目的是盡早將不會發生碰撞的對象從計算過程中剔除，使得處理過程專注于可能存在碰撞的物體之間的計算?？紤]到層次包圍體和空間劃分所存在的局限性，結合Delaunay三角網格[11]的結構特性及穩定性，本文提出了一種利用Delaunay三角剖分的碰撞檢測算法。該算法在減少兩兩組合測試數量的同時，也利于新物體對象的插入與退出，也適合于系統中存在少量移動物體，算法時間效率滿足現實應用的需要。

1 算法的基本原理

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

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

三角剖分實質是用三角形表示點集合中的各點與其相鄰點之間連接的拓撲關系。在一個點集合中，可能存在很多種的三角剖分，但Delaunay三角剖分是唯一的，也是最優的。Delaunay三角剖分存在許多的優化準則，其中空外接球準則和最小角最大準則就是確保三角剖分中盡可能避免出現病態的三角形。在3D點集中，如果不存在五點共球現象，則該點集的 Voronoi結構中每個面是 2個Voronoi多面體的公共面，每條邊恰好是 3個

Voronoi多面體的公共邊，并且每個頂點是 4個Voronoi多面體的公共點。將共一個Voronoi頂點的4個 Voronoi多面體所對應的點集中的點連成的四面體稱為該點集的Delaunay四面體。

在Delaunay三角剖分性質中，區域性對移動物體的碰撞檢測有著十分重要的意義。在 Delaunay三角網格中，區域性是指新增、刪除、移動某一個數據點時只會影響鄰近的三角形。如圖2所示，當物體由A移至B的過程中，在三角形234中進行碰撞檢測，當跨越三角形234的邊界24時要考慮與其相關B位置所在的三角形124的碰撞可能，所以必須與1物體進行測試，當完全到達三角形124內，只需要三角形124中的碰撞測試。

圖2 移動物體的碰撞過程

由此可見，Delaunay三角網格的區域性對物體移動的碰撞檢測帶來非常高的效率，首先，整個網格結構無需大地變化，只需對新物體插入的相關三角形進行跟進優化；其次，在局部范圍內兩兩組合碰撞測試的數量沒有太大變化，而層次包圍盒和空間劃分中樹型結構的更新將會耗費大量的時間，甚至在空間劃分中增加了兩兩組合測試的數量。

2 算法的具體實現

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

(1) 對復雜物體對象集合進行包圍盒預處理，獲取各物體對象包圍盒的中心點；

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

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

(4) 對局部新形成的三角形依據優化準則進行優化（如互換對角線等）。將形成的三角形置于三角形集合；

(5) 不斷循環執行步驟(3)，直至插入所有點。

如果系統需要查詢哪些對象之間存在碰撞，在步驟(3)中依次標記碰撞物體的組合，不要退出程序，繼續進行步驟(4)即可。

3 對象組合測試的優化

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

采用分離軸測試方法可以快速判斷兩個組合

物體的包圍體相交狀態。如果包圍體已經處于相交狀態，下一步工作就是進行底層的圖元測試。若將物體的全部圖元表述都參與測試，計算測試量是非常巨大的，可以采用針對發生重疊的兩個包圍體的重疊部分確定兩個對象的發生底層測試的基本圖元的數量。

由于三角形具有很好的穩定性，它經常被用來表示物體對象表面，物體對象碰撞測試的底層圖元測試就轉化為了空間三角形的位置關系計算。兩個空間三角形之間位置關系可采用文獻[12]所述的改進算法。

4 算法的實驗及分析

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

圖3 凸體樣本和碰撞場景

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

由此可見，采用Delaunay三角剖分的碰撞檢測技術時間效率能夠達到實際應用水平；算法實現比較方便，其并可對整個碰撞檢測過程實施檢測；此算法最適合用于在系統中少量物體存在的移動的場景，因為，物體對象的移動只會影響局部的三角剖分，而不影響全局物體對象。

表1 多次隨機分布對象的碰撞檢測平均時間

表2 相同環境條件下新算法與傳統算法的時間效率比較(ms)

圖4 時間效率比較

5 總 結

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

[1] 于凌濤, 王 濤, 宋華建, 等. 面向虛擬手術的碰撞檢測優化算法[J]. 哈爾濱工程大學學報, 2014, 35(9)：1164-1170.

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

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

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

[5] 高玉琴, 何云峰, 于俊清. 改進的基于AABB包圍盒的碰撞檢測算法[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] 孫繼忠, 胡 艷, 馬永強. 基于Delaunay三角剖分生成Voronoi圖算法[J]. 計算機應用, 2010, 30(1)： 75-79.

[12] 于海燕, 何援軍. 空間兩三角形的相交問題[J]. 圖學學報, 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

國家自然科學基金資助項目(61073083)

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