This explanation is currently available in Japanese.
ひとことで
2 次元の格子の各点に数値を持たせ、数値がしきい値をまたぐ所を線でつないで、輪郭線を取り出す方法です。格子の四角形 1 つごとに、4 つの角が内側か外側かで 2⁴ = 16 通りのケースに分け、表から「どの辺からどの辺へ線を引くか」を決めます。マーチングキューブの 2 次元版で、仕組みを理解する入り口にもなります。
ゲームでの使いどころ
- 壊せる 2D 地形：『ワームス』のように、爆発で地面が丸くえぐれるゲーム。地形を「格子の値」で持ち、爆発の周りの値を下げて輪郭を作り直す。
- 当たり判定の輪郭：輪郭の線分をそのまま 2D 物理エンジンの当たり判定（エッジ・チェーン）に使う。
- 洞窟の自動生成：セルオートマトンで作ったマス目の洞窟を、なめらかな輪郭のメッシュに変える。
- 戦場の霧・領域表示：視界や陣地の範囲を値の場で持ち、その境界線をきれいな線で描く。等高線（地図の高さの線）もこの方法で引ける。
しくみ
格子点の値を 、しきい値を とします。
- ケース番号：四角形の 4 つの角について、 なら 1 とし、4 ビットの数（0〜15）にします。
- 辺の上の点：内側と外側の角を結ぶ辺の上に点を置きます。位置は両端の値から線形補間します。
- 線を引く：ケース番号で表を引き、辺の上の点どうしを線で結びます。ほとんどのケースは線 1 本、ケース 0 と 15 は線なしです。
- 塗り：内側の角と辺の上の点を順にたどれば、四角形の内側の部分の多角形が得られ、三角形に分けて塗れます。
あいまいなケース：対角の 2 つの角だけが内側のケース（5 と 10）は、「内側どうしをつなぐ」か「外側どうしをつなぐ」かの 2 通りの線の引き方があります。四角形の中心の値（4 つの角の平均）がしきい値より大きいかで決める方法がよく使われます。
実装のポイント
- 補間を忘れない：辺の中点に点を置くだけだと、輪郭が 45° の階段状になります。値の補間を入れると、同じ格子でもなめらかな曲線になります。
- 変更された所だけ作り直す：爆発で値を書き換えたら、その周りのマスだけ輪郭を作り直します。格子をチャンクに分けておくと管理しやすくなります。
- 掘るときは最小値で：爆発の円の距離場を作り、元の値との最小値（掘る）や最大値（盛る）を取ると、なめらかな縁の穴になります。
- 線分をつなぐ：物理エンジンに渡すときは、ばらばらの線分を端点でつないで長い折れ線（チェーン）にしておくと、当たり判定が安定し、処理も軽くなります。
つまずきやすい点
- 格子より細い形は消える：格子の間隔より細い橋や柱は、値の場に表れず、輪郭から消えてしまいます。
- あいまいなケースの不一致：隣り合うマスであいまいなケースの決め方がそろっていないと、輪郭が途切れたり交差したりします。
- 値の急な変化：値が 0/1 の 2 値だと補間が効かず、階段状になります。距離や密度のように、なめらかに変わる値を持たせます。
デモで試すこと
- 地形をドラッグして掘ると、緑の輪郭がすぐに作り直されます。上から落ちてくる青いボールが、掘った穴に転がり込むことを確かめてください。ボールは輪郭と同じ値の場を当たり判定に使っています。
- 「盛る」にしてドラッグすると、土を足して橋や壁を作れます。
- 「格子の細かさ」を小さくし、「格子点を表示」で、黄色の点（内側）と輪郭の関係を見てください。「辺の上で位置を補間する」を切ると、輪郭が階段状になります。
- 「16 通りのケース」で、すべてのケースの線の引き方と、あいまいなケース 5 と 10 を確かめられます。