重なりを見つける四つの方法

目標

AABB、円、分離軸定理で重なりを判定し、ブロードフェーズで検査の回数を減らし、レイとボックスの交差を解きます。このラボが終われば、物理エンジンの衝突検出の層を、自分で作れるようになります。

なぜ重要なのか

物体が200個なら、ペアは19,900個です。すべてで精密な判定をすると、物理の計算が始まる前に、フレームが終わります。ところが、実際に重なっているペアは、300個にもなりません。そのため、衝突検出は2つの層に分かれます。重なるはずのないペアをとても安く取り除くブロードフェーズと、残ったペアを正確に見るナローフェーズです。

ナローフェーズの一般解が、分離軸定理です。2つの凸図形が離れているなら、それを分ける直線が必ず存在し、その方向は、2つの図形の辺のどれかと平行です。そのため、辺の法線方向にだけ投影してみれば済みます。そして、重なったとき、最も小さい重なりを与えた軸が、そのまま最も短く押し出す方向なので、検出と応答が同じ計算から出ます。

ステップ

/root/collideに、ツールボックスを置きます。
/root/collide/aabb.pyに、軸並行バウンディングボックスを作ります。
/root/collide/circle.pyに、円と円の判定を作ります。
/root/collide/sat.pyに、分離軸定理を作ります。
/root/collide/out/sat.pngに、重なった図形と最小移動ベクトルを描きます。
/root/collide/boxes.txtと/root/collide/out/06-broad.txtに、総当たり検査とソート・アンド・スイープの結果を書きます。
/root/collide/ray.pyと/root/collide/out/07-ray.txt、ray.pngに、レイとボックスの結果を書きます。

参考

絵は、nohup python3 -m http.server 8080 -d /root/collide/out &で立てて、Webプレビューでhttp://localhost:8080/を開きます。
関数は、/root/collideの中に置いてください。採点ツールが、そのフォルダーをimportのパスに入れて、直接呼び出してみます。
よくあるミスの1つ目は、ブロードフェーズが、ナローフェーズと異なる答えを出すことです。ブロードフェーズは、答えを変えるのではなく、同じ答えを安く得るものなので、ペアの数が違えば、breakの条件が間違っています。
よくあるミスの2つ目は、レイの判定で、max(tmin, 0)の0を抜かすことです。そうすると、レイの後ろにあるボックスにも、当たったと出ます。

描画のツールボックスを置く

/root/collide/gfxlib.pyを例のとおりに保存し、/root/collide/check.pyでテストパターンを描いて、/root/collide/out/00-check.pngを作ってください。パターンは、64x64の黒い背景に、(0,0)から(63,63)まで、白(255,255,255)の対角線を引き、そのあとに、(0,32)から(63,32)まで、赤(255,0,0)の横線を重ねて引いたものです。

このラボからは、PNGエンコーダーを作り直しません。最初のラボで手で作ったものと同じコードを、ツールとして配ります。ここで学ぶのは、ファイル形式ではないからです。

ラボのPodにはボリュームがないので、前のラボで作ったファイルが残っていません。そのため、ラボごとに、ツールボックスを置き直すことから始めます。

Canvas(w, h, bg)を作り、line(x0, y0, x1, y1, rgb)で2本の線を引いたあと、write_png(path)で保存してください。交差点(32,32)が赤になるには、横線をあとで引く必要があります。

このラボでは、重なった図形と最小移動ベクトルを描くのに使います。

軸並行バウンディングボックス

/root/collide/aabb.pyに、overlap(a, b)とpenetration(a, b)を作ってください。ボックスは、(minx, miny, maxx, maxy)の4つの実数で、境界がちょうど接している場合も、重なりとみなします。penetrationは、重なっていれば、軸ごとの重なりの幅(dx, dy)を、重なっていなければ、(0.0, 0.0)を返します。

重ならない条件を先に書くほうが、ずっと短くなります。

not (a[2] < b[0] or b[2] < a[0] or a[3] < b[1] or b[3] < a[1])

不等号に等号を入れるかどうかが、そのまま「接している場合」の判定です。このラボは、接していることを重なりとみなすので、上の式のように、等号を除きます。

重なりの幅は、min(a[2], b[2]) - max(a[0], b[0])です。2つのボックスの右端のうち左にあるものから、左端のうち右にあるものを引いた値です。

判定のルールは、1か所だけに置いてください。複数の場所で違えて決めると、ボックスが床で震えたり、くっついたりします。

円と円

/root/collide/circle.pyに、circle_hit(c1, r1, c2, r2)を作ってください。中心間の距離が半径の和より小さいときだけ、重なったとみなして、(True, 법선, 깊이)を返し(プレースホルダーは、法線と深さです)、そうでなければ、(False, (0.0, 0.0), 0.0)を返します。法線は、1から2に向かう単位ベクトルで、深さは、r1 + r2 - 거리です(プレースホルダーは、距離です)。2つの中心がちょうど同じなら、法線を(1.0, 0.0)とします。

距離が0のときを別に処理しないと、0での割り算が起きます。物体2つがちょうど同じ位置で生まれることは、実際には思ったより頻繁にあります。スポナーで一度にまとめて作るときが、そうです。

比較だけを行うなら、平方根を避けられますが、ここでは、深さを求める必要があるので、実際の距離が必要です。

法線の方向を、1から2へと決めておくことが重要です。次のモジュールの力積の計算が、この約束をそのまま使います。逆にすると、物体が互いを引き寄せます。

分離軸定理

/root/collide/sat.pyに、sat_hit(a, b)を作ってください。a、bは、反時計回りに書いた凸多角形(頂点のリスト)で、重なっていれば、(True, 축, 깊이)を返し(プレースホルダーは、軸と深さです)、そうでなければ、(False, (0.0,0.0), 0.0)を返します。軸は、2つの図形のすべての辺の法線のうち、重なりが最も小さいもので、aの重心からbの重心へ向かうように、符号を合わせます。

辺(x0,y0) -> (x1,y1)の法線は、(ey, -ex)を正規化したものです(ex = x1-x0、ey = y1-y0)。

1つの軸での重なりは、min(a1, b1) - max(a0, b0)で、この値が0以下なら、その軸が2つの図形を分ける軸なので、すぐに終えて構いません。残りの軸を見る必要はありません。

最後に軸の符号を合わせる理由は、辺の法線がどちらの図形のものかによって、方向が逆に出ることがあるからです。dot(축, 무게중심b - 무게중심a) < 0なら、反転してください(プレースホルダーは、軸と2つの重心です)。

正方形が2つ、x方向に1.5だけ離れていれば、軸は(1,0)、深さは0.5が出る必要があります。

重なりと押し出す方向を描く

/root/collide/draw.pyで、/root/collide/out/sat.png(256x256、黒い背景)を作ってください。多角形Aは、[(-1,-1),(1,-1),(1,1),(-1,1)]を白(255,255,255)の枠線で、Bは、Aを(1.5, 0.5)だけ移したものを、黄(255,220,60)の枠線で描き、Bの重心から、축 * 깊이だけ伸びる最小移動ベクトルを、赤(255,60,60)の線で描きます(プレースホルダーは、軸と深さです)。画面座標は、sx = 128 + 40*x、sy = 128 - 40*yです。

多角形の枠線は、頂点を順番につないで、最後から最初の点に戻る線分です。gfxlib.Canvasのlineを使ってください。

最小移動ベクトルは、sat_hit(A, B)が返した軸と深さを掛けたものです。この分だけBを押せば、2つの図形がちょうど離れます。それが「最小」という言葉の意味です。

描く順序は、A、B、矢印です。重なる所では、あとで描いたものが勝ちます。

絵を見ると、2つの四角形が、x方向にだけわずかに重なっていて、矢印が右を指しているのが見えます。y方向の重なりのほうが深いのに、xを選ぶ理由は、「最も短く押し出す方向」だからです。

並べ替えておいて走査する

/root/collide/gen_boxes.pyを例のとおりに保存して実行すると、/root/collide/boxes.txtに、ボックスが200個作られます。そのボックスについて、総当たり検査とソート・アンド・スイープをそれぞれ回して、/root/collide/out/06-broad.txtに、pairs_brute=、pairs_sweep=、checks_brute=、checks_sweep=の4行を書いてください。

総当たり検査は、i < jであるすべてのペアを見ることで、検査の回数は、200*199/2 = 19,900です。

ソート・アンド・スイープは、次のとおりです。ボックスをminxで並べておくと、あるボックスと重なりうるものは、並べた順序で、後ろに続くもののうち、minxがこのボックスのmaxxを超えないものだけです。その地点で、内側のループをbreakしてください。

checks_sweepは、内側のループで、実際に重なりの判定を呼び出した回数です(breakで抜け出したものは、数えません)。

2つの方法が見つけたペアの数は、必ず同じでなければなりません。ブロードフェーズは、答えを変えるのではなく、同じ答えを安く得るものです。異なるなら、breakの条件が間違っています。

レイとボックス: スラブ法

/root/collide/ray.pyにray_aabb(o, d, box)を作って、レイ5本を、ボックス(-1,-1,1,1)に向けて撃ち、結果を/root/collide/out/07-ray.txtに、r1=hit,tまたはr1=miss,0.000000の形式で、5行書いてください。そして、/root/collide/out/ray.png(256x256)に、ボックスを白で、当たったレイは緑(60,255,120)で当たった地点まで、外れたレイは赤(255,80,80)で長さ6だけ、描いてください。画面座標は、sx = 128 + 30*x、sy = 128 - 30*yです。レイは、順番に、o=(-3,0) d=(1,0)、o=(-3,3) d=(1,0)、o=(0,0) d=(1,0)、o=(-3,-3) d=(0.7071067811865476, 0.7071067811865476)、o=(3,0) d=(1,0)です。

スラブ法は、軸ごとに、レイがその軸の2つの平面の間にある区間[t1, t2]を求めて、すべての軸の区間を、共通部分として絞り込んでいく方法です。

t1 = (box.min - o) / d      # 방향이 음수면 t1 과 t2 가 뒤바뀐다
t2 = (box.max - o) / d
tmin = max(tmin, min(t1, t2))
tmax = min(tmax, max(t1, t2))

方向の成分が0なら、割り算が破綻します。そのときは、原点がその軸の区間の中にあるかだけを見て、外なら、外れです。

最後の判定は、tmax >= max(tmin, 0)です。0を入れる理由は、レイが後ろ側へ伸びないからです。これを抜かすと、レイの後ろにあるボックスにも、当たったと出ます。5本目のレイが、まさにその場合です。

レイの出発点がボックスの中にあれば、tは0です(3本目のレイ)。