9. ポリゴンメッシュ・ボリューム・その他の形状表現

第7章ではソリッドと其の境界の表し方を、第8章では制御点から滑らかな曲線と曲面を作る方法を見ました。
此の章では、実際のソフトウェアが殆どの場合に保存して描画する表現を扱います。
ポリゴンメッシュ、其れを滑らかにする細分割曲面、中身の有る物（CTスキャン、スカルプト、壊せるゲームの世界）の為のボクセルと八分木、メタボールの様な陰関数曲面、そして手で作るのではなく「生成する」その他の表現、つまりフラクタル、L-system、パーティクル、点群です。

何故此れが大事なのでしょうか？
GPUが描くのは三角形なので、形状が元々どんな表現であっても、殆どの場合は最後に三角形メッシュになり、メッシュの持ち方がメモリと時間のコストを決めます。
又、多くの形状は最初は別の形で記述する方がずっと楽です。
CTスキャンの脳は数値の格子、煙の雲は何千ものパーティクル、木は短い書き換え規則です。
検定対策としては、此の章は分野3（モデリング）の最後の3つのシラバス項目、ポリゴン曲面の表現、ボリュームを用いた形状表現、そのほかの形状表現法を扱います。
話題が多いので、其々を短くまとめ、全てに小さな数値例を付けます。

9.1 ポリゴン曲面

ポリゴンメッシュは、頂点と辺を共有する平らな多角形で出来た面です。
曲面上の点を標本化して其れらを繋ぐと、曲面はポリゴン曲面になります。
ポリゴンが多い程、近似は元の曲面に近付きます。
メッシュの位相（トポロジー）の保存と検査（境界表現、ハーフエッジ構造、オイラーの公式）は第7章で扱ったので、此処では描画の為のデータとしてメッシュを見ます。

何故三角形なのか

リアルタイムレンダリングは殆ど全て三角形を使います。
理由は3つです：

• 必ず平ら。 3点は必ず1つの平面上に有るので、三角形には決まった1つの法線が有ります。4つの角が1つの平面上に無い四角形（非平面の四角形）には1つの法線が無く、どう分割するかで描かれ方が変わります。
• 必ず凸で単純。 エッジ関数と重心座標による補間（第6章 6.9節）は、特別な場合分け無しに全ての三角形で使えます。
• 他の多角形は全て三角形に分割出来る。 $n$頂点の凸多角形は$n-2$個の三角形に分割出来ます（1つの頂点からの扇形）。単純多角形なら何でも三角形分割出来ます。

モデリングツールでは今でも四角形やn角形で作業出来ます（編集し易く、9.2節の細分割にも向いています）が、書き出しや描画の時に三角形分割します。

インデックス付きメッシュ：頂点バッファとインデックスバッファ

メッシュを保存する素朴な方法は三角形のリストで、各三角形の3つの角の位置を其の儘書き出します。
此れをポリゴンスープと言います。
しかし閉じたメッシュでは1つの頂点を約6個の三角形が共有するので、殆どのデータを6回ずつ保存する事になります。
インデックス付きメッシュは、各頂点を頂点バッファに1回だけ保存し、三角形をインデックスバッファの頂点番号の3つ組で表します：

此処での「頂点」は位置だけではなく、GPUが角ごとに必要とする全てを指します。
典型的には位置（float 3個、12バイト）、法線（12バイト）、テクスチャ座標（float 2個、8バイト）で、1頂点32バイトです。
左の図の三角形は全て角を反時計回りに並べているので、全て此方を向いています（巻き順が大事な理由は6.4節で説明しました）。

数値例。 100 × 100マスの地形で、各マスを2つの三角形に分けます：

• 頂点：$101\times 101=10201$個、三角形：$2\times 100\times 100=20000$個。
• ポリゴンスープ：$3\times 20000=60000$個の角が32バイトずつで$1920000$バイト。
• インデックス付き、32ビットのインデックス：頂点が$10201\times 32=326432$バイト、インデックスが$60000\times 4=240000$バイトで、合計$566432$バイト。スープの約29%です。
• インデックス付き、16ビットのインデックス：$10201\le 65535$なので使えます。インデックスは$120000$バイトになり、合計$446432$バイト、約23%です。

頂点の共有は仕事も減らします。
GPUは最近変換した頂点を小さなキャッシュに残すので、6個の三角形が共有する頂点も変換は1回で済む事が多いのです。
穴の無い閉じた三角形メッシュでは、第7章のオイラーの公式から$T\approx 2V$（球と同じ形のメッシュなら丁度$T=2V-4$）が得られます。
「1頂点あたり三角形約6個」は此処から来ています。
$3T$個の角を$V$個の頂点で割ると約6です。

トライアングルストリップとトライアングルファン

インデックスバッファでも繰り返しは多く、隣の三角形とは2頂点を共有しています。
トライアングルストリップは、新しい頂点が直前の2頂点と三角形を作る様に頂点を並べます。
$n$個の三角形に必要なインデックスは$3n$個ではなく$n+2$個だけです。
右の図では、6個のインデックス3, 0, 4, 1, 5, 2で4個の三角形が出来ます。
三角形$k$は頂点$v_k,v_{k+1},v_{k+2}$を使いますが、其の儘では1つおきに時計回りになってしまうので、$k$が奇数の時GPUは逆の順番で取ります。
此処では三角形3 0 4、4 0 1、4 1 5、5 1 2になり、全て反時計回りです。
トライアングルファンは1つの中心頂点を共有し、$(v_0,v_k,v_{k+1})$で三角形を作ります。
凸多角形や円板に打って付けです。

100 × 100の地形では、マスの1行を1本のストリップにすると$2\times 100+2=202$個のインデックスが要り、100行で$20200$個、リストの$60000$個の3分の1です。
行同士は、特別なプリミティブリスタートのインデックス（又は面積0の「縮退」三角形）で1本の長いストリップに繋げられます。
今の実践では、インデックス付きの三角形リストが標準です。
頂点キャッシュが有ればほぼ同じ速さで、生成も処理も簡単だからです。
頂点バッファとインデックスバッファはOpenGLシリーズの第4章で自分で作ります。

面法線と頂点法線

面法線は1枚の平らな多角形の法線で、2本の辺の外積です（線型代数 第5章）。
全ての三角形を其の面法線で照らすと、メッシュは角張って見え、三角形が1枚ずつ見えます（フラットシェーディング、第10章）。
ポリゴン曲面を近似元の滑らかな曲面の様に見せるには、各頂点に頂点法線を持たせます。
其の頂点の周りの面の法線の平均で、レンダラーは其れを三角形の中で補間します（グーローシェーディングとフォンシェーディングは第10章で扱います）。
平均の取り方はよく使われる物が3つ有ります：

• 重み無し：各面法線を正規化して足し、和を正規化します。
• 面積重み付き：正規化していない外積を足します。其の長さは三角形の面積の2倍なので大きな面ほど強く効き、正規化も1回減ります。
• 角度重み付き：正規化した各面法線に、其の面の其の頂点での角度を掛けます。面を更に細かい三角形に分けても変わらないので、三角形分割の仕方に最も依存しません。

数値例。 頂点$V=(0,0,0)$がテーブルの天板の左の縁に有ります（此のシリーズの何時もの通りyが上です）。
三角形1は天板の一部で、$V$、$A=(2,0,0)$、$B=(0,0,-2)$です。
三角形2は左の側面の一部で、$V$、$B$、$D=(0,-1,-2)$です。

従って天板は$+y$を向き面積$\frac{4}{2}=2$、側面は$-x$を向き面積$\frac{2}{2}=1$です。
Vでの三角形1の角度は90°（$\frac{\pi }{2}\approx 1.5708$）、三角形2の角度は$(0,0,-2)$と$(0,-1,-2)$の間の角度で$\arccos \frac{4}{2\sqrt{5}}\approx 0.4636$ラジアン（26.6°）です。

3つの方法で3つの違う法線が出て、どれも「正解」ではありません。
此の頂点は鋭い縁の上に有り、其処では1本の法線では正しく表せないからです。
其処でハードエッジの話になります。

ハードエッジとスムージンググループ

平均を取るのは、本物の面が滑らかな所では正しく、テーブルや箱の縁の様な折れ目では間違いです。
解決法は頂点を分ける事です。
同じ位置を2回（又はもっと）保存し、各コピーに其の側の法線を持たせます。
レンダラーからは2つの別々の頂点に見え、照明にくっきりした縁、ハードエッジが出来ます。
モデリングツールでは辺をハード又はソフトに指定したり、面をスムージンググループに入れたりでき、法線は同じグループの面の間でだけ平均されます。

数値例：立方体。 立方体の角は8個ですが、各角は3枚の面に接し、法線が3種類有ります。
平らな面で描くには$8\times 3=24$個の頂点（1面に4個）と$6\times 2\times 3=36$個のインデックスが必要で、16ビットのインデックスなら$24\times 32+36\times 2=840$バイトです。
共有した8頂点だけなら$8\times 32+36\times 2=328$バイトで済みますが、平均した法線は角から斜めに外を向き、立方体はぼてっとした塊の様に陰影が付きます。
同じ分割はテクスチャの継ぎ目でも起きます。
テクスチャのUV展開が切り開かれている所では1つの頂点に2つの違うテクスチャ座標が要るので、2回保存されます。
其の為、実際のメッシュの頂点数は「角の位置の数」よりかなり多いのが普通です。

メッシュの品質

三角形を集めれば何でも良いメッシュになる訳ではありません。
知っておきたい問題：

• 非多様体の部分（3枚以上の面が共有する辺、1つの頂点だけで接する2つのソリッド）と穴は、3Dプリントから第7章の内外判定まで、閉じた面を前提にするアルゴリズムを壊します。
• 巻き順の不揃い：時計回りの三角形と反時計回りの三角形が混ざると、背面除去が間違った面を消し、法線が内側を向きます。
• T字接合（Tジャンクション）：頂点が別の三角形の辺の途中に乗っている状態です。丸め誤差で辺の両側が完全には一致しなくなり、ピクセル大のひび割れが出ます。
• 細長い三角形（スリバー）：とても細く長い三角形です。補間が悪く、陰影のアーティファクトを生み、シミュレーションにも向きません。メッシュ生成ツールは三角形を正三角形に近く保とうとします。
• 三角形が多過ぎる、又は少な過ぎる：細部は平らな所ではなく、曲がっている所に使うべきです。

詳細度（LOD）

1 km先の建物は数十ピクセルにしかなりません。
其処で10万個の三角形を全部描くのは無駄な仕事で、1ピクセルより小さい三角形はエイリアシングも酷くなります。
詳細度（LOD、level of detail）とは、モデルの版を幾つか持ち、距離又は画面上の大きさで選ぶ事です：

• 離散LOD：少数の版（例えば20,000、5,000、1,250、300三角形）をしきい値で切り替えます。切り替えはポッピングと呼ばれる突然の跳びとして見える事が有り、レンダラーは2つの版を一瞬混ぜる（クロスフェード）か、頂点を新しい位置へ滑らかに動かして（ジオモーフィング）隠します。
• 連続LOD：メッシュを少しずつ粗く又は細かく出来ます。例えばHoppeのプログレッシブメッシュ（1996年）で、目に見える跳びは有りません。地形レンダラーは場所ごとにも細かさを変え、カメラの近くは細かく、遠くは粗くします。

数値例。 半径$r=1$ mの球は、縦の視野角60°、高さ1080ピクセルの画面でどの位の大きさになるでしょうか？
距離$d$では見える高さが$2d\tan 30\mathrm{°}$で、球の直径は2なので、ピクセル単位の高さは

10 mで約187ピクセル、100 mで約18.7ピクセルです。
100 mでは球が覆うのは約$\pi \times {9.35}^2\approx 275$ピクセルなので、20,000三角形の版では1ピクセルあたり約73個の三角形になります。
明らかに300三角形のLODの出番です。
エンジンは正に此の画面上の大きさでLODを選び、物体のバウンディングスフィアが画面の高さの何割を占めるかで表す事が多いです。

メッシュの簡略化

粗い版は何処から来るのでしょうか？
メッシュの簡略化は、形を保ちながら三角形の数を減らします：

• 頂点クラスタリング：モデルに格子を被せ、1つのセルの中の頂点を全て1つにまとめます。速くて頑丈ですが、形を考慮せず、位相が変わる事も有ります。
• 頂点除去：頂点を1つ取り除き、残った穴を三角形分割し直します。
• エッジ縮約（エッジコラプス）：辺の両端を1つの頂点に引き寄せます。閉じた三角形メッシュの内部では、1回の縮約で頂点1個、辺3本、三角形2個が減ります（辺を共有していた2つの三角形が消え、辺が2組ずつ1本にまとまります）。従って$V-E+F$は変わりません。20,000三角形から5,000三角形にするには$\frac{20000-5000}{2}=7500$回の縮約が必要です。

腕の見せ所は、次にどの辺を縮約し、新しい頂点を何処に置くかの選び方です。
標準的な答えはGarlandとHeckbertの二次誤差尺度（QEM、1997年）で、新しい頂点が元の面の平面からどれだけ離れるかを測ります。
導出は此のシリーズの第2部で行います。
縮約を順番に記録し、其の逆操作（頂点分割）も持てば、前の節のプログレッシブメッシュ其の物になります。

メッシュのファイル形式

知っておきたい形式は4つで、目的が其々違います：

小さなOBJファイルの例として、2つの三角形で出来た単位正方形を示します（OBJは頂点を1から数える事に注意）：

# square.obj
v 0 0 0
v 1 0 0
v 1 1 0
v 0 1 0
vn 0 0 1
f 1//1 2//1 3//1
f 1//1 3//1 4//1

面の角は位置/テクスチャ座標/法線と書き、真ん中が空なら「テクスチャ座標無し」の意味です。
STLのバイナリの構造は単純なので、ファイルサイズを手で計算出来ます。
80バイトのヘッダー、4バイトの三角形の数、其の後に三角形1個あたり50バイト（法線と3つの角のfloat 12個で48バイト、と2バイトの属性欄）です。
20,000三角形の地形は$80+4+50\times 20000=1000084$バイトで、ポリゴンスープとほぼ同じ大きさです。
STLは正にポリゴンスープだからです。
glTF 2.0はKhronosが2017年に公開し、2022年に国際規格ISO/IEC 12113になりました。
此の節の頂点バッファとインデックスバッファを、GPUに其の儘送れる形で保存します。
glTFファイルはOpenGLシリーズの第13章で自分で読み込みます。

コード：面積重み付きの頂点法線

線型代数シリーズのlinalg.hhヘッダーを使うと、面積重み付きの法線はループ1つです。
各三角形の正規化していない外積を其の3頂点に足し、最後に正規化します。

#include <cstdio>
#include <vector>
#include "linalg.hh"

// Area-weighted vertex normals: add each triangle's unnormalized face normal
// (its length is twice the triangle's area) to its three vertices, then normalize.
std::vector<Vec3> vertexNormals(const std::vector<Vec3> &pos, const std::vector<unsigned> &idx) {
  std::vector<Vec3> n(pos.size(), Vec3{0, 0, 0});
  for (size_t t = 0; t + 2 < idx.size(); t += 3) {
    unsigned a = idx[t], b = idx[t + 1], c = idx[t + 2];
    Vec3 fn = cross(pos[b] - pos[a], pos[c] - pos[a]);
    n[a] = n[a] + fn;
    n[b] = n[b] + fn;
    n[c] = n[c] + fn;
  }
  for (Vec3 &v : n) v = normalize(v);
  return n;
}

int main() {
  // the table edge of section 9.1: V, A, B on the top, D on the side
  std::vector<Vec3> pos = {{0, 0, 0}, {2, 0, 0}, {0, 0, -2}, {0, -1, -2}};
  std::vector<unsigned> idx = {0, 1, 2, 0, 2, 3};
  std::vector<Vec3> n = vertexNormals(pos, idx);
  printf("normal at V: (%.3f, %.3f, %.3f)\n", n[0].x, n[0].y, n[0].z);
  return 0;
}

normal at V: (-0.447, 0.894, 0.000)

結果は表の面積重み付きの行と一致します。
此れらの法線はモデリング座標系での物なので、非均等な拡大縮小の後は第5章 5.4節の通り逆転置行列で変換しなければならない事を忘れないで下さい。

9.2 細分割曲面

考え方

第8章では制御点の長方形の格子から滑らかな曲面を作りましたが、キャラクターの頭は長方形ではありません。
パッチを縫い合わせる必要が有り、継ぎ目を滑らかに保つのは大変です。
細分割曲面は代わりに、どんな形や位相でも良い普通の粗いポリゴンメッシュ、制御メッシュ（ケージ）から出発し、決まった規則で何度も細かくします。
各段階で新しい頂点を加え、古い頂点を少し動かし、メッシュは滑らかな極限曲面に収束します。
方式は2つの系統に分かれます：

• 近似型：古い頂点が動き、極限曲面は制御メッシュの頂点を通りません（カトマル・クラーク法、ループ法、ドー・サビン法）。
• 補間型：古い頂点は其の儘で、曲面は其れらを通ります（例：バタフライ法）。

カトマル・クラーク法

カトマル・クラーク法（Catmull–Clark、1978年）は映画とモデリングツールの標準です。
どんなポリゴンメッシュにも使え、1回の後には全ての面が四角形になります。
1回の細分割で3種類の新しい点を計算します：

1. 各面の面点（フェースポイント）：其の面の頂点の平均。
2. 各辺の辺点（エッジポイント）：辺の2つの端点と、隣接する2つの面の面点の平均。
3. 古い各頂点$𝐏$の頂点点（バーテックスポイント）：其処に集まる辺の数、価数を$n$として、古い頂点は次の位置に動きます。

$𝐅$は$𝐏$の周りの$n$枚の面の面点の平均、$𝐑$は$𝐏$の周りの$n$本の辺の中点の平均です。
其の後、$k$角形の古い面を$k$枚の四角形で置き換えます。
各四角形は、動かした頂点1つ、其の隣の辺点2つ、面点1つで出来ています。

数値例：立方体（角は$(\pm 1,\pm 1,\pm 1)$）。

• 面$x=1$の面点：4つの角の平均は$(1,0,0)$です。6つの面点は$(\pm 1,0,0)$、$(0,\pm 1,0)$、$(0,0,\pm 1)$です。
• $(1,1,1)$から$(1,1,-1)$への辺の辺点：此の辺の面は$x=1$と$y=1$で、面点は$(1,0,0)$と$(0,1,0)$なので、辺点は$\frac{(1,1,1)+(1,1,-1)+(1,0,0)+(0,1,0)}{4}=\frac{(3,3,0)}{4}=(0.75,0.75,0)$です。
• $𝐏=(1,1,1)$（価数$n=3$）の頂点点：$𝐅=\frac{(1,0,0)+(0,1,0)+(0,0,1)}{3}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$。3本の辺の中点は$(0,1,1)$、$(1,0,1)$、$(1,1,0)$なので$𝐑=(\frac{2}{3},\frac{2}{3},\frac{2}{3})$。$n-3=0$なので古い位置は消えます：

角は中心からの距離$\sqrt{3}\approx 1.73$から約$0.96$へと強く引き込まれ、面点は距離1の儘です。
立方体は丸くなる途中です。

各段階の後の数：頂点8、辺12、面6は、頂点$8+12+6=26$、辺48、四角形24になり、次に98、192、96、更に386、768、384になります。
オイラーの公式は全ての段階で成り立ち（$26-48+24=2$）、面の数は1段階ごとに4倍になるので、細分割は数段階しか行いません。

特異頂点

規則正しい四角形の格子では全ての頂点の価数が4で、其処ではカトマル・クラーク法は第8章の一様な双3次Bスプライン曲面を正確に再現します。
極限は曲率まで連続（$C^2$）な滑らかな曲面です。
それ以外の価数の頂点は特異頂点（エクストラオーディナリー頂点）と呼ばれ、立方体の8つの角は価数3です。
辺点の価数は常に4で、面点の価数は其の面の辺の数になるので、制御メッシュの三角形や五角形は最初の1回で特異頂点を1つずつ増やします。
其れ以降は全ての面が四角形で、新しい頂点は全て価数4なので、特異頂点の数は変わりません。
特異頂点はどんどん孤立していき、其処では極限曲面は接平面までの連続（$C^1$）になります。
其の為、モデラーは特異頂点が少なく、害の無い場所に置かれた「全て四角形」の制御メッシュを好みます。

境界とクリース

境界の辺（面が1枚しか無い辺）では辺点は単に辺の中点で、境界の頂点は2つの境界上の隣だけを使って$\frac{1}{8}{𝐏}_{\text{prev}}+\frac{6}{8}𝐏+\frac{1}{8}{𝐏}_{\text{next}}$に動きます。
境界は3次Bスプライン曲線になります。
同じ規則をメッシュ内部のクリースとして指定した辺に使うと、デザイナーが望む場所に鋭い縁が出来ます。
Pixarのセミシャープクリースは最初の数段階だけ鋭い規則を使い、遠くからは鋭く、近くではわずかに丸い縁を作ります。

ループ法

ループ法（Charles Loop、1987年）は三角形版です。
全ての辺に新しい頂点を入れて、各三角形を4つに分けます：

• 辺の（奇数）頂点：$𝐚$から$𝐛$への辺で、其の2つの三角形の向かいの頂点が$𝐜$と$𝐝$なら、新しい頂点は$\frac{3}{8}(𝐚+𝐛)+\frac{1}{8}(𝐜+𝐝)$です。
• 古い（偶数）頂点：価数$n$で隣が${𝐪}_1\dots {𝐪}_n$なら、$𝐏\prime =(1-n\beta )𝐏+\beta \sum {𝐪}_i$です。Loopの元の式は$\beta =\frac{1}{n}\left(\frac{5}{8}-{\left(\frac{3}{8}+\frac{1}{4}\cos \frac{2\pi }{n}\right)}^2\right)$で、よく使われる簡単な選択（Warrenの物）は$n>3$で$\beta =\frac{3}{8n}$、$n=3$で$\frac{3}{16}$です。

規則正しい価数6では、どちらも$\beta =\frac{1}{16}$です。
Loopの式では$\frac{1}{6}\left(\frac{5}{8}-{\left(\frac{3}{8}+\frac{1}{8}\right)}^2\right)=\frac{1}{6}\cdot \frac{3}{8}=\frac{1}{16}$、もう一方は$\frac{3}{8\cdot 6}=\frac{1}{16}$です。

数値例。 尖った頂点$𝐏=(0,0,1)$の周りに、平面$z=0$上の単位円に6つの隣が有るとします（其の和は$(0,0,0)$）。
すると$𝐏\prime =(1-\frac{6}{16})(0,0,1)+\frac{1}{16}(0,0,0)=(0,0,0.625)$で、尖りが均されます。
又、$𝐚=(0,0,0)$から$𝐛=(2,0,0)$への辺で向かいの頂点が$𝐜=(1,2,0)$と$𝐝=(1,-2,1)$なら、新しい頂点は$\frac{3}{8}(2,0,0)+\frac{1}{8}(2,0,1)=(1,0,0.125)$です。
三角形メッシュの規則正しい頂点は価数6で、他の価数は特異頂点です。
極限はカトマル・クラーク法と同じく、特異頂点（$C^1$）以外では$C^2$です。

ドー・サビン法など

ドー・サビン法（Doo–Sabin、カトマル・クラーク法と同じ1978年）は「双対」の方式です。
各面の各頂点について其の面の中に新しい点を作り（最も簡単な形では、其の頂点、隣の2つの辺の中点、面点の平均。四角形なら其の頂点に$\frac{9}{16}$、両隣に$\frac{3}{16}$ずつ、向かいの角に$\frac{1}{16}$の重みになり、DooとSabinの重みと丁度一致します）、古い面、古い辺、古い頂点の其々から新しい面を作ります。
規則正しい格子では双2次Bスプラインになります（$C^1$まで）。
バタフライ法は最もよく知られた補間型の方式です。
古い頂点は動かず、新しい辺の頂点は蝶の形に並んだ8つの近傍から計算します。

実際には

Pixarの短編映画『ゲーリーじいさんのチェス』（Geri's Game、1997年）は、Pixarがキャラクターに細分割曲面を使った最初の作品で、Pixarは其の実装を2012年にオープンソースのライブラリOpenSubdivとして公開しました。
今では殆どのモデリングツールに組み込まれています（例えばBlenderのサブディビジョンサーフェスモディファイアはカトマル・クラーク法です）。
アーティストはローポリの制御メッシュを作り、細分割はソフトに任せます。
ゲームでは普通オフラインで細分割し、結果をLOD付きの普通のメッシュとして出荷するか、GPUのテッセレーションを使います。
テッセレーションはGLSLシリーズの第15章で少し触れます。

9.3 ボリュームを用いた形状表現

メッシュが表すのは表面だけです。
医用スキャン、スカルプト、流体、掘れるゲームの世界では、何処でも中身が何かを知る必要が有ります。

ボクセル

ボクセル（「体積要素」、volume element）はピクセルの3次元版で、規則正しい3次元格子の小さな立方体に値を1つ持たせた物です。
ソリッドが占めるボクセルに印を付けて保存する方法が、第7章で紹介したボクセル表現（空間占有列挙）です。
ボクセルでは幾つかの事が簡単になります。
内外判定は配列を1回引くだけで、CSG演算（和・積・差）はボクセルごとのOR、AND、AND NOTです。
代償はメモリで、解像度の3乗で増えます：

• ${512}^3=134217728$個のボクセル。
• 1個1ビット（内か外か）：$\frac{134217728}{8}=16777216$バイト = 16 MiB。
• 1個1バイト：128 MiB。CTデータの様に1個16ビット：256 MiB。
• 解像度を2倍の${1024}^3$にすると全て8倍になり、16ビットの格子で2 GiBです。

又、格子が非常に細かくないとボクセルモデルはカクカクします。
ボクセルの格子は標本化された画像なので、第2章のエイリアシングが全て起こります。

八分木

典型的な物体のボクセルの殆どは、深く内側か遠く外側に有ります。
同じ「充満」や「空」のセルを何百万個も保存するのは無駄です。
八分木（オクトツリー）は空間を適応的に保存します。
全体を囲む1つの立方体（根）から始め、各立方体を次の様に分類します：

• 充満（全体が物体の内側）：葉にします。
• 空（全体が外側）：葉にします。
• 部分的（境界上）：8つの同じ大きさの子立方体（各軸を半分）に分け、其れらを分類します。

最大の深さまで続け、其処で残った部分的な立方体は充満か空として扱います（又はボクセルの様に値を持たせます）。
2次元版は1つの正方形を4つの子に分ける四分木です。

数値例。 空間は立方体$[0,8{)}^3$、物体は箱$[2,8{)}^3$（片隅の$6\times 6\times 6$の箱）、最大の深さは3（単位ボクセル）です。

• 深さ0：根は部分的なので、大きさ4の8つの立方体に分けます。
• 深さ1：立方体$[4,8{)}^3$は完全に内側なので充満の葉1つです。他の7つの立方体は全て箱と一部だけ重なります（どれも少なくとも1つの軸が$[0,4)$に有り、其処で箱が覆うのは$[2,4)$だけです）。従って7つ全てを大きさ2の立方体に分けます。
• 深さ2：其の7つの立方体の其々で、$[0,4)$に有った全ての軸で$[2,4)$に入っている子が内側です。そういう軸が1つの立方体は充満4つと空4つ、2つなら充満2つと空6つ、3つ全て（立方体$[0,4{)}^3$）なら充満1つと空7つの子を持ちます。此れらの立方体は3個、3個、1個なので、充満の葉は$3\times 4+3\times 2+1=19$個、空の葉は$3\times 4+3\times 6+7=37$個です。全て決まったので深さ3には届きません。

合計：ノードは$1+8+56=65$個、其のうち葉は57個（充満20、空37）です。
体積の確認：$1\times 4^3+19\times 2^3=64+152=216=6^3$。
同じ解像度の普通のボクセル格子は$8^3=512$セルです。

右半分は、曲がった形で八分木が得をする理由を示しています。
深さ5（$32\times 32$の格子、1,024セルと同じ解像度）の円板の四分木はノード325個で、小さなセルは境界沿いにだけ集まります。
一般に八分木のノード数は物体の表面積に比例して、大体解像度の2乗で増え、ボクセル格子は3乗で増えます。
八分木（と其の仲間の疎なボクセル構造やバウンディングボリューム階層）は空間内の探索の高速化にも使われます。
レイトレーシング、衝突判定、第6章の視錐台カリングです。

CTとMRIのボリュームデータ

実際のボリュームデータの最大の源は医療です。
CTスキャナー（X線コンピュータ断層撮影）は、各小体積がX線をどれだけ強く吸収するかを1枚ずつ測り、値はハンスフィールド単位（空気は約−1000、水は0、骨は数百以上）です。
典型的な1枚は$512\times 512$の標本で、16ビット整数で保存されます。
MRI（磁気共鳴画像法）は水素原子核からの信号を測り、軟部組織がよく見えます。
何百枚もの断面を積み重ねると、スカラー値の3次元格子、正にボクセルの意味でのボリュームになります。
断面の間隔は断面内の標本の間隔より大きい事が多いです（異方性のボクセル）。
科学や工学のシミュレーションも、3次元格子上の温度、密度、圧力という同じ種類のデータを作ります。
こういう格子にはまだ面が有りません。
メッシュを得るには、値がしきい値を横切る面、等値面を抽出します。

マーチングスクエア法：2次元の等値線

2次元版が一番追い易いので、最後まで計算してみましょう。
標本$f(x,y)$の格子としきい値$c$が与えられ、曲線$f=c$（地図の等高線の様な等値線）を求めます。
マーチングスクエア法は正方形のセルを1つずつ処理します：

1. 各角に内側（$f>c$）か外側（$f\le c$）かの印を付けます。
2. 4つの印をまとめて4ビットのケース番号にします。左下 = 1、右下 = 2、右上 = 4、左上 = 8です。
3. ケースを表で引き、曲線がどの辺を横切り、どう繋ぐかを調べます。
4. 交点を其の辺の上に線型補間で置きます。値$f_0$の${𝐩}_0$から値$f_1$の${𝐩}_1$への辺では、次の通りです。

ケースは$2^4=16$通りです：

数値例。 4 × 4の標本の格子で、しきい値は$c=5$です（行は上の$y=3$から下の$y=0$の順）：

内側の標本は真ん中の4つ、9、7、7、6です。
左下の角が$(0,0)$のセルは右上の角$(1,1)$だけが内側なのでケース4、真ん中のセルは4つの角が全て内側なのでケース15（曲線無し）です。
周りを順に見ると、下の行が4、12、8、真ん中の行が6、15、9、上の行が2、3、1です。
内側と外側の標本を結ぶ辺には全て交点が出来ます：

各セルが2つの交点を繋ぎ、8本の線分が1本の閉じた曲線になります：

$(2.25,1)$が標本6から4分の1しか離れていない事に注目して下さい。
6は5を僅かに上回るだけだからです。
補間は、常に辺の中点に置くのではなく、値が示す場所に曲線を置きます。
此れが結果を滑らかにします。

曖昧なケース。 ケース5と10では2つの内側の角が対角に有り、4つの交点の繋ぎ方が2通り有ります。
2つの別々の角の欠片か、セルを横切る1本の帯かです。
角の値だけでは決められません。
簡単な規則は、4つの角の平均をセルの中心の値の推定として見て、其れが$c$より大きければ内側の角同士を繋ぐ事です。
角が左下6、右下2、右上7、左上1で$c=5$のセルは、ケースが$1+4=5$で、中心の推定はなので、2つの内側の角は別々の儘です。
一番大事なのは、隣り合うセルが同じ様に決める事です。
そうすれば曲線に隙間が出来ません。

#include <cstdio>

// Marching squares on a 4 x 4 grid of samples, iso value c.
// Corner bits: 1 bottom-left, 2 bottom-right, 4 top-right, 8 top-left (set when f > c).
const int N = 4;
const float f[N][N] = { // f[y][x], y = 0 is the bottom row
    {1, 3, 2, 0},
    {3, 7, 6, 2},
    {1, 9, 7, 3},
    {1, 1, 3, 2}};

struct P2 {
  float x, y;
};

// point on the segment from p0 (value v0) to p1 (value v1) where the value is c
P2 crossing(P2 p0, float v0, P2 p1, float v1, float c) {
  float t = (c - v0) / (v1 - v0);
  return {p0.x + t * (p1.x - p0.x), p0.y + t * (p1.y - p0.y)};
}

int main() {
  const float c = 5;
  // which edges each case connects: b(ottom) r(ight) t(op) l(eft); 5 and 10 are the saddles
  const char *table[16] = {"",   "lb", "br",    "lr", "tr", "lb tr", "bt", "lt",
                           "lt", "bt", "br lt", "tr", "lr", "br",    "lb", ""};
  for (int y = 0; y + 1 < N; ++y) {
    for (int x = 0; x + 1 < N; ++x) {
      float bl = f[y][x], br = f[y][x + 1], tr = f[y + 1][x + 1], tl = f[y + 1][x];
      int caseIndex = (bl > c) | (br > c) << 1 | (tr > c) << 2 | (tl > c) << 3;
      // a real implementation would test the cell center for cases 5 and 10 here
      P2 pbl{float(x), float(y)}, pbr{x + 1.0f, float(y)};
      P2 ptr{x + 1.0f, y + 1.0f}, ptl{float(x), y + 1.0f};
      auto edgePoint = [&](char e) {
        switch (e) {
        case 'b': return crossing(pbl, bl, pbr, br, c);
        case 'r': return crossing(pbr, br, ptr, tr, c);
        case 't': return crossing(ptl, tl, ptr, tr, c);
        default: return crossing(pbl, bl, ptl, tl, c);
        }
      };
      printf("cell (%d, %d) case %2d:", x, y, caseIndex);
      for (const char *s = table[caseIndex]; *s; s += (s[2] ? 3 : 2)) {
        P2 a = edgePoint(s[0]), b = edgePoint(s[1]);
        printf("  (%g, %g)-(%g, %g)", a.x, a.y, b.x, b.y);
      }
      printf("\n");
    }
  }
  return 0;
}

cell (0, 0) case  4:  (0.5, 1)-(1, 0.5)
cell (1, 0) case 12:  (1, 0.5)-(2, 0.75)
cell (2, 0) case  8:  (2, 0.75)-(2.25, 1)
cell (0, 1) case  6:  (0.5, 1)-(0.5, 2)
cell (1, 1) case 15:
cell (2, 1) case  9:  (2.25, 1)-(2.5, 2)
cell (0, 2) case  2:  (0.5, 2)-(1, 2.5)
cell (1, 2) case  3:  (1, 2.5)-(2, 2.5)
cell (2, 2) case  1:  (2, 2.5)-(2.5, 2)

マーチングキューブ法

マーチングキューブ法（LorensenとCline、1987年）は同じ考え方の3次元版で、グラフィックスで最もよく引用される論文の1つです：

• 入力：スカラー値の3次元格子（ボリューム）としきい値。
• 立方体ごと：8つの角が内側か外側かで8ビットのケース番号になり、$2^8=256$通りです。
• 表：各ケースについて、角が立方体の辺の上に有る三角形のリストを予め用意します（1つの立方体で最大5個）。回転と内外の入れ替えを使うと、256通りは15の基本パターン（空のパターンを含む）にまとまります。
• 補間：三角形の各角を、2次元と同じ線型補間で辺の上に置きます。
• 出力：等値面を近似する三角形メッシュ。

頂点法線は殆どただで手に入ります。
場の勾配$\mathrm{\nabla }f$は等値面に垂直で、格子上では中心差分、例えば$\frac{\mathrm{\partial }f}{\mathrm{\partial }x}\approx \frac{f(x+1,y,z)-f(x-1,y,z)}{2}$で推定します。
法線は勾配を正規化した物で$f$が増える向きを指すので、「内側 = 大きな値」なら外向きの法線は勾配の符号を反転した物です。

3次元の曖昧さ。 内側の角が対角に有る立方体の面は、マーチングスクエア法のケース5と全く同じ様に曖昧です。
元の15パターンの表では、其の面を共有する2つの立方体が違う選択をする事が有り、面に穴が開きます。
対策としては、曖昧な面を漸近的判定法（単なる平均ではなく、双線型補間の鞍点の値を調べる）で決める方法、ケースを増やした表（Marching Cubes 33）、各立方体を四面体に分ける方法（マーチングテトラヘドラ法、曖昧な面が無い）が有ります。
もう1つの実際的な問題は大きさです。
細かいCTボリュームからは簡単に何百万個もの小さな三角形が出来るので、普通は後で簡略化（9.1節）します。

ボリュームレンダリング

ボリュームを見せる方法は面の抽出だけではありません。
ボリュームレンダリング（直接ボリュームレンダリング）はメッシュを作りません。
各ピクセルについてレイをボリュームの中に進め、各標本を伝達関数で色と不透明度に変換し、其れらを積み重ねます。
複数の組織を同時に半透明で見せられ、此れは等値面には出来ない事です。
第16章（可視化）と此のシリーズの第2部で再び扱います。

9.4 陰関数曲面

定義と内外判定

曲面は関数の零点の集合としても表せます：

此れが陰関数曲面です。
第8章のパラメトリック曲面はパラメータから点を作ります（$𝐩(u,v)$）。
其方は描くのもテクスチャを貼るのも簡単ですが、「此の点は内側か？」に答えるのは大変です。
陰関数曲面は其の逆で、点を列挙するのは簡単ではありませんが、内外判定は1回の評価です。
此処ではが内側、$f>0$が外側という約束を使います（逆の符号を使う本も有るので、読む時は定義を確認して下さい）。

数値例。 原点の周りの半径3の球：$f(x,y,z)=x^2+y^2+z^2-9$。

• $(1,1,1)$：、内側。
• $(1,2,2)$：$1+4+4-9=0$、面上。
• $(3,3,0)$：$9+9+0-9=9>0$、外側。

面上の点の法線は、此処でも勾配です。
$\mathrm{\nabla }f=(2x,2y,2z)$は$(1,2,2)$で$(2,4,4)$、正規化すると$(\frac{1}{3},\frac{2}{3},\frac{2}{3})$で、当然球から真っ直ぐ外を向きます。
陰関数曲面を描くには、$f$を格子上で標本化してマーチングキューブ法を使う（ポリゴン化）か、レイを飛ばして各レイ上で$f=0$の根を探します（第12章）。

メタボール

陰関数曲面は柔らかく有機的な、ぷよぷよした形で輝きます。
各「玉」$i$に中心${𝐜}_i$と、中心の近くで強く半径$R$で0に落ちる場を与え、全ての玉の場を足し、和がしきい値$T$に等しい所を面とします：

$g$は例えば、で$g(r)={\left(1-\frac{r^2}{R^2}\right)}^2$、其の外では$g(r)=0$です。
（此処では大きい値が内側なので、上の意味での陰関数は$T-F$です。）
Blinnは此の考え方を「blobby」な物体と呼び（1982年）、メタボールという名前は日本の西村らによる物で（1985年）、Wyvillらは「soft objects」と呼びました（1986年）。
違いは減衰関数$g$です。

数値例（$R=2$、$T=0.5$）。
玉が1つだけなら面は$g(r)=0.5$の所で、$1-\frac{r^2}{4}=\sqrt{0.5}\approx 0.7071$より$r^2\approx 1.1716$、$r_0\approx 1.082$です。
次に2つの玉を$x=\pm 1.2$に置きます。
1つずつの球（半径1.082で$x=\pm 0.118$まで）は触れてさえいません。
中点では各中心までの距離が1.2なので、$g(1.2)=(1-\frac{1.44}{4}{)}^2={0.64}^2=0.4096$、和は$0.8192>0.5$です。
中点は内側で、2つの玉は滑らかな首で繋がっています。
代わりに$x=\pm 1.5$なら、$g(1.5)=(1-\frac{2.25}{4}{)}^2={0.4375}^2\approx 0.1914$、和はで、離れた儘です。

黄色の曲線は、場の値の細かい格子に上のマーチングスクエア法のコードを使って計算した物で、破線の円は玉1つの時の面です。
此れがメタボールの魅力の全てです。
融合は自動的に起こり、中心を動かすと特別な処理無しに位相が変わります（塊1つか2つか）。
液体、粘土の様なキャラクター、細胞に打って付けです。

minとmaxによるCSG

CSG（第7章）の集合演算は、「内側が負」の約束の陰関数では1行になります：

点が和集合に入るのはどちらかの形の内側の時（小さい方の値が負）、積集合に入るのは両方の内側の時（大きい方の値が負）、差集合に入るのはAの内側でBの外側の時です。

数値例。 原点の半径3の球Aと、$(4,0,0)$の半径2の球Bを距離で書きます：$f_A=\Vert 𝐩\Vert -3$、$f_B=\Vert 𝐩-(4,0,0)\Vert -2$。

点$(2.5,0,0)$は両方の球の中に有るので、差では削り取られます。
シェーダーでは同じ事が数行です：

float sdSphere(float3 p, float3 center, float radius) {
  return length(p - center) - radius;
}

float csgUnion(float a, float b) { return min(a, b); }
float csgIntersect(float a, float b) { return max(a, b); }
float csgSubtract(float a, float b) { return max(a, -b); }

float sdSphere(vec3 p, vec3 center, float radius) {
  return length(p - center) - radius;
}

float csgUnion(float a, float b) { return min(a, b); }
float csgIntersect(float a, float b) { return max(a, b); }
float csgSubtract(float a, float b) { return max(a, -b); }

float sdSphere(float3 p, float3 center, float radius) {
  return length(p - center) - radius;
}

float csgUnion(float a, float b) { return min(a, b); }
float csgIntersect(float a, float b) { return max(a, b); }
float csgSubtract(float a, float b) { return max(a, -b); }

minとmaxは形が出会う所に鋭い折れ目を作ります。
其れを「滑らかなmin」に置き換えると、メタボールの様に融合します。

符号付き距離関数

上の球は特別な種類の陰関数を使っていました。
値が面までの実際の距離で、内側では負になる符号付き距離関数（SDF）です。
其の勾配の長さは（殆ど）何処でも1で、値はレイに沿って面を越えずに安全に進める距離を教えてくれます。
此れがスフィアトレーシング（レイマーチング）の基礎です。
2次元の距離関数はGLSLシリーズの第6章で見ましたし、同シリーズの第14章では其れで作った3次元のシーンをレイマーチングします。
SDFは此のシリーズの第2部でしっかり扱います。
2つのSDFのminとmaxでも内外は正しく出ますが、結果は距離の目安（上限や下限）に過ぎず、常に正確な距離とは限らない事に注意して下さい。

9.5 そのほかの形状表現

山、海岸線、植物、炎、煙の様に、メッシュやパッチでは殆どモデリング出来ない物も有ります。
此れらは普通、規則やランダムな過程で生成します。

フラクタル

フラクタル（Mandelbrotが1975年に作った言葉）は、どの縮尺でも細部が有る形で、典型的には自己相似性を持ちます。
小さな部分が全体と同じ様に見えるのです。
古典的な例はコッホ曲線（1904年）です。
線分を3等分し、真ん中の3分の1を正三角形の2辺で置き換え、新しい全ての線分で此れを永遠に繰り返します。

$n$回の後には長さ$3^{-n}$の線分が$N=4^n$本有るので、長さは$L={\left(\frac{4}{3}\right)}^n$です。
曲線は小さな範囲に収まっているのに、長さは際限無く増えます。
こういう曲線はどの位「大きい」のでしょうか？
1次元ではなく（無限に長い）、2次元でもありません（面積が無い）。
相似次元（フラクタル次元の1つの形）が其れに答えます。
形が自分自身を$r$倍に縮小した$N$個のコピーで出来ているなら、次の通りです。

普通の形で確かめましょう。
線分は1/2倍のコピー2個で$D=\frac{\log 2}{\log 2}=1$、正方形は1/2倍のコピー4個で$D=\frac{\log 4}{\log 2}=2$です。
コッホ曲線は1/3倍のコピー4個です：

約束通り、線と平面の間です。
本物の海岸線や山の稜線も或る範囲の縮尺で似た振る舞いをするので、フラクタルの手法は説得力の有る地形を作ります。
正確には自己相似でない形の次元はボックスカウント法で測ります。
形を大きさ$s$の箱で覆い、必要な箱の数を数え、$s$を小さくすると数がどう増えるかを見ます。

中点変位法による地形

実用的なフラクタルが中点変位法（Fournier、Fussell、Carpenter、1982年）です。
1次元では、真っ直ぐな線から始め、各段階で全ての線分の中点をランダムな量だけ上下に動かし、次の段階ではランダムの幅を小さくします（半分にすると自然な粗さになり、パラメータ$H$を使った係数$2^{-H}$で調整出来ます）。

数値例。 点は$x=0\dots 8$、両端は$h(0)=h(8)=0$、ランダムの幅は段階1から3で$d=2$、1、0.5です。
再現出来る様に「乱数」$r\in [-1,1]$を書いておきます：

最終的な形には段階1の大きな丘と段階3の小さなでこぼこが有り、どの縮尺でも同じ粗さです。
2次元の格子で同じ考え方を使うのがダイヤモンド・スクエア法で、高さマップ全体を作ります。
今の地形は、滑らかなノイズ関数を幾つかのオクターブで足し合わせる方法（非整数ブラウン運動）で作る事の方が多く、GLSLシリーズの第8章で試せます。

L-system

L-system（リンデンマイヤー・システム、1968年）は、生物学者Aristid Lindenmayerが植物の成長を記述する為に考えた文字列の書き換え系です。
公理（最初の文字列）と、全ての記号を同時に置き換える規則から成り、世代ごとに書き換えます。

数値例1（形無し）。 公理A、規則$\text{A}\to \text{AB}$と$\text{B}\to \text{A}$：
A → AB → ABA → ABAAB → ABAABABA。
長さ1、2、3、5、8はフィボナッチ数で、小さな規則が成長のパターンを生む事を示しています。

形を作るには、文字列を平面上を歩くタートルへの命令として読みます：

括弧が枝を作ります。
数値例2。 公理F、規則$\text{F}\to \text{F[+F]F[-F]F}$、$\delta =30\mathrm{°}$、歩幅1で、タートルは原点から上向き（90°）で始めます。
世代1の文字列はF[+F]F[−F]Fです。
タートルはFで$(0,1)$まで描き、状態を積み、120°に向きを変えて$(0+\cos 120\mathrm{°},1+\sin 120\mathrm{°})=(-0.5,1.866)$まで描き、取り出して$(0,1)$の90°に戻り、$(0,2)$まで描き、積み、60°に向きを変えて$(0.5,2.866)$まで描き、取り出し、$(0,3)$まで描きます。
3歩の幹に左と右の枝が1本ずつ付きました。
各世代で全てのFが11個の記号になるので、Fの数は$5^n$、文字列の長さは1、11、61、311、1561です（Fは11個の記号になり、他の記号は其の儘写されます）。

本格的な植物のモデルは、3次元の回転（ロールとピッチ）、規則のランダムな選択（確率的L-system）、長さや太さのパラメータ、葉や花を加えます。
映画やゲームの樹木や植生のツールは、此れらの考え方の上に作られています。

パーティクルシステム

炎、煙、爆発、火花、水しぶきには面が全く有りません。
Reeves（1983年）は其れらをパーティクルシステムとしてモデル化し、映画『スタートレックII カーンの逆襲』（1982年）の「ジェネシス」の場面で初めて使いました。
多数の小さな粒子の雲で、各粒子は位置、速度、色、透明度、大きさ、寿命を持ちます。
毎フレーム、新しい粒子が（平均値の周りにランダムなばらつきを持って）発生し、全ての粒子が速度と重力や風の様な力で動き、属性は年齢と共に変わり、寿命が尽きた粒子は消滅します。
形は何千もの単純でランダムな粒子の統計的な結果です。
ReevesとBlau（1985年）は此の考え方を草や木に広げ、各粒子の軌跡を葉や枝にしました。

簡単な計算です。
毎秒500個の粒子を作り、各粒子が2秒生きるエミッターは、常に約$500\times 2=1000$個の粒子が生きている状態に落ち着きます。
GPUでは何百万もの粒子をコンピュートシェーダーでシミュレーションし、普通はテクスチャを貼ったカメラを向く小さな四角形（ビルボード）として描きます。
粒子の動き（力、衝突）は物理ベースのアニメーション、第14章の範囲です。

点群とポイントベースレンダリング

3次元レーザースキャナーや（後で述べる）フォトグラメトリは点群を測ります。
面上の何百万もの点で、各点は位置と、多くの場合は色と法線を持ちますが、繋がりの情報は有りません。
メッシュに変換する（表面再構成、例えばポアソン表面再構成）事も、点を其の儘描く事も出来ます。
ポイントベースレンダリングは各点を法線の向きに置いた小さな円盤や楕円、スプラットとして描き、重なったスプラットが混ざって閉じた面の様に見えます。
点の描画は、どうせ点がピクセルより多い時（巨大なスキャン、遠くの細部）に自然です。
最近の3D Gaussian Splatting（2023年）は、写真に合わせた何百万もの半透明のガウス分布のスプラットでシーン全体を表します。
スキャナー其の物は第17章の範囲です。

プロシージャルモデリング

プロシージャルモデリング（手続き型モデリング）とは、全ての頂点を手で置く代わりに、形状を生成する規則やプログラムを書く事です。
フラクタル、L-system、パーティクルシステムは全て其の例で、他にもノイズによる地形、岩や雲の生成、建物の為のシェイプグラマーが有ります。
建物の正面を階に、階を窓と壁に、ランダムなパラメータ付きの規則で分けていき、数ページの規則から様々な建物の並ぶ街全体が出来ます（CityEngineというツールの元になったCGAシェイプグラマーがよく知られた例です）。
利点は少ないデータから得られる大きな多様性と変更のし易さ（規則を変えれば全ての建物が更新される）で、欠点はアーティストが思い描く通りの形にするのが直接モデリングするより難しい事です。
Houdiniの様なノードベースのツールやBlenderのジオメトリノードは、実践でのプロシージャルモデリングです。

イメージベーストモデリングとフォトグラメトリ

最後に、形状は写真からも作れます。
フォトグラメトリは物体を色々な位置から沢山撮影し、写真の間で対応する特徴を見つけ、カメラの位置と疎な点群を復元し（structure from motion）、其の後密な点群とテクスチャ付きのメッシュを作ります（多視点ステレオ）。
此のイメージベーストモデリングは、今の実在の場所や物のゲームや映画のアセットの多くの作り方です。
モデルを作らずに画像から直接描画するのは第12章のイメージベーストレンダリングで、3次元入力装置は第17章で扱います。

9.6 表現の選び方

どの表現にも得意な事と苦手な事が有ります：

実際には表現同士は常に変換されます。
CTボリュームはマーチングキューブ法でメッシュになり、細分割の制御メッシュは細分割でメッシュになり、点群は再構成でメッシュになり、メッシュは物理計算や大域照明の為にボクセルになります（ボクセル化）。

検定のポイント

• インデックス付きメッシュは各頂点を頂点バッファに1回だけ保存し、三角形をインデックスで表します。トライアングルストリップは$n$個の三角形に$n+2$個のインデックスで済みます。
• 頂点法線は面法線の平均（重み無し、面積又は角度で重み付け）です。ハードエッジは平均ではなく頂点の分割で作ります。
• LODは距離又は画面上の大きさで版を切り替え、目に見える跳びがポッピングです。エッジ縮約は頂点1個、辺3本、三角形2個を減らします。
• カトマル・クラーク法：入力はどんな多角形でも良く、出力は四角形。面点、辺点、頂点点$\frac{𝐅+2𝐑+(n-3)𝐏}{n}$。規則正しい価数は4。双3次Bスプラインの一般化。ループ法：三角形を4つに分ける。規則正しい価数は6。ドー・サビン法：双対の方式で双2次。3つとも近似型です。
• ボクセル = 空間占有列挙表現で、メモリは解像度の3乗で増えます。八分木は部分的な立方体を8つに分けます。
• マーチングキューブ法：入力はスカラー値のボリュームとしきい値、出力は三角形。256ケース、15の基本パターン、辺に沿った線型補間。曖昧な面で穴が開く事が有ります。
• 陰関数曲面$f(𝐩)=0$：符号で内外が分かります。メタボールは場を足してしきい値で切ります。CSGはminとmaxです。
• フラクタル（相似）次元$D=\frac{\log N}{\log (1/r)}$。コッホ曲線は$\frac{\log 4}{\log 3}\approx 1.26$です。
• L-systemは全ての記号を並列に書き換え、タートルが文字列を解釈し、括弧が枝を作ります。パーティクルシステム（Reeves、1983年）は炎や煙の様なぼんやりした現象をモデル化します。

9.7 まとめ

• ポリゴン曲面は平らな多角形で曲面を近似します。GPUが三角形を描くのは、三角形が必ず平らで凸だからです。
• インデックス付きメッシュ（頂点バッファ + インデックスバッファ）は共有する頂点を何度も保存しません。ストリップとファンはインデックスのリストを更に短くします。
• 滑らかなシェーディングの為に頂点法線を面法線から平均します。ハードエッジ、スムージンググループ、テクスチャの継ぎ目では頂点を分けます。
• LODはモデルの版を幾つか持ち画面上の大きさで選びます。エッジ縮約による簡略化で其れらを作ります。OBJ、PLY、STL、glTFは違う目的でメッシュを保存します。
• 細分割曲面は粗い制御メッシュを滑らかな極限へと細かくします。カトマル・クラーク法（四角形）、ループ法（三角形）、ドー・サビン法（双対）。特異頂点では$C^1$までです。
• ボクセルは3次元格子に値を保存し（メモリは解像度の3乗で増える）、八分木は必要な所だけを分けます。CTとMRIはボリュームデータを作ります。
• マーチングスクエア法とマーチングキューブ法は、ケースの表と線型補間で等値線と等値面を抽出します。曖昧なケースには一貫した規則が必要です。
• 陰関数曲面$f=0$は内外判定と融合を簡単にします。メタボールは場を足し、CSGはminとmaxを使い、符号付き距離関数はレイマーチングを可能にします。
• フラクタル、中点変位法、L-system、パーティクルシステム、点群、プロシージャルモデリング、フォトグラメトリは、手でモデリングするのが現実的でない形状を生成又は取得します。

9.8 用語

9.9 課題

1. ★ 256 × 256マスの地形を三角形に分けます。頂点と三角形は幾つですか？32バイトの頂点で、ポリゴンスープとインデックス付きメッシュのメモリを計算して下さい。インデックスは16ビットに出来ますか？其の理由も答えて下さい。
2. ★★ 四角錐の頂上が$(0,2,0)$、底面の角が$(\pm 1,0,\pm 1)$に有ります（三角形4枚と正方形1枚）。カトマル・クラーク法を1回適用し、角が$(0,2,0)$、$(1,0,1)$、$(-1,0,1)$の三角形の面点と、頂上（価数4）の新しい位置を計算して下さい。細分割したメッシュの頂点、辺、面の数は幾つで、オイラーの公式$V-E+F=2$は成り立ちますか？
3. ★★ $g(r)=(1-\frac{r^2}{4}{)}^2$（）、しきい値$T=0.5$の2つのメタボールがx軸上に距離$d$離れて有ります。どんな距離なら2つの中点が面の内側になりますか？次に中心が$\pm 1.2$の時、点$(0,0.9)$を調べて下さい。内側ですか？
4. ★★ 公理F、規則$\text{F}\to \text{F[+F][-F]F}$、$\delta =30\mathrm{°}$のL-systemについて、世代1を書き、世代2と3の文字列の長さとFの数を求め、世代1で最初のFの後にタートルが描く3本の線の終点を計算して下さい（原点から上向き、歩幅1）。
5. ★★★ コッホ雪片は、正三角形の3辺にコッホ曲線を付けた物です。周の長さは際限無く増えるのに面積は収束する事を示し、面積の極限が最初の三角形の面積の何倍かを求めて下さい。（ヒント：各段階で新しい小さな三角形が幾つ加わるかを数え、等比級数を足します。）

選択問題

問1 ★ 次のうち、マーチングキューブ法の説明として正しい物はどれか。

問2 ★ 次のうち、細分割曲面について正しい物はどれか。

問3 ★★ 全ての線分を、長さが其々1/4の8本の線分で置き換える事を繰り返して曲線を作る。極限の曲線の相似次元（フラクタル次元）はどれか。

9.10 実践課題

方眼紙に島の小さな等高線図を作り、其の途中でメッシュ、法線、マーチングスクエア法と其の曖昧なケース、LODを使います。
方眼紙（少なくとも20 × 20マス、格子の1歩を4マスにします）、定規、鉛筆、2色のペン、電卓を用意して下さい。

島は、間隔10 mの5 × 5の格子上の高さ（メートル）で与えられます。
$x$は右、$y$は紙の上向きで、高さ$h$が3つ目の軸の役をします（右手系：$x$が東、$y$が北、$h$が上）。
負の高さは水の下です。
行は上（$y=4$）から下（$y=0$）の順です：

1. メッシュ。 格子の各マスを2つの三角形にします。頂点、三角形、インデックスの数を数え、ポリゴンスープとインデックス付きメッシュ（32バイトの頂点、16ビットのインデックス）のメモリを計算して下さい。
2. 法線。 頂上$(2,2)$の頂点法線を中心差分で推定して下さい。$\frac{\mathrm{\partial }h}{\mathrm{\partial }x}\approx \frac{h(3,2)-h(1,2)}{2\cdot 10}$、$y$も同様にして、$𝐧\propto (-\frac{\mathrm{\partial }h}{\mathrm{\partial }x},-\frac{\mathrm{\partial }h}{\mathrm{\partial }y},1)$です。正規化し、斜面が水平から何度傾いているかを計算します。
3. 海岸線。 格子を描き、各点の横に高さを書いて下さい。しきい値$c=0$で陸と水の点に印を付け、16個のセルの其々にケース番号を書き、全ての交点を線型補間で計算します（小数点以下3桁）。
4. 曖昧なセル。 陸の角が対角に有るセルが1つ有ります。其れを見つけ、中心の平均で決め、1色目のペンで海岸線を描いて下さい。次に、もう一方を選んだ場合の線を鉛筆で描きます。其々の選び方で島は幾つになりますか？
5. 面積。 海岸線が囲む面積を座標の公式（靴紐公式）$A=\frac{1}{2}|{\sum }_i(x_i{y}_{i+1}-x_{i+1}{y}_i)|$（点はループに沿った順に並べ、最後の点の次は最初の点）で計算し、平方メートルに直して下さい。
6. 2本目の等高線。 2色目のペンで、10 mの等高線を同じ方法で描いて下さい。
7. 粗いLOD。 標本を1つおきにだけ残し（$x,y\in \{0,2,4\}$の3 × 3の格子）、此の粗い版の海岸線を描いて下さい。形と面積を手順5と比べると、どの細部が消えましたか？

自分で確認する方法：全ての交点は2つの格子点の間に有り、高さがしきい値に近い方の点の側に寄っています。
手順4の海岸線は16点の1本の閉じた曲線です。
10 mの等高線は完全に海岸線の内側に有ります。
手順2の法線は長さが1で、地面が下がっていく側に傾いています（地面は$+x$と$+y$の方へ下がるので、$x$と$y$の成分は正です）。
粗い海岸線が囲む面積は、細かい方より小さくなります。