[發(fā)明專利]一種面向GPU的三角網(wǎng)格碰撞檢測方法

在審

• 申請?zhí)枺?/td>: 201710076449.X
• 申請日: 2017-02-13
• 公開（公告）號: CN106875491A
• 公開（公告）日: 2017-06-20
• 發(fā)明（設(shè)計(jì)）人: 張新宇;任花
• 申請（專利權(quán)）人: 華東師范大學(xué)
• 主分類號: G06T19/00
• 分類號: G06T19/00
• 代理公司: 上海精晟知識產(chǎn)權(quán)代理有限公司31253
• 代理人: 馮子玲

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)圖形學(xué)領(lǐng)域，尤其涉及一種面向GPU的三角網(wǎng)格碰撞檢測方法。

背景技術(shù)

碰撞檢測(Collision Detection，簡稱CD)技術(shù)用于檢測空間中的一個或多個幾何物體之間是否存在重疊，如果存在則識別重疊特征。碰撞檢測算法被廣泛地應(yīng)用在計(jì)算機(jī)圖形學(xué)領(lǐng)域的多方面應(yīng)用中，包括基于物理的動畫、幾何建模、6-DOF觸覺渲染、機(jī)器人路徑規(guī)劃、醫(yī)學(xué)成像、交互式計(jì)算機(jī)游戲等。

隨著多核圖形處理器(Graphics Processing Unit，簡稱GPU)這樣的大規(guī)模并行處理器的快速發(fā)展，以及NVIDA推出的通用并行計(jì)算架構(gòu)CUDA(Compute Unified Device Architecture，簡稱CUDA)。許多基于單處理器的算法已經(jīng)利用CUDA技術(shù)擴(kuò)展到GPU上。如層次包圍盒(Bounding Volume Hierarchy，簡稱BVH)結(jié)構(gòu)就是提高碰撞檢測性能很好的技術(shù)。但是由于一般的串行算法對數(shù)據(jù)依賴較高，從存儲器結(jié)構(gòu)訪問數(shù)據(jù)會有延遲。如BVH這類空間數(shù)據(jù)結(jié)構(gòu)的算法復(fù)雜度較高，很多都需要進(jìn)行預(yù)處理或是代價較高的數(shù)據(jù)結(jié)構(gòu)重構(gòu)。為了解決這些問題，首先，需要將這些有效的串行算法重新設(shè)計(jì)適用于大規(guī)模的并行處理器，其次，需要在保證碰撞檢測性能提高的基礎(chǔ)上，摒棄預(yù)處理以及代價較高的數(shù)據(jù)結(jié)構(gòu)重構(gòu)操作。

因此，本領(lǐng)域的技術(shù)人員致力于開發(fā)一種面向GPU的三角網(wǎng)格碰撞檢測方法，利用對基本的碰撞檢測算法的優(yōu)化在GPU上進(jìn)行大規(guī)模并行計(jì)算來對物體進(jìn)行快速、準(zhǔn)確的碰撞檢測，算法適用于中等復(fù)雜度的模型，涉及基于分離軸的三角形相交測試、減少內(nèi)存訪問優(yōu)化策略、共享內(nèi)存優(yōu)化策略等方法，降低了算法復(fù)雜度，提高了碰撞檢測算法的性能。

發(fā)明內(nèi)容

有鑒于現(xiàn)有技術(shù)的上述缺陷，本發(fā)明所要解決的技術(shù)問題是開發(fā)一種面向GPU的三角網(wǎng)格碰撞檢測方法，利用對基本的碰撞檢測算法的優(yōu)化在GPU上進(jìn)行大規(guī)模并行計(jì)算來對物體進(jìn)行快速、準(zhǔn)確的碰撞檢測，算法適用于中等復(fù)雜度的模型，涉及基于分離軸的三角形相交測試、減少內(nèi)存訪問優(yōu)化策略、共享內(nèi)存優(yōu)化策略等方法，降低了算法復(fù)雜度，提高了碰撞檢測算法的性能。

為實(shí)現(xiàn)上述目的，本發(fā)明提供了一種面向GPU的三角網(wǎng)格碰撞檢測方法，包括基本碰撞算法部分和算法優(yōu)化部分，其中，

基本碰撞算法的具體步驟包括：

步驟11、進(jìn)行三角形相交測試；

步驟12、進(jìn)行兩個物體間的碰撞檢測；

算法優(yōu)化部分利用減少內(nèi)存訪問策略和共享內(nèi)存策略，具體步驟包括：

步驟21、通過減少內(nèi)存訪問次數(shù)的策略，對基本碰撞算法進(jìn)行優(yōu)化；

步驟22、通過內(nèi)存共享的策略，對基本碰撞算法進(jìn)行優(yōu)化；

步驟23、結(jié)合減少內(nèi)存訪問的次數(shù)和內(nèi)存共享，對基本碰撞算法進(jìn)行優(yōu)化。

進(jìn)一步地，步驟11具體為：

步驟111、尋找三角形對之間所有的潛在分離軸；

步驟112、利用分離軸方式進(jìn)行三角形相交測試。

尋找潛在的分離軸方式：假設(shè)有三角形x₁x₂x₃和三角形x₄x₅x₆，π₁、π₂分別是三角形x₁x₂x₃和三角形x₄x₅x₆的平面法線，e_i(i＝1,…6)為三角形x₁x₂x₃和三角形x₄x₅x₆的邊，令L為潛在的分離軸，對于三維空間的兩個三角形，分離測試只要考慮有限集合的潛在的分離軸，這里的分離軸包括π₁，π₂，e_i×e_j(i＝1,2,3；j＝4,5,6)，π₁×e_i(i＝1,2,3)，π₂×e_j(j＝4,5,6)。