パラメータ化のアルゴリズム

6.3 パラメータ化のアルゴリズム

従来法の問題点を改善する方法の説明のために，パラメータ化のアルゴリズムや重みの更 新法についての若干の知識が必要となるため，ここではパラメータ化の基本的なアルゴリズ ムについて説明する．

6.3.1 諸定義

まず，使用するメッシュや記号を定義する．3Dモデルは円筒投影のときとは異なり，空間 的に閉じておらず，分岐などもない１枚のメッシュと見なせるものとする．次に，メッシュ の任意頂点をiで表し，この頂点に接続する他の頂点をj∈ N(i)で表す．

6.3.2 問題の定式化：線形スパース方程式による解法

パラメータ化の多くは，頂点同士を結ぶ変の重み付き長さを最小化することで行われる．

図6.5は簡単なメッシュのパラメータ化を示したものであり，重みが等しい場合には，パラ メータ化によりすべての辺の長さが等しくなる．メッシュ全体のエネルギーを式で表せば，

E =∑

i

∑

j∈N(i)

w_i,jku_i−u_jk² (6.1)

となる．ここでu_iは2次元頂点座標，k · kはユークリッドノルム，w_i,jは各辺にかける重み を表している．この代表的な重みとして面積比などがある[Floater 1997]．このエネルギー を最小化する{u_i}^{を得るため，}u_iで微分してゼロベクトルを与える時の{u_i}^{を考えれば，}

∂E

∂u_i = ∑

j∈N(i)

wi,j(ui−uj) =0 (6.2)

i

) Ν(i j∈

j j j

i u −u

ω,

i

j

Before parameterization After parameterization 1

: case ωi_,j==

図6.5: 簡単なメッシュのパラメータ化

76 第6章 ３次元メッシュ・パラメータ化によるジオメトリ画像化と形状復元

が得られる．また，上式はスパース行列を用いれば，

WU=0, where

Wi,j=











∑

jwi,j, i=j

−w_i,j, j ∈ N(i) 0, otherwise

Ui =ui

(6.3)

と簡単に表すことができる．ただしこのままでは拘束が足りず，解は{ui} =0に収束して しまう．

拘束条件としては，メッシュ端の境界上の頂点をあらかじめ二次元平面上に固定すること が一般的で，式(6.3)に対して拘束条件を加えた場合，境界の頂点座標を縦に並べた行列B と，Wの境界の頂点に対応する行を書き換えたWˆ を用いて，

WUˆ =B where

Wˆi,j =











1 i=j 0 i6=j

i∈boundary W_i,j otherwise

Bi =





ui i∈boundary 0 otherwise

(6.4)

と書き直される．これによりパラメータ化された頂点座標を，

U= ˆW⁻¹B (6.5)

として得ることができる．なお，境界の頂点の配置uiは，基本的には境界の形状が凸型を満 たしていれば配置は自由で，一般に円形や長方形が用いられる．

6.3.3 メッシュストレッチ

単にパラメータ化を行っただけでは，図6.2 (a)のような粗密がメッシュに生じるため，パ ラメータ化されたメッシュを再度，重みw_i,jを変えてパラメータ化することで，メッシュを 拡げていく[Sander et al. 2001, Sander et al. 2002, Yoshizawa et al. 2004]．ここではこのこ とをメッシュストレッチと呼ぶ．

反復時の重みの更新は，以前の重みw^t−1に対して，現在の2Dメッシュの拡がり具合を表 す量σi,jを乗算することで行われ，

w_i,j^t =σ_i,jw^t_i,j⁻¹

w_i,j^t =w_i,j^t /∑

jw^t_i,j

(6.6)

6.3. パラメータ化のアルゴリズム 77

これによりメッシュの疎密が緩和され，図6.2 (b)(c)のように，リメッシュの結果が向上する．

6.3.3.1 反復ストレッチの終了条件

メッシュの拡がりが収束したかどうかは，σ_i,jの値が1に収束したかどうかを調べること で行うことができる．

1 n

∑

{i,j}

|σi,j−1|² < threthold (6.7)

ここで{i, j}はメッシュに含まれるすべての辺を表し，nはその総数を表している．

6.3.4 問題点

[Sander et al. 2001]や[Yoshizawa et al. 2004]では，σ_i,j として，方向や距離を考慮した メッシュの伸びを表す量が用いられているが，この方向性に対する拘束力が強いため，場所 によっては十分にメッシュを拡げることができず，このような部分のリメッシュ形状を劣化 させてしまう．また，このようにσ_i,jの拘束力が強かったり，変化が大きいと，パラメータ 化を繰り返す際にσ_i,jが単調に収束せず，振動するなどの問題が生じる．

78 第6章 ３次元メッシュ・パラメータ化によるジオメトリ画像化と形状復元