衝突検出：原理、手法、応用

主な手法と表現

実用的な衝突検出では、処理をブロードフェーズとナローフェーズに分ける。ブロードフェーズ手法は、互いに離れたオブジェクトの組を高速に除外する。ナローフェーズのアルゴリズムは、候補となった組を詳細に調べる。代表的な表現とアルゴリズムには、次のものがある。

• 境界ボリューム：高速な除外判定に用いる、軸平行境界ボックス（AABB）、有向境界ボックス（OBB）、球、k-DOPなど。
• 階層構造：複雑なメッシュを木構造に編成し、問い合わせを高速化する境界ボリューム階層（BVH）など。
• 空間分割：衝突の可能性がある領域を局所化する、一様グリッド、四分木・八分木、BSP木など。
• スイープ・アンド・プルーンおよびソート・アンド・スイープ：時間的コヒーレンスを利用し、重複する区間を効率的に見つける手法。
• 厳密な幾何学的判定：精密なナローフェーズ検査のためのGilbert–Johnson–Keerthi（GJK）アルゴリズム、分離軸定理（SAT）、三角形同士の交差判定など。

実装と性能上の考慮事項

衝突システムの設計では、速度、精度、堅牢性の均衡を取る必要がある。ゲームのようなリアルタイム用途では、近似的で高速な判定と、積極的なブロードフェーズでの候補削減が重視される。一方、航空やロボティクスなど安全性が重要なシステムでは、信頼性の高い検出と、物体が高速に移動した際のすり抜けを避ける連続衝突検出が重視される。数値的安定性、退化した幾何形状の扱い、物体が変形または移動する際に一貫性のある高速化構造を維持することは、一般的な工学上の課題である。

歴史と発展

衝突検出は、コンピュータグラフィックスおよび制御システムとともに発展してきた。計算幾何学とロボティクスにおける初期の研究は、交差判定の基礎となる手法を確立した。インタラクティブな3次元グラフィックスと物理シミュレーションが1990年代から2000年代にかけて広く普及すると、エンジン開発者や研究者は、リアルタイム制約や複雑なシーンに対応するため、高速化構造とアルゴリズムの種類を拡充した。

応用と例

衝突検出は多くの分野で利用される。

• インタラクティブエンターテインメントとシミュレーション：ゲームエンジンにおけるヒット、接触、環境との衝突の検出。
• ロボティクスと自律システム：安全な運動計画と障害物回避の確保。
• 工学とCAD：アセンブリの干渉チェックと仮想試作。
• 航空宇宙および輸送の安全：移動する物体間で起こり得る競合の監視。
• 科学シミュレーション：分子ドッキングと粒子衝突の解析。

実際の実装やライブラリについては、より詳細な記事や、オープンソースライブラリのリポジトリなどの技術的な概説とツール集を参照できる。

関連概念と区別

衝突検出は衝突応答とは異なる。検出は衝突が発生するかどうかを答えるのに対し、応答は力、衝撃量、または補正運動を計算する。さらに重要な区別として、固定時間ステップで確認する離散衝突検出と、運動中の最初の接触時刻を求める連続衝突検出がある。堅牢なシステムでは、複雑な場合や退化した場合を確実に扱うため、複数の判定とフォールバック戦略を組み合わせることが多い。