衝突判定
Early work in this area involved "separating plane" methods. Two triangles collide essentially only when they can not be separated by a plane going through three vertices. That is, if the triangles are {v_1,v_2,v_3} and {v_4,v_5,v_6} where each v_j is a vector in \mathbb R^3, then we can take three vertices, v_i,v_j,v_k, find a plane going through all three vertices, and check to see if this is a separating plane. If any such plane is a separating plane, then the triangles are deemed to be disjoint. On the other hand, if none of these planes are separating planes, then the triangles are deemed to intersect. There are twenty such planes.
If the triangles are coplanar, this test is not entirely successful. One can add some extra planes, for instance, planes that are normal to triangle edges, to fix the problem entirely. In other cases, objects that meet at a flat face must necessarily also meet at an angle elsewhere, hence the overall collision detection will be able to find the collision.
Better methods have since been developed.  Very fast algorithms are available for finding the closest points on the surface of two convex polyhedral objects.  Early work by Ming C. Lin used a variation on the simplex algorithm from linear programming.  The Gilbert-Johnson-Keerthi distance algorithm has superseded that approach.  These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, when used with starting points from the previous collision check.
The end result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.
Where most of the objects involved are fixed, as is typical of video games, a priori methods using precomputation can be used to speed up execution.
Pruning is also desirable here, both n-body pruning and pairwise pruning, but the algorithms must take time and the types of motions used in the underlying physical system into consideration.
When it comes to the exact pairwise collision detection, this is highly trajectory dependent, and one almost has to use a numerical root-finding algorithm to compute the instant of impact.
As an example, consider two triangles moving in time {v_1(t),v_2(t),v_3(t)} and {v_4(t),v_5(t),v_6(t)}. At any point in time, the two triangles can be checked for intersection using the twenty planes previously mentioned. However, we can do better, since these twenty planes can all be tracked in time. If P(u,v,w) is the plane going through points u,v,w in \mathbb R^3 then there are twenty planes P(v_i(t),v_j(t),v_k(t)) to track. Each plane needs to be tracked against three vertices, this gives sixty values to track. Using a root finder on these sixty functions produces the exact collision times for the two given triangles and the two given trajectory. We note here that if the trajectories of the vertices are assumed to be linear polynomials in t then the final sixty functions are in fact cubic polynomials, and in this exceptional case, it is possible to locate the exact collision time using the formula for the roots of the cubic. Some numerical analysts suggest that using the formula for the roots of the cubic is not as numerically stable as using a root finder for polynomials.June 2008
Alternative algorithms are grouped under the spatial partitioning umbrella, which includes octrees, binary space partitioning (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Since BSP trees can be precomputed, that approach is well suited to handling walls and fixed obstacles in games.   These algorithms are generally older than the algorithms described above.
Bounding boxes (or bounding volumes) are most often a 2D rectangle or 3D cuboid, but other shapes are possible. A bounding box in a video game is sometimes called a Hitbox.
The bounding diamond, the minimum bounding parallelogram, the convex hull, the bounding circle or bounding ball, and the bounding ellipse have all been tried, but bounding boxes remain the most popular due to their simplicity. Bounding boxes are typically used in the early (pruning) stage of collision detection, so that only objects with overlapping bounding boxes need be compared in detail.
A triangle mesh object is commonly used in 3D body modeling. Normally the collision function is a triangle to triangle intercept or a bounding shape associated with the mesh.  A triangle centroid is a center of mass location such that it would balance on a pencil tip. The simulation need only add a centroid dimension to the physics parameters.  Given centroid points in both object and target it is possible to define the line segment connecting these two points.
The position vector of the centroid of a triangle is the average of the position vectors of its vertices. So if its vertices have Cartesian  coordinates (x_1,y_1,z_1), (x_2,y_2,z_2) and (x_3,y_3,z_3) then the centroid is \left(\frac{(x_1+x_2+x_3)}{3},\frac{(y_1+y_2+y_3)}{3},\frac{(z_1+z_2+z_3)}{3}\right).
Here is the function for a line segment distance between two 3D points. \mathrm{distance} = \sqrt{(z_2 - z_1)^2 + (x_2 - x_1)^2 + (y_2 - y_1)^2}
Here the length/distance of the segment is an adjustable "hit" criteria size of segment. As the objects approach the length decreases to the threshold value. A triangle sphere becomes the effective geometry test. A sphere centered at the centroid can be sized to encompass all the triangle's vertices.
ビデオゲームにおいては、非常に限られた計算機時間をいくつかのタスクに分割する必要がある。ゲームではこのようなリソースの制限に加え、かなり原始的な衝突検出アルゴリズムを使用せざるをえないという制限があったにもかかわらず、ゲームのプログラマーは、一応はプレイヤーの信頼に足るプログラムを作り上げて来た。
2Dのゲームの時代においては、処理するオブジェクトの数が非常に限られていたため、すべてのオブジェクトの衝突判定を行うことはそれほど問題ではなかった。2Dのゲームでは、ハードウェアにピクセル単位の衝突判定が実装されている場合もあり、その場合はハードウェアが画面上のスプライト同士の間で重複するピクセルを検出して報告してくれるので、ソフトの開発者としても効率的で楽だった。もしハードの支援が無かった場合でも、画面にタイルパターンを並べ、BGのタイルパターンと自機のスプライトが重なったかどうかをチェックするだけで十分な衝突判定が可能であった。ペアワイズ法を使った衝突判定のチェックにおいては、「ヒットボックス」と呼ばれる長方形の境界(円形の場合もある)が使用され、これで十分に正確な衝突判定が行えると考えられて来た。
3Dのゲームにおける衝突判定は、「空間をいくつかの区画に分割して刈り込む」という空間分割法か、もしくは「3Dのオブジェクトをいくつかの球に分割してペアワイズチェックを行う」という方法を長い間使用していた。現実を厳密にシミュレートしようとするようなタイプのシミュレーションゲームはともかくとして、ゲームで物理的に正確な衝突判定を行うことはまれである。そもそも、たとえゲームで正確な衝突判定を目指したところで、必ずしもすべての場合において正確な衝突判定のチェックが行えるわけでもない。
ゲームは実際の物理を模倣する必要がないため、衝突判定の確実性はそれほど問題ではない。ほとんどすべてのゲームは事後衝突検出を使用しており、もし衝突が検知された場合は非常に単純なルールを使用して解決される。たとえば、キャラクターが壁にめり込んだことが検知された場合、キャラクターは単に壁にめり込んでいなかった最後の場所まで戻される、と言う処理を行うゲームもある。一部のゲームでは、キャラクターが壁にめり込むまでに移動できる距離を計算し、壁にめり込まない距離までしか移動できないようにする、という処理を行う。
ゲームでフィールドとの衝突判定を行う場合、基本的にはキャラクターを「点」で近似するだけで十分である。この場合、バイナリ空間分割木は、「点」がフィールド内にめり込んだ状態であるか、それともそうでないかをチェックするための実行可能で効率的でシンプルなアルゴリズムを提供する。キャラクター同士の衝突、もしくは敵弾や当たるとダメージを受ける物との衝突判定はまた別の手法を用いて行われる。
シミュレーションの堅実性は、あらゆる入力に合理的な方法で反応するかどうかで決まる。たとえば超高速なレーシングゲームを想像すると、1つのシミュレーションステップから次のシミュレーションステップへと移行するごとに(つまり、1フレームごとに)、車はレーシングトラックに沿ってかなりの距離を進むことが想定される。もしトラックに薄い障害物(レンガの壁など)があった場合、フレームごとの移動距離が大きすぎて衝突判定が間に合わず、車が壁をすり抜けるバグが起こりがちだが、現実世界では車が壁をすり抜ける可能性はまったくない。シミュレーションと言う観点からすると、これは非常に望ましくないバグである。他の例を挙げると、事後衝突判定アルゴリズムが必要とする「軌道修正(フィックス)」が正しく実装されていないため、キャラクターがフィールドに復帰できず、壁の中にキャラクターが閉じ込められたり、キャラクターが壁を通過したりして、下に床が無い場合は無限に落下し続ける致命的なバグが発生することがある。「無限落下」や「ケツワープ」などと呼ばれるバグが知られている。これらのバグは、衝突判定および物理シミュレーションシステムの欠陥によるものである。『Big Rigs:Over the Road Racing』は、衝突判定システムにバグがある、もしくは衝突判定システムが欠如していることにより、「史上最低のクソゲー」として名高い。
ヒットボックス(hitbox)とは、ビデオゲームにおいてリアルタイムの衝突判定のために一般的に使用される「見えない四角」であり、バウンディングボックスの一種である。3Dモデル(3Dゲームの場合)やスプライト(2Dゲームの場合)などの可視オブジェクトと同じ場所にアタッチされることが多く、2Dゲームでは長方形、3Dゲームでは直方体の形をしている。円形または球形をしている場合もよくあるが、それでもほとんどの場合は「ボックス」と呼ばれる(海外でも)。可動オブジェクトでは、モーション中の精度を確保するために、可動する各パーツにヒットボックスがアタッチされているのが一般的であるMarch 2018。
ヒットボックスは、キャラクターと敵の打撃や弾丸との衝突判定を取る場合など、「一方向」の衝突を検出するために使用される。衝突によってフィードバックが発生する場合、例えば壁にぶつかった際にフィードバックによって反発が起き、すぐ次のフレームでは壁から引き離される、と言うような場合は、ヒットボックスの位置が絶えず変化することになり、ヒットボックスの位置の管理がとても面倒になるので、ヒットボックス方式を使うのは適していない。このような場合はヒットボックス方式より単純な実装である「軸並行境界ボックス方式(Axis-Aligned Bounding Box、AABB方式)」を使うのが適している。しかしプレーヤー目線では、これらの実装方式を区別せず、どちらも単に「ヒットボックス」と言う場合も多い。
ヒットボックスとよく似た概念としてハートボックス(hurtbox)と言うものも存在する。「ダメージを受ける衝突判定」と「ダメージを与える衝突判定」を使い分ける必要がある場合、前者を「ヒットボックス(あたり判定)」と呼び、後者を「ハートボックス(攻撃判定)」と呼ぶ。たとえば、攻め側のパンチのヒットボックスが相手側のハートボックスと衝突した場合は攻撃が「通った」と判定されるが、相手側のヒットボックスと衝突した場合は「相打ち」または「打撃キャンセル」と判定されたい、というような場合に使われる。ハートボックス同士が衝突しても何も起きない。なお、この用語は業界全体で標準化されておらず、「ヒットボックス」と「ハートボックス」の定義がこれと逆になっているゲームもあり、またどちらも単に「ヒットボックス」と呼ぶゲームもある。
ゲームにおいては衝突判定の精密性よりもリアルタイム性が重視されるので、以下のような手法がよく用いられる。
衝突判定を取りたい双方のオブジェクトを「四角い箱(矩形、ボックス)」で梱包することを考える。この「四角い箱」のことを一般的に「境界ボックス(バウンディングボックス)」と呼ぶが、ゲーム業界では「ヒットボックス」と呼ぶ。以下に述べるのは、ヒットボックス方式を用いた衝突判定の「基本的な方法」である。
2D空間において、それぞれの矩形を座標(x, y) と幅・高さ(lx, ly) で表す。ふたつの矩形A・矩形B について衝突判定を行うには、以下の条件が成り立っているかどうかを調べる。成り立てば当たり、そうでなければ外れと判定できる。
(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})
3D空間においては、衝突判定を取りたい双方のオブジェクトを「直方体」とみなし、幅・高さ・奥行き(lx, ly, lz) で表す以外は上と同じである。
ヒットボックス方式の主な実装方法は、上で述べた他に、境界球方式、AABB方式、OBB方式、凸包方式、などがある。後者に行くにしたがって精密な衝突判定が行えるが、計算コストが大きくなり、特に凸包方式はゲームではまず使われない。2010年代以降には凸包同士の衝突計算をGJKアルゴリズムを用いてGPUでリアルタイムで実行するための研究が進んでおり、今後のゲームエンジンに実装される可能性もある(すでに実装されている可能性もある)が、複雑なオブジェクト同士の衝突判定を行う伝統的な方法としては、複数のヒットボックスを組み合わせて近似する方式が使われる。
ヒットボックス方式の一種で、衝突判定を取りたい双方のオブジェクトを「円形」または「球形」とみなす。円形の境界ボックスの事を「ヒットボックス」と呼ぶ。ちなみに海外でも円形なのに「ヒットボックス」と呼ばれる。「境界円」「ヒットサークル」と呼ばれることもまれにある。
円を中心(x,y)、半径 r で表すと、二つの円 A, B が当たっていることは「Aの中心とBの中心の距離が、Aの半径とBの半径の和以下である」ことと同値であるから、円どうしの衝突判定は
(A_x-B_x)^2 + (A_y-B_y)^2 \le (A_r+B_r)^2
これを3次元に拡張すると、球と球の衝突判定を行うことができる。球形の境界ボックスのことを「境界球(Bounding Sphere)」と呼ぶが、やはりこれも「ヒットボックス」と呼ぶことが多い。
(A_x-B_x)^2 + (A_y-B_y)^2 + (A_z-B_z)^2 \le (A_r+B_r)^2
特に3D空間で衝突判定を取る場合において、上記の方式では管理が面倒になる場合は「軸並行境界ボックス方式(Axis Aligned Bounding Box, AABB方式)」を使う。
ヒットボックス方式の「基本的な方法」ではオブジェクトのバウンディングボックス(境界ボックス)の左上の点をオブジェクト自体の座標とみなし、そこから右下までの長さを取るのが一般的なのに対して、AABB方式ではヒットボックスの中心座標をオブジェクト自体の座標とみなし、そこからxyz軸方向に±何mの広がりがある、という表し方をする。ヒットボックスの中心を(x,y,z), 双方向への広がりの大きさを(rx,ry,rz)とすると、このヒットボックスは x方向については x-rx ~ x+rx, y方向には y-ry ~ y+ry, z方向には z-rz ~ z+rz の範囲を占める。軸並行境界ボックス方式を用いてふたつのヒットボックスA・Bについて衝突判定を行うには、以下のようになる。
(A_x-A_{rx} \le B_x+B_{rx}) \land (B_x-B_{rx} \le A_x+A_{rx})
\land (A_y-A_{ry} \le B_y+B_{ry}) \land (B_y-B_{ry} \le A_y+A_{ry})
\land (A_z-A_{rz} \le B_z+B_{rz}) \land (B_z-B_{rz} \le A_z+A_{rz})
AABBは大雑把な衝突判定や可視判定で使われることがある。
AABB方式は2Dの衝突判定を取る場合でも使われることがある。特に四角いヒットボックスと円形のヒットボックスの衝突判定を取る時は、四角いヒットボックスの座標をAABB方式で管理した方が楽である。
有向境界ボックス(Oriented Bounding Box)。
2Dゲームにおいて、ピクセル単位で衝突判定を取る方式。スプライト画像をベースとする衝突判定の方式なのでimage-based collision detectionともいう。1980年代頃までの8bit機ではスプライトの表示位置ごとの衝突判定を取ることしかできなかったが(当時のスプライトの大きさは基本的に8x8であったため、8ドット単位の衝突判定になった)、この方式を用いることで、1ドット単位の衝突判定が可能になる。
MSX2(1985年発売)の「スプライトモード2」ではハードウェアの支援が得られることがウリの一つであった。ハードウェアの支援が得られないハードにおいてソフトウェアベースでピクセルパーフェクトを実現する方式がいくつかあるが、現代においてこれをソフトウェアで実装するには、基本的には複数のヒットボックスを組み合わせて衝突判定を取る方式が用いられる。そもそも現代の2Dゲームエンジンでは8bit機時代のようなスプライト機能をソフトウェア上で擬似的に実装しているだけであるので、現代のハードウェアの性能をもってすれば、ソフトウェアベースでピクセルパーフェクトを実装することは特に困難ではない。
複雑な形状のポリゴンモデルの衝突判定を行うとき、ポリゴンモデルを「複数の球の組み合わせ」とみなし、それぞれの球において衝突判定を行うことでオブジェクト同士の衝突判定を行うことができる。セガの初代『バーチャファイター』(1993年)で初めて実装された手法。現在はポリゴンのキャラクター同士の衝突判定を取る際の基本的な手法であるが、これが初めて実装された1993年当時は衝撃的であったとのこと(『バーチャファイター』以前のゲームは、各キャラクターの姿勢や動作の一つ一つについてヒットボックスを個別に実装していたため、メモリを食う上にキャラクターの見た目と衝突判定が一致していなかった)。
バイナリ空間分割木(Binary space partitioning, BSP木)を用いる方法。広大な3D空間において衝突判定を行いたい場合、空間をいくつかの区画に分割して刈り込む、と言う方法を取る。
上記の衝突判定ではすべて、オブジェクト同士が衝突しているかどうかを「1フレームごと」にチェックする、つまり「離散的(Discrete)」な衝突検出法を用いた。1フレームごとにしか衝突判定を行わないことで、高速な衝突判定が行えるが、しかしこの方式を用いた場合、オブジェクトが速すぎてヒットボックスが1フレーム以下の時間で壁を通り過ぎてしまって衝突判定が行われない、トンネリング(いわゆる「壁抜け」)が起こりがちである。それを防ぐためには、1フレームごとに離散的に衝突判定を行うのではなく、連続的に衝突判定を行う「連続的衝突判定」(Continuous Collision Detection, CCD)と言う手法を取るのが一般的である。そのための最も一般的な手法がこれである。
オブジェクトを球体で近似する。この球が、現在の速度で直線的に動くと考え、「ある点」から「ある点」まで移動することで出来る軌跡を考える。この結果できた、カプセルのような形をしたボリューム(掃引体)のことを「球体スウィープボリューム(sphere-swept volume:SSV)」と言う。このボリュームが別のオブジェクトと接触していた場合、衝突が発生していると考えられる。