衝突判定
As an example, consider two triangles moving in time v 1 ( t ) , v 2 ( t ) , v 3 ( t ) {\displaystyle {v_{1}(t),v_{2}(t),v_{3}(t)}} and v 4 ( t ) , v 5 ( t ) , v 6 ( t ) {\displaystyle {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 ) {\displaystyle P(u,v,w)} is the plane going through points u , v , w {\displaystyle u,v,w} in R 3 {\displaystyle \mathbb {R} ^{3}} then there are twenty planes P ( v i ( t ) , v j ( t ) , v k ( t ) ) {\displaystyle 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.
バイナリ空間分割木(Binary space partitioning, BSP木)を用いる方法。広大な3D空間において衝突判定を行いたい場合、空間をいくつかの区画に分割して刈り込む、と言う方法を取る。
衝突判定を取りたい双方のオブジェクトを「四角い箱(矩形、ボックス)」で梱包することを考える。この「四角い箱」のことを一般的に「境界ボックス(バウンディングボックス)」と呼ぶが、ゲーム業界では「ヒットボックス」と呼ぶ。以下に述べるのは、ヒットボックス方式を用いた衝突判定の「基本的な方法」である。
2D空間において、それぞれの矩形を座標(x, y) と幅・高さ(lx, ly) で表す。ふたつの矩形A・矩形B について衝突判定を行うには、以下の条件が成り立っているかどうかを調べる。成り立てば当たり、そうでなければ外れと判定できる。
( A x ≤ B x + B l x ) ∧ ( B x ≤ A x + A l x ) ∧ ( A y ≤ B y + B l y ) ∧ ( B y ≤ A y + A l y ) {\displaystyle (A_{x}\leq B_{x}+B_{lx})\land (B_{x}\leq A_{x}+A_{lx})\land (A_{y}\leq B_{y}+B_{ly})\land (B_{y}\leq A_{y}+A_{ly})}