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

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

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

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