[發明專利]一種基于三維模型體素化的內部球改進構造方法

無效

• 申請號: 201310138285.0
• 申請日: 2013-04-19
• 公開（公告）號: CN103236079A
• 公開（公告）日: 2013-08-07
• 發明（設計）人: 李重;王君良;許鴻堯
• 申請（專利權）人: 浙江理工大學
• 主分類號: G06T17/00
• 分類號: G06T17/00;G06T17/30
• 代理公司: 浙江英普律師事務所 33238
• 代理人: 陳小良

1.一種基于三維模型體素化的內部球改進構造方法，其特征在于包括下述步驟：

（1）模型表面體素化

首先計算出模型的AABB包圍盒，然后根據體素單位對包圍盒進行劃分，得到每個大小為L×L×L空間體素列表，分辨率為X/L×Y/L×Z/L，接著使用立方體和三角面求交算法確定這些基本體元作為邊界體素，并將這些體素標記為非空，從而完成3D模型表面的體素化操作；其中，L是體素單位長度，X、Y、Z分別表示三維方向的長度；

其中，AABB包圍盒是指一個其表面法向與坐標軸方向相一致的長方體，用兩個頂點坐標a^max和a^min來表示一個模型的AABB，其中，a^max=(X_max,Y_max,Z_max)，a^min=(X_min,Y_min,Z_min)，以這兩點為對角頂點構成的包圍盒即為模型AABB包圍盒；

其中，立方體和三角面求交：以立方體的中心為原點建立坐標系，基于分離軸定理，對13條軸線進行測試，步驟如下：

(A)計算出檢測的13條軸線，分別為立方體法向3條軸線，三角形面法向1條軸線，立方體三個法向和三角形三條邊叉積構成的9條軸線；

如果上述立方體和三角形面均能被13條軸線分離，則立方體和三角面不相交；反之，只要其中有一條軸線不能將兩者分離，則立方體和三角面相交；

(B)當軸線為立方體法向時，進行三角形面和立方體最小包圍盒的重疊檢測；

(C)當軸線為三角形面法向時，先確定立方體對角線和三角面法線的方向最接近的對角線兩個頂點；

若對角線頂點中小的那一個頂點在三角形面的正面一側或對角線頂點中大的那一個頂點在三角形面的反面一側，則立方體和三角面不相交；反之，兩者相交；

(D)當軸線為立方體法向和三角形三條邊的叉積時，先將三角形面和立方體的頂點都投影到軸線上，以立方體的投影點的中心為原點，然后在三角形面的投影點中找出最大值M和最小值m；

在立方體的投影點中計算投影覆蓋的區間半徑R，若有|M|>R、且|m|>R，則立方體和三角面不相交；反之，兩者相交；

若在(B)、(C)、(D)步驟過程中均沒有檢測到相交時，返回立方體和三角面不相交；

（2）模型內部體素化

在確定了封閉模型表面體素之后，對空體素的六個方向進行掃描，在六個方向均找到邊界體素，即將此體素標記為內部體素，然后對內部區域填充，填充過程如下：

初始化時所有體素的標志位設為0，經過表面的體素化后，使表面邊界體素的標志位為1，則外部和內部體素標記為0；具體算法步驟有：

(A)選擇X、Y、或Z三個方向中的一個方向進行掃描；

(B)掃描到第一個標記為1且后一體素標記為0的體素，記下體素標號T₁；其中的T表示X、Y、或Z三個方向中的一個；

(C)繼續掃描，找到第一個標記為1且前一體素標記為0的體素，記下體素標號T₂；

(D)該體素行中，標號在T₁和T₂之間的即為內部體素；

(E)驗證標號在T₁和T₂之間的體素，對其進行六個方向掃描；若均有邊界體素，則可確定T₁和T₂之間的體素是內部體素，并將其標記為-1；

（3）內部球基本構造

（A）對邊界體素中，中心在模型內部的體素進行二次細分預處理，得到新的體素集合；

（B）初始化得到所有體素中心作為球心，并計算相應的半徑；

（C）在步驟（B）的集合中找到半徑值最大的球體，作為一個確定構造的球體；

（D）找到一個確定構造的球體之后，在剩余的球體中，將球心落在這個確定構造的球體內的球體作為取消的球體；

（E）在剩余的球體中，重復步驟（C）和（D），在本步驟中剩余的球體是指除去步驟（D）中確定構造的球體和球心在這個球體內的取消的球體；

（F）直到所有球體都確定構造或取消構造；

（4）內部球聚類構造層次球結構

使用聚類方法對模型的內部球進行球體分類，用于球體層次樹結構構造和網格模型分割；聚類方法的操作如下：

設聚類個數為n，給定內部球個數為m，中心為p_j，對應半徑為r_j，其中j=0,1,…,m-1；初始聚類中心為w_i，其中i=0,1,…,n-1；迭代聚類參數k_ij的計算為：

k_ij:=|{w_k:d(p_j,w_k)<d(p_j,w_i)}|∈{0,1,…,n}…………………………(1)

聚類中心w_i的更新為

wi:=Σj=0mhλ(kij)·pj·vjΣj=0mhλ(kij)·vj····························································(2)]]>

其中hλ(k)=e-kλ,]]>vj=43π·rj3;]]>

初始λ的值第t次迭代的λ值為t_max是最大迭代次數；

球體聚類過程中，兩中心p_j和w_i的距離可分成三部分：p_j到模型表面投影點p_tj的最短距離d_j，w_i到模型表面投影點w_ti的最短距離d_i，表面兩點測地距離為d(p_tj,w_ti)；因此兩內部球心的測地距離可表示為：

d(p_j,w_i)=d_j+d(p_tj,w_ti)+d_i.。

2.根據權利要求1所述的一種基于三維模型體素化的內部球改進構造方法，其特征在于，將內部球中心和聚類中心按同向投影到模型表面，按聚類中心到模型表面距離最短的方向為投影方向，所有球心按這個方向投影構成同向投影，對于有凸起、凹陷、有彎曲的三維模型表面，取最短的交點為投影點，對網格表面模型上的兩個中心：內部球中心在模型表面的投影點和聚類中心在模型表面的投影點，計算模型表面兩點間測地距離。