衝突判定
衝突判定（しょうとつはんてい、Collision Detection）とは、コンピュータゲームや物理シミュレーション、計算幾何学などの分野において、ある物体が別の物体に当たったか（衝突したか）どうかを判定するプログラム処理のこと。
具体的な判定方法
同じ図形どうしの判定
- 矩形
矩形を点(x, y) と幅・高さ(lx, ly) で表す。ふたつの矩形A・矩形B について衝突判定を行うには、以下の条件が成り立っているかどうかを調べる。成り立てば当たり、そうでなければ外れと判定できる。
[math] (A_x \le B_x+B_{lx}) \land (B_x \le A_x+A_{lx}) \land (A_y \le B_y+B_{ly}) \land (B_y \le A_y+A_{ly}) [/math]
- AABB
矩形を3次元に拡張したものを AABB (Axis Aligned Bounding Box, 軸に平行な直方体) と呼ぶ。2次元の矩形は左上の点とそこから右下までの長さで表すのが一般的なのに対して、AABBでは直方体の中心座標とxyz軸方向に±何mの広がり(半径のようなもの)、という表し方をすることが多い。AABBの中心(x,y,z), 大きさ(rx,ry,rz) とすると、このAABBは x方向については x-rx ～ x+rx, y方向には y-ry ～ y+ry, z方向には z-rz ～ z+rz の範囲を占める。AABBの衝突判定は以下のようになる。
[math](A_x-A_{rx} \le B_x+B_{rx}) \land (B_x-B_{rx} \le A_x+A_{rx})[/math] [math]\land (A_y-A_{ry} \le B_y+B_{ry}) \land (B_y-B_{ry} \le A_y+A_{ry})[/math] [math]\land (A_z-A_{rz} \le B_z+B_{rz}) \land (B_z-B_{rz} \le A_z+A_{rz})[/math]
AABBは大雑把な衝突判定や可視判定で使われることがある。
- 円、球
円を中心(x,y)、半径 r で表すと、二つの円 A, B が当たっていることは「Aの中心とBの中心の距離が、Aの半径とBの半径の和以下である」ことと同値であるから、円どうしの衝突判定は
[math](A_x-B_x)^2 + (A_y-B_y)^2 \le (A_r+B_r)^2[/math]
これを3次元に拡張すると、球と球の衝突判定を行うことができる。
[math](A_x-B_x)^2 + (A_y-B_y)^2 + (A_z-B_z)^2 \le (A_r+B_r)^2[/math]
- 複雑な形状の衝突判定を行うとき、複数の球を組み合わせて近似的に判定することもできる。ただしこの方法はセガの特許なので注意。
- 動く球
- 動く球は、移動開始時の中心・速度ベクトル・半径、で表す。
- 両方の球が静止していれば→球の衝突判定を使う
- 2つの球が同じ速度→球の衝突判定を使う
- 0 < t < 1 なる媒介変数 t を使って、球Aの中心は (A0 + t Va), 球Bの中心は (B0 + t Vb) と表せる。このように動いていく球A・球Bの中心どうしの距離が、半径の和以下になるような時刻 t が存在するか? を求める。