并行連續(xù)碰撞檢測算法綜述

朱亞輝　黃襄念　張亞俊

摘 要： 在參考大量國內(nèi)外文獻的基礎(chǔ)之上，分析了GPU并行計算的連續(xù)碰撞檢測算法的相關(guān)理論、研究現(xiàn)狀和研究熱點問題。目前，隨著計算機圖形硬件的快速發(fā)展，為了實現(xiàn)大型虛擬復(fù)雜動態(tài)場景實時性交互、高精度和高執(zhí)行效率的目的，采用GPU并行計算與碰撞檢測先進算法相結(jié)合的方式，使得連續(xù)碰撞檢測算法的應(yīng)用與發(fā)展都有了開創(chuàng)性地變革。最后對其技術(shù)難點和發(fā)展方向進行了總結(jié)與展望。

關(guān)鍵詞： 圖形硬件； 虛擬現(xiàn)實； GPU； 并行計算； 連續(xù)碰撞檢測

中圖分類號：TP391.09 文獻標(biāo)志碼：A 文章編號：1006-8228（2015）06-04-03

Abstract： This paper， based on a large number of domestic and foreign literature reading， analyzes the related theories of continuous collision detection algorithm for GPU parallel computing， the research status and the research hot topics. At present， with the rapid development of computer graphics hardware， in order to achieve large-scale complex virtual dynamic scene real-time interaction， high precision and high efficiency of implementation， using a combination of GPU parallel computing and advanced collision detection algorithm， which includes the bounding box hierarchy method， the distance tracking method and the continuous collision detection algorithm， the application and development of continuous collision detection algorithm has a groundbreaking change. Finally the research difficulties and the development direction of the technology are summarized and prospected.

Key words： graphics hardware； virtual reality； GPU； parallel computation； continuous collision detection

0 引言

隨著計算機應(yīng)用技術(shù)的快速發(fā)展，人類對于計算性能的追求更加逾越，作為高性能計算和超級計算的核心技術(shù)，并行計算是充分利用資源加速計算的主要途徑。在虛擬現(xiàn)實、3D游戲、軍事模擬和手術(shù)仿真等領(lǐng)域，計算機圖形硬件的迅速發(fā)展，使得連續(xù)碰撞檢測算法在對提高虛擬場景的執(zhí)行效率和流暢性等方面，發(fā)揮出了非常重要的作用。本文主要對現(xiàn)有的碰撞檢測算法進行實質(zhì)性分析，深入學(xué)習(xí)連續(xù)碰撞檢測的特征與優(yōu)點，GPU與并行的計算方案，分析當(dāng)前的研究形式，總結(jié)技術(shù)經(jīng)驗和存在的問題，進而探討GPU多核可并行的連續(xù)碰撞檢測算法。

1 相關(guān)理論分析

本文在查閱大量國內(nèi)外文獻和參考書籍的基礎(chǔ)上，總結(jié)和分析了GPU并行連續(xù)碰撞檢測算法的基本理論，對以后多核并行的研究提供了巨大的參考價值。

1.1 碰撞檢測

在計算機輔助設(shè)計與制造（CAD/CAM）、計算機幾何、機器人和自動化、工程分析、計算機圖形學(xué)、虛擬現(xiàn)實等領(lǐng)域中，碰撞檢測是關(guān)鍵性問題，它主要完成：監(jiān)測模型之間是否發(fā)生碰撞，報告發(fā)生或即將發(fā)生碰撞的部位，動態(tài)的查詢模型之間的距離。從計算幾何的角度理解是二維模型的移動構(gòu)成了三維集合的形式。

影響碰撞檢測的關(guān)鍵因素有：實時性，精確度，沉侵性，模型類別，檢測類別，以及場景特征等，這些因素都影響它的實時碰撞效率。

1.2 連續(xù)碰撞檢測的先進算法

1.2.1 包圍盒層次法

該算法的基本思想是：用一個簡單的包圍盒將復(fù)雜的幾何形體圍住，當(dāng)對兩個物體碰撞檢測時，首先檢查兩者的包圍盒是否相交，若不相交，則說明兩個物體未發(fā)生碰撞，否則再進一步對兩個物體做檢測，求包圍盒的交運算，快速排出不相交的物體，從而加速了算法。

典型的包圍盒有軸向包圍盒（AABB）、方向包圍盒樹（OBB）和球形包圍盒?；跁r空包圍盒的空間分割法，其中應(yīng)用最廣泛的是任意空間二分法、四叉樹和空間八叉樹。

1.2.2 距離跟蹤算法

該算法通過尋找和跟蹤兩個多面體之間的最近點來計算它們之間的距離，當(dāng)距離小于或等于零時，兩者就發(fā)生了碰撞。距離跟蹤算法分為靜態(tài)和動態(tài)兩種。典型的靜態(tài)算法是Dobkin-Kirkpatrick算法，其基本思想是在線性條件下對模型做預(yù)處理運算，建立層次數(shù)據(jù)結(jié)構(gòu)，從計算本質(zhì)性問題上降低復(fù)雜度。處理動態(tài)距離計算的一般方法是將時間離散化，根據(jù)模型當(dāng)前的位置和方向計算距離，設(shè)定合適的檢測空間，通過時間間隔判定最近特征（包括：點、線、面）。利用這種跟蹤模型的最近特征的方法，并利用運動連續(xù)性就可以取代靜態(tài)距離的計算。

1.2.3 連續(xù)碰撞檢測算法

連續(xù)碰撞檢測算法是指在一個連續(xù)的時間間隔[t1，tn]內(nèi)，判斷運動物體是否與其他物體相交的算法。從本質(zhì)上說，在大規(guī)模場景中其計算速度比較慢，其優(yōu)點在于保證算法效率上，加入四維時空問題和結(jié)構(gòu)空間精度建模，使連續(xù)碰撞檢測算法很好地解決了離散碰撞檢測算法的穿刺和遺漏現(xiàn)象。

連續(xù)碰撞用線性插值計算相應(yīng)點在兩個時間域的運動軌跡，并把碰撞檢測簡化為執(zhí)行基本元素測試，可以檢測離散時間點間發(fā)生的碰撞，很好地解決了“隧道效應(yīng)”問題。目前先進的算法有：基于代數(shù)方法的連續(xù)碰撞檢測[1]、基于距離的碰撞檢測算法[2]和基于運動插值的算法[3]等。這兩年來，文獻[4]基于分離距離的碰撞檢測算法，從包圍體層次樹、代數(shù)幾何特征、單純形法、數(shù)學(xué)規(guī)劃、距離場等區(qū)分角度進行分析與討論，碰撞檢測對象正朝著多表現(xiàn)形式、非凸、形變、多物體發(fā)展，碰撞檢測算法正朝著動態(tài)、連續(xù)、并行化發(fā)展。文獻[5]提出基于距離的凸體快速連續(xù)碰撞檢測算法，通過判斷一段時間內(nèi)兩物體之間的最小距離是否為零，來確定發(fā)生碰撞的精確位置，對多個運動物體間的連續(xù)碰撞檢測，根據(jù)環(huán)境要求做出相應(yīng)響應(yīng)，調(diào)整運動物體位置，有效的提高了實時性和準(zhǔn)確性。

1.3 GPU及并行計算

1.3.1 GPU工作原理和特點

GPU工作原理：完成3D圖形的生成，將圖形映射到相應(yīng)的像素點上，對每個像素進行計算確定最終顏色并完成輸出。

GPU能夠從硬件上支持多邊形變換和光源處理，確定計算機多邊形的3D位置和處理動態(tài)光線效果，也稱為3D渲染的“幾何處理”。

主要特征：超長圖形流水線技術(shù)、高速緩存和并行計算。

1.3.2 GPU構(gòu)造和處理流程

圖形處理器從固定圖形處理流水線已發(fā)展到現(xiàn)在可編程圖形處理流水線，使實時碰撞檢測等發(fā)生了巨大改變。GPU的圖形處理流水線完成如下工作。①頂點處理：這階段GPU讀取描述3D圖形外觀的頂點數(shù)據(jù)，并根據(jù)頂點數(shù)據(jù)確定3D圖形的形狀及位置關(guān)系。②光柵化處理：顯示將上面生成的圖形上的點和線通過一定的算法轉(zhuǎn)換成相應(yīng)的像素點。③像素處理：GPU完成對像素的計算和處理，來確定每個像素的最終屬性。④輸出圖像：由光柵化引擎最終完成像素的輸出，顯示出圖像，以幀率的形式保存在顯存幀緩沖區(qū)。

概述GPU圖形繪制管線，可分為三個主要階段。①應(yīng)用程序階段：使用高級編程語言（C、C++、Java等）進行開發(fā)，主要和CPU、內(nèi)存打交道，完成碰撞檢測。②幾何階段：完成頂點坐標(biāo)變換、光照、裁剪、投影以及屏幕映射，經(jīng)過變換和投影之后得到頂點坐標(biāo)、顏色和紋理坐標(biāo)。③光柵化階段：基于幾何階段的輸出數(shù)據(jù)，為像素正確著色，每個像素的信息存儲在顏色緩沖器中，以便繪制完整的圖像。

1.3.3 GPU的并行計算

無論是CPU發(fā)送給GPU的頂點數(shù)據(jù)，還是GPU光柵生成器產(chǎn)生的像素數(shù)據(jù)都是按照并行處理的方法做獨立計算。頂點數(shù)據(jù)和像素數(shù)據(jù)一般都是由四元數(shù)表示，適合于并行計算。在GPU中專門設(shè)置了SIMD指令來處理向量，一次可同時處理四路數(shù)據(jù)，為了進一步提高并行度，可以增加流水線的條數(shù)。多條流水線可以在單一控制部件的集中控制下運行，也可以獨立運行。在單指令多數(shù)據(jù)流的結(jié)構(gòu)中，GPU通過單指令多數(shù)據(jù)流指令類型來支持?jǐn)?shù)據(jù)并行計算。

2 并行連續(xù)碰撞檢測算法研究現(xiàn)狀

近幾年國內(nèi)外研究人員在前人做了相當(dāng)多有意義的工作基礎(chǔ)上，針對不同的應(yīng)用，提出了很多實用的碰撞檢測算法，為碰撞檢測技術(shù)的快速發(fā)展作出了重要貢獻。隨著對碰撞檢測準(zhǔn)確性要求的不斷提高，出現(xiàn)了一類涉及到四維時空精確建模的連續(xù)碰撞檢測算法，從早期文獻[6]在可形變物體間的連續(xù)碰撞檢測方面進行了深入研究，通過引入一些優(yōu)化技術(shù)，使算法具有一定的實時性，到文獻[7]針對可變形物體之間的連續(xù)碰撞檢測算法中存在的問題，并提出了一種用于連續(xù)碰撞檢測算法中的基于子空間的剔除算法。

隨著GPU可編程性和浮點計算能力的出現(xiàn)與發(fā)展，近幾年出現(xiàn)了一類基于GPU流計算的碰撞檢測算法，該算法利用圖形硬件的可編程性，將碰撞檢測計算映射到圖形處理流水線的頂點處理器和片段處理器，通過實時繪制過程完成碰撞檢測計算，通過遮擋查詢獲得碰撞檢測結(jié)果，減輕了CPU的計算負擔(dān)，也克服了圖像空間算法不準(zhǔn)確的缺點。文獻[8]基于CUDA并行碰撞檢測算法研究，提出了一種基于層次包圍盒的并行碰撞檢測算法，用多處理器并行遍歷層次樹以避免單處理器性能問題，實現(xiàn)了多平臺下多GPU的調(diào)用。文獻[9]在基本圖元的相交測試方面，提出了一種基于通用計算圖形處理器（GPGPU）的并行碰撞檢測算法，使相交測試任務(wù)移交給GPGPU來加速碰撞檢測過程。

3 創(chuàng)新點研究內(nèi)容

3.1 基于CUDA結(jié)構(gòu)的連續(xù)碰撞檢測算法

隨著仿真場景規(guī)模的增大，在單處理器上難以實現(xiàn)對碰撞檢測算法的實時性要求，CPU逐漸向多核方向發(fā)展，并結(jié)合GPU可編程圖形硬件技術(shù)，充分發(fā)揮并行計算能力來解決效率低的問題。文獻[8]提出了一種基于層次包圍盒的并行碰撞檢測算法，結(jié)合CUDA平臺提供的并行計算解決方案，多處理器以并行的方式生成層次包圍盒樹來進一步提高算法效率。文獻[10]利用GPU可編程語言和多線程程序解決檢測沖突問題，CUDA將GPU視作數(shù)據(jù)并行計算設(shè)備，多任務(wù)機制負責(zé)管理多個并發(fā)運行的CUDA應(yīng)用程序和圖形應(yīng)用程序?qū)PU的訪問。

3.2 基于GPGPU的實時連續(xù)碰撞檢測算法

文獻[11]提出了基于GPGPU的數(shù)據(jù)集中于逆置換映射算法，對現(xiàn)有渲染管線和實時碰撞進行計算，改進了檢測方式，提高了實時運行的效率。文獻[12]并行算法來加速樣品為基礎(chǔ)的運動規(guī)劃連續(xù)碰撞查詢，為目前多核心GPU和數(shù)據(jù)并行的多線程碰撞檢測能力提供有效的解決方案，用一種聚類方案和碰撞包遍歷多種路徑進行有效的碰撞查詢。

3.3 基于OpenCL的多GPU并行計算

文獻[13]提出了適應(yīng)方法與八叉樹實現(xiàn)快速碰撞檢測，使用GPU和NVIDIA CUDA在一起采用并行計算方法，提高了適應(yīng)機器人與環(huán)境模型的碰撞檢測計算能力。文獻[14]在結(jié)合OpenCL的基礎(chǔ)上，剔除運動物體之間碰撞檢測的多余物體，執(zhí)行大規(guī)模并行掃描和剪枝，使用CUDA架構(gòu)處理移動物體的連續(xù)碰撞檢測，并由GPU完全實現(xiàn)。

3.4 優(yōu)化的連續(xù)碰撞檢測算法

文獻[15]提出的快速算法-CCD算法，在三角模型之間準(zhǔn)確地實現(xiàn)碰撞檢測查詢，通過精確幾何計算范式，在數(shù)量級上精度計算更快更準(zhǔn)。文獻[16]基于視圖剔除方法開發(fā)一個新的連續(xù)自動碰撞檢測算法，實現(xiàn)在可變形表面用一個簡單的實體模型進行交互。文獻[17]提出在保證產(chǎn)生正確的碰撞結(jié)果同時，優(yōu)化計算精確的算法，即使是在退化的場景下，仍然可以選擇幾何精確的檢測計算，速度快、可靠性強。

4 結(jié)束語

并行連續(xù)碰撞檢測算法在虛擬場景中應(yīng)用日益廣泛，GPU在可編程性和并行計算方面性能的快速提高，讓我們看到了并行化技術(shù)的強大功能。并行性優(yōu)化方案在保證精確性的同時，提高了碰撞檢測的速度，減輕了CPU的負擔(dān)。未來在更加復(fù)雜的虛擬場景中將會有巨大的應(yīng)用價值，但同時因精確性和實時性的相互制約，連續(xù)碰撞檢測算法的研究仍面臨著許多挑戰(zhàn)與難題。

4.1 目前存在的問題

⑴ 連續(xù)碰撞檢測算法隨著計算機硬件技術(shù)的發(fā)展在實時性和精確度上矛盾突出；

⑵ 復(fù)雜場景中可變形物體的自碰撞檢測以及物體之間的碰撞檢測對高頻率的碰撞檢測算法要求較高；

⑶ 利用GPU的并行計算能力還不能實時解決連續(xù)碰撞檢測的距離計算；

⑷ 大部分算法沒有利用好GPU高性能并行計算進行層級間的算法優(yōu)化；

⑸ 大規(guī)模運動場景中結(jié)合使用層次包圍體樹和層次空間劃分算法未完全達成一致；

⑹ 目前只停留在簡單物體間碰撞檢測，并行生成樹算法的速度提升不明顯。

4.2 展望

我們堅信GPU多核可并行計算將一直是連續(xù)碰撞檢測算法研究的主題，主要在以下幾方面還需要進一步深入研究。

⑴ 探索利用GPU的并行計算能力，使用圖形處理器進行寬階段算法優(yōu)化，進行離散碰撞檢測的刺穿深度計算和連續(xù)碰撞檢測的距離計算。

⑵ 對于大規(guī)模場景中可形變物體的碰撞檢測，結(jié)合層次空間劃分方法，充分利用GPU進行物體層次包圍盒樹的更新計算。

⑶ 利用GPU可編程的多核并行化計算能力，有效的結(jié)合其他方法來獲取準(zhǔn)確的碰撞信息。

⑷ 更好地利用運動物體的時空相關(guān)性，快速剔除大量無關(guān)的物體。

參考文獻：

[1] Jia X， Choi Y K， Mourrain B， et al. An algebraic approach to

continuous collision detection for ellipsoids[J]. Computer Aided Geometric Design，2011.28（3）：164-176

[2] Bergen G. A fast and robust GJK implementation for collision

detection of convex objects[J]. Journal of Graphics Tools，1999.4（2）：7-25

[3] Tang M，Curtis S，Yoon S E， et al. ICCD： Interactive continuous

collision detection between deform able models using connectivity-based culling[J].Visualization and Computer Graphics， IEEE Transactions on，2009.15（4）：544-557

[4] 潘海鴻，馮俊杰，陳琳，徐杰，付兵.基于分離距離的碰撞檢測算法綜述[J].

系統(tǒng)仿真學(xué)報，2014.7（26）：1407-1417

[5] 劉麗，張國山，邴志剛，劉敏.基于GJK的凸體快速連續(xù)碰撞檢測研究[J].

河北科技大學(xué)學(xué)報，2014.5（35）：440-447

[6] Naga K G， Kabul I， Lin M C. Fast Continuous Collision Detection

among deform-able Models Using Graphics Processor. Computer and Graphics，2007.31（1）：5-4

[7] Yong Shui. Research on Continuous Collision Detection Algorithm

In Virtual Reality[D]. University of Science and Technology of China，2013.5（2）：1-17

[8] 田園，萬毅.基于CUDA的并行碰撞檢測算法研究[J].甘肅科技，

2011.14（27）：27-31

[9] 寇兆坤.基于Delta3D的并行碰撞檢測技術(shù)研究[D].哈爾濱工程大

學(xué)，2013.12（1）：1-20

[10] Gucer， D； Ozguc， HB. Simulation of a flowing snow avalanche

using molecular dynamics. Turkish Journal of Electrical Engineering and Computer Sciences，2014.6（22）：1596-1610

[11] Nykl， S； Mourning， C； Chelberg， DM. Interactive Mesostructures

with Volumetric Collisions.IEEE Transactions on Visualization and Computer Graphics，2014.7（20）：970-982

[12] Pan， J； Manocha， D. GPU-based parallel collision detection for

fast motion planning. International Journal of Robotics Research，2012.2（31）：187-200

[13] Kaldestad， K. B； Hovland. G； Anisi， D. A. 3D Sensor-Based

Obstacle Detection Comparing Octrees and Point clouds Using CUDA. Modeling Identification and Control，2012.4（33）：123-130

[14] Liu， Fuchang； Harada， Takahiro； Lee， Youngeun； Kim， Young J.

Real-time Collision Culling of a Million Bodies on Graphics Processing Units. ACM Transactions on Graphics，2010.6（29）：145-158

[15] Tang， Min； Tong， Ruofeng； Wang， Zhendong； Manocha， Dinesh.

Fast and Exact Continuous Collision Detection with Bernstein Sign Classification. ACM Transactions on Graphics，2014.6（33）：1229-1237

[16] Wong， Sai-Keung； Cheng， Yu-Chun. Continuous Self-Collision

Detection for Deformable Surfaces Interacting with Solid Models. Computer Graphics Forum，2014.6（33）：143-153

[17] Brochu， Tyson； Edwards， Essex； Bridson， Robert. Efficient

Geometrically Continuous Collision Detection. A CM Transactions on Graphics，2012.4（31）：1148-1156