（メモ）Subdivision Surface Theory
まとめなおすの面倒だからメモのままのっけとく。
気が向いたらそのうちなおす。
Subdivision Surface Theory GAMASUTRA http://www.gamasutra.com/view/feature/131585/subdivision_surface_theory.php?print=1
Pixar が Siggraph '98 に出展した Geri's Game で知られる
ポリゴンモデルを使って面を描画する
普通のポリゴンと違って、完全になめらかな曲線をかける
Pixar の場合は1ピクセル未満の大きさまでポリゴンを分割
技術自体は新しくないけど、実装には制限がかなり大きい
Pixar のも微妙だったけど、それでもスケーラブルなジオメトリ実装として注目された
Pixar の作品をきっかけに研究が加速
今ではかなり成熟した技術に
スケーラブルなジオメトリ技術はゲームでも重要
最近（2000年当時）は1フレームあたりのポリゴンがローエンドで10000、ハイエンドで数十万
ハードウェアの差が酷いからこれを吸収するのに役立つ
この記事はあくまで理論的概要
実際のプロダクトに直接は役立たないけど、理論を知っておくことで今後SubDを扱うときの強みになる
The What and the Why
再分割曲面 = 分割を繰り返してなめらかな曲面をつくる
もとからある頂点群（control net）を動かしたり新しい頂点をつくったりする
頂点を消しちゃうのもあるけど、マイナー
control net と limit surface は、"トポロジー的に" 同一
要するに位相が同じ、コーヒーカップとドーナツのホモトピー
このトポロジーの同一性はすごく重要
ベジェとか B-Spline パッチだとモデリングが難しいし、気をつけないとひびとかアーティファクトが出る
場合によっては縮退エッジ（三角形パッチ）が必要になってくる
再分割曲面だと、任意の control net から任意のトポロジーを生成できる
control net をアニメーションさせてもメッシュにひびとかはいらないし、キャラモデルに向いてる
アニメつけたときの面の連続性の確保はすごく大事
The basics.
まずは一般的な特徴
計算コストや扱いやすさに気をつける
Continuity: the holy grail.
微分可能性
C^0 連続のとき、曲面は1回も微分できない、穴を空けることもできない
C^1 連続のとき、1回だけ微分できる、微分可能な接平面を持つ閉じた曲面、尖った繋ぎ目を持つことができない
SubDも、アルゴリズムによっては C^1 連続な曲面しか生成できないものと、C^2 連続な曲面まで生成できるものがある
この連続性というのが非常に重要
常になめらかな曲面を生成できるか
現実の世界に本当に flat な平面や本当に sharp なエッジはほとんど存在しない
To Interpolate or not to Interpolate
Approximating Scheme
control net の各頂点が limit surface の上に乗らない、分割を繰り返すごとに limit surface に近づくように移動してく
尖ったエッジになるように頂点を置いても最終的にはだいぶ丸くなる
もとの頂点と limit surface 上の対応する頂点が遠くなって、直感的にモデリングしにくい
Interporating Scheme
control net の各頂点が limit surface の上に乗る、分割を繰り返しても移動しない
もとの頂点の位置から limit surface が視覚的に想像しやすい
control net の「出っ張り」がそのまま残りやすい
→ Figure 1
Surfaces in Uniform
各手法は Uniform と Ununiform にわけられる → stationary と nonstationary
分割手法の違い
Uniform は常に同じ比率でエッジを分割する、Ununiform はエッジごとに重み付けアリ
Stationary は常に同じ比率で分割を繰り返す、Nonstationary は分割ごとに違う比率になりうる
ここで紹介する手法は基本的に全部 Uniorm/Stationary
手法ごとに Ununiform/Nonstationary な拡張がある
Subdivision Shape
Uniform/Ununiform ほど重要じゃないけど、control net を構成するポリゴンが三角形か四角形かでも分けられる
triangular: 三角形のエッジを分割して新しい三角形をつくる
quadrilateral: 四角形の面を分割して新しい四角形をつくる
いずれにせよ、再帰ごとに分割方法を変えないこと、四角形を重心で四分割したあとに対角線で割ったりしない、重心ならずっと重心
→ Figure 2
Extraordinary Vertices
分割を繰り返しても同じ座標を保つ、特別な頂点、ってのがある
limit surface を考えるときはこの頂点の存在が重要
どこにあるのか？ vertex calence（隣接エッジ）は？
→ Figure 3
Surcace Evaluation
control net を起点に頂点を分割したり面を割ったりしながら再帰的に分割するプロセス
Interpolating sheme: tangent masks を使って各頂点に付与する面法線を計算する
Approximating sheme: evaluation masks を使って各頂点の limit position を計算する
mask は masquerade、新しい頂点座標を計算するときに、どの頂点をもとに計算するか
→ Figure 4
各手法の基底関数の support に影響される、制御点を動かしたときの影響の局所性を決めるパラメータ
A Note on Notation
頂点を V であらわす
再帰分割の深さ、レベルを i であらわして、レベル i の頂点は V^i
隣接エッジの個数が N のとき、隣接頂点を ε_j であらわす、レベル i の隣接頂点は ε_j^i、隣接エッジは e_j^i
文献によって異なるけどだいたい雰囲気は同じ
The Polyhedral Scheme
もっともシンプルで教育的な手法
三角形の各辺について、中点に新しい頂点を置く
control net と limit surface が一致する
uniform, 常に中点で辺を分割する
stationary, 常に同じ方法で分割する
C^0 連続, 分割後のメッシュが有効な接平面を持たない
生成されるすべての頂点が extraordinary vertices
evaluation masks, control net と limit surface が一致するから必要ない
tangent masks, なめらかな曲面を生成しない = 有効な接平面が存在しないから必要ない
→ Figure 6
Float Like a butterfly…
(modified) butterfly subdivisioin scheme
C^1 連続のなめらかな曲面を生成できる
Dyn, Levin, Gregory, "A Butterfly Subdivision Scheme for Surface Interpolation with Tension Control", ACM TOG, 1990
http://www.math.tau.ac.il/~niradyn/papers/butterfly.pdf
interpolating, trianguler, もとの三角形の辺上に新しい頂点を置く
各係数と重み付け（tension control）を使って新しい頂点を生成
基底関数はコンパクトサポート
→ Figure 7, 数式
係数 w が、control net を limit surface にどれだけ近付けるか、を決めるための重み
w = -1/16 のときに前述の多面体分割と等価
control net のエッジ付近、隣接エッジ数が5未満のときは、必要な点が足りなくて w=-1/16 にせざるをえないときがある
このとき、なめらかな曲面を生成できなくてモデリングが難しくなる
これを解決するために考えられたのが 1993 に発表された modified butterfly scheme
もとの 8 点じゃなくて 10 点で再分割する
→ Figure 8, 数式
Dyn, N., S. Hed, and D. Levin. “Subdivision Schemes for Surface Interpolation.” Workshop in Computational Geometry (1993), A. C. et al., Ed.,” World Scientific, pp. 97?118.
全部の係数を合計すると 1 を超えるのは相変わらず
この合計値は修正前の butterfly より大きくなってて、デザイナ的に扱いにくさが増してる
w=0 のときは修正前の butterfly と同じ
この修正でも、修正前のなめらかな曲線が生成できない問題は残ってる
1996 年にこれがさらに拡張されて、すべての領域で C^1 連続を確保できるようになった
extraordinary vertices に関する制約を変えた
Zorin, D., P. Schroder, and W. Sweldens. “Interpolating Subdivision for Meshes with Arbitrary Topology.” Siggraph ‘96. pp. 189?192.
http://mrl.nyu.edu/~dzorin/papers/zorin1996ism.pdf
エッジの両端点が通常の頂点で隣接エッジ数が両方とも 6 のときは、10 点の butterfly と同じアルゴリズム
片方が extraordinary のときは、その頂点の隣接エッジ数にしたがって違う係数を使う
隣接エッジの "向こう側" の端点が extraordinary かどうかは気にしなくていい
→ Figure 9, 数式
エッジの両端が特異頂点のときは、それぞれの端点ごとに↑の数式で計算してから、両者の平均をとる
interpolating だから evaluation masks はいらないけど、頂点ごとの接ベクトルを計算するときに tangent masks が明示されてると便利
細かい理論は複雑で役に立たないからここには書かない
→ Figure 10
Catmull-Clark Surfaces
quadrilateral, epproximating
1. control net の各面について、それぞれの中心に新しい頂点を置く
2. control net の各辺について、それぞれの端点と 1 の頂点との中心に新しい頂点を置く
3. 1 と 2 で計算したすべての頂点について、↓の式に従って位置を更新する
→ Figure 11, 数式
→ Figure 13
互いに隣接する頂点同士をつないで、新しい辺を構成する
===
This is the only one of the three schemes shown here where the scheme can actually create an extraordinary vertex during subdivision.
This is not as bad as it may seem, though. After a single subdivision step, all the faces in the control net are quadrilaterals. Therefore, the scheme can only introduce new extraordinary vertices during the first subdivision step. After a single subdivision step, the number of extraordinary vertices is set and will not change.
→ この部分よくわからない
結局分割を行うことで特異頂点が増えることはないよって意味だと思うんだけど
それだと1文目の can actually create an extraordinary vertex during subdivision が意味不明
===
evaluation masks の計算は以下のとおり、N は隣接エッジの数
分割後の control net を計算に使うとこに注意
→ 数式
tangent masks の計算は以下のとおり
複雑な式にみえるけど、N が定数なことに注目して事前計算すればコストはそれほど高くない
面法線は t_0 と t_1 の外積を正規化して求める
→ 数式
Catmull-Clark Extended
Catmull-Clack はハイエンドCGでよく使われる
Pixar の Geri's Game
数学的な美しさと、sharp/semi-sharp な折り目を表現できる Pixar による拡張
折り目表現の実装はシンプル
折り目を付けたい辺や頂点に [0,∞] の係数を用意する
0 のとき完全になめらかな limit surface そのものを近似して、∞ のときは完全に尖る
この拡張の影響で、Catmull-Clark が nonuniform で nonstationary になる
辺や頂点に重み付けされるから nonuniform
semi-sharp 部分は途中まで線形に計算し（尖らせ）たあとに、なめらかな近似を行うから nonstationary
折り目付近では B-spline と全然違うものになるし、evaluation/tangent masks も無効になる
ゲームとかで使うには tangent masks を捨てるのが難しいから、こういう拡張は計算コスト的に難しいかもしれない
