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

1、碰撞檢測(cè)用于確定兩個(gè)或多個(gè)物體彼此之間是否發(fā)生接觸或穿透，是計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)、計(jì)算機(jī)游戲以及CAD/CAM等領(lǐng)域一個(gè)非常重要的問題。經(jīng)過研究人員多年的探索，出現(xiàn)了許多在一定程度上比較成熟的碰撞檢測(cè)算法。但是，隨著應(yīng)用中三維模型的越來越復(fù)雜，以及人們對(duì)交互實(shí)時(shí)性和場(chǎng)景真實(shí)性要求的提高，給碰撞檢測(cè)算法的效率也提出了更高的要求。同時(shí)，圖形處理器通用計(jì)算技術(shù)的快速發(fā)展，為實(shí)時(shí)碰撞檢測(cè)問題的解決提供了一種全新的方法。 在對(duì)已有碰撞檢

2、測(cè)算法深入分析的基礎(chǔ)上，本文結(jié)合GPU通用計(jì)算平臺(tái)CUDA，從如下三個(gè)方面對(duì)碰撞檢測(cè)算法進(jìn)行設(shè)計(jì)和改進(jìn)： 首先，從GPU的通用計(jì)算角度出發(fā)，提出一種基于GPU通用計(jì)算的碰撞檢測(cè)算法。算法進(jìn)行一物體所有三角形和另一物體所有三角形之間的相交測(cè)試，以判斷兩物體之間是否發(fā)生碰撞；通過CUDA平臺(tái)，將相交測(cè)試計(jì)算映射到GPU多線程，以利用GPU強(qiáng)大的并行計(jì)算能力，完成并行化的碰撞檢測(cè)計(jì)算。 其次，在上述算法的基礎(chǔ)上，引入層次樹改進(jìn)

3、算法性能，得到一種基于GPGPU的實(shí)時(shí)碰撞檢測(cè)算法。對(duì)于兩物體間的碰撞檢測(cè)，算法首先遍歷一個(gè)物體的層次包圍盒樹，進(jìn)行包圍盒與另一物體的三角形之間的相交測(cè)試，快速剔除兩物體中明顯不相交的三角形，將相交計(jì)算復(fù)雜度從O（N2）降至O（N）；然后進(jìn)行兩物體潛在相交三角形之間的相交測(cè)試，獲得碰撞檢測(cè)結(jié)果。所有相交測(cè)試計(jì)算均由GPU多線程并行執(zhí)行。算法利用了“CPU+GPU異構(gòu)運(yùn)算”的思想，將不同的任務(wù)在CPU和GPU之間進(jìn)行合理的分配，獲得較優(yōu)的

4、算法性能。 最后，根據(jù)CUDA編程的優(yōu)化原則，對(duì)算法的GPU內(nèi)存訪問方式和線程并行度進(jìn)行優(yōu)化。在內(nèi)存存取方面，有效利用CUDA的共享內(nèi)存機(jī)制，將數(shù)據(jù)的全局內(nèi)存讀取次數(shù)從每線程一次降低至每塊一次；在線程并行度方面，結(jié)合計(jì)算量和GPU的計(jì)算能力對(duì)網(wǎng)格和塊的維度進(jìn)行合理配置。 實(shí)驗(yàn)結(jié)果表明，基于GPGPU的實(shí)時(shí)碰撞檢測(cè)算法，能適應(yīng)任意形狀物體間的碰撞檢測(cè)，具有較好的實(shí)時(shí)性。本文的研究成果，對(duì)物體間的實(shí)時(shí)碰撞檢測(cè)具有一定的理論和