本記事では、Generative Designにおける興味深い手法の一つである面分割アルゴリズムについて、すでに提案されているアイデアを平易に紹介することを目的とする。特にポリゴンで表現される任意の3Dモデルに適用できるCatmull-Clarkアルゴリズム、Michael Hansmeyerの面分割手法を導入的に紹介する。

Catmull-Clark Subdivision

Catmull-Clark subdivisionは平滑化を目的とした面分割アルゴリズムで、任意の閉じたジオメトリに再帰的に適用できる。アルゴリズム自体は、Bilinear分割（単純にエッジや面の中央に新たなポイントを置き、面を細分化する分割）を行ったあと、近傍のポイント座標の加重平均をとって位置を再計算していくものとなる。加重平均の取り方は、分割におけるポイントの生成過程ごとに異なる。

構造的なコンポーネント分類

• F: Face point 面の中央に生成される点
• E: Edge point 辺の中央に生成される点
• C: Corner point 分割前から存在する頂点

手順

1. 面の中央（各頂点の座標の平均）に点Fを与える
2. エッジの中点に新しい点Eを与え、その座標を近傍の点の加重平均として計算する
3. 既存のジオメトリの点Cの位置を近傍の点の加重平均として再計算する

このアルゴリズムの白眉は、ある程度の条件を満たしていれば、自己交差のあるジオメトリであっても、それらしい形状におさめてしまえるということだ。とくにQuad Modeling ¹ のパラダイムにおいては、トポロジーが美しく機能的にふるまう。数学的には、離散的なサーフェスのBi-Cubic補間としてとらえられるそうだ。

分割前のジオメトリのエッジやポイントをハンドル的に扱い、分割後の形状を操作するという発想もできる。この考えはBlenderにおいても一般化されている。分割前のエッジと分割後のサーフェスを同時に表示してモデリング作業を行う。

ただし、アルゴリズムを実装しようとすると、ある程度の難しさがある。近傍の点をF, E, Cに分類する必要がある。ハーフエッジ構造のようなグラフ構造を用いて、有向線分をたどりながら点の性質を解釈しなければならない。幸い、多くのモデリングソフトは内部的にハーフエッジ構造を持ってくれる。

また、別の困難として、リアルタイム表現への適用が難しいという点が挙げられる。ゲームエンジンなどのラスタライズ過程では、三角形にストリップ分割されるなど、GPU転送に最適化されたうえでシェーディングが行われる場合が多い。その過程でQuad構造は失われる傾向にある。Catmull-Clark面分割はGeometry ShaderなどのGPUユニットで導出することが難しいため、基本的にはオフライン処理におさまることになる。

Michael Hansmeyer Subdivision

Catmull-Clark等の面分割における加重平均部分に拡張を施したのが、Michael Hansmeyerである。入力メッシュから任意の複雑な装飾形状を生成する手法として提案されている。² この手法によって造形された多様で美しい結果は、Subdivided Columns や Digital Grotesque といったプロジェクトで見ることができる。

任意のジオメトリに再帰的に適用でき、パラメータを与えることで多様な見た目に変化するという点で、手続き的な造形手法の極めて優れた例ということができそうだ。

パラメトリックに重み付けを行うことで、コンポーネントごとに意図的に押し出したり、へこませたりする操作ができ、多孔構造やドレーパリー、折構造のような立体的なパターンを表現できる。再帰的に細分化され、適用される加重平均部分のパラメータ伝達についても、様々な手法が提案されている。詳しくは原典をあたってもらうとして、静的に与える方法のほかに、位置ベースでパラメータを与える方法、拡散的に世代間で伝達する方法などが提案されている。

この手法の難しい部分は、パラメータを穏当に設定しないと、すぐに自己交差を引き起こすなど、好ましくない破綻が生じてしまうことだ。Catmull-Clarkの加重平均パラメータを基準とし、その差分を調整していく形になる。筆者は画像のように、得られた面分割の結果をエッジハンドルのように捉え、必要な回数だけCatmull-Clarkアルゴリズムによって平滑化し、安定化された形状を得ている。

なお、この実装についてはHoudiniのDigital Asset (HDA) として公開しているので、興味があれば使ってみてほしい。

NA Weighted Subdiv (HDA)