重なっているとどうやって分かるのか

一言でいうと

衝突検出は、2つの段階に分かれます。ブロードフェーズで、「重なるはずがない」ペアを安く取り除き、ナローフェーズで、残ったペアだけを正確に判定します。凸図形の正確な判定は、分離軸定理1つで終わります。

なぜ必要なのか

物体がn個なら、ペアはn(n-1)/2個です。200個なら19,900ペアで、2,000個なら200万ペアです。毎ステップ、これをすべて精密に検査すると、物理の計算が始まる前に、フレームが終わります。

ところが、実際に重なっているペアは、たいていごくわずかです。上の200個の例で、実際に重なっているペアは、300個もありません。残りの19,600ペアは、「わざわざ精密に見る必要がない」ことを、はるかに安く知ることができます。この構造が、ブロードフェーズとナローフェーズに分かれた理由です。

どう動くのか

AABB(軸並行バウンディングボックス)は、最も安い判定です。ボックス2つが重なるかどうかは、軸ごとに区間が重なるかだけを見れば済みます。

겹친다  ⟺  a.maxx >= b.minx  그리고  b.maxx >= a.minx
           그리고  a.maxy >= b.miny  그리고  b.maxy >= a.miny

軸ごとに1回ずつ、比較4回で終わります。重なりの深さも、同じ式から出ます。軸ごとに、min(maxs) - max(mins)が、その軸の重なりの幅で、より浅い軸が、実際に押し出す方向です。

円と球は、その次に安いです。中心間の距離が、半径の和より小さければ重なっていて、法線は、中心をつなぐ方向、めり込んだ深さは、r1 + r2 - 거리です(プレースホルダーは、距離です)。ここで気をつけるのは、2つの中心がちょうど同じときです。距離が0だと、方向を決められないので、任意の方向を決めてやる必要があり、そうしないと、0での割り算が起きます。

分離軸定理(SAT)は、凸図形一般に使う方法です。2つの凸図形が重なっていないなら、2つの図形を完全に分ける直線が必ず存在します。そして、その直線の方向は、2つの図形の辺のどれかと平行です。そのため、各辺の法線方向に2つの図形を投影して、区間が離れている軸を1つでも見つければ、重なっていないということになります。

for 축 in A의 변 법선들 + B의 변 법선들:
    A 를 축에 투영 → [a0, a1]
    B 를 축에 투영 → [b0, b1]
    겹침 = min(a1, b1) - max(a0, b0)
    if 겹침 <= 0: 떨어져 있다 (여기서 즉시 끝낸다)
    가장 작은 겹침과 그 축을 기억해 둔다

離れている軸を見つけられなければ、重なっていて、このとき、最も小さい重なりを与えた軸が、最も短く押し出す方向です。これを最小移動ベクトル(MTV)と呼び、次のモジュールの衝突応答が、この方向を使います。

ブロードフェーズの古典的な方法は、ソート・アンド・スイープ(sweep and prune)です。ボックスを、x軸の最小値で並べておくと、あるボックスと重なりうるボックスは、並べた順序で、後ろに続くもののうち、minxがこのボックスのmaxxを超えないものだけです。その地点で止めれば済みます。

ブロードフェーズには、ソート・アンド・スイープのほかにも、いくつか方法があります。グリッド(spatial hash)は、空間を一定の大きさのマスに分けて、各物体を、自分がまたがるマスに登録しておく方法です。物体の大きさがそろっていて、均等に散らばっているときに、最も速いです。動的バウンディングボックスツリー(dynamic AABB tree)は、ボックスを二分木にまとめておいて、枝単位で飛ばす方法なので、大きさの差が大きい物体が混ざっていても、よく持ちこたえます。Box2DとBulletが、このツリーを使います。

どの方法でも、共通点が1つあります。ブロードフェーズは、実際に重なっているペアを絶対に見逃してはいけませんが、重なっていないペアを渡すことは構いません。見逃すと、物体が互いに通り抜けますが、余分に渡しても、ナローフェーズが取り除いてくれるだけで、結果は同じです。そのため、ブロードフェーズの判定は、常に余裕のある側に作ります。

現場での姿

速い物体が薄い壁を通り抜ける問題(トンネリング)は、検出の限界から来ます。ステップの開始と終わりでしか、重なりを見ないので、1ステップのうちに壁を完全に通り過ぎてしまうと、どの時点にも重なりがありません。解決法は、移動の経路を走査する連続衝突検出か、ステップを細かく分割することです。

もう1つは、境界値の一貫性です。ちょうど接している場合を、重なりとみなすかどうかを、コードの複数の場所で違えて決めると、ボックスが床に接したり離れたりを繰り返して、震えます。判定のルールは1か所に置いて、全員がそれを呼び出すようにする必要があります。

最後に、ナローフェーズの出力が何であるべきかを、決めておくことが重要です。重なったという真偽だけでは、次の段階が何もできません。衝突応答が必要とするものは、3つです。押し出す方向(法線)、どれだけめり込んだか(深さ)、そして、どこで接したか(接触点)です。このラボは、前の2つまでを作り、接触点は扱いません。接触点は、回転を計算するときに必要で、それだけでも別のテーマになるからです。

次のラボですること

AABB、円、分離軸定理を順に作り、重なった2つの多角形と最小移動ベクトルを、絵に描きます。次に、ボックス200個について、総当たりの検査と、ソート・アンド・スイープを、それぞれ回して、同じ結果を、はるかに少ない検査で得られることを、数字で確認し、最後に、レイとボックスの交差を、スラブ法で解いて、絵に描きます。