GJK

ひとことで

2 つの凸形状が重なっているか、離れているならその最短距離はいくつかを求める方法です。「A のすべての点から B のすべての点を引いた形（ミンコフスキー差）」が原点を含めば重なっており、離れていれば原点までの距離がそのまま 2 つの形の距離になる、という性質を使います。ミンコフスキー差を実際に作る必要はなく、「ある方向にいちばん遠い点（サポート点）」を求める関数さえあれば、どんな凸形状（球・箱・カプセル・凸多面体）にも同じコードで使えます。多くの 3D 物理エンジンの中心的な判定です。

ゲームでの使いどころ

• 物理エンジンの詳細判定：Bullet、PhysX、Jolt などで、凸形状どうしの判定に使われる。
• 距離が必要な処理：「壁からどれだけ離れているか」「2 つの物体の最も近い点」。
• [連続衝突判定](/keywords/world/collision/continuous-collision-detection/)：距離から「確実にぶつからない時間」を求めて少しずつ進める保守的な前進法の土台。
• めり込みの深さ：重なっている場合は、EPA（拡張多面体法）と組み合わせて、押し戻す向きと深さを求める。

しくみ

ミンコフスキー差：$A - B = \{\mathbf{a} - \mathbf{b} \mid \mathbf{a} \in A,\ \mathbf{b} \in B\}$ は凸形状です。A と B に共通の点があれば $\mathbf{a} - \mathbf{b} = \mathbf{0}$ となる組があるので、原点を含みます。離れていれば、原点からこの形までの距離が、A と B の最短距離です。

サポート関数：方向 $\mathbf{d}$ にいちばん遠いミンコフスキー差の点は

と、それぞれの形のサポート点の差で求まります。球なら $\mathbf{c} + r\,\mathbf{d}/|\mathbf{d}|$、多角形なら $\mathbf{d}$ との内積が最大の頂点です。

単体を育てる：2 次元では点・線分・三角形（3 次元では四面体まで）の「単体」を使います。

1. 適当な方向のサポート点 1 つで単体を作ります。
2. 単体の中で原点に最も近い点 $\mathbf{p}$ を求め、それに必要ない頂点を捨てます。三角形が原点を囲んでいれば、重なっていると決まります。
3. 原点の方向 $-\mathbf{p}$ のサポート点 $\mathbf{w}$ を求めます。$\mathbf{w}$ が $\mathbf{p}$ より原点側にほとんど進まなければ、それ以上近づけないので、$|\mathbf{p}|$ が最短距離です。
4. そうでなければ $\mathbf{w}$ を単体に加えて 2 に戻ります。

たいてい数回のくり返しで終わります。

実装のポイント

• 最初の方向：2 つの形の中心を結ぶ向きなど、答えに近い方向から始めると、くり返しが減ります。前のフレームの単体を使い回すのも効果的です。
• 最も近い 2 点：単体の頂点ごとに、元になった A と B のサポート点を覚えておくと、最近点を表す重み（重心座標）から、A 上と B 上の最も近い点が求まります。
• 丸みのある形：カプセルや角の丸い箱は、「芯の形 + 半径」として扱い、芯どうしの距離から半径を引くと、GJK の苦手な曲面を避けられます。
• 終了条件と上限：浮動小数点の誤差で終わらないことがあるので、くり返しの回数に上限を付けます。

つまずきやすい点

• 凸でない形には使えない：凹んだ形は凸な部品に分けてから使います。
• めり込みの深さは出ない：GJK だけでは、重なっていることはわかっても、どれだけめり込んでいるかはわかりません。EPA や、分離軸定理を併用します。
• ほぼ接している場合：距離が 0 に近いと、「重なっている」と「わずかに離れている」の判定が不安定になります。小さな余白（接触の許容量）を設けます。

デモで試すこと

1. 左が 2 つの形、右がそのミンコフスキー差（紫）と原点（白い点）です。緑の形を動かすと、ミンコフスキー差も一緒に動きます。
2. 形が止まると、GJK の手順が 1 つずつ進みます。黄色が単体、黄色の矢印が次に探す方向（原点の向き）、赤い点が単体の中で原点に最も近い点です。
3. 形が重なっているときは、単体の三角形が原点を囲んで終わります。離れているときは、原点に最も近い点で止まり、その距離が 2 つの形の最短距離です（左の赤い線が、その 2 点を結びます）。
4. 「自動で動かす」を切って緑の形をドラッグすると、好きな位置で手順を見られます。「1 手順の時間」で速さを変えられます。