この記事では、3D 環境で衝突検出を実装するために使用されるさまざまなバウンディングボリューム手法の概要を説明します。 追求記事では、特定の 3D ライブラリでの実装について説明します。
2D 衝突検出と同様に、座標軸に沿ったバウンディングボックス（axis-aligned bounding boxes、AABB）は、2つのゲームエンティティがオーバーラップしているかどうかを判断するための最も速いアルゴリズムです。 これは、ゲームエンティティを回転しない（つまり座標軸に沿った）ボックスで包み、3D 座標空間でこれらのボックスの位置をチェックして、それらが重なっているかどうかを確認することで構成されます。
パフォーマンス上の理由から、座標軸に沿った拘束（axis-aligned constraint）があります。 回転しない2つのボックス間の重複領域は、論理比較のみで確認できますが、回転するボックスには追加の三角関数操作が必要であり、計算に時間がかかります。 回転するエンティティがある場合は、バウンディングボックスの寸法を変更してオブジェクトを包むか、球（回転に対して不変）などの別のバウンディングジオメトリータイプを使用することを選択できます。 以下のアニメーション GIF は、回転するエンティティに合うようにサイズを調整する AABB の図形例を示しています。 ボックスは常に寸法を変更して、内部に含まれるエンティティにぴったりとフィットします。
注: この手法の実際の実装については、Three.js を使用したバウンディングボリュームの記事を確認してください。
点が AABB 内にあるかどうかを確認するのは非常に簡単です。 点の座標が、AABB 内にあるかどうかを確認する必要があります。 各座標軸を個別に検討します。 Px、Py、Pz を点の座標、BminX–BmaxX、BminY–BmaxY、BminZ–BmaxZ を AABB の各座標軸の範囲とすると、次の式を使用して、2つの間で衝突が発生したかどうかを計算できます。
あるいは、JavaScript では、次のようになります。
function isPointInsideAABB(point, box) {
return (point.x >= box.minX && point.x <= box.maxX) &&
(point.y >= box.minY && point.y <= box.maxY) &&
(point.z >= box.minZ && point.z <= box.maxZ);
}
AABB が別の AABB と交差するかどうかのチェックは、点のテストと同様です。 ボックスの境界を使用して、座標軸ごとに1つのテストを実行する必要があります。 次の図は、X 軸上で実行するテストを示しています。 基本的には、AminX–AmaxX と BminX–BmaxX の範囲は重複しているかです。
数学的には、これは次のようになります。
そして、JavaScript では、これを使用します。
function intersect(a, b) {
return (a.minX <= b.maxX && a.maxX >= b.minX) &&
(a.minY <= b.maxY && a.maxY >= b.minY) &&
(a.minZ <= b.maxZ && a.maxZ >= b.minZ);
}
バウンディングスフィア（bounding spheres）を使用して衝突を検出することは、AABB よりも少し複雑ですが、それでもテストはかなり迅速です。 球の主な利点は、回転に対して不変であるため、包まれたエンティティが回転しても、バウンディングスフィアは同じままであるということです。 主な欠点は、包んでいるエンティティが実際に球形でない限り、包むのは通常適切ではないことです（つまり、バウンディングスフィアで人を包むと、多くの誤検知が発生しますので、AABB の方が適しています）。
球に点が含まれているかどうかを確認するには、点と球の中心との間の距離を計算する必要があります。 この距離が球の半径以下の場合、点は球の内側にあります。
2つの点 A と B の間のユークリッド距離が であることを考慮すると、点対球の衝突検出の式は次のようになります。
あるいは、JavaScript では、次のようになります。
function isPointInsideSphere(point, sphere) {
// Math.pow を呼び出すよりも高速であるため、乗算を使用しています
var distance = Math.sqrt((point.x - sphere.x) * (point.x - sphere.x) +
(point.y - sphere.y) * (point.y - sphere.y) +
(point.z - sphere.z) * (point.z - sphere.z));
return distance < sphere.radius;
}
上記のコードは平方根を特徴としており、計算にコストがかかる可能性があります。 これを回避する簡単な最適化は、距離の2乗と半径の2乗を比較することで構成されているため、最適化された方程式には、代わりに distanceSqr < sphere.radius * sphere.radius が含まれます。
球対球のテストは、点対球のテストに似ています。 ここでテストする必要があるのは、球の中心間の距離がそれらの半径の合計以下であることです。
数学的には、これは次のようになります。
あるいは、JavaScript では、次のようになります。
function intersect(sphere, other) {
// Math.pow を呼び出すよりも高速であるため、乗算を使用しています
var distance = Math.sqrt((sphere.x - other.x) * (sphere.x - other.x) +
(sphere.y - other.y) * (sphere.y - other.y) +
(sphere.z - other.z) * (sphere.z - other.z));
return distance < (sphere.radius + other.radius);
}
球と AABB が衝突しているかどうかのテストは少し複雑ですが、それでも単純で高速です。 論理的なアプローチは、AABB のすべての頂点をチェックし、それぞれに対して点対球のテストを実行することです。 ただし、これはやり過ぎです。 AABB の最も近い点（必ずしも頂点である必要はありません）と球の中心との間の距離を計算して、球の半径以下であるかどうかを確認するだけで済むため、すべての頂点をテストする必要はありません。 この値は、球の中心を AABB の限界にクランプすることで取得できます。
JavaScript では、次のようにこのテストを行います。
function intersect(sphere, box) {
// クランプして球の中心からボックスの最も近い点を取得します
var x = Math.max(box.minX, Math.min(sphere.x, box.maxX));
var y = Math.max(box.minY, Math.min(sphere.y, box.maxY));
var z = Math.max(box.minZ, Math.min(sphere.z, box.maxZ));
// これは isPointInsideSphere と同じです
var distance = Math.sqrt((x - sphere.x) * (x - sphere.x) +
(y - sphere.y) * (y - sphere.y) +
(z - sphere.z) * (z - sphere.z));
return distance < sphere.radius;
}
3D 物理エンジン（3D physics engines）は、衝突検出アルゴリズムを提供していますが、そのほとんどは、バウンディングボリュームにも基づいています。 物理エンジンが機能する方法は、通常はその視覚的表現に付属した物理的なボディ（physical body）を作成することです。 このボディには、速度、位置、回転、トルクなどのプロパティと、物理的な形状（physical shape）があります。 この形状は、衝突検出の計算で考慮されるものです。
このような手法が実際に動作していることを確認できるライブ衝突検出デモ（ソースコード付き）を用意しました。 これは、オープンソースの 3D 物理エンジン cannon.js を使用しています。
MDN の関連記事
外部リソース