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

在審

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

1.一種面向GPU的三角網(wǎng)格碰撞檢測(cè)方法，其特征在于，包括基本碰撞算法部分和算法優(yōu)化部分，其中，

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

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

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

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

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

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

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

2.如權(quán)利要求1所述的一種面向GPU的三角網(wǎng)格碰撞檢測(cè)方法，其特征在于，所述步驟11具體為：

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

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

3.如權(quán)利要求2所述的一種面向GPU的三角網(wǎng)格碰撞檢測(cè)方法，其特征在于，尋找潛在的分離軸方式具體為：假設(shè)有三角形x₁x₂x₃和三角形x₄x₅x₆，π₁、π₂分別被設(shè)置為是所述三角形x₁x₂x₃和所述三角形x₄x₅x₆的平面法線，e_i(i＝1,…6)被設(shè)置為所述三角形x₁x₂x₃和所述三角形x₄x₅x₆邊；令L為潛在的分離軸，分離軸包括π₁，π₂，θ_i×θ_j(i＝1,2,3；j＝4,5,6)，π₁×θ_i(i＝1,2,3)，π₂×θ_j(j＝4,5,6)。

4.如權(quán)利要求3所述的一種面向GPU的三角網(wǎng)格碰撞檢測(cè)方法，其特征在于，所述三角形x₁x₂x₃在直線L上的投影區(qū)間被設(shè)置為所述三角形x₄x₅x₆在所述潛在的分離軸L上的投影區(qū)間被設(shè)置為如果存在一條直線L，使得I₀與I₁兩個(gè)投影區(qū)間不相交，判定兩個(gè)三角形不相交；當(dāng)兩個(gè)三角形在直線L上的投影區(qū)間滿足或者時(shí)，判定兩個(gè)三角形不相交。

5.如權(quán)利要求1所述的一種面向GPU的三角網(wǎng)格碰撞檢測(cè)方法，其特征在于，所述兩個(gè)物體間的碰撞檢測(cè)具體為：每一個(gè)CUDA線程讀取物體A中的一個(gè)三角形a和物體B中的一個(gè)三角形b，然后計(jì)算它們對(duì)應(yīng)的相交狀態(tài)；當(dāng)三角形a和三角形b相交，它們對(duì)應(yīng)的三角形索引號(hào)被存儲(chǔ)。

6.如權(quán)利要求1所述的一種面向GPU的三角網(wǎng)格碰撞檢測(cè)方法，其特征在于，所述步驟21具體為：三角形數(shù)據(jù)被設(shè)置為讀取一次，多次使用；每一個(gè)CUDA線程讀取所述物體A中的一個(gè)三角形，同時(shí)讀取所述物體B中的K個(gè)三角形，每一個(gè)CUDA線程進(jìn)行K次基礎(chǔ)碰撞檢測(cè)。

7.如權(quán)利要求1所述的一種面向GPU的三角網(wǎng)格碰撞檢測(cè)方法，其特征在于，所述步驟22具體為：從設(shè)備內(nèi)存加載三角形數(shù)據(jù)到共享內(nèi)存，然后將數(shù)據(jù)同步給其他所有CUDA線程，使得每個(gè)CUDA線程都可以安全讀取到不同CUDA線程填充的所述共享內(nèi)存的地址；從物體A和物體B中分別加載K個(gè)三角形數(shù)據(jù)進(jìn)入所述共享內(nèi)存，利用所述共享內(nèi)存的數(shù)據(jù)進(jìn)行碰撞測(cè)試，最后將結(jié)果寫回所述設(shè)備內(nèi)存。

8.如權(quán)利要求1所述的一種面向GPU的三角網(wǎng)格碰撞檢測(cè)方法，其特征在于，所述步驟23具體為：利用共享內(nèi)存的方式，先從物體A和物體B中分別加載K個(gè)三角形數(shù)據(jù)進(jìn)入共享內(nèi)存，然后利用所述共享內(nèi)存中的三角形數(shù)據(jù)進(jìn)行碰撞檢測(cè)；碰撞檢測(cè)時(shí)，利用減少內(nèi)存訪問(wèn)的策略，讀取物體A中的一個(gè)三角形與物體B中的所有三角形進(jìn)行碰撞檢測(cè)。