朱亞輝　黃襄念　張亞俊

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

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

中圖分類號(hào)：TP391.09 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

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

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

1.1 碰撞檢測(cè)

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

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

1.2 連續(xù)碰撞檢測(cè)的先進(jìn)算法

1.2.1 包圍盒層次法

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

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

1.2.2 距離跟蹤算法

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

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

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

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

1.3 GPU及并行計(jì)算

1.3.1 GPU工作原理和特點(diǎn)

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

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

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

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

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

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

1.3.3 GPU的并行計(jì)算

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

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

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

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

3 創(chuàng)新點(diǎn)研究?jī)?nèi)容

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

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

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

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

3.3 基于OpenCL的多GPU并行計(jì)算

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

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

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

4 結(jié)束語

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

4.1 目前存在的問題

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

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

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

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

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

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

4.2 展望

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

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

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

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

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

參考文獻(xià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] 潘海鴻，馮俊杰，陳琳，徐杰，付兵.基于分離距離的碰撞檢測(cè)算法綜述[J].

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

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

河北科技大學(xué)學(xué)報(bào)，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的并行碰撞檢測(cè)算法研究[J].甘肅科技，

2011.14（27）：27-31

[9] 寇兆坤.基于Delta3D的并行碰撞檢測(cè)技術(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