サブディビジョンサーフェス

3Dコンピュータグラフィックスの分野において、サブディビジョンサーフェス（一般にSubDサーフェスまたはSubsurfと略される）は、より粗いポリゴンメッシュの仕様によって表され、再帰アルゴリズム法によって生成される曲面である。基礎となる内側メッシュ^[1]である曲面は、制御ケージまたは外側メッシュと呼ばれる粗いメッシュから、各ポリゴン面を最終的な基礎となる曲面により近似するより小さな面に細分化する反復プロセスの機能的限界として計算することができる。あまり一般的ではないが、全体的な形状や体積を変えずに面をより小さな面に細分化することでメッシュにジオメトリを追加する単純なアルゴリズムが使用される。

その逆はポリゴンの縮小、つまり細分化の解除です。^[2]

サブディビジョン サーフェス アルゴリズムは、本質的に再帰的です。プロセスは、ベース レベルのポリゴン メッシュから始まります。次に、このメッシュにリファインメント スキームが適用されます。このプロセスでは、そのメッシュを取得して細分化し、新しい頂点と新しい面を作成します。メッシュ内の新しい頂点の位置は、近くの古い頂点、エッジ、および/または面の位置に基づいて計算されます。多くのリファインメント スキームでは、古い頂点の位置も変更されます (新しい頂点の位置に基づいて変更される場合もあります)。

このプロセスにより、元のメッシュよりも密度の高いメッシュが生成され、ポリゴン面の数が多くなります (多くの場合、4 倍)。この結果のメッシュは、同じリファインメント スキームに何度も通して、さらにリファインメントされたメッシュを生成することができます。各反復は、多くの場合、サブディビジョンレベルと呼ばれ、ゼロ (リファインメントが行われる前) から始まります。

限界細分割面は、このプロセスを無限回繰り返し適用して生成される面です。ただし、実際の使用では、このアルゴリズムは限られた、かなり少ない回数 ( ) だけ適用されます。 ${\displaystyle \leq 5}$

数学的には、サブディビジョンサーフェスの異常頂点（四角形メッシュの4価でないノード）の近傍は、パラメトリックに特異な点を持つスプラインです。^[3]

サブディビジョン サーフェスの改良スキームは、補間と近似の2 つのカテゴリに大まかに分類できます。

• 元のメッシュ内の頂点の元の位置と一致させるには、補間スキームが必要です。
• 近似スキームはそうではありません。必要に応じてこれらの位置を調整できます。

一般に、近似スキームの方が滑らかさは増しますが、ユーザーは結果全体をあまり制御できません。これは、スプラインサーフェスと曲線に似ています。スプライン サーフェスと曲線では、ベジェ曲線は特定の制御点を補間する必要がありますが、B スプラインではその必要はありません (より近似的です)。

サブディビジョン サーフェス スキームは、操作するポリゴンの種類によっても分類できます。四辺形 (quads) に最適なものもあれば、主に三角形 (tris) を操作するものもあります。

近似とは、限界面が初期メッシュを近似し、細分化後に新しく生成された制御点が限界面内にないことを意味します。^{[説明が必要]}近似細分化スキームには 5 つあります。

• CatmullとClark（1978）Quadsは、双3次 一様 Bスプラインノット挿入を一般化します。任意の初期メッシュに対して、この方式は、C ¹連続である異常頂点を除いてどこでもC ²連続である極限面を生成します（PetersとReif 1998）。^[4]
• Doo-Sabin (1978)、Quads – 2 番目の細分化方式は Doo と Sabin によって開発されました。彼らは曲線に対する Chaikin のコーナーカット法 (George Chaikin、1974 ^[5] ) を曲面に対してうまく拡張しました。彼らは、双二次一様B スプライン曲面の解析的表現を使用して細分化手順を生成し、任意の初期メッシュに対して任意のトポロジーを持つC ¹極限曲面を作成しました。補助点により、Doo-Sabin 細分化の形状を改善できます。^[6]細分化後、すべての頂点の価数は4 になります。 ^[7]
• Loop (1987)、三角形 – Loop は、6 つの方向ベクトルの 4 次ボックス スプラインに基づくサブディビジョン スキームを提案し、 C ¹連続である特別な頂点を除くすべての場所でC ²連続の極限面を生成する規則を提供しました(Zorin 1997)。
• ミッドエッジサブディビジョンスキーム (1997–1999) – ミッドエッジサブディビジョンスキームは、Peters-Reif (1997) ^[8]と Habib-Warren (1999) ^[9]によって独立して提案されました。前者は、各エッジの中点を使用して新しいメッシュを構築しました。後者は、4 方向のボックススプラインを使用してスキームを構築しました。このスキームは、任意のトポロジを持つ初期メッシュ上にC ¹連続極限面を生成します。(ミッドエッジサブディビジョンは、2 ステップで距離が半分になるため、「√2 サブディビジョン」とも呼ばれ、最も遅いと考えられます。)
• √3 分割方式 (2000)、三角形 – この方式は Kobbelt ^[10]によって開発され、いくつかの興味深い機能を提供します。任意の三角形メッシュを処理でき、C ¹連続である異常な頂点を除いてどこでもC ²連続であり、必要に応じて自然な適応的な改良を提供します。少なくとも 2 つの特徴があります。三角形メッシュのデュアル方式であり、プライマル方式よりも改良率が遅いことです。

細分化の後、元のメッシュの制御点と新しく生成された制御点が極限面上で補間されます。最も初期の研究は、Dyn、Levin、Gregory (1990) によるいわゆる「バタフライ スキーム」で、曲線の 4 点補間細分化スキームを面の細分化スキームに拡張したものです。Zorin、Schröder、Sweldens (1996) は、バタフライ スキームでは不規則な三角形メッシュの滑らかな面を生成できないことに気付き、このスキームを修正しました。Kobbelt (1996) は、曲線の 4 点補間細分化スキームをさらに一般化し、面のテンソル積細分化スキームにしました。1991 年、Nasri は Doo-Sabin を補間するスキームを提案しました。^[11]一方、1993 年には Halstead、Kass、DeRose が Catmull-Clark のスキームを提案しました。^[12]

• バタフライ（1990）、三角形 - スキームの形状にちなんで名付けられました
• 修正バタフライ（1996）、クワッド^[13] - 不規則なトポロジーによって生成されるアーティファクトを克服するために設計された
• Kobbelt (1996)、Quads – 均一分割の欠点を克服しようとする変分分割法

• 1978 年: 細分割面は、エドウィン・キャットマルとジム・クラーク (キャットマル-クラーク細分割面を参照)、およびダニエル・ドゥーとマルコム・セービン (ドゥー-セービン細分割面を参照)によって説明されました。
• 1995年: ウルリッヒ・ライフが異常頂点付近の細分曲面の挙動を解明した。^[14]
• 1998年:ジョス・スタムは、任意のパラメータ値の下でのCatmull-Clarkサブディビジョンサーフェスの正確な評価法を考案しました。^[15]

• ジェリーのゲーム（1997年） - 人間の皮膚を表現するためにサブディビジョンサーフェスを使用する先駆者となったピクサー映画
• 非一様有理Bスプライン（NURBS）サーフェス – 曲面を表現する別の方法

• ジェリーのゲーム: 1997 年に完成したピクサーによるオスカー受賞アニメーション。キャットマル クラーク分割法(および布のシミュレーション) を使用したサブディビジョン サーフェスを導入しました。
• モデリングとアニメーションのためのサブディビジョンチュートリアル、SIGGRAPH 1999 コースノート
• モデリングとアニメーションのサブディビジョンチュートリアル、SIGGRAPH 2000 コースノート
• 異常頂点近傍の細分化アルゴリズムへの統一的アプローチ、ウルリッヒ・ライフ（Computer Aided Geometric Design 12(2):153–174 1995年3月）
• サーフェスとボリュームメッシュの細分化、最も一般的なスキームを使用して細分化を実行するソフトウェア
• 計算幾何学アルゴリズムライブラリ CGAL における表面分割法