オクルージョンクエリによる衝突判定の問題点

前のページまでの説明で、今回の手法について良い点しか挙げていませんでしたが、いくつか目をつむっていた注意点があるので補足します。

衝突判定結果が遅延する

WebGLQuery共通の注意点ですが、クエリ結果を取得できるのは数フレーム後ですので、実際の衝突から判定は少し遅れます。衝突判定の結果を他の情報と組み合わせてなにかするときは、他の情報と時間軸が異なっている場合に意図せぬ齟齬が発生することがあるので注意が必要です。

描画命令が増える

今回の手法は深度テストのみのために、設定を変えて判定対象のオブジェクトを2回ずつ余計にレンダリング(A→B、B→A)しているため、衝突判定を行わない場合と比べると、描画命令数が3倍になります。これがこの手法の衝突判定のコストですので、CPUで計算した場合と比較して負荷が妥当かどうか、というところです。処理内容自体は深度テスト専用のシェーダーを使えばライティングなどのフラグメントシェーダーの処理はほぼなくなり、頂点の変形(視点/姿勢/透視投影変換+スキニング変換)と描画命令自体の負荷がコストとなってきます。

また、今回は2つのオブジェクトのみで衝突判定を行いましたが、判定するオブジェクトが増えると、オブジェクトのペアはO(n^2)で増えるので、処理負荷も二次関数的に増加します。これはもちろん今回の手法に限らず衝突判定自体の特徴ですが、今回の手法では増えるのが描画命令数なので、あまりに増えるのは少し心配です。CPUを使って、バウンディングボックスや空間分割などの従来の手法で衝突する可能性のあるペアを荒くフィルタをしておいて、この手法で詳細に調べることも可能です。また、形が単純だったり重要度の低いオブジェクトはバウンディングボックスだけで判定するのもいいでしょう。

衝突箇所はわからない

今回の手法では、ANY_SAMPLES_PASSEDクエリですべてのピクセルが深度テストに失敗したかどうかをもとに判定しているため、オブジェクトのどの部位で(あるいはどのピクセルで)衝突が発生しているのかはまったくわかりません。たとえば敵キャラクターへの攻撃が当たったときに攻撃方向の反対へ吹き飛ばすような演出を行いたいとしましょう。キャラクター同士の基準座標(衝突判定は遅延していることにも注意が必要かもしれません)をもとに吹き飛ばす方向を計算することはできますが、それは本当の衝突点とモーメントではないので、場合によってはリアリティが減るかもしれません。回転する軌道の攻撃だった場合でも必ず後ろへ吹き飛んでしまいますので、なにか別の情報(たとえば攻撃中の技ごとに吹き飛ぶ方向や回転の支点を設定しておく)と合わせて判定するなどの対策を考えるとより演出力が増します。

また、今回の衝突判定に限った問題ではありませんが、単純にキャラクター同士の衝突判定だけでは両方のキャラクターが同時に攻撃をした場合に、どちらのキャラクターの攻撃が当たったのかもわかりません。攻撃判定をもったオブジェクトを別につくり、その攻撃判定と相手キャラクターのペアでそれぞれ判定する方法がありますが、衝突判定を行うべきオブジェクトが増えると描画命令数がどんどん増えることには注意が必要です。

今回のロジックで正しく衝突検知できないケースとその改善策

実は、前のページで解説したロジックをそのままに実装すると、いくつかのケースで判定に問題が発生します。まずは最初のページで紹介したデモを再掲します。ただし、ロジックは前のページそのままにしているため、最初のページのデモとは判定方法が少し異なります。これを「判定タイプ1」とよぶことにします。どのようなケースで問題となるかみてみましょう。

オクルージョンクエリを使用した衝突判定:デモ画像

衝突を検知できるのは視点内のみ

今回の手法ではオブジェクトを描画したときの深度テスト結果をもとにするので、オブジェクトの一部でも、スクリーンに描画されなかった部分については、衝突を検知できません。変な言い方ですが見えている範囲しか見えないので、画面外で衝突していてもわからないわけです。この問題は、カメラがオブジェクトに寄りすぎると発生する可能性があります。これは従来のCPUベースの方法では発生しなかった問題です。

上記のデモでは、状態①(判定タイプ1)のような視点の場合にこの問題が発生します。カメラを引くとようやく衝突していることに気づき、オブジェクトが光ります。

カメラ外で衝突している場合に発生する判定の問題の解決策

この問題を解決できないか考えてみます。本来オブジェクトが衝突しているかどうかは視点に依存しないはずなので、衝突判定のためのオクルージョンクエリを使用する深度テストのステップは、どの視点からでも実行できるはずです。それならば、実際に画面表示するためにオブジェクトを描画する視点(描画用カメラとぶことにします)とは別の視点からテストを行う方法が有効そうです。テストをする視点(深度用カメラとします)は全体を見るように引いた場所に固定しておきます。こうすれば描画用カメラがどれだけ寄って視点外で衝突していても、深度用カメラ内に衝突が写っていれば検知が可能です。判定タイプ1のデモにこの対応を追加してみました。

z = 60の場所に深度用カメラを固定配置し、中心を向くようにしてあります。さきほどとまったく同じ視点の状態①(判定タイプ2)で、衝突を正しく検知できています。注意点として、あまりに引いた場所に深度用カメラを配置すると、深度バッファに描画されるオブエジェクトの解像度が小さくなります。解像度が小さいと、描画されるオブジェクトの形状は簡易化するので、意図しない衝突判定となることがあります。今回はやっていませんが、広い空間で判定を行いたい場合は、ある程度描画用カメラに追従しつつ、寄り過ぎないように少し後ろになるように深度用カメラを動かすのがいいかもしれません。

凸型でないオブジェクトは正確に判定できないことがある

これが一番大きな問題です。実は、衝突条件を考えるときの説明でこっそり「凸型の立体を考え」という条件を出していました。凸型の立体とは、凹んだ部分(面同士の成す外角が180°未満となる部位)や穴がまったくないものを指します。たとえば、3Dライブラリで「プリミティブ」とよばれる基礎立体の中では直方体(Box/Cube)や球体(Sphere)がこれに当たります。ドーナツ(Torus)は穴があいているので凸型ではありません。簡易デモの猿(Suzanne)も、耳やあごに鈍角があり、凸型ではありません。

今回の手法は、凸型の立体同士の衝突判定でないと正確な衝突検知はできません。どういうことか図示すると、非凸型立体の場合、本当は衝突していなくても衝突条件①’「視点から見てAの表面よりBの裏面が奥にあるピクセルが1ピクセル以上ある」かつ②’「視点から見てBの表面よりAの裏面が奥にあるピクセルが1ピクセル以上ある」を満たしてしまうケースがあるのです。

ケース4 Aと非凸型立体Bが接触していない場合に正しく判定できるか

このように、視点から見て凹型のオブジェクトに他方が入り込んでいる場合、衝突していないにもかかわらずクエリ結果は両方とも1になります。 ケース4:衝突していない非凸型オブジェクトの場合にA→Bの順番で描画したときのクエリ結果 ケース4:衝突していない非凸型オブジェクトの場合にB→Aの順番で描画したときのクエリ結果

ケース5 Aと非凸型立体Bが接触していない場合(別視点)に正しく判定できるか

同じ状態を別の視点から見た場合、視線の方向によっては「衝突していない」と正常な判定になることもあります。

ケース5:衝突していない非凸型オブジェクトの場合に別の視点でA→Bの順番で描画したときのクエリ結果 ケース5:衝突していない非凸型オブジェクトの場合に別の視点でB→Aの順番で描画したときのクエリ結果

残念なことに、凸型立体は非常に稀な属性で、単純な形の立体しかありません。3Dソフトでモデリングするような3Dオブジェクトで凸型立体になるものは皆無です。判定タイプ1のデモでも状態②(判定タイプ1)のような視点の場合にこの問題が発生します。カメラを動かすと衝突していないことがわかるのですが、視点に沿ってオブジェクトA→オブジェクトB→オブジェクトA(あるいはB→A→B)と並んでしまうピクセルがある場合に偽陽性を起こします。

さらには、直線上でオブジェクトが他方に挟まれていなくても、オブジェクトA→オブジェクトBとなるピクセルとオブジェクトB→オブジェクトAとなるピクセルが視点内に混在するだけでも衝突を誤検知します。状態③(判定タイプ1)のような視点の場合です。非凸型立体について、今回の手法で正確な検知ができるのは非凸型立体を囲む最小の凸型立体の範囲のみで、凸部分に他方のオブジェクトが入り込むと視点によっては誤検知してしまい、別の視点では正しく検知できるのでやっかいな問題です。

非凸型立体で発生する衝突判定の問題の解決策

解決策を考えてみます。視点によっては誤検知するのであれば、先ほどのように深度用カメラを描画用カメラと分けてみます。判定タイプ2の方式であれば、状態②(判定タイプ2)状態③(判定タイプ2)も誤検知せず、正しく非衝突と判定できています。しかし、判定タイプ2はZ軸方向の視点で深度用カメラを固定しただけなので、状態④(判定タイプ2)のような場合にはZ軸方向でオブジェクトが他方にはさまれた状態となり、誤検知となります。さらに、判定タイプ2では深度用カメラを固定しているので、描画用カメラをどう動かしてもずっと誤検知のままです。

深度用カメラの一部の視点で偽陽性となるなら、もうひとつ深度用カメラを追加してみるのはどうでしょうか? 衝突条件①’「視点から見てAの表面よりBの裏面が奥にあるピクセルが1ピクセル以上ある」と②’「視点から見てBの表面よりAの裏面が奥にあるピクセルが1ピクセル以上ある」を、2つの視点からそれぞれ行い、どちらの視点でも条件を満たしている場合のみ衝突しているとみなすわけです。2つの視点では運が悪いと誤検知となるケースはまだありそうですね。コップの上から他方が入り込んだ(そして接触していない)場合、水平方向と奥行き方向で条件判定を行っても、どちらの場合でも誤検知します。

結論として、対象が3次元なので、視点をもう1つ加えて3つの深度用カメラをXYZ軸の方向に向けてそれぞれ垂直に判定するよう配置してみました。これが今回の手法の完成形で、最初のページで紹介したデモと同じものです。

状態④(判定タイプ3)はもちろん、いままで問題となった状態①(判定タイプ3)状態②(判定タイプ3)状態③(判定タイプ3)すべてのケースを解決し、正しく衝突判定ができています。これで今回のデモについてはほとんどのケースがカバーできるようになったと思いますが、当然、これでも完全ではありません。やっぱり形状と方向によっては衝突していないのにしていると誤検知してしまうことはありますが、そのようなケースではもうほとんど衝突していると考えてしまっていいようにも思います。

この解決策ですが、深度カメラの視点を変えて3回チェックを行うので、当然描画命令が増えます。1つのペアのオブジェクト同士の判定につき、衝突判定チェック1回の場合(判定タイプ1/判定タイプ2)と比べて4倍、衝突判定を行わない場合と比べると6倍の描画命令が衝突判定のために余計に必要となります。実用に耐えられるかはシーンごとに異なるので、実際に確認してみるしかないでしょう。同じ頂点変換を何度も行うので、以前紹介したTransform Feedbackですべての頂点についてスキニング計算まで行った状態で頂点バッファに書き戻しておけば、1フレーム内で同じ計算を何度もする必要はなくなるので有効かもしれません。

参考文献

オクルージョンクエリを使用した衝突判定の手法、説明について、下記の書籍を参考にしています。