[發明專利]支持骨架個性化編輯的輕量化三維樹木模型構建方法

有效

• 申請號: 201410066348.0
• 申請日: 2014-02-26
• 公開（公告）號: CN103914869B
• 公開（公告）日: 2017-02-22
• 發明（設計）人: 董天陽;劉思遠;紀磊;范菁
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06T17/00
• 分類號: G06T17/00
• 代理公司: 杭州天正專利事務所有限公司33201
• 代理人: 王兵,黃美娟

1.支持骨架個性化編輯的輕量化三維樹木模型構建方法，包括下列步驟：

步驟一，從三維樹木模型的三角網格數據中獲取樹木枝干的頂點信息，將枝干部分劃分成若干個拓撲結構簡單的子樹枝，以子樹枝為基本處理單元進行骨架提取，并整合所有子樹枝的骨架形成完整的樹木模型骨架結構；樹木枝干模型的骨架提取過程包括以下五個分步驟：

1.1從模型文件中獲取樹木枝干的頂點信息，包括頂點編號，頂點三維坐標x、y、z的值；

1.2根據樹木枝干的頂點信息，建立一個枝干的帶權n階無向連通圖G；根據組成每個平面圖元的頂點信息可以得到無向連通圖G的邊(v,v')；每條邊的權值就是構成這條邊的兩個頂點(x_a,y_a,z_a)和(x_b,y_b,z_b)間的歐式距離d，如公式(1)。

d=(xa-xb)2+(ya-yb)2+(za-zb)2---(1)]]>

1.3在無向連通圖G中選擇坐標值z最小的頂點為源點s，采用最短路徑算法計算從源點s出發到圖G中所有頂點的最短路徑，形成有向帶權圖G'；

1.4將有向帶權圖G'劃分成k個層次，即將每條枝干利用公式(2)平均分成k段(d_i…d_k)；

d_i=d_max/k(i=1,…,k)???(2)

d_max為有向帶權圖G'中所有頂點之間的最大距離，k的值根據樹木的品種和樹木模型的拓撲層次分別確定；隨后，計算有向帶權圖G'中每一層次的中心節點O和半徑R，中心節點即可作為枝干的骨架節點；

1.5依次連接枝干的每個骨架節點，得到樹木模型的骨架曲線，即樹木模型的枝干骨架結構；

步驟二，根據骨架節點的三維坐標點數據，依次計算每個子樹枝的末端骨架節點到父親樹枝骨架節點的距離，選擇其中最小距離值的一個骨架節點為子樹枝的生長點，連接子樹枝末端骨架節點和子樹枝的生長點；

p為樹枝a末端骨架節點，為了尋找樹枝a在主干上的生長點v_grow，則需要求出主干的骨架節點中距離p最近的點；首先利用公式(3)計算出主干上的點v_i∈V_skeleton(i=1...n)到點p的距離d_i，其中n為主干上的頂點數量；

設樹枝上兩個點p(x_p,y_p,z_p)和v_i(x_i,y_i,z_i)，則兩點之間的距離表示為d_i：

di=(xp-xi)2+(yp-yi)2+(zp-zi)2---(3)]]>

在所有的距離值d_i(i=1...n)中，求出距離最小值d_min，可表示為：

d_min=min(d_i|i=1…n)???(4)

則樹枝a的生長點v_grow為距離d_min所代表的骨架節點；p點距離主干中的q點最近，q點即為樹枝a的生長點。

步驟三，通過鼠標、觸摸屏等交互方法編輯三維樹木模型的生長點位置，由用戶進行生長點拖拽，并根據樹枝生長點位置的變化實時平移調整該生長點對應的子樹枝；

設原始生長點p坐標為(x,y,z)，通過交互式編輯后p’的坐標為(x’,y’,z’)則平移向量為可表示為：

p→=p-p′=(x-x′,y-y′,z-z′)---(5)]]>

又假設樹枝b包含的骨架節點集合為V_skeleton，由于樹枝b生長點的位置變化將引起V_skeleton中所有點坐標位置改變，則有：

vi=vi+p→{vi∈Vskeleton}---(6)]]>

平移調整后，通過交互式編輯首先將p的位置向左下方移動，移動的向量為樹枝b和屬于它的子樹枝向左移動同樣的向量如果將樹枝a的生長點q的位置向正下方移動則樹枝a和屬于他的子樹枝同樣向下移動

步驟四，用戶可以選擇向上或向下保持生長角度的子樹枝生長方向的調整策略，并根據選擇的子樹枝生長方向調整策略計算平移調整后子樹枝的生長角度，使得經過骨架編輯后子樹枝的生長角度與原始狀態保持一致；

4.1采用向上保持生長角度策略時，以子樹枝與其生長點上端的父親樹枝之間的夾角為樹枝生長角度；

θ和分別是樹枝a和樹枝b的生長角度，也就是樹枝a和b與向量和之間的夾角；夾角計算過程如下：

假設向量的坐標為(x₁,y₁,z₁)，生長點p和樹枝b的中心點o所形成的向量的坐標為(x₂,y₂,z₂)，則和之間的夾角θ的余弦值利用公式(7)可求得：

cosθ=pm→·po→|pm→|*|po→|---(7)]]>

其中，分子為向量和的點積，分母為向量和模的數量積，計算公式分別如下：

pm→·po→=x1*x2+y1*y2+z1*z2---(8)]]>

|pm→|*|po→|=x12+y12+z12*x22+y22+z22---(9)]]>

然后，將求得的向量之間夾角的余弦值cosθ帶入公式(10)，求得夾角的弧度值rad，可表示為：

rad=acos(cosθ)???(10)

最后，將弧度值rad帶入公式(11)轉換成向量間的角度θ；

θ=rad*1803.14---(11)]]>

經過骨架編輯平移調整后的骨架結構中，由于樹枝b位置的平移，使得樹枝b與向量之間的夾角變為θ'；運用向上保持生長方向調整策略，調整樹枝b與之間的夾角θ'，使它與θ相等；同時，由于p位置發生偏移，使得與樹枝a之間的夾角發生變化，因此樹枝a的所有坐標信息同樣也需要進行調整使得夾角為

4.2在向下保持生長角度的策略中，以子樹枝與其生長點下端的父親樹枝之間的夾角為樹枝生長角度；

樹枝b的生長角度為ξ，樹枝b與向量之間的夾角，與向上保持生長方向相比，同樣是生長點p的位置發生變化；

4.3由于骨架節點坐標均為三維坐標，在進行骨架個性化編輯時所產生的位置偏移也是相對于三維空間的，因此在進行樹枝生長方向選擇調整時的旋轉軸為三維空間任意坐標向量；p原始三維坐標點，p’為旋轉后的坐標點，l為旋轉軸；

設原始點p坐標為(x,y,z)，繞過點Q(x₀,y₀,z₀)的方向向量為的任意坐標軸l，旋轉后得到p’的坐標為(x’,y,z’)。p’的計算公式(12)如下所示：

x'=(x-x₀)*(n_x²*(1-cosθ)+cosθ)+

(y-y₀)*(n_x*n_y*(1-cosθ)-n_zsinθ)+

(z-z₀)*(n_x*n_z*(1-cosθ)+n_ysinθ)+x₀

y'=(x-x₀)*(n_x*n_y*(1-cosθ)+n_z*sinθ)+

(y-y₀)*(n_y²*(1-cosθ)+cosθ)+

(z-z₀)*(n_y*n_z*(1-cosθ)-n_xsinθ)+y₀

z'=(x-x₀)*(n_x*n_z*(1-cosθ)-n_y*sinθ)+

(y-y₀)*(n_y*n_z*(1-cosθ)+n_x*sinθ)+

(z-z₀)*(n_z²*(1-cosθ)+cosθ)+z₀???(12)

公式12中θ是點p繞旋轉軸l的旋轉角度，(n_x,n_y,n_z)是旋轉軸l的方向余弦，可表示為公式(13)，其中|l|為旋轉軸向量模。

(nx,ny,nz)=(xl|l|,yl|l|zl|l|)---(13)]]>

生長點p經過個性化編輯平移到p’，使得被動樹枝a調整自己的生長角度；利用公式(11)求出旋轉后樹枝a中的所有坐標值。定義旋轉坐標軸l的方向向量為和的法向量，且過生長點q。向量的計算公式如下：

n→=a→⊗b→=(aybz-azby)i→+(azbx-axbz)j→+(axby-aybx)k→---(14)]]>

步驟5，采用骨架節點和圓臺的方式表示三維樹木模型，根據一一對應的骨架節點和半徑信息來實現枝干模型的重構；

一根樹枝由若干圓臺表示出來，該圓柱體的底面和頂面具有不同的半徑，且圓柱體的上下面以枝干的骨架節點為圓心；根據一一對應的骨架節點和半徑信息構造一系列具有不同上、下面的圓柱體來實現樹枝模型的重構；

5.1在骨架節點中獲取每根樹枝的骨架節點的三維坐標點數據和半徑信息；

5.2將樹枝底向上的骨架節點和半徑每兩個分為一組，然后，每組中的骨架節點對應圓臺的下底和上底中心位置，根據半徑信息繪制圓臺；

5.3將所有圓臺進行拼接構成模型的枝干；

步驟六，通過計算樹木模型局部樹枝的外部輪廓，用凸包的方式進行表示，然后通過選取已有的紋理模板去填充相應的樹枝凸包，實現樹木模型整體樹冠的重構；

6.1根據樹枝包含的子樹枝個數和樹枝的生長方向將所有紋理進行分類，在每一類紋理中選取一個紋理作為模板紋理；

6.2通過采用增量凸包算法求取局部枝葉三維凸包，并記錄三維坐標信息；

6.3根據凸包的三維信息在紋理模板庫中選用復合樹枝基本信息的紋理進行三維樹冠重構。