Separating Axis Theorem / SAT

This explanation is currently available in Japanese.

ひとことで

2 つの凸形状が重なっていないなら、その間に 1 本の直線（3 次元では平面）を引いて分けられる、という定理です。言いかえると、ある軸に両方の形を投影したとき、影と影の間に隙間ができる軸（分離軸）が存在します。凸多角形なら、調べるべき軸は辺の法線だけに限られるので、全部の候補軸で影が重なっていれば「重なっている」と言い切れます。重なっているときは、重なりが最小の軸の方向へ押し出せば離れる（最小移動ベクトル）こともわかります。

ゲームでの使いどころ

• 2D の当たり判定：回転する箱や多角形どうしの判定と押し戻し（Box2D や多くの 2D エンジンの箱どうしの判定）。
• 回転した箱（OBB）どうし：3 次元では、面の法線 6 本と辺の組み合わせ 9 本の、合わせて 15 本の軸を調べる。
• 押し戻し：プレイヤーが壁に食い込んだとき、最小移動ベクトルの分だけ押し出す。
• カリング：視錐台と AABB の判定も、分離軸の考え方で書ける。

しくみ

軸 $\mathbf{n}$ に形を投影すると、頂点 $\mathbf{v}$ の影の位置は $\mathbf{v}\cdot\mathbf{n}$ です。すべての頂点の最小と最大が、その形の影の区間 $[\min, \max]$ です。

1. 両方の形の、すべての辺の法線を候補軸として集めます（平行な軸は 1 本にまとめてよい）。
2. 各軸で、A と B の影の区間を求めます。
3. どれか 1 本で区間が重ならなければ（$A_{\max} < B_{\min}$ または $B_{\max} < A_{\min}$）、その軸が分離軸で、形は重なっていません。そこで打ち切れます。
4. すべての軸で重なっていれば、形は重なっています。重なりの量

が最小の軸 $\mathbf{n}^*$ と、その量 $o^*$ が、最小移動ベクトル $o^*\,\mathbf{n}^*$ です。向きは、A の中心から B の中心への向きと逆になるようにそろえます。

凸でない形では、影が重なっていても実際は離れていることがあるので、凸形状に分解してから使います。

実装のポイント

• 円との判定：円には辺がないので、多角形の辺の法線に加えて、「円の中心から多角形の最も近い頂点へ向かう軸」を 1 本足します。
• 接触点：押し戻しだけでなく、転がりや摩擦を計算するには接触点が必要です。最小の軸に最もよく向いた辺どうしを切り取って（クリッピング）求めます。
• 前のフレームの分離軸を先に試す：物体はフレーム間で少ししか動かないので、前回の分離軸がまた分離軸であることが多く、1 本目で打ち切れます。
• 3 次元の OBB：辺どうしの外積の軸は、辺が平行に近いと長さが 0 に近くなります。その軸は飛ばします。

つまずきやすい点

• 法線を正規化しない：軸が単位ベクトルでないと、重なりの量が軸ごとにずれた大きさになり、最小移動ベクトルが正しくなりません。判定だけなら正規化は不要です。
• 押し出す向きを間違える：最小の軸の向きを中心どうしの向きと合わせないと、逆向きに押し込んでしまいます。
• 頂点の多い形は重い：軸の数は辺の数に比例し、投影も頂点の数だけかかります。頂点の多い凸形状には GJK の方が向いています。

デモで試すこと

1. 緑の五角形と青い四角形の、すべての辺の法線（合わせて 9 本）を 1 本ずつ順に軸として取り、黄色の点線の上に 2 つの影（区間）を描きます。
2. 形が離れているとき、隙間のある軸では影の間に白い線が現れます。左下の「分離軸」で、最初に見つかった軸がわかります。
3. 緑の形の中心をドラッグして重ねると、どの軸でも影が重なり、赤い矢印（最小移動ベクトル）が表示されます。「重なったら押し出す」を入れると、その分だけ押し出されます。
4. 「緑の多角形の向き」を変えると、軸の向きも一緒に回ります。「軸を 1 本ずつ順に見せる」を切ると、分離軸か最小の軸だけを表示します。