三次元の衝突検出

二次元の衝突検出と同様に、座標軸に沿ったバウンディングボックス（axis-aligned bounding boxes、AABB）は、2つのゲームエンティティが重複しているかどうかを判断するための最も速いアルゴリズムです。 これは、ゲームエンティティを回転しない（つまり座標軸に沿った）ボックスで包み、三次元座標空間でこれらのボックスの位置をチェックして、それらが重なっているかどうかを確認することで構成されます。

軸配置の制約があるのは、パフォーマンス上の理由からです。回転していない2つのボックスの間の重複領域は論理比較だけでチェックできますが、回転したボックスではさらに三角関数の演算を運営する必要があり、計算にかかる時間が長くなってしまいます。回転するエンティティがある場合、外接ボックスの寸法を変更してオブジェクトを包むようにするか、球などの別の外接ジオメトリ タイプ（回転に対して不変）を使用できます。以下のアニメーション GIF は、回転するエンティティにサイズを合わせる AABB のグラフィック例です。ボックスは常に寸法を変化させ、中に含まれるコンテナーの中にぴったりとフィットします。

点が AABB 内にあるかどうかを確認するのは非常に簡単です。 点の座標が、AABB 内にあるかどうかを確認する必要があります。 各座標軸を個別に検討します。 P_x、P_y、P_z を点の座標、B_minX–B_maxX、B_minY–B_maxY、B_minZ–B_maxZ を 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 軸上で実行するテストを示しています。 基本的には、A_minX–A_maxX と B_minX–B_maxX の範囲は重複しているかです。

数学的には、これは次のようになります。

そして、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 の間のユークリッド距離が $\sqrt{(A_x - B_x) ^ 2) + (A_y - B_y)^2 + (A_z - B_z)}$ であることを考慮すると、点対球の衝突検出の式は次のようになります。

あるいは、JavaScript では、次のようになります。

function isPointInsideSphere(point, sphere) {
  // Math.pow を呼び出すよりも高速であるため、乗算を使用しています
  const 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;
}

球対球のテストは、点対球のテストに似ています。 ここでテストする必要があるのは、球の中心間の距離がそれらの半径の合計以下であることです。

数学的には、これは次のようになります。

あるいは、JavaScript では、次のようになります。

function intersect(sphere, other) {
  // Math.pow を呼び出すよりも高速であるため、乗算を使用しています
  const 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) {
  // クランプして球の中心からボックスの最も近い点を取得します
  const x = Math.max(box.minX, Math.min(sphere.x, box.maxX));
  const y = Math.max(box.minY, Math.min(sphere.y, box.maxY));
  const z = Math.max(box.minZ, Math.min(sphere.z, box.maxZ));

  // これは isPointInsideSphere と同じです
  const 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 の関連記事

• Three.js によるバウンディングボリューム衝突検出
• 2D 衝突検出

外部リソース

• Gamasutra のゲームのための簡単な交点テスト（英語）
• ウィキペディアのバウンディングボリューム（英語）