虛擬場景中動態碰撞檢測算法研究

摘 要：在虛擬場景中，為了保持環境的真實性，為使用者提供沉浸式體驗，需要及時進行碰撞檢測，更新繪制結果。碰撞檢測技術是虛擬現實領域中的關鍵問題之一，具有廣闊的應用前景。碰撞檢測算法分為動態和靜態兩方面，其中動態碰撞檢測算法是目前的研究重點。本文對常見的動態碰撞檢測算法展開討論，并展望了動態碰撞檢測未來的發展方向。

關鍵詞：碰撞檢測；動態；物體空間；圖像空間

中圖分類號：TP391.9 文獻標識碼：A 文章編號：2096-4706（2018）06-0115-02

Abstract：In the virtual scene，in order to maintain the authenticity of the environment and provide the user with immersion experience，collision detection should be carried out in time and the result of drawing is updated. Collision detection technology is one of the key problems in the field of virtual reality，and has broad application prospects. Collision detection algorithm is divided into two aspects：dynamic and static. Dynamic collision detection algorithm is the focus of current research. In this paper，common dynamic collision detection algorithms are discussed，and the future research directions of dynamic collision detection are prospected.

Keywords：collision detection；dynamic；object space；image space

0 引 言

隨著計算機仿真技術的快速發展，虛擬現實技術被廣泛地應用于如醫療、游戲等領域。其中，碰撞檢測是虛擬現實中的關鍵技術之一。近年來對虛擬場景描述性的精確性、復雜度均在日益提升，使用者對虛擬環境下的沉浸式體驗感要求也在不斷提高，高效、實時性的碰撞檢測算法已成為人們研究的熱點問題。碰撞檢測算法的實質是檢測在同一時刻是否存在多個物體處于同一共享空間。

目前，主流的碰撞檢測算法分為兩大類，即靜態檢測算法和動態檢測算法。其中，靜態檢測算法不需要進行預處理，主要針對靜止狀態下各物體是否發生碰撞展開研究，該算法在精度方面要求嚴格，同時具有較高的計算復雜度，從現有情況來看，大部分算法多傾向于平面內凸多邊形的研究。動態碰撞檢測算法針對物體在動態情況下檢測是否有碰撞發生，比如虛擬博物館場景下，使用者在參觀過程中是否與其他使用者或者其他物體產生碰撞。動態碰撞檢測算法是碰撞檢測算法中的研究重點。本文著重針對動態碰撞檢測算法展開討論。

1 動態碰撞檢測算法

動態碰撞檢測算法分為離散碰撞檢測和連續碰撞檢測兩種。其中，離散碰撞檢測因其檢測速度較快，是檢測算法中的重要研究內容?；诳臻g角度的不同，離散碰撞檢測分為基于物體空間的碰撞檢測算法以及基于圖像空間的碰撞檢測算法。基于物體空間的碰撞檢測算法中，比較經典的算法是空間分割法和層次包圍盒法。

1.1 空間分割法

空間分割法的主要思想是根據某些劃分規則將空間劃分為多個等體積的子單元格，對處于同一子單元格中的物體進行碰撞的相交測試?？臻g分割法只適用于物體在空間均勻分布的稀疏環境，當物體的數量較多且分布不均勻時，如果分割不恰當會導致計算量增大，降低碰撞檢測的效率，且會占用大量的存儲空間?？臻g分割法中常見的算法包括均勻網格法、八叉樹法及BSP樹算法[1]。均勻網格法的重點是選擇合適的尺寸來分割物理空間，比較適合軟體對象的檢測。八叉樹法主要用于三維空間的碰撞檢測中，基本思想是首先將空間劃分為八個相同大小的立方體，如果劃分后的子立方體中的物體數量依然較多，則將子立方體再分解為八個，直至子立方體中的物體數量滿足要求為止。BSP樹法可以用于任何維度的碰撞檢測場景中，其重點是分割平面的確定。

國內外的研究學者對基于空間分割的碰撞檢測算法展開了深入研究。Moore等人基于Cyrus-Beek裁剪算法對凸多面體和凹多面體展開碰撞檢測[2]。劉燕翎等人在八叉樹基礎上，提出了一種新的適合動態場景中對物體碰撞進行檢測的交互樹算法，實現對物體對象有規律地進行剖分后的有效碰撞檢測[3]。

1.2 層次包圍盒法

層次包圍盒法的基本思想是利用包圍盒將物體及它的所有單元子集進行包裹，從而構造出層次樹，再通過遍歷兩個物體的層次包圍盒進行相交檢測。包圍盒緊密性的好壞將直接影響檢測算法的執行效率。常見的層次包圍盒算法有包圍球、OBB包圍盒（任意方向包圍盒）、AABB包圍盒（軸向包圍盒）、K-DOPs包圍盒（離散方向包圍盒）等。層次包圍盒具有檢測速度快、效率高、構造簡單等特點，是虛擬場景碰撞檢測中使用較為廣泛的一種算法。

Gino在基于AABB包圍盒算法基礎上，提出了一種對于復雜模型進行剛性運動和變形的檢測方法，實現模型變形時快速更新AABB樹[4]。Gottschalk提出了層次包圍盒性能的計算公式，在相交測試代價和相交測試數量這二者之間實現平衡[5]。靳雁霞等人提出了基于包圍球的變形體碰撞檢測算法，通過粒子群算法將三維空間問題簡化為二維空間問題，能對變形體碰撞展開檢測，且執行效率較高[6]。

如果虛擬場景中物體數目較多時，單一的包圍盒檢測算法不僅會占用大量的存儲空間，還會增加相交測試的時間開銷，難以滿足檢測的精確性和實時性的要求。針對復雜場景中的碰撞檢測，人們對基本的包圍盒算法進行改進，結合其他算法來提高檢測效率。王振文等人在OBB包圍盒算法基礎上提出了一種基于拓撲網格的碰撞檢測算法，利用網格單元與物體之間的投影相交測試對碰撞進行檢測，最終得出精確碰撞點[7]。劉昭等人提出了一種將八叉樹和層次包圍盒算法結合的快速碰撞檢測算法，實現了在保證檢測精確性的情況下提高檢測的實時性[8]。

1.3 基于圖像空間的碰撞檢測算法

目前，基于圖像空間的碰撞檢測算法主要基于兩種，一種是用圖像處理器GPU（Graphics Processing Unit，GPU）分擔CPU的工作量，通過緩沖區域的色度值來對碰撞情況進行檢測。另一種是將物體的投影從三維投影到二維參考平面上，通過在不同階段投影獲得的緩存信息計算分析來對碰撞進行檢測。對于變形體來說，與包圍盒檢測算法不同，基于圖像空間的碰撞檢測算法不用對變形體進行預處理，實時性更好，更適用于變形體之間的碰撞檢測。

近年來，隨著圖形硬件的飛速發展，基于圖像空間的碰撞檢測算法研究已取得了較多的成果。Baciu等人結合多種緩存的組合功能，提出RECODE算法，一定程度上提高了碰撞檢測的效率[9]。于海軍等人針對物體較多、規模較大的復雜場景，提出了一種新的基于圖像空間的快速碰撞檢測算法。算法融合了OBB包圍盒算法優勢和GPU的加速繪制功能，通過構造可能存在的碰撞檢測集，提高檢測效率[10]。鄒益勝等人根據光線與封閉物體間的相交性，設計出的基于圖像空間的碰撞檢測算法可以處理包括非凸體在內的多種物體，具有較好的檢測平穩性[11]。由于GPU的使用，如何保持檢測準確性與繪制的快速性，如何使用基于圖像空間的碰撞檢測算法在大規模復雜場景中的應用等問題已引起了人們的廣泛關注。

2 結 論

碰撞檢測算法在虛擬場景中有著重要作用，為了實現用戶方便友好地與虛擬系統進行交互，需要快速準確地檢測出碰撞發生的位置信息，要求虛擬系統中選擇的碰撞檢測算法具有高實時性和高精確性。

本文著重對虛擬場景中的動態碰撞檢測算法進行了綜述，對目前常見的檢測算法，包括空間分割法、層次包圍盒法、以及基于圖像空間碰撞算法中已取得的研究成果進行了介紹。在今后的研究中，碰撞檢測算法在復雜場景中的應用、軟體模型、接觸與干涉的區分等問題還需要進一步的進行探討。

參考文獻：

[1] Christer Ericson.實時碰撞檢測算法技術 [M].劉天慧，譯.北京：清華大學出版社，2010.

[2] Moore M，Wilhelms J. Collision Detection and Response for Computer Animation [C].Conference on Computer Graphics and Interactive Techniques ACM，1988.

[3] 劉雁翎，諸昌鈐.一種適合處理動態場景的交互樹 [J].計算機應用，2001（11）：7-9.

[4] Gino van den Bergen. Efficient Collision Detection of Complex Deformable Models using AABB Trees [J].Journal of Graphics Tools，1997，2（4）：1-13.

[5] Gottschalk S，Lin M C，Manocha D. OBB Tree：a hierarchica lstructure for rapid interference detection [C].Conference on Computer Graphics and Interactive Techniques ACM，1996：171-180.

[6] 靳雁霞，任超，李照，等.融合智能算法的變形體碰撞檢測算法研究 [J].計算機工程與應用，2017，53（19）：130-135.

[7] 王振文，徐華.復雜場景中基于拓撲空間網格的碰撞檢測算法 [J].計算機系統應用，2017（12）：116-123.

[8] 劉昭，李偉，趙魯陽，等.基于空間剖分和分類遍歷的碰撞檢測算法 [J].電子設計工程，2016，24（24）：151-153.

[9] Baciu G，Wong SK，Sun H. RECODE：an image-based collision detection algorithm [J].Computer Animation and Virtual Worlds，2015，10（4）：181-192.

[10] 于海軍，馬純永，張濤，等.基于圖像空間的快速碰撞檢測算法 [J].計算機應用，2013，33（2）：530-533.

[11] 鄒益勝，丁國富，周曉莉，等.一種基于圖像空間的碰撞檢測算法 [J].系統仿真學報，2011，23（5）：944-949.

作者簡介：李佳（1982-），女，四川雅安人，副教授，碩士研究生。研究方向：虛擬現實技術；董屹（1980-），男，四川南充人，館員，碩士研究生。研究方向：計算機軟件設計。