[發(fā)明專利]基于三角網(wǎng)格變形體的自碰撞檢測方法

無效

• 申請?zhí)枺?/td>: 201210030632.3
• 申請日: 2012-02-12
• 公開（公告）號: CN102609992A
• 公開（公告）日: 2012-07-25
• 發(fā)明（設(shè)計）人: 沈旭昆;趙凌;鄭小萌;趙沁平
• 申請（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號: G06T19/00
• 分類號: G06T19/00
• 代理公司: 北京科迪生專利代理有限責(zé)任公司 11251
• 代理人: 李新華;成金玉

1.一種基于三角網(wǎng)格變形體的自碰撞檢測方法，所述變形體包括肌肉蒙皮組織或紡織布料，其特征在于如下步驟：

(1)建立基于層次包圍體的數(shù)據(jù)結(jié)構(gòu)；

(2)基于星型輪廓的自碰撞檢測預(yù)處理階段；

(3)基于星型輪廓的自碰撞檢測實時階段。

2.根據(jù)權(quán)利要求1所述的基于三角網(wǎng)格變形體的自碰撞檢測方法，其特征在于：所述步驟(1)中基于層次包圍體的數(shù)據(jù)結(jié)構(gòu)的表達(dá)形式為：

(a)層次包圍體BVH構(gòu)造為樹的每個結(jié)點與物體基本元素的一個子集相關(guān)聯(lián)，并且用指定類型的包圍體包住該子集的基本元素；

(b)BVH的葉節(jié)點復(fù)制到底層，拓展成拓展層次包圍體XBVH。

3.根據(jù)權(quán)利要求1所述的基于三角網(wǎng)格變形體的自碰撞檢測方法，其特征在于：所述步驟(2)中基于星型輪廓的自碰撞檢測預(yù)處理階段算法為：

(a)網(wǎng)格劃分與xBVH構(gòu)建，xBVH節(jié)點的數(shù)據(jù)結(jié)構(gòu)包括用法向量錐方法進(jìn)行方向測試所要求的數(shù)據(jù)結(jié)構(gòu)，xBVH節(jié)點自身包含的面片信息，以及xBVH構(gòu)成二叉樹必要的指針信息；

(b)自碰撞檢測樹SCTT的構(gòu)建：相鄰的面片構(gòu)成的節(jié)點是SCTT節(jié)點，不相鄰的子面片對構(gòu)成的節(jié)點不是SCTT節(jié)點；

(c)包圍盒測試樹BVTT的構(gòu)建：把包含了xBVH根節(jié)點的兩個子節(jié)點定義為BVTT的根節(jié)點(xBVH?root.left，xBVH?root.right)；并遞歸地定義其他節(jié)點：對于SCTT節(jié)點(A，B)，它的子節(jié)點集是{(A.child，B.child)}，其中A.child和B.child是相鄰的；如果A和B在xBVH中有相同的父節(jié)點，即A.parent＝B.parent，則(A.left，A.right)和(B.left，B.right)也是其子節(jié)點。

4.根據(jù)權(quán)利要求1所述的基于三角網(wǎng)格變形體的自碰撞檢測方法，其特征在于：所述步驟(3)中基于星型輪廓的自碰撞檢測實時階段步驟：

方向測試：在碰撞的粗略檢測過程中，自頂而下的檢測包圍盒樹的結(jié)點，若此結(jié)點對應(yīng)區(qū)域的α＜π/2，α為結(jié)點的半錐角，則斷定這塊區(qū)域沒有發(fā)生自碰撞，停止進(jìn)一步檢測；但若α≥π/2，則判斷這塊區(qū)域可能發(fā)生了自碰撞；如此，通過判斷節(jié)點的半錐角α值是否大于π/2，來判斷區(qū)域內(nèi)是否發(fā)生自碰撞，進(jìn)而決定是否繼續(xù)檢測其子節(jié)點；

輪廓測試：在SCTT節(jié)點A的二維投影輪廓片段的基礎(chǔ)上，計算輪廓頂邊的下邊界和底邊的上邊界，所述下邊界即頂邊的最低點，所述上邊界即底邊的最高點；

包圍盒測試：利用體積略大而幾何特性簡單的包圍盒將復(fù)雜幾何對象包裹起來，在進(jìn)行碰撞檢測時，首先進(jìn)行包圍盒之間的相交測試，只有包圍盒相交時，才對其所包裹的對象作進(jìn)一步求交計算；而在構(gòu)造碰撞體的包圍盒時，引入樹狀層次結(jié)構(gòu)，快速剔除不發(fā)生碰撞的元素，減少大量不必要的相交測試；

基元檢測：對于三角形面片來說，基元測試即檢測空間中兩個三角形是否相交。