基于CUDA的并行碰撞檢測(cè)算法研究

1、基于CUDA的并行碰撞檢測(cè)算法研究 田園1，萬毅1，張學(xué)智2作者簡介：田園（1984-），男，碩士，主要研究方向：計(jì)算機(jī)圖形學(xué)，并行計(jì)算通信聯(lián)系人：萬毅（1970-），男，教授，主要研究方向：信號(hào)處理，數(shù)字通信. E-mail: 1.51.51.51.51.51.51.51.51.51.51.51.51.51.51.51.51.5School of Information Science & Engineering, Lanzhou University, Lanzhou 730000;School of Information Science & Engineering, Lanzhou U

2、niversity, Lanzhou 730000;School of Physical and Technology, Lanzhou University, Lanzhou 730000蘭州大學(xué)信息科學(xué)與工程學(xué)院，蘭州 730000;蘭州大學(xué)信息科學(xué)與工程學(xué)院，蘭州 730000;蘭州大學(xué)物理科學(xué)與技術(shù)學(xué)院，蘭州 730000730000;730000;甘肅省蘭州市城關(guān)區(qū)天水南路222號(hào)蘭州大學(xué)飛云樓431;甘肅省蘭州市城關(guān)區(qū)天水南路222號(hào)蘭州大學(xué)飛云樓431;田園（1984-），男，碩士，主要研究方向：計(jì)算機(jī)圖形學(xué)，并行計(jì)算;萬毅（1970-），男，教授，主要研究方向：信號(hào)處理，數(shù)字通

3、信;田園;萬毅;張學(xué)智Tian Yuan;Wan Yi;Zhang Xuezhi萬毅1.51.51.51.51.51.51.51*|*學(xué)位論文*|*石其. 基于GPU的碰撞檢測(cè)算法研究D. 長沙：湖南大學(xué)，2009.2*|*期刊*|*馬登武，葉文，李瑛. 基于包圍盒的碰撞檢測(cè)算法綜述J. 系統(tǒng)仿真學(xué)報(bào)，2006，18（4）：1058-1061.3*|*專著*|*Michael J.Quinn. PARALLEL PROGRAMMING IN C WITH MPI AND OPENMPM. 北京：清華大學(xué)出版社，2005.4*|*專著*|*David B.Kirk, Wen-mei W.Hwu.

4、 Programming Massively Parallel ProcessorsM. 北京：清華大學(xué)出版社，2009.5*|*期刊*|*曹家音. 基于KD-Tree遍歷的并行光線跟蹤加速算法J. 科技傳播，2010，（17）：233-233，2246*|*期刊*|*熊一梅，曾憲文，陳一民. 基于并行的快速碰撞檢測(cè)算法的研究J. 計(jì)算機(jī)應(yīng)用與軟件，2008，25（4）：48-50.7*|*期刊*|*Xavier Provot. Deformation Constraints in a Mass-Spring Model to Describe Rigid Cloth BehaviorJ. I

5、n Graphics Interface 1995, 18(5): 147-154.8*|*期刊*|*陳旿，徐乃平. 真實(shí)感布仿真中布與剛體的碰撞檢測(cè)及修正J. 軟件學(xué)報(bào)，2001，12（12）： 1874-1880.9*|*期刊*|*王曉榮，王萌，李春貴. 基于AABB包圍盒的碰撞檢測(cè)算法的研究J. 計(jì)算機(jī)工程與科學(xué)，2010，32（4）：59-61.10*|*期刊*|*沈照功，潘振寬. 基于彈簧質(zhì)點(diǎn)模型的布料仿真及碰撞處理方法J. 計(jì)算機(jī)仿真，2006，23（3）：284-287.|1|田園|Tian Yuan|蘭州大學(xué)信息科學(xué)與工程學(xué)院，蘭州 730000|School of Infor

6、mation Science & Engineering, Lanzhou University, Lanzhou 730000|田園（1984-），男，碩士，主要研究方向：計(jì)算機(jī)圖形學(xué)，并行計(jì)算|甘肅省蘭州市城關(guān)區(qū)天水南路222號(hào)蘭州大學(xué)飛云樓431|730000|*|2|萬毅|Wan Yi|蘭州大學(xué)信息科學(xué)與工程學(xué)院，蘭州 730000|School of Information Science & Engineering, Lanzhou University, Lanzhou 730000|萬毅（1970-），男，教授，主要研究方向：信號(hào)處理，數(shù)字通信|甘肅省蘭州市城關(guān)區(qū)天水南路222

7、號(hào)蘭州大學(xué)飛云樓431|730000|3|張學(xué)智|Zhang Xuezhi|蘭州大學(xué)物理科學(xué)與技術(shù)學(xué)院，蘭州 730000|School of Physical and Technology, Lanzhou University, Lanzhou 730000|基于CUDA的并行碰撞檢測(cè)算法研究|Parallel Collision Detection Algorithm Research Based on CUDA|（1. 蘭州大學(xué)信息科學(xué)與工程學(xué)院，蘭州 730000；2. 蘭州大學(xué)物理科學(xué)與技術(shù)學(xué)院，蘭州 730000）摘要：碰撞檢測(cè)是計(jì)算機(jī)圖形仿真中的關(guān)鍵問題之一。盡管研究人員提出了

8、許多優(yōu)秀的碰撞檢測(cè)算法，但是隨著仿真場(chǎng)景規(guī)模的增大，在單處理器上實(shí)現(xiàn)的碰撞檢測(cè)算法已經(jīng)難以達(dá)到實(shí)時(shí)性的要求。因此，當(dāng)前研究的核心問題是如何提高碰撞檢測(cè)的速度。本文在對(duì)已有算法研究分析的基礎(chǔ)上，提出了一種基于層次包圍盒的并行碰撞檢測(cè)算法。該算法的核心思想是用多處理器并行遍歷層次樹以避免單處理器需要兩棵樹相互遍歷的情況，并提出以并行的方式生成層次包圍盒樹來進(jìn)一步提高算法效率。結(jié)合CUDA平臺(tái)提供的并行計(jì)算解決方案，整個(gè)算法在圖形處理器上得以實(shí)現(xiàn)。結(jié)果表明，該算法顯著提高了碰撞檢測(cè)的速度，滿足實(shí)時(shí)性的需求。關(guān)鍵詞：計(jì)算機(jī)圖形；碰撞檢測(cè)；層次包圍盒；并行；CUDA中圖分類號(hào)：TP3-0Parallel

9、 Collision Detection Algorithm Research Based on CUDATian Yuan1, Wan Yi1, Zhang Xuezhi2(1. School of Information Science & Engineering, Lanzhou University, Lanzhou 730000;2. School of Physical and Technology, Lanzhou University, Lanzhou 730000)Abstract: Collision detection is one of the key problems

10、 in compute graphics simulation. Although researchers have made many excellent algorithms, with the increasing of scene scale, collision detection on single processor has been diffcult to achieve requirement of real-time. Therefore, the current research problem is how to improve the efficiency of co

11、llision detection. After analysing the existing algorithms, this paper proposed a parallel collision detection algorithm based on hierarchical bounding volumes. The core thought of this algorithm is using mutilprocessors to traverse hierarchy tree to avoid single processor needs two trees mutual tra

12、verse, and proposes using parallel method to establish hierarchy tree to further improve efficiency. With the parallel computing solutions of CUDA, this algorithm has been achieved on graphics processor. The result shows that the algorithm greatly improves the speed of collision detection and adapts

13、 the demand of real-time.Key words: compute graphics; collision detection; hierarchical bounding volumes; parallel; CUDA0 引言碰撞檢測(cè)問題在計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)、計(jì)算機(jī)游戲以及CAD/CAM等領(lǐng)域有著非常重要的研究意義1。在計(jì)算機(jī)生成的虛擬場(chǎng)景中，必須遵循一個(gè)現(xiàn)實(shí)生活中普遍存在的事實(shí)：兩個(gè)不可穿透的物體不能同時(shí)占據(jù)空間中相同的區(qū)域。因此，碰撞檢測(cè)問題對(duì)于能否產(chǎn)生具有真實(shí)感的圖形場(chǎng)景至關(guān)重要。近二十年來，國內(nèi)外研究人員己經(jīng)在碰撞檢測(cè)領(lǐng)域中做了相當(dāng)多有意義的工作，針對(duì)不同的應(yīng)

14、用、采用不同的方法提出了很多實(shí)用的碰撞檢測(cè)算法，為碰撞檢測(cè)技術(shù)的快速發(fā)展做出了重要貢獻(xiàn)1?，F(xiàn)有的碰撞檢測(cè)算法大致可分為兩類：空間分解法和層次包圍盒法。這兩種方法的目的都是減少不必要的幾何元素相交測(cè)試，提高碰撞檢測(cè)的效率。然而，隨著人們對(duì)虛擬場(chǎng)景真實(shí)度要求的不斷提高，場(chǎng)景規(guī)模越來越大，模型也越來越復(fù)雜，現(xiàn)有的碰撞檢測(cè)算法已無法滿足實(shí)時(shí)碰撞檢測(cè)需要。因此，如何減少碰撞檢測(cè)所帶來的系統(tǒng)消耗問題已經(jīng)成為重要的研究內(nèi)容之一。近年來，計(jì)算行業(yè)正在從只使用CPU的“中央處理”向CPU與GPU并用的“協(xié)同處理”發(fā)展。為了打造這一全新的計(jì)算模式，NVIDIA公司開發(fā)了一種稱為CUDA(Compute Unifi

15、ed Device Architecture，統(tǒng)一計(jì)算設(shè)備架構(gòu))的通用并行計(jì)算架構(gòu)，該架構(gòu)使得GPU能夠解決復(fù)雜的計(jì)算問題。得益于CUDA所帶來的并行計(jì)算解決方案，并行碰撞檢測(cè)算法的研究迎來了新的機(jī)遇。并行計(jì)算是一種能夠有效提高碰撞檢測(cè)速度的方法，經(jīng)過分析研究，我們提出了一種基于CUDA的并行碰撞檢測(cè)算法。1 并行碰撞檢測(cè)算法的基本思想我們所提出的是一種基于層次包圍盒的并行碰撞檢測(cè)算法。層次包圍盒的碰撞檢測(cè)算法由于具有較好的性能，適用于復(fù)雜環(huán)境中的碰撞檢測(cè)，因而受到了廣泛的研究。層次包圍盒方法是利用體積略大而形狀簡單的包圍盒把復(fù)雜的幾何對(duì)象包裹起來，在進(jìn)行碰撞檢測(cè)時(shí)首先進(jìn)行包圍盒之間的相交測(cè)試

16、；如果包圍盒相交，再進(jìn)行幾何對(duì)象之間精確的碰撞檢測(cè)2。在單處理器的情況下，首先必須對(duì)兩個(gè)需要進(jìn)行碰撞檢測(cè)的對(duì)象分別生成層次包圍盒樹(簡稱包圍樹)，再通過雙重遞歸遍歷兩棵包圍樹來確定需要進(jìn)行檢測(cè)的部分。如果某個(gè)對(duì)象在模擬過程中發(fā)生位移或形變，則必須在下一次進(jìn)行碰撞檢測(cè)前對(duì)該對(duì)象的包圍樹進(jìn)行更新，而更新過程依然是一個(gè)遍歷樹的過程。由此可見，當(dāng)一個(gè)對(duì)象含有的基本幾何元素越多時(shí)，生成包圍樹的時(shí)間越長，并且包圍樹的深度越大，遍歷所需要的時(shí)間也更長。為了減少碰撞檢測(cè)的系統(tǒng)消耗，我們的想法是利用并行的方法來生成包圍樹和避免雙重遞歸遍歷。根據(jù)我們的分析，層次包圍盒的碰撞檢測(cè)是一種典型的單指令多數(shù)據(jù)流3(Sin

17、gle Instruction Multiple Data，簡稱SIMD)問題，即處理器多次執(zhí)行重復(fù)的代碼，每次處理不同的數(shù)據(jù)。對(duì)于這類問題，可以使用多個(gè)處理器，每個(gè)處理器同一時(shí)刻執(zhí)行相同的代碼但處理不同的數(shù)據(jù)，從而實(shí)現(xiàn)并行化。1.1 并行生成包圍樹生成一棵包圍樹有自頂向下和自底向上兩種方法。自底向上生成包圍樹的方法與霍夫曼編碼相似。單個(gè)處理器完成這項(xiàng)工作的方法是：(1)根據(jù)給定的n個(gè)基本幾何元素的包圍盒構(gòu)成n棵二叉樹的集合，其中每棵二叉樹中只有一個(gè)根結(jié)點(diǎn)，其左右子樹均為空。(2)從F中取出，用貪婪算法在其余的二叉樹中找到與距離最近的，將與作為左右子樹構(gòu)造一棵新的二叉樹，并且新二叉樹根結(jié)點(diǎn)包圍

18、盒大小由其左右子樹決定。重復(fù)該過程直到F中所有的二叉樹被處理完。該過程的時(shí)間復(fù)雜度為。(3)刪除F中原有的二叉樹，將新生成的樹全部加入F中。(4)重復(fù)(2)和(3)，直到F只含有一棵樹為止。上述算法的時(shí)間復(fù)雜度為。從生成樹的過程來看，處理器重復(fù)做相同的工作來處理不同的數(shù)據(jù)，屬于SIMD問題，因此可以使用并行的方式。我們所提出的并行生成包圍樹算法的基本思想是：(1)根據(jù)n個(gè)基本幾何元素的包圍盒構(gòu)成n棵二叉樹的集合，其中每棵二叉樹中只有一個(gè)根結(jié)點(diǎn)，其左右子樹均為空。(2) 從F中取出，并行計(jì)算其余根結(jié)點(diǎn)到的距離，再用并行的方式找到與距離最小的根結(jié)點(diǎn)，將和加入到集合中。重復(fù)該過程直到F中所有的根結(jié)點(diǎn)

19、全部加入H中，其中與之間的距離最小。(3)用多個(gè)處理器對(duì)有序集合H中的根結(jié)點(diǎn)進(jìn)行處理，由處理器將H中，作為左右子樹構(gòu)造一棵新的二叉樹。(4)刪除F中原有的二叉樹，將新生成的樹全部加入F中。(5)重復(fù)(2)、(3)和(4)，直到F只含有一棵樹為止。圖1 并行生成包圍樹的基本思想并行生成樹的過程如圖1所示。對(duì)于有n個(gè)根結(jié)點(diǎn)和p個(gè)處理器的情況，該算法在計(jì)算根結(jié)點(diǎn)之間距離的時(shí)間復(fù)雜度是；在上述算法(2)中，總共需要進(jìn)行次查找，并行查找最小值的時(shí)間復(fù)雜度為，那么得到集合H所需要的時(shí)間復(fù)雜度為；在生成樹時(shí)，并行算法的時(shí)間復(fù)雜度為。整個(gè)算法的時(shí)間復(fù)雜度為，與單處理器所采用的算法相比較，當(dāng)p越接近n時(shí)，并行算

20、法的效率越好。1.2 并行遍歷包圍樹單處理器進(jìn)行碰撞檢測(cè)時(shí)需要對(duì)兩棵包圍樹進(jìn)行雙重遞歸遍歷。假設(shè)對(duì)象A與B進(jìn)行碰撞檢測(cè)，若樹A根結(jié)點(diǎn)與樹B根結(jié)點(diǎn)的包圍盒相交，則樹A向下遍歷，當(dāng)?shù)竭_(dá)樹A的某個(gè)葉結(jié)點(diǎn)時(shí)，用該葉結(jié)點(diǎn)遍歷樹B，如果能到達(dá)樹B的葉結(jié)點(diǎn)，再進(jìn)行進(jìn)一步的幾何元素相交測(cè)試。假設(shè)對(duì)象A的包圍樹含有n個(gè)結(jié)點(diǎn)，對(duì)象B的包圍樹含有m個(gè)結(jié)點(diǎn)，那么完成碰撞檢測(cè)的時(shí)間復(fù)雜度為。為了避免雙重遞歸遍歷所帶來的系統(tǒng)消耗，減少遍歷的次數(shù)，我們的想法是只生成對(duì)象A的包圍樹，在碰撞檢測(cè)時(shí)，只為對(duì)象B的所有基本幾何元素生成包圍盒，然后由多個(gè)處理器分別處理每個(gè)包圍盒與樹A的遍歷問題。該方法的時(shí)間復(fù)雜度是(p是處理器個(gè)數(shù))

21、，與并行生成包圍樹一樣，當(dāng)p越接近n時(shí)，算法的效率越好。2 并行碰撞檢測(cè)算法的實(shí)現(xiàn)自2006年NVIDIA公司推出統(tǒng)一渲染架構(gòu)的G80核心以來，可編程流處理器已取代原有的固定管線流程成為當(dāng)今GPU發(fā)展的模式。G80核心擁有128個(gè)Streaming Processor(流處理器，簡稱SP)，每8個(gè)SP被劃分為1個(gè)Streaming Multiprocessor(流多處理器，簡稱SM)，每個(gè)SM可容納768個(gè)活動(dòng)線程，那么一個(gè)G80核心便可以同時(shí)建立12280個(gè)活動(dòng)線程。而NVIDIA之后推出的G200核心，擁有240個(gè)SP，每個(gè)SM可容納1024個(gè)線程，能夠同時(shí)建立的活動(dòng)線程數(shù)更是高達(dá)3072

22、0個(gè)4。由此可見，GPU為并行計(jì)算提供了一個(gè)很好的解決方案。CUDA技術(shù)是一種基于NVIDIA圖形處理器的并行計(jì)算體系架構(gòu)，并使用標(biāo)準(zhǔn)C語言作為其編程語言。CUDA程序分為在host執(zhí)行和在device執(zhí)行兩個(gè)部分，host就是傳統(tǒng)的CPU，而device就是支持CUDA的GPU。在執(zhí)行CUDA程序時(shí)，host將需要并行計(jì)算的數(shù)據(jù)在內(nèi)存中準(zhǔn)備好，傳入顯存中由device進(jìn)行處理，數(shù)據(jù)處理完成后再從顯存?zhèn)骰貎?nèi)存中供用戶使用。根據(jù)我們提出的算法，首先是生成對(duì)象的包圍樹。我們定義一個(gè)基本幾何元素的包圍盒為一個(gè)含有包圍盒頂點(diǎn)坐標(biāo)、幾何元素頂點(diǎn)坐標(biāo)的結(jié)構(gòu)體。由host為對(duì)象所有基本幾何元素生成包圍盒并存

23、儲(chǔ)在內(nèi)存中的一維結(jié)構(gòu)體數(shù)組中，根據(jù)幾何元素個(gè)數(shù)計(jì)算出包圍樹深度depth及每層結(jié)點(diǎn)的個(gè)數(shù)。假設(shè)包圍樹每層結(jié)點(diǎn)個(gè)數(shù)分別為，2，1(i=depth-1)，在顯存中分配大小為的結(jié)構(gòu)體數(shù)組用于存儲(chǔ)生成的包圍樹。將包圍盒數(shù)組從內(nèi)存中傳入顯存后，我們?cè)赿evice上為數(shù)組中每一個(gè)元素建立一個(gè)對(duì)應(yīng)的線程，由這些線程完成以下工作：(1)以數(shù)組中指定元素對(duì)應(yīng)的包圍盒作為目標(biāo)，計(jì)算其余包圍盒與它之間的距離。該過程可以由多個(gè)線程并行完成，每個(gè)線程負(fù)責(zé)與其對(duì)應(yīng)的包圍盒的處理。(2) 將包圍盒數(shù)組調(diào)整成為有規(guī)則的序列，使得數(shù)組下標(biāo)為和的兩個(gè)包圍盒距離最近。這一過程的方法如圖2所示。在Step 1中，指定數(shù)組中第一個(gè)元素

24、為目標(biāo)包圍盒，計(jì)算其余包圍盒到的距離并用并行查找最小值的方法找到與距離最近的包圍盒。查找結(jié)束后，與距離最近的包圍盒將被移至數(shù)組中的位置。再指定作為目標(biāo)，用相同的方法找到與距離最近的包圍盒。這一過程將被重復(fù)執(zhí)行次，直到數(shù)組被調(diào)整完為止。圖2 調(diào)整包圍盒數(shù)組序列這里使用的并行查找最小值的方法如圖3所示。我們將含有n個(gè)元素的數(shù)組分成n個(gè)只有一個(gè)元素的子序列，使用個(gè)處理器對(duì)兩個(gè)相鄰子序列進(jìn)行合并，得到個(gè)新的子序列，在合并時(shí)將對(duì)比兩個(gè)子序列中第一個(gè)元素的值，將較小的值作為合并后子序列中第一個(gè)元素的值，再對(duì)新得到的個(gè)子序列兩兩合并，如此反復(fù)直到合并成一個(gè)序列為止。整個(gè)過程結(jié)束后，數(shù)組中的最小值將位于數(shù)組第

25、一個(gè)元素。圖3 并行查找最小值(3)由多個(gè)線程生成包圍樹每層結(jié)點(diǎn)，并存儲(chǔ)在事先分配好的數(shù)組中。該過程如圖4所示。圖4 多線程生成包圍樹假設(shè)對(duì)象A與B進(jìn)行碰撞檢測(cè)，并且device已為對(duì)象A生成包圍樹，那么只需要為對(duì)象B所有基本幾何元素生成包圍盒，用每個(gè)包圍盒去遍歷對(duì)象A的包圍樹。當(dāng)host將對(duì)象B的包圍盒數(shù)組從內(nèi)存中傳入顯存后，我們?cè)赿evice上建立與包圍盒數(shù)目相同的線程，由每個(gè)線程獨(dú)立完成一個(gè)包圍盒與包圍樹的遍歷問題。當(dāng)某個(gè)線程執(zhí)行的遍歷到達(dá)樹A的葉結(jié)點(diǎn)時(shí)，則該線程執(zhí)行進(jìn)一步的幾何元素相交測(cè)試，并完成碰撞響應(yīng)。CUDA并行遍歷層次包圍樹的過程如圖5所示。圖5 并行遍歷層次樹由于CUDA不支

26、持堆棧結(jié)構(gòu)，因此CUDA線程深度遍歷二叉樹無法用遞歸或堆棧的方式實(shí)現(xiàn)。文獻(xiàn)5中給出了一種模擬堆棧5的方法，使得CUDA線程深度遍歷二叉樹得以實(shí)現(xiàn)。3 實(shí)驗(yàn)結(jié)果我們?cè)谥袊茖W(xué)院近代物理研究所的超級(jí)計(jì)算中心上對(duì)并行算法進(jìn)行實(shí)驗(yàn)。該超算中心采用聯(lián)想深騰7000G高性能服務(wù)器，每個(gè)計(jì)算結(jié)點(diǎn)配置2個(gè)Intel Xeon 2.33GHZ處理器，8G內(nèi)存和4個(gè)G200核心，能夠獲得50-150倍于通用CPU的加速計(jì)算效果。實(shí)驗(yàn)所用的碰撞場(chǎng)景如圖6所示。我們?cè)趫?chǎng)景中水平放置一塊布，并固定布的兩個(gè)角，使其在受到重力作用自然下垂時(shí)呈懸掛狀態(tài)。在布的下方放置一個(gè)球體，使布在下垂過程中受到球體的阻擋而部分覆蓋在球體上

27、。當(dāng)布覆蓋在球體上并達(dá)到靜止?fàn)顟B(tài)時(shí)，我們開始統(tǒng)計(jì)并行算法和串行算法在生成包圍樹和遍歷樹所需要的平均時(shí)間。圖6 碰撞檢測(cè)實(shí)驗(yàn)場(chǎng)景表1是GPU并行算法和CPU串行算法執(zhí)行時(shí)間的對(duì)比。從實(shí)驗(yàn)結(jié)果來看，當(dāng)問題規(guī)模較小時(shí)，GPU在生成包圍樹時(shí)所需要的時(shí)間比CPU要長，其主要原因在于CUDA在組織線程、啟動(dòng)內(nèi)核函數(shù)和分配任務(wù)所消耗的時(shí)間掩蓋了實(shí)際的執(zhí)行時(shí)間。在完成一次碰撞檢測(cè)的時(shí)間方面，CPU隨著問題規(guī)模的增大，需要的時(shí)間也越來越長，而GPU則只需要遍歷一棵樹的時(shí)間便能夠完成碰撞檢測(cè)，較CPU有了明顯的提高。表1 碰撞檢測(cè)串行算法與并行算法時(shí)間對(duì)比基本幾何元素個(gè)數(shù)執(zhí)行時(shí)間(ms)球體布生成包圍樹完成碰撞檢測(cè)頂點(diǎn)三角形頂點(diǎn)三角形CPUGPU加速比CPUGPU加速比102419225761058621401:0.4417.611.61:2.04409679382304441810527861:1.34137.548.21:2.851638432258409679382572557401:4.48518.8187.31:2.764 總結(jié)本