虛擬現(xiàn)實(shí)中碰撞檢測的異構(gòu)加速研究.pdf

1、近年GPU通用計(jì)算的發(fā)展為虛擬現(xiàn)實(shí)領(lǐng)域算法的改進(jìn)提供了良好的條件,為并行化解決效率問題提供了機(jī)遇。CPU+GPU組成的異構(gòu)計(jì)算環(huán)境更是為虛擬現(xiàn)實(shí)算法中實(shí)時(shí)性問題的解決提供了更好的方法。
　　 虛擬現(xiàn)實(shí)技術(shù)廣泛應(yīng)用于計(jì)算機(jī)游戲、計(jì)算機(jī)輔助教學(xué)、計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域,并在近十年有巨大的發(fā)展。隨著人們對(duì)虛擬現(xiàn)實(shí)系統(tǒng)場景逼真度及高交互性要求的日益提高,系統(tǒng)計(jì)算數(shù)據(jù)量也大幅度提升。其中,場景中物體的碰撞檢測計(jì)算是整個(gè)計(jì)算的重要組成部分。因

2、此,解決碰撞檢測計(jì)算的實(shí)時(shí)性常常是整個(gè)虛擬現(xiàn)實(shí)系統(tǒng)高效實(shí)現(xiàn)的關(guān)鍵。
　　 碰撞檢測是判定兩個(gè)或更多對(duì)象是否有一個(gè)或多個(gè)交點(diǎn)的過程。碰撞檢測的研究是計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)、醫(yī)學(xué)模擬等領(lǐng)域的重要分支。在很多情況下,移動(dòng)對(duì)象在虛擬場景地圖中移動(dòng)不允許發(fā)生與某些對(duì)象的穿透,實(shí)時(shí)的碰撞檢測算法是解決這類問題的關(guān)鍵。
　　 層次包圍盒技術(shù)與空間劃分技術(shù)是碰撞檢測算法的兩個(gè)基礎(chǔ)方法,它們分別從兩個(gè)方面降低碰撞檢測過程的計(jì)算復(fù)雜度。盡管

3、這幾年碰撞檢測研究有了較多有價(jià)值的成果,但隨著場景與模型規(guī)模復(fù)雜度的日益提高,同時(shí)用戶對(duì)人機(jī)交互的實(shí)時(shí)性與精確性要求也越來越高,核心算法需要有更高的效率。但是,經(jīng)典的層次包圍盒技術(shù)與空間分割技術(shù)不能直接使用GPU做加速計(jì)算,需要對(duì)其進(jìn)行改進(jìn)以適應(yīng)GPU的硬件多線程處理。
　　 本文圍繞虛擬場景中碰撞檢測問題,對(duì)提高復(fù)雜場景下檢測效率進(jìn)行了分析與研究,在對(duì)各種基本碰撞檢測算法深入理解的基礎(chǔ)上,結(jié)合NVIDIA CUDA通用計(jì)算平臺(tái)

4、,以異構(gòu)編程的思想從下幾個(gè)方面對(duì)算法進(jìn)行改進(jìn):
　　 首先,對(duì)碰撞檢測算法中物體模型包圍球?qū)哟螛湟约叭切螖?shù)據(jù)集合的數(shù)據(jù)結(jié)構(gòu)進(jìn)行詳細(xì)分析,再基于CPU+GPU異構(gòu)計(jì)算思想進(jìn)行問題分解,分層討論寬階段的初步檢測與大規(guī)模多物體檢測。在寬階段碰撞檢測算法與窄階段碰撞檢測算法中改進(jìn)CPU端執(zhí)行部分以適應(yīng)GPU端對(duì)輸入數(shù)據(jù)的要求,分離出計(jì)算密集型的Device(GPU)端部分；然后,創(chuàng)建適合GPU處理的相交測試邏輯,再將場景中物體間相交測

5、試映射到CUDA線程執(zhí)行模型；最后,根據(jù)GPU存儲(chǔ)器模型進(jìn)行效率優(yōu)化。具體的說,在寬階段碰撞檢測中,CPU負(fù)責(zé)包圍球?qū)哟螛涞臉?gòu)建與遍歷,GPU負(fù)責(zé)一物體包圍球?qū)哟螛渑c另一物體三角形集合的并行相交測試,剔除不可能相交的三角形集合,得到潛在相交集合；在窄階段碰撞檢測中,GPU以上一階段的數(shù)據(jù)為輸入,對(duì)三角形集合進(jìn)行精確的并行相交測試,并最終得出測試結(jié)果。對(duì)于多物體場景則先在CPU端對(duì)場景對(duì)象集合進(jìn)行分組,以便于后續(xù)GPU并行執(zhí)行,然后,GP