ゲームシーンにおいて、オブジェクト同士の衝突判定はリアリティの演出に欠かせない要素です。衝突判定はキャラクターの攻撃のヒット判定や物理演算、地面や障害物との接触判定など、さまざまな用途で使用されます。これほど身近な衝突判定ですが、正確性や負荷をきちんと考慮するのはなかなか難しく、妥当な方法の実装・選定は開発者にとって悩ましい課題ではないでしょうか。
本記事では、ANY_SAMPLES_PASSEDの記事で紹介した「オクルージョンクエリ」を使って、従来の衝突判定の方法で発生しがちな課題 - 正確性、処理負荷、スキニング変形 - をある程度解決した、GPUベースの衝突判定の方法を紹介します。一般的にイメージされる従来の衝突判定の方法とは別のアプローチをしており、それゆえに使い所は選びますが、おもしろい発想だなと個人的には思います。プロジェクトに取り入れるかはさておき、このような方法もあるんだと引き出しを増やしてもらえれば幸いです。
オクルージョンクエリ（ANY_SAMPLES_PASSED）を使用した衝突判定のデモの紹介
まずはオクルージョンクエリを使用したGPUベースの衝突判定のデモを紹介します。スキニングアニメーションをする2つの3Dモデルが衝突（交差）しているとき、それを検知してモデルが光ります。3D空間をドラッグしてカメラを動かしたり、モデルの位置やアニメーション状態を画面右のUIで変更して、さまざまな条件で複雑なモデル同士が衝突を判定できていることを試してみてください。衝突判定の精度も粗いものではなく、ギリギリまで近づいても衝突判定されず、本当に接触してはじめて衝突判定されることが確認できると思います。
3Dモデル: glTF Sample Models | KhronosGroup
3Dにおける衝突判定の難しさ
3Dの世界ではオブジェクトの形状が複雑化し、正確な衝突判定の難度と計算負荷は2Dと比べて跳ね上がります。WebGLではオブジェクトは3つの頂点で構成される三角形の集まりですが、オブジェクト同士ですべての三角形（あるいは頂点）について衝突しているかどうかをまじめに判定しようと思うと途方もない作業になるでしょう。この方法にはかなり無理があるので、一般的にはもう少し工夫をします。
たとえばオブジェクトをぴったり覆うような直方体（バウンディングボックスといいます）を定義し、この直方体同士で簡易的に衝突判定を行う方法があります。直方体同士の衝突判定であれば低負荷で計算可能です。このような簡易的な判定方法は計算量の低減とトレードオフで正確性を犠牲にしており、衝突していないのにしていると判定したり、あるいはその逆で衝突していないのに衝突していると判定してしまうことがあります。
表現内容によっては、他にも問題が発生します。キャラクターなどの高度な3Dオブジェクトは、モデル自体が変形します。3Dモデルを目にする機会がある人は、「スキニングアニメーション」や、「ボーン」といった言葉を聞いたことがあると思います。3Dモデルの内部に人の骨のように疑似的な芯（ボーン）を通し、各頂点をボーンに関連付けます。モデリングソフトでアニメーションを作るときに、すべての頂点をいちいち動かしたりせず、このボーンを動かすことで自動的に関連付けられた頂点が肌（スキン）のようにボーンについてくるのがスキニングアニメーションです。
普通、このボーンにそったスキニングアニメーションの変形（頂点の移動）はGPU（頂点シェーダー）で行いますので、CPU側にはスキニング変形後の情報はありません。一方、衝突判定の計算はCPUで行われることが多く、そういった場合には変形前の情報で作られたバウンディングボックスをもとに計算してしまいます。これでは変形後の正しいモデルのポーズをもとにした判定をすることができません。この問題を回避するには、バウンディングボックスをあらかじめスキニング変形の最大領域を考慮して大きめに作っておく（さらに正確性を犠牲にする）か、スキニング変形をCPUでも行う（計算負荷が増す）か、いずれにせよマイナスを受け入れなくてはなりません。
あらためて先に紹介したデモをみてみましょう。バウンディングボックスによる判定のように、個々の3Dモデルを囲む直方体の領域（目には見えませんが）同士が接触した程度では衝突判定されないことがわかります。また、スキニングアニメーションによって変形したモデルであっても正確に変形後の最新状態を認識し、衝突の判定に使用しています。どのような仕組みでこの判定を実現できているのか、詳しくみていきましょう。
スクリーン空間で衝突条件を考える
3D空間にある2つのオブジェクトが衝突（交差）している場合、どういう状態になっているのか、描画後の結果から考えてみます。まずはスクリーン（Canvas）に描画された、ある1ピクセルに注目します。視点（カメラ）からスクリーンを見ているところをさらに横から見ると、2つのオブジェクト「A」と「B」の見え方は下記の9通りに分類されます。
- AもBも見えない（このピクセルにはAもBも描画されていない）
- Aのみが見える
- Bのみが見える
- Aが完全にBの前にある
- Aの中にBの表面が入り込んでいる
- Aの中にBが完全に入り込んでいる
- Bの中にAが完全に入り込んでいる
- Bの中にAの表面が入り込んでいる
- Bが完全にAの前にある
それぞれのオブジェクトは閉じた凸型の立体を考え、「[（左ブラケット）」は視点からみたオブジェクトの表面、「]（右ブラケット）」は裏面をあらわします。
このうち、AとBが衝突しているのは5〜8の4ケースです。この4ケースをA、Bそれぞれの面同士の関係であらわすと、①「Aの表面よりBの裏面が後ろにある」、かつ②「Bの表面よりAの裏面が後ろにある」場合となります。
これらの条件は逆に考えるとわかりやすいかもしれません。オブジェクトAとBのどちらも描画されているケースのみ考えると、ケース1〜3は除外します。①を満たさない、つまり「Aの表面よりBの裏面が前にある」場合は、Bが完全にAより前にあることになります（ケース9）。この場合は衝突していません。同様に、②を満たさず、「Bの表面よりAの裏面が前にある」と、Aが完全にBより前にある状態です（ケース4）。つまり、①と②の両方を満たしていれば衝突していますし、そうでない場合は衝突していません。
ここまではある1ピクセルにのみ注目していましたが、考えを拡張しましょう。同様に、すべてのピクセルについて確認し、この4ケースにあてはまるピクセルが1ピクセルでもあればAとBは衝突しているといえますし、1ピクセルもなければ衝突していないといえます。まとめると、①’「視点から見てAの表面よりBの裏面が奥にあるピクセルが1ピクセル以上ある」かつ②’「視点から見てBの表面よりAの裏面が奥にあるピクセルが1ピクセル以上ある」ことがオブジェクトAとBが衝突している条件となります。
「ある重なり条件に当てはまるピクセルが1ピクセル以上あるかどうか」というのは、以前紹介したオクルージョンクエリANY_SAMPLES_PASSEDでわかる、「深度テストに成功したピクセルが1ピクセル以上あるかどうか」に似ていますね。そうです、どうにかしてこの条件を深度テストに置き換えようというのが今回のオクルージョンクエリを使った衝突判定の戦略です。
深度テストと隠面カリングおさらい
ここで、WebGLの深度テストと隠面（フェース）カリングについておさらいしておきましょう。
深度テスト
深度テストは、描画するスクリーンの画面サイズと同じサイズの深度バッファ（値を保存しておく場所）を用意して、深度バッファのすべての内容を①「1.0」に初期化しておきます。オブジェクトを描画する際に、現在描画しようとしているピクセルについて、オブジェクトの深度値と深度バッファに保存されている深度値を比較するテストを②「行い」ます。描画しようとしているオブジェクトの深度値のほうが③「小さい」場合に深度テスト成功とし、④「深度バッファの値を更新」しつつそのピクセルをオブジェクトの色で⑤「塗りつぶします」。これをピクセルごとに行い、深度値が現在値より小さい（手前にある）場合のみピクセルを塗りつぶすことで、描画する順番に依存することなくオブジェクト同士の前後関係をピクセル単位で正しく表現します。
以上が一般的な深度テストの使われ方ですが、WebGLをはじめ多くの3D APIでは深度テスト機能はもう少し柔軟で、上記の説明のうちカッコ付きで番号を振った部分に関して、条件や値、実行有無を細かく個別に選択できます。
-
深度バッファのすべての内容を①「
1.0」に初期化
深度バッファの初期値は必ずしも1.0である必要はありません。0.0〜1.0の間で好きな値をWebGLRenderingContextのclearDepth()メソッドで設定しておくと、clear()メソッドに深度（DEPTH_BUFFER_BIT）を指定して呼び出した際に、その値で初期化されます。 -
深度値を比較するテストを②「行い」
深度テストを行うこともできますし、行わないこともできます。WebGLRenderingContextのenable()メソッドに深度（DEPTH_TEST）を設定すると深度テストが有効になります。無効にしたい場合はdisable()メソッドで設定できます。 -
オブジェクトの深度値のほうが③「小さい」場合に深度テスト成功
深度テストの成功条件はWebGLRenderingContextのdepthFunc()メソッドでいくつかの条件の中から選択して設定できます。描画しようとしているオブジェクトの深度値が深度バッファの値「未満」の場合に成功とするLESSや「以下」の場合に成功とするLEQUALが一般的ですが、逆に、「以上」の場合のGEQUALや、深度値に関わらず「常に」深度テスト成功とするALWAYSというのもあります。 -
④「深度バッファの値を更新」しつつ
深度テストに成功したときに、深度バッファに深度値を書き込むかどうかも選べます。WebGLRenderingContextのdepthMask()メソッドにtrueを渡せば深度バッファを更新しますし、falseを渡した場合は深度バッファを更新しません。深度テストをするのに深度バッファは更新したくないなんてことがあるのか？ と思うかもしれませんが、半透明のオブジェクトを描画する際に使ったりします。 -
そのピクセルをオブジェクトの色で⑤「塗りつぶします」
こちらは深度テストとしての機能ではありませんが、深度テストに成功したとき（もしくはそもそも深度テストを行わない場合）に、ピクセルを塗りつぶす（カラーバッファへ書き込む）かどうかも選べます。WebGLRenderingContextのcolorMask()メソッドの4つの引数でRGBAそれぞれについてtrueかfalseを設定します。すべての引数にfalseを設定すると、オブジェクトを描画しても画面上にはまったく変化があらわれません。深度バッファのみ更新したい場合にdepthMask(true)、colorMask(false, false, false, false)というような指定をします。
隠面カリング
不透明なオブジェクトの場合、視点から見て裏側（前を向いた人間でいうと背中）は描画する必要がありません。この描画を間引くことで負荷を抑えるのが隠面カリングです。ポリゴンはWebGLでは3つの頂点がつくる三角形ですが、この三角形が視点から見て時計回りで構成されているか、反時計回りで構成されているかで裏側かどうかを判断します。たとえば、オブジェクトやモデルを作るとき、外側から見て三角形をつくる頂点の順番がすべて反時計回りになるようにしておけば、視点から見た裏側は時計回りになります。時計回りの描画を省けば見える表側のみを描画できます。
WebGLRenderingContextのcullFace()メソッドにBACKを設定すると裏面をカリングして表面のみ描画します（バックフェースカリング）。FRONTを設定すると表面をカリングします（フロントフェースカリング）。裏面のみ描画することもできるわけですね。時計回りと反時計回り、どちらを表面として扱うかはfrontFace()メソッドで設定します。デフォルトではCCW（=CounterClockWise）、反時計回りが表面ですが、CW（=ClockWise）を設定すると時計回りの場合に表面として扱います。
次のページでは、深度テストを使ってスクリーン空間で考えた衝突条件をどのように判定するのか、実際のコードを交えて説明します。