基于GPU的碰撞檢測算法研究.pdf

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

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

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

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