基于GPU并行加速碰撞檢測算法的研究.pdf

1、碰撞檢測在計(jì)算機(jī)圖形學(xué)中主要是指虛擬場景中兩個(gè)或多個(gè)物體在同一時(shí)刻是否占據(jù)同一個(gè)位置。碰撞檢測自從計(jì)算機(jī)出現(xiàn)以后，就一直受到人們的關(guān)注和研究，隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們對虛擬場景的的真實(shí)性要求也越來越高，而碰撞檢測對虛擬場景是否具有真實(shí)感和沉浸感非常關(guān)鍵。隨著時(shí)間的發(fā)展，研究人員針對提高碰撞檢測的效率研究出了很多算法，這些算法對于當(dāng)時(shí)的特定場景產(chǎn)生了很好的效果，具有一定的實(shí)時(shí)性。然而，隨著虛擬場景復(fù)雜程度的增加以及物體的精細(xì)程度提高，其

2、實(shí)時(shí)性大受影響。近年來，隨著圖形處理器飛速發(fā)展，GPU的架構(gòu)和功能發(fā)生了革命性的變化，使得GPU可以應(yīng)用于通用計(jì)算，因而，對如何解決碰撞檢測實(shí)時(shí)性問題提供了新的思路和方法。
　　本文通過對典型的碰撞檢測算法進(jìn)行深入分析，利用GPU強(qiáng)大的并行處理能力，提出了一種基于GPU并行加速的碰撞檢測算法，從以下幾個(gè)方面對算法進(jìn)行了設(shè)計(jì)和改進(jìn)：
　?、偻ㄟ^深入分析傳統(tǒng)的基于AABB層次包圍樹的碰撞檢測算法，發(fā)掘算法中可以并行化的部分，在構(gòu)

3、建層次包圍盒樹時(shí)，采用自底向上的方式并行處理，加快生成和更新層次樹的速度。
　?、谠趯哟螛溥M(jìn)行遍歷時(shí)，也進(jìn)行了并行優(yōu)化處理，得到一種基于GPU通用計(jì)算的實(shí)時(shí)碰撞檢測算法。在對兩個(gè)物體進(jìn)行碰撞檢測時(shí)，直接利用三角形與另一個(gè)物體的層次包圍盒樹進(jìn)行遍歷，判斷其相交情況，由于算法使用CUDA線程的方式來進(jìn)行處理，因此只需執(zhí)行一個(gè)遍歷的過程，其時(shí)間復(fù)雜度為O(N)，相比于CPU的時(shí)間復(fù)雜度O(N2)，有很大改進(jìn)。當(dāng)碰撞檢測結(jié)束后，GPU將