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

衝突判定とは

衝突判定とは「物体が別の物体に衝突したか」を判定するプログラム処理のことです。計算科学の問題に属します。ロボット工学、計算物理学、ゲーム、シミュレーションなど様々なコンピューティング分野で応用されています。

衝突判定の難点

衝突判定は常に監視する必要があり、負荷の大きい処理となりま。特に3次元形状はポリゴン(三角形、多面体)の集合で表現されるため、その運動解析にはポリゴン同士の衝突を検出し、適当な反発力を定義して干渉を防ぐ必要があります。他にも

■扱う物体が多い程、また形状が複雑なほど計算負荷が大きい
■多面体の場合、辺と辺、面と角、面と辺の接触など、様々なケースがある
■3D物体は自己交差、つまり境界以外の場所で交差する傾向がある（面がねじれていたり、ループ状に交差していたりする）
■布のように変形を伴う物体の衝突では、剛体の衝突判定と違って判定が複雑
■動体がフレームレート以上の高速で動くと、衝突判定を免れ、すり抜けてしまう

などの難点があります。

大雑把でも許される衝突判定

産業用、研究用のコンピュータシミュレーションでは、現実世界の物理現象を可能な限り正確にシミュレートする必要があります。しかし娯楽用のゲームにおいては、ハードの性能が許す範囲内でリアルタイム性を損なわず、かつバグが起きないようにすれば問題ありません。プレーヤーが十分満足する範囲内であれば大雑把に扱っても許されます。

ゲーム内の衝突判定

ゲームでは単純な事後衝突検出を採用しています。例えばキャラクターが壁にめり込んだ場合、めり込んでいなかった最後の場所まで戻すという処理があります。他にも壁にめり込まない距離までしか移動できないようにする、という処理もあります。

2Dゲーム時代では、処理するオブジェクトの数が限られていたため、全オブジェクトの衝突判定を行うことは簡単でした。画面にタイルパターンを設け、タイルパターンと自機のスプライト(※)が重なったかどうかをチェックするだけで十分判定が可能でした。（※スプライトとは、1画面の絵を構成する要素を複数の細かい画像にし、それらを画面上の任意の位置で合成して表示する技術です）

3Dゲームにおいては「空間をいくつかの区画に分割して刈り込む」という空間分割法、あるいは「3Dのオブジェクトをいくつかの球に分割してペアワイズチェックを行う」という方法があります。

高速物体の衝突判定

既に述べましたが、動体が高速で動くと衝突判定を免れてすり抜けてしいます。例えばシミュレーションが60fps（毎秒60コマ）で動作している場合、通常は60分の1秒（＝16.67ms単位）で衝突判定を取るのが一般的ですが、動体の動きが速すぎると16.67msの時間内で空間をワープしてしまい「すり抜け」となります。

この単純な解決策はシミュレーションの処理単位時間を狭めることです。ただしそれだけ計算負荷も大きくなります。別手法としては「1フレーム前の位置から、現在フレームの位置までの残像領域を考え、その残像領域が衝突しているかで衝突判定を行う」という考えがあります。移動軌跡を考えて、それが別の物体に接触しているか評価します。ただしこの手法も複雑で、一般的には直線移動(なおかつ加速度変化なし)で考えてしまうことがほとんどです。しかしこの考えでは、例えば放物線で動く、投擲運動では精度が荒くなってしまいます。また回転運動も考慮すると、単なる直線運動では不十分です。このように複雑な動作が介入する場面では、フレームレートを上げると容易に解決できます。

頭髪の衝突判定

ヒューマンインターフェースなどの分野において人間をよりリアルに表現するためには、頭髪の精密な再現が避けられません。しかし実際の物理現象に基づいて自然な頭髪の動きを再現しようとすると計算負荷が甚大です。

頭髪は極めて多くの糸状物体から構成されており、髪の毛一本一本について運動を制御するためには、 髪の毛一本一本を三角柱などによってモデル化する手法や、実測値に基づく確立モデルによって動きを求める手法、微小線分の振舞いを 「射影方程式」 を解き、それらを異方性反射モデルによってレンダリングする手法があります。これらの手法で問題をとなるのは、膨大な髪の毛を扱うことによる計算負荷の増大や記憶容量の増加です。 そこで頭髪を 「空間曲線」によって近似し剛体セグメントモデルを用いて運動を制御することで、少ない形状データでリアルに表現する方法があります。

また衝突判定としては、頭部を包むように疑似外力領域を設け、疑似外力の作用によって頭部内部への頭髪の進入を防ぐ手法、円筒座標系における頭部中心から表面までの距離をあらかじめ衝突判定用バッファとして用意しておく手法があります。前者は、特別な衝突処理が必要ない分計算が高速化されますが、厳密な衝突回避はなされていません。一方後者では、判定に要する時間は僅かですが、物体のそれぞれについて衝突判定用バッファを用意しなければならず、頭髪の座標変換も個々の物体について行なわなければなりません。

布の衝突判定

布もコンピュータグラフィックスにおいて様々なシーンで用いられます。例えば布を有限個の質点群で近似すると、衝突計算を行うためには布を構成する質点ごとに物体の各面に対して衝突判定を行う必要があり計算コストが高くなります。静止物体とのリアルタイム衝突判定は比較的容易に計算できますが、布が接している物体がすべて静止している状況は稀です。動きながら形状を変える物体と布とのリアルタイム衝突計算はいまだ困難な問題の1つです。

一般的なバウンディングボリュームを用いた衝突判定は、布などの変形する物体にも用いられます。しかし形状の変形に伴いバウンディングボリュームを修正もしくは再構築する必要があります。他にも布と衝突する形状をボクセルで表現し衝突判定を行う手法もあります。ただし物体の内外情報のみ持つボクセルを用いる場合は、衝突を回避するための、布に加えなければならない力を別に求める必要があります。

布に作用する力まで導出可能な手法としては、距離関数を用いた衝突計算があります。距離関数とは、ある空間において境界条件が与えられたときに境界の最近点までの距離を示す関数で、どのような物体の表面形状も表すことができます。衝突判定を行えるだけでなくこの関数の空間一階微分はその最近点に向かうベクトルであるため、衝突回避のために加えなければならない力のベクトルも求めることができます。

光子や水滴など粒子間の衝突判定

通常、シミュレーションでは粒子間の相互作用は計算負荷の増大をもたらすためほとんど無視されます。しかし粒子濃度が高くなると粒子同士の衝突が顕著になり、粒子問の衝突による粒子運動への影響が無視できなくなります。例えば曲管内のような空間平均的な濃度が低くても、局所的に高濃度が発生する場合は、粒子間の相互作用は避けては通れません。

一般的な粒子間の衝突判定は粒子間の距離を計算することにより行います。粒子間の距離が粒子の直径より大きければ衝突しておらず、逆に小さければ衝突しているとみなします。ただし、衝突判定の際に全ての粒子の組み合わせで距離を計算していたのでは粒子数Nに対してO(N^2)の計算量となり、計算コストが多大となります。そこでバケット法と呼ばれる領域分割を用いて近くにある粒子のみ距離を計算します。この処理により計算量はO(N1)となります。他にも、いくつかの粒子を一つの大きな粒子で代表してシミュレーションを行う手法があります。このように高負荷計算になりがちな粒子シミュレーションでは、いかに重要な部位のみ拾いあげ、不必要な情報を落とせるかが鍵を握ります。

上記の手法は決定論的な判断方法です。確率論的な方法も存在します。例えば気象シミュレーションでは、バルク法と呼ばれる雲微物理計算法が用いられます。バルク法では粒子を、水蒸気・雲水・雨水・雲氷・雪・霰の６カテゴリーに分類し、各計算格子点に含まれる混合比を計算します。またビン法と呼ばれる手法では、粒子径分布関数や衝突頻度因子、合体率を用いて水滴の衝突成長を評価します。

クォータニオンを用いた衝突判定

3次元の剛体の運動シミュレーションは一般に、剛体の位置、姿勢(回転)、運動量および角運動量を状態変数として微分方程式で表現します。また移動量だけでなく方向の情報も重要なためベクトルを用いて表現され、重心の位置ペクトル、3×3の回転行列、運動量ベクトル、角遅動量ベクトルで表されます。ただし、剛体の姿勢(回転)をオイラー角から計算された3×3の回転行列で表すと、シミュレーションが進むにつれて数値誤差が増大し、軸周りの回転に伴う誤差が大きくなってしまうなどの不都合が生じます。そこで回転行列のかわりに、ハミルトンによって考案されたクォータニオン(四元数)で表現します。クォータニオンは、1つのスカラーと3つのベクトル成分あわせて4成分を持ちます。

クォータニオンとは回転軸（ベクトル）と回転角（スカラー）よりなる４成分で、３次元空間の姿勢を表現します。クォータニオン表現ではオイラー角による回転表現で生じるような特異点（※）が存在しません。そのため、宇宙・防衛分野における飛翔体の姿勢計算には、伝統的にクォータニオンが用いられてきました。また、最近では3次元コンピューターグラフィックの分野でも物体を表示するためにクォータニオンが使用されています。

（※ジンバルロックとも言い、2つの回転軸が同じ向きになってしまったときに回転の自由度が1つ落ちてしまうことです。例えばy軸を90度回転させるとx軸と重なってしまい、そこから先はどう回転させてもx軸の回転ができなくなる問題です）

剛体の衝突応答について

剛体とは全く変形しない物体のことで実際には存在しません。実際の構造物の解析を行うには内部変形を計算する必要があり、ヤング率の高い硬い物体の場合はタイムステップを非常に小さくしなければならず、シミュレーションに多くの時間を必要とします。一方剛体は変形を考慮する必要がないため低コストとなります。その点で変形の無視できるような物体の近似として剛体シミュレーションは非常に有用です。

剛体衝突において衝突応答には主に3つの手法があります。1つは力積ベースの方法で、衝突時の速度から力積を求め速度変化を計算します。この方法を用いる場合、衝突が検出されるとその衝突が起こった時刻に戻り衝突応答を行う必要があります。

2つ目の方法は拘束条件を解く方法です。しかしこの方法は衝突の数をnとするとO(n^3)の計算量がかかります。3つ目の方法はペナルティ法で、剛体間に若干のめり込みを許容し、そのめり込み量に応じた反発力を加えるというものです。この手法は計算コストが低く、複数の衝突を同時に扱えるというメリットもあります。

参考文献
・https://ja.wikipedia.org/wiki/%E8%A1%9D%E7%AA%81%E5%88%A4%E5%AE%9A

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

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

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

・王宏、伊藤裕一、谷口伸行、非構造格子において効率的な粒子追跡法及び衝突判定法に関する研究(OS26c 乱流,反応流,混相流などの解析モデルと数値手法)、計算力学講演会講演論文集、vol.17

・大西領、高橋桂子、雲に見られる乱流現象–気相乱流中での微小水滴の衝突–、〔特集〕地球科学における流体現象２ ～地球表層編～

・坂本尚久、小山田 耕二、粒子ベースボリュームレンダリング、可視化情報学会論文集 Vol.２７ No.２

続きです。アルゴリズムの詳細について解説しています。