graphics.hatenablog.com

技術系テクニカルアーティストのあれこれ

再分割曲面のもうちょい基礎。

参考資料はこれ↓と、あと google 先生。


ざくっと概要

「再分割」ってのは、適当な区分線形関数を再帰的に適用すること。
こんなかんじ↓
f:id:hal1932:20120808194040p:plain

この図だと赤→青→緑ってかんじで直線の分割を繰り返してるけど、この分割を無限回繰り返すと曲線に収束するってのはわりとイメージしやすいと思う。その曲線のことを 極限曲線 っていう。曲面の場合は 極限曲面。

実際の分割にはいろんなアルゴリズムがあるんだけど、Chaikin のアルゴリズムってのがわりと単純でわかりやすい。
f:id:hal1932:20120807213833j:plain


B-Spline 曲線

数式自体はごくシンプルで、こんなかんじ↓
<br /> C_0(t) = \left\{<br /> \begin{array}{ll}<br /> 1 & (0 \leq t < 1) \\<br /> 0 & (otherwise)<br /> \end{array}<br /> \right
<br /> C_l(t) = \int C_{l-1}(s) C_0(t-s) ds<br />

l=0 なら単純に各辺が 1 の正方形関数で、l=1 のときはこれをふたつ畳み込んだかたちになる。
<br /> C_1(t) = \int C_0(s) C_0(t-s) ds<br />
これは Wikipedia の図解がいいかんじ。直角三角形ね。

l=2 のときも似たようなかんじで、
<br /> C_2(t) = \int C_1(s) C_0(t-s) ds<br />
直角三角形と正方形を畳み込む。面倒だから図は用意しないけど、底辺（support）が 3 で高さが 0.75 のガウス関数みたいなかたち。


制御点と精緻化の関係

この B-Spline の l にあたるのを 次数 っていうんだけど、この次数をひたすら増やしてって曲線を少しづつなめらかにしていく仮定を 精緻化（refinement） と呼ぶ。いちおう精緻化方程式ってのがあるけど、そんなん覚えても使わないから省略。

で、この B-Spline、与えるパラメータをごにょごにょして線形結合のかたちに分解できるのね。こんなかんじに↓
C_0(t) = C_0(2t) + C_0(2t-1)
C_0(2t) ってのは C_0(t) に 2 倍の dilation を与えて support が 1/2 になったやつ、C(2t-1) はさらに -1 の translation を与えたやつ。詳細は省くけど、Wavelet の多重解像度解析（MRT）とかやったことあるとこのへんはきっとおもしろい。

さらにこいつをパラメータ化して
C_l(t) = \left[ x(t), y(t), z(t) \right] = \sum_i p_i C_l^i(t)
みたいにしたとき、このパラメータ t に対する (x_i,y_i,z_i) \in p_i \in {\bf R}^3 とかを 制御点 と呼ぶ。

やっぱり細かい数式は省くけど、B-Spline の精緻化を繰り返すってことは support を 1/2 にしながらひたすら線形結合をしていくってことで、これは各制御点の間に新しい制御点を追加してくことに相当する。これを無限に繰り返すことで、特異点以外では C2 級になるなめらかな曲線を生成できるわけだ。

これを 3 次元に拡張したのが、再分割曲面（subdivision surfaces）。


再分割曲面

再分割曲面の場合は当然ながら制御点は 3 次元空間上に配置されていて、これらの制御点で構成されるポリゴンを 制御多面体（制御メッシュ） と呼ぶ。その制御メッシュをまた精緻化していくんだけど、再分割曲面自体は、その制御多面体の極限曲面として定義される。たとえば Maya とかでみるやつはこの極限曲面なわけだ。モデリングしてるときに「2」とか「3」を押すとでてくるハイポリっぽいアレは、実はパラメータ化された再分割曲面だったりする。
f:id:hal1932:20120807222401j:plain

曲面の場合は、面を分割する face scheme と頂点を分割する vertex scheme の 2 種類があるんだけど、ここでは face scheme の Catmull-Clark 曲面を取り上げてみる。CG でまずやるのってやっぱこれだし、Pixar はやっぱすごい。


Catmull-Clark 曲面

昨日のエントリ でも書いたんだけど、これを使った n 角形の再分割手順は以下の通り。基本的には「分割」と「平均」の操作。
1. 面頂点の平均をとって新しい面頂点を計算する
2. 面の稜線の端点と「新しい面頂点」の平均をとって新しい稜線の端点を計算する
3. 頂点の座標を↓の式で更新する
\frac{Q}{n} + \frac{2R}{n} + \frac{S(n-3)}{n}
Q はその頂点に隣接する新しい面頂点の平均、Rはその頂点に隣接する古い稜線の中点の平均、S はもともとの頂点。

ちなみに真面目にこの 3 つの数式を解くと導出できるんだけど、面がすべて同じ大きさの正方形のとき、Catmull-Clark 曲面は双三次 B-Spline 曲面に一致する。

制御多面体の凸包（convex hull）に曲面が内包されるのと、極限曲面が完全にパラメトリックに表現できるってのが特徴。ようするに、曲面の制御がわりとやりやすいってのと、わざわざ面倒な再帰計算をしなくても極限曲面が計算できる。ちなみに特異点が C1 連続でそれ以外は C2 連続になってる。