衝突検出（ブロード/ナローフェーズ）

なぜ衝突検出を二段階に分けるのか

横にスクロール

n個の物体があるとき、素朴に「すべての組」を厳密に衝突判定すると組の数は n*(n-1)/2 で、計算量は O(n^2) です。物体が数千に増えるとこれだけで破綻します。しかも1組ごとの厳密判定（凸多面体同士の接触点計算など）は決して安くありません。そこで実用的な衝突検出は、粗く速い刈り込みと精密だが高価な判定を分業させます。前段がブロードフェーズ、後段がナローフェーズです。

ブロードフェーズは各物体を単純な包絡体（多くは軸並行境界ボックス＝AABB）で近似し、「明らかに当たりようがない組」を大量に捨てて、衝突の可能性がある組（潜在接触対）だけをナローフェーズへ渡します。ナローフェーズはその少数の組に対してのみ、実際の形状を使った厳密判定を行い、接触しているか、していれば接触点・接触法線・貫入深さを計算します。これらは後段の衝突応答（力積計算）が必要とする情報です。

ブロードフェーズ：AABBと掃引による刈り込み

AABB同士の交差判定は極めて安価で、各軸の区間が重なるかを見るだけです。3次元なら「x区間が重なり、かつy区間が重なり、かつz区間が重なる」ときのみ交差。1軸でも離れていれば即座に非交差と判定でき、分岐が早く抜けます。問題は「どの組のAABBを突き合わせるか」で、ここを総当たりにすると結局 O(n^2) に戻ってしまいます。

代表的な高速化が掃引と刈り込み（Sweep and Prune、SAP）です。各AABBの各軸方向の下端・上端を端点リストとして持ち、軸に沿ってソートしておきます。ソート済み端点を走査し、ある物体の区間が「開いている」間に開始する他物体だけが、その軸で重なり得る候補です。全軸で重なった組だけが潜在接触対になります。フレーム間で物体の移動が小さければ端点の順序はほとんど変わらないため、挿入ソートによる逐次更新がほぼ O(n) で効く（時間的コヒーレンス）のがSAPの強みです。

グリッドや境界体積階層（BVH）は空間そのものを分割・階層化して近傍だけを調べる別系統の刈り込みで、シーンの性質（物体サイズの均一性、分布の偏り）に応じてSAPと使い分けます。いずれも狙いは同じ——ナローフェーズに渡す組を実効的に O(n) 前後まで削ることです。空間分割の考え方はレンダリングの可視性判定とも共通し、グラフィックスの原理 で扱う空間データ構造と地続きです。

ナローフェーズ(1)：分離軸定理（SAT）

ここからは絞り込まれた組を厳密に判定します。凸形状に対する基本原理が分離軸定理（Separating Axis Theorem、SAT）です。定理はこう述べます——2つの凸集合が交差しないための必要十分条件は、両者を射影したとき区間が重ならないような分離軸が少なくとも1本存在すること。裏返せば、ありうる分離軸すべてに射影して1本でも隙間があれば非衝突、どの軸でも重なれば衝突です。

凸ポリトープ（多角形・多面体）では、調べるべき分離軸の候補が有限に絞れるのが要点です。2次元の凸多角形同士なら、候補軸は各辺の法線だけで十分。3次元の凸多面体同士なら、各面の法線に加えて、両者のエッジ方向の外積も候補に含める必要があります（面法線だけでは辺同士がずれて当たるケースを取りこぼす）。各候補軸に全頂点を射影して区間 [min, max] を作り、2区間が重なるかを調べます。

SAT（凸ポリトープ）の判定手順:

  1. 候補軸を列挙
       2D: A・B 各辺の法線
       3D: A・B 各面の法線 ＋ (Aの各エッジ)×(Bの各エッジ)
  2. 各候補軸 axis について:
       Aの全頂点を axis に射影 → 区間 [minA, maxA]
       Bの全頂点を axis に射影 → 区間 [minB, maxB]
       if maxA < minB or maxB < minA:
           分離軸を発見 → 非衝突を確定して即終了
  3. どの軸でも区間が重なった → 衝突
       各軸の重なり量(overlap)のうち最小の軸が最小貫入方向、
       その overlap が貫入深さ、押し戻し方向(MTV)になる

全軸で重なった場合、重なり量が最小の軸が最も浅い貫入方向を与え、その重なり量が貫入深さ、押し戻すべき方向（最小移動ベクトル＝MTV）になります。これが衝突応答へ渡す情報です。SATは実装が直截で凸ポリトープに強い一方、候補軸数は面数・エッジ数に依存し、球や円など滑らかな凸形状は面法線という離散的な軸を持たないため素直には扱えません。

ナローフェーズ(2)：GJK と EPA

GJK（Gilbert–Johnson–Keerthi）アルゴリズムは、任意の凸形状を統一的に扱えるより一般的な手法です。鍵はミンコフスキー差 A - B（Aの各点からBの各点を引いた差集合）という発想で、次の等価性が成り立ちます——AとBが交差する ⇔ ミンコフスキー差が原点を含む。GJKはミンコフスキー差を陽に構築せず、サポート写像（ある方向で最も遠い形状上の点を返す関数）だけを使って、原点を囲もうとする単体（点→線分→三角形→四面体）を反復的に更新し、原点包含の可否を判定します。

サポート写像さえ定義できれば形状の種類を問わない（球でもカプセルでも凸包でもよい）ことがGJKの最大の利点です。射影軸を全列挙するSATと違い、必要な方向のサポート点だけを都度問い合わせるため、面数の多い凸包でも効率的に判定できます。ただしGJK単体が返すのは基本的に交差しているか否か（と非交差時の最短距離）であり、貫入している場合の深さと法線はそのままでは得られません。

実装の観点では、単純な箱・多角形が主体ならSAT、球やカプセルを含む多様な凸形状を統一的に回すならGJK/EPA、と使い分けるのが一般的です。両者は排他ではなく、プリミティブ組み合わせごとに最速の専用ルーチン（球対球、球対箱など）を持ち、汎用ケースだけGJK/EPAに委ねる実装も広く行われます。

連続衝突検出：トンネリングを防ぐ

以上はすべて離散衝突検出——各フレームの静止スナップショットで交差を調べる方式です。ここに高速移動物体の落とし穴があります。弾丸のように速い物体は、前フレームでは壁の手前、次フレームでは壁の向こう側にいて、どちらのスナップショットでも壁と交差していない。結果、薄い壁をすり抜けます。これがトンネリングです。フレーム間の移動量が物体や障害物の厚みを超えると発生し、フレームレートに依存して顕在化します。

対策が連続衝突検出（Continuous Collision Detection、CCD）です。物体を「前フレーム位置から今フレーム位置へ動く軌跡」として扱い、その掃引形状が障害物と交わる最初の接触時刻（Time of Impact、TOI）を区間 [0, 1] の中で求めます。TOIが存在すれば、その瞬間まで物体を進めて接触として処理し、貫通を未然に防ぎます。

離散 vs 連続:

  離散: 各フレームで位置を止めて交差判定
        → フレーム間で「またいだ」薄い障害物を見逃す（トンネリング）

  連続(CCD): 移動を軌跡として捉え最初の接触時刻 TOI∈[0,1] を求める
    ・掃引/シェイプキャスト: 形状を移動方向に掃引した体積の交差を解く
    ・保守的前進: 「今の最短距離」の分だけ安全に前進する操作を反復し
                  TOI へ単調に近づける（GJKの距離計算と相性が良い）
    ・二分探索TOI: 移動区間を細分し交差が切り替わる時刻を挟み込む

CCDは正確だが高価なので、全物体には適用せず、速度がしきい値を超える物体（弾丸・高速な破片）にだけ有効化するのが実務です。この段階的適用は、まず粗く絞ってから精密判定へ進むという衝突検出全体の設計思想と一貫しています。TOIをどう解くか（保守的前進はGJKの距離計算を反復利用でき、二分探索は素朴だが汎用）はエンジンごとに選択されます。物体の運動そのものをどう積分するかは物理シミュレーションの数値積分の問題で、プログラミングの原理 で扱う数値計算とも関わります。

まとめ

衝突検出は、粗く速いブロードフェーズと精密で高価なナローフェーズの二段構えで、総当たりのO(n^2)を避けます。ブロードフェーズはAABBと掃引と刈り込み（あるいはグリッド・BVH）で潜在接触対を実効的にO(n)前後まで絞り、偽陽性は許すが偽陰性は許さない保守的な近似で候補を渡します。ナローフェーズは絞られた組を厳密に判定します。凸ポリトープには分離軸定理（SAT）が直截で、全候補軸に射影して隙間の有無を調べ、重なり最小の軸から貫入方向と深さを得ます。球やカプセルを含む任意の凸形状にはGJKが有効で、ミンコフスキー差の原点包含をサポート写像だけで判定し、貫入量はEPAで復元します。そして高速移動物体のトンネリングには連続衝突検出が要で、軌跡の掃引や保守的前進で最初の接触時刻（TOI）を求め、すり抜けを防ぎます。いずれの段階も「まず安く絞り、必要なところだけ精密に、そして特殊ケースにだけ重い手法を」という一貫した設計思想の上に成り立っています。