衝突判定のアルゴリズムの話2

前回の続きです。

アルゴリズム

一般に多面体同士の衝突判定手法では、点と面の判定や線と線の判定といったように、衝突の種類により衝突判定のアルゴリズムが異なります。また、その衝突後の挙動のシミュレーションを行うには衝突の際に生じる力を評価する必要もあり、これも当然衝突の種類により異なります。またアルゴリズムの脆弱性から、しばしば物体が互いに貫通するような現象が生じ、これを防止するためには積分の時間刻みを調整する必要がありますが、時間刻みに関しても明確な指針を示すことは困難です。ゲームにおいては衝突判定の精密性よりもリアルタイム性が重視されるので、以下のような手法がよく用いられます。

■ヒットボックス方式

衝突判定を取りたい双方のオブジェクトを「四角い箱（矩形）」で梱包するします。この四角い箱を一般的に「境界ボックス（バウンディングボックス）」と呼びます。2D空間においては、それぞれの矩形を座標(x, y) と幅・高さ(lx, ly) で表し、2つの矩形A・Bで衝突判定を行います。3D空間においては、双方のオブジェクトを「直方体」とみなし、幅・高さ・奥行き(lx, ly, lz) で表します。

ヒットボックス方式の主な実装方法は、上で述べた他に、境界球方式、AABB方式、OBB方式、凸包方式、などがあります。後者に行くにしたがって精密な衝突判定が行えますが、計算コストが大きくなり、特に凸包方式はゲームではまず使われません。

■軸並行境界ボックス方式（AABB方式）

特に3D空間で衝突判定を取る場合において、上記の方式では管理が面倒になる場合は「軸並行境界ボックス方式(Axis Aligned Bounding Box, AABB方式)」を使います。

ヒットボックス方式の基本的概念は、オブジェクトのバウンディングボックスの左上の点をオブジェクト自体の座標とみなし、そこから右下までの長さを取るのが一般的です。対してAABB方式では、ヒットボックスの中心座標をオブジェクト自体の座標とみなし、そこからxyz軸方向に±何mの広がりがある、という方式で表します。

■境界円・境界球

ヒットボックス方式の一種で、衝突判定を取りたい双方のオブジェクトを「円形」または「球形」とみなします。円を中心(x,y)、半径 r で表すと、二つの円 A, B が当たっていることは「Aの中心とBの中心の距離が、Aの半径とBの半径の和以下である」ことと同値です。これに基づき判定します。

■バーチャファイター方式

複雑な形状のポリゴンモデルの衝突判定を行うとき、ポリゴンモデルを「複数の球の組み合わせ」とみなし、それぞれの球において衝突判定を行うことでオブジェクト同士の衝突判定を行うことができます。

■バイナリ空間分割木方式（BSP木方式）

バイナリ空間分割木（Binary space partitioning, BSP木）を用いる方法です。広大な3D空間内の衝突判定に使われ、空間をいくつかの区画に分割して刈り込むという方式です。

■球体スウィープボリューム（SSV）

上記の衝突判定ではすべて、オブジェクト同士が衝突しているかどうかを「1フレームごと」にチェックする離散的な衝突検出法です。1フレームごとにしか衝突判定を行わないことで、高速な衝突判定が行えますが、この方式を用いた場合、オブジェクトが速すぎて壁をすり抜けるトンネリングが起こります。それを防ぐためには、1フレームごとに離散的に衝突判定を行うのではなく、連続的に衝突判定を行う「連続的衝突判定」（Continuous Collision Detection, CCD）と言う手法を取るのが一般的です。その最も一般的な手法がSSVです。

SSVではオブジェクトを球体で近似します。この球が、現在の速度で直線的に動くと考え、「ある点」から「ある点」まで移動することで出来る軌跡を考えます。この結果で生まれたカプセル形の「球体スウィープボリューム（sphere-swept volume:SSV）」から衝突有無を判定します。ただし、物体の角運動を無視しているため、回転運動をしているオブジェクトではやはり「壁抜け」を起こしやすい欠点があり、またかなり計算機負荷の高い手法であるため、大量のオブジェクトが存在する状況では計算量が増大し、オーバーヘッド（処理落ち）が発生する懸念があります。

■投機的連続的衝突判定（投機的CCD）

前述の、球体スウィープボリュームを用いた連続的衝突判定では、物体が等速直線運動を行うものとして、物体の角運動を無視しています。特に回転運動が多いピンボールゲームでは致命的な結果となります。これを防ぐために、投機的連続的衝突判定（投機的CCD）法があります。

投機的 CCDは、オブジェクトの直線運動と回転運動の両方に基づき、最小の軸平行バウンディングボックス (AABB) を拡張します。このアルゴリズムは潜在的な接触を取得するため投機的（事の成否が不確実で冒険的）です。

■その他

・球と直方体で衝突判定を取る場合、双方を球か直方体で近似すると計算は楽でますが、見た目との誤差が大きくユーザーが不満を抱きます。これらを緩和するため、直方体を楕円形で近似して衝突判定を行う方法があります。

・複雑なポリゴンモデルの衝突判定を取る場合、複数のポリゴンを一つのポリゴンとみなして衝突判定を行ったり、一旦ボクセルに変換して衝突判定を行う手法があります。また、投影像の画素ごとの奥行き値を比較して衝突判定を行うという手法もあります。

・「壁抜け」を防ぐために、単に「フレームレートを限界まで上げる」という手法があります。

参考文献
・https://ja.wikipedia.org/wiki/衝突判定

・西川善司、https://gamemakers.jp/article/2023_03_03_30379/

・原田隆宏、越塚誠一、布と高解像度のモデルとのリアルタイム衝突計算、情報処理学会論文誌、Vol.48、No.4

・ 三枝太、森島繁生、ダイナミックスモデルに基づく頭髪の運動表現 、情報処理学会研究報告グラフィクスとCAD（CG） 、Vol.1997、No.98