Simplestar Game

:::::::::::038話　衝突判定:::::::::::

3Dゲームの当たり判定、衝突判定って2Dと違って難しくなってくる領域ですよね。
今回は Bullet （ブレットよ呼ぶよ、バレットと間違えないでね）の衝突判定について勉強します。
状況に応じて、最適な当たり判定方法を選択できる予備知識を身につけたい！
そんな気持ちで、ドキュメントとサンプルコードを読み進めてみました。

こちら、036話のイラストを描いた日と同じ日に描いておいたものです。（いわゆるストック）
手前にある手を大きく描こうという気持ちで挑戦したのだけど、やっぱり難しいですね。

はい、すみません本題に戻ります。
まずこちらのドキュメントを最後まで読んでみましょう。

Bullet User Manual and API documentation

ああ、APIリファレンスまで全部読む必要はないです。
全部読みました？だいたい概要は理解できたと思うのですが
具体的に運用するにはサンプルを読んでみないとわからないですよね。
ということで、今回以降の入門講座は Bullet の
衝突判定　→　基本形状（衝突形状）　→　関節の使い方　→　ソフトボディ　→　オマケ（パフォーマンステスト）
の順番でサンプルソースを読解していこうと思います。

では今回は、「衝突判定」についてですね。
ドキュメントにて紹介がある通り、 Demo の Collision Demo から理解の突破口をつかみ
Simplex Demo → Collision Interfacing Demo → Gjk Convex Cast / Sweep Demo → Raytracer Demo
Continuous Convex Collision → User Collision Algorithm の順番で詳細を見ていくことにしましょう。

Collision Demo

ヘッダファイルは読んでもあまり意味ないですね。
以下のソースをもくもくと読み進めます…

実行結果は次のようになります。

ふむふむ、では解説をしていきたいと思います。
左側の小さいのが boxA , 右側の大きいのが boxB です。
initPhysics() 関数内で boxA を向かって左へ10[m]移動、boxBは原点配置。
大きさはそれぞれ一辺 2[m] と 8[m]としています。

あまりやっちゃいけないことだけど、グローバル変数の shapePtr 配列に
boxA, boxBの順でポインタを渡しています。（解放し忘れて、メモリリークを引き起こしそうな書き方だな…）

なんか関数の合間にグローバル変数として次の記述があるけど、これも普通やってはいけません。
可読性を下げますから…せめて、コメントほしいんだけど…

ちなみに "Perturbation" とは、物理用語の 摂動 《惑星などがその引力によって他の惑星などの運動を乱すこと》.を意味するらしい。

ひとまず、衝突物体の形状と姿勢が決まったので次のコードで描画しています。
描画コードはみなさんそれぞれ独自のものだから、このコードは正直何しているかわかればよいです。

今回の衝突判定の肝となる部分が以下のコード
物体の衝突を確認するための検出器の作成と、その使い方のコード部分です。

衝突形状を2つ登録して、使うときはそれぞれの姿勢行列を渡しているのがうかがえます。
getClosestPoints 関数で両者にとっての最近傍点を求めることができるようです。
なんとも、わかりやすいですね。

では、一体どんな情報が手に入ったのか具体的に見ていきましょう。
で確認しているコードが次の箇所でした。

m_distance には 5[m] の値が入っていました。
つまり、ボックスとボックスの間の距離 10 - (1 + 4) m が結果として与えられているわけ。
また、m_pointInWorld に入っている座標は boxB の面上の位置でした。（感覚とは逆のような気が…）
そして、m_normalOnBInWorld はその名前の通り
boxB の位置から、boxA への最近傍点へ伸ばした方向ベクトルの単位ベクトルを意味しています。

これで2つの形状の衝突判定方法が具体的になりました。
btGjkPairDetector に 2つの btConvexShape ポインタを渡して初期化し、任意の Solver を指定しておきます。
あとは ClosestPointInput 構造体のメンバにそれぞれの物体の姿勢行列を渡して、getClosestPoints 関数を呼ぶだけ！
gjkOutput には上記で確認した情報が入ります。
当たっているかどうかの判定は、 m_distance の値を見れば一目瞭然ですね。

試しに、boxA を向かって左へ 5[m] の位置に配置した場合は m_distance は 0[m] になりました。
boxA を向かって左へ 4[m] の位置に配置した場合は m_distance は -1[m] になりました。
まず、これだけで衝突判定、お互いの衝突までの距離を求めることができます。

続きのコードは初見の人には、正直わかりづらいです。
やっていることは boxA の姿勢を計算して描画し、そのときの最近傍点のペアを表示するというもの。
あまりのわかりづらさにイライラしたので
アニメーションしながら、最近傍点ペアを結ぶ線分を随時描画するものに書き換えてみました。
私と同じで残りのコードの理解が嫌な方は次の方法を試してみてはいかがでしょうか？

次の関数を入れ替えて実行します。（こっちの方がわかりやすいと思うんですよ！）

実行結果はこんな感じになります。

いかがでしたでしょうか？
Bullet の衝突判定の突破口をつかめましたでしょうか？

ここまでで出てきたのは、衝突形状のペアを設定して、それぞれの位置姿勢から
お互いのの最近傍点を求めるというものでした。
(キーワードは btGjkPairDetector です。)

SimplexDemo

こちらのデモは実行すると、四面体の表面から原点までの距離で最短のラインを描画するというものです。

そもそも Simplex って何なんでしょう。
ドキュメントの記述を読むと、どうも 1 から 4 点で作成されるオブジェクトのことを指していますね。
以下はドキュメントの記述そのまま。
This is a very low level demo testing the inner workings of the GJK sub distance algorithm. This calculates the distance between a simplex and the origin, which is drawn with a red line. A simplex contains 1 up to 4 points, the demo shows the 4 point case, a tetrahedron. The Voronoi simplex solver is used, as described by Christer Ericson in his collision detection book.

おわかり？
用途として、原点からの最近傍点を求めるのに使える感じでしょうか？
比較的高速に処理結果が得られるようですが
対象が四面体に限られると用途がすぐに思いつかないです。
ひとまず、こんな方法もあるということを覚えておこうと思います。

CollisionInterfaceDemo

衝突判定方法は、 btGjkPairDetector を使う方法だけではありません。
ほかにどんなものがあるのか、このデモで確認してみましょう。
かなり役立つ情報が満載なデモです。
ではデモのソースコードを読んでみてください。

相変わらずヘッダファイルに情報はありませんね。
引き続き実装を見てみましょう。

実行結果がこちら↓

今回新しくコールバック関数というものが登場していることを確認しましたでしょうか？
さっそく解説していきたいと思います。

お決まりの initPhysics() 関数で boxA (一辺 2 [m]), boxB （一辺 1 [m]）のボックスを衝突形状として作成して
これまたグローバル変数の btCollisionObject 配列にそれぞれ順番に([0]と[1]に)設定しています。
(今回はシェイプのポインタを渡さず setCollisonShape 関数で衝突オブジェクトにシェイプを設定していますね。)
あとは btCollisionWorld を btDefaultCollisionConfiguration, btCollisionDispatcher, btAxisSweep3 から作成しています。
だんだん World の作り方に慣れてきたころでしょうか。

今回の肝となる部分がこちら↓　(ソースにはハイライトを入れておきました。)

struct btDrawingResult : public btCollisionWorld::ContactResultCallback

日本語だと接触の結果通知構造体？（いやいや、英語のままでいいですね。）
これを継承している btDrawingResult 構造体のメンバ関数 addSingleResult をオーバーライドして
第一引数に入っている結果より、boxA, boxBの接触点の位置を取り出し、これを結ぶ線分を描画しているんです。
（どういう訳かAPIリファレンスにこの構造体の情報が無いんですよね…比較的新しい情報なんでしょうか？）

どこにも説明が無いので、想像になってしまいますが btManifoldPoint には、両接触点の位置と接触深度が入っています。
第2引数以降は名前から察するに、boxA, boxB のオブジェクト情報と
btCollisionWorld におけるそれぞれのインデックスでしょうね。

この構造体の使い方は簡単、次のように contactTest の引数に参照を渡すだけです。

指定したオブジェクトが「何か」（もちろん衝突物体ですが）に接触していれば、コールバック関数が呼ばれる仕組みです。
呼ばれる回数は接触点の数だけ呼ばれます。
コメントアウトしているコードに注目してください
これは、2つのオブジェクトを指定してその接触結果をコールバックする場合の方法です。
つまり btCollisionWorld::contactPairTest を使えばOKということ。

そのほかのコードを読んでみましたが、オブジェクトの移動と回転の制御をしているだけなので
特に解説する必要はない感じです。

さて、ひときわ興味深いのは #if 0 で論理的に到達できないコードの部分です。
こちらを通るようにすると、結局のところ contactTest と同じ結果が得られます。
使い方の利点は、コメントにある通り btCollisionWorld に登録していなくても結果が得られるという点です。
その他の利点は接触点ごとにループ処理を書けるので、細かい対応はこちらの方が簡単に行えそうです。

気になる使い方はこんな感じ↓

今回の結果を得たいだけならば、 numManifolds でループせずとも
btPersistentManifold* contactManifold = contactPointResult.getPersistentManifold();
で得た2つのオブジェクト間の接触結果で十分でした。
この辺、もう少しコメント書いておいてほしいですよね…まったく、わかりづらいったらありゃしない！

とにかく！ここからわかるのは world の dispatcher から オブジェクト間のアルゴリズムさえ取得できれば
アルゴリズムの processCollision 関数で2つのオブジェクト間の衝突判定結果が得られるということ。
また、 getAllContactManifolds を使えばアルゴリズムが処理するすべての接触点処理ができるというわけです。
便利便利！
ちなみにエントリポイントがコチラ↓

いかがでしたでしょうか？
今回の CollisionInterface デモで知ることになった衝突結果を取得する方法を以下にまとめます。
btCollisionWorld::ContactResultCallback を world に登録して
contactTest または contactPairTest でコールバック関数 addSingleResult が呼ばれるというもの。
オーバーライドしておけば、任意の処理がそこで行えるようになります。
（当たった時だけ反応する系のアクションに向いているコーディングですね。）

もう一つは world の dispatcher から オブジェクト間のアルゴリズムを取得し
processCollision で2つのオブジェクト間の衝突結果を取得する方法です。
(getAllContactManifolds でアルゴリズムが処理するすべての接触点判定の取得もできます。）

はい、ということで
この調子でもっといろいろなケースの衝突判定結果の取得方法を見ていきましょう。

Gjk Convex Cast / Sweep Demo

このデモ、ドキュメントを読む限りでは、事前に衝突を検知して、衝突までの時間から
壁に沿って移動するキャラクターなどに使うと便利…と書かれています。
具体的にどうやるのか知りたいので、デモのコードを解読していきましょう。

いつもの通り、ヘッダは説明要らずなので飛ばしました。
これ読んで実行結果が予想できる人はすごいと思います。（私には無理…）
実行結果はこちら↓

では解説していきます。
最初の initPhysics 関数では、これまでの btCollisionWorld とは違い、
物理演算も行う btDiscreteDynamicsWorld を作成しています。

また、ゆらゆらと揺らめく地面のメッシュとして btBvhTriangleMeshShape を作っています。
これの作り方は簡単
btTriangleIndexVertexArray に頂点バッファとインデックスバッファを渡し
これを btBvhTriangleMeshShape のコンストラクタに渡すだけです。
btBvhTriangleMeshShape ですが、これは btCollisionShape を派生させて作ったクラスです。
一般的な話ですが dynamicsWorld にオブジェクトを追加するには、shape のほかに mass と transform を必要とします。
この操作については、次の関数を用いて行っていました。

戻り値には、実際に dynamicsWorld に追加した剛体へのポインタが返されています。
あとは、無数のボックスをあちこちに追加するコードが書かれています。
これも btCollisionShape の派生クラス btBoxShape を作成して上記の関数で dynamicsWorld へ追加しているだけですね。
ドキュメントを読んでいる方は知っていると思いますが
btCollisonShape は同じものを使うなら、使いまわし可能なのでコイツは一回の作成だけで十分です。

そして今回の肝となる btConvexcastBatch の登場です。
これはこのデモ用に作成されたクラスです。
定義がソースに書かれているので確認してみてください。
コンストラクタで、次の値を設定していますね。（本当、コメント書いていてほしいね…まったく！）

つまりですよ、コンストラクタでメンバの100本のレイ（図の緑色のライン）の発生源と照射先の位置を決定していたのです。

メンバ関数の move ですが、ここには x軸方向に往復させるだけの記述しか書かれていませんでした。

さてさて、注目すべきは cast 関数です。
btCollisionWorld::ClosestConvexResultCallback 構造体に、レイの開始位置と終端位置(btVector3)を渡してインスタンスを用意します。
次に X軸での回転を混ぜた（シェイプの底面がレイの方向と垂直になるようにした） from と to の姿勢行列(btTransform)を用意します。
あとは、 btCollisionWorld::convexSweepTest 関数にシェイプと一緒にこれらを渡します。

この関数は内部ですべての衝突オブジェクトと判定を行い、最初にヒットした位置の情報を構造体に入れるというものです。
Sweep って聞いてわかるかな？ from の位置から to へ向かってオブジェクトを移動させて
軌跡だけ見たなら如意棒（にょいぼう）のように衝突物体を伸ばしていく操作のことです。

ヒットしたかどうかは hasHit 関数で判定できます。
ヒットした位置は m_hitPointWorld, 法線は m_hitNormalWorld, 開始位置と終端位置までの長さに対する
ヒットした位置までの比は m_closestHitFraction に入ります。

以下、ちょっと冗長かもしれませんが、再度 Sweep Test について説明します。
さっきからレイ（線）と言っていますが、結局のところ指定したシェイプを sweep してヒットするか調べているわけで
厳密なレイではありません。また、sweep とはその方向への引き延ばしを意味します。
用途としてはやはり、進行方向にこのまま進み続けたら、どれくらいで衝突物体に当たるかを調べるときに使えそう
次に勉強するレイキャストとはまた違った「シェイプ」を考慮した SweepCast による衝突判定です。
使いどころがありそうなので、覚えておきましょう。

Raytracer Demo

衝突判定で一番やりたかったこと、それはレイキャスト判定です。
直線を引いて当たった衝突物体とその位置、法線を取得するというもの。
今回はそのレイキャスト判定について学びます。

ではさっそくデモのソースコードを確認してみてください↓

実行結果はこんな感じになります。

では、ソースコードにハイライトを入れている void Raytracer::displayCallback() 関数にご注目ください。
次のコードにて、一度画面をクリアした後にカメラ位置を始点に
すべての画素（ピクセル位置）に向かってレイを放っていることがうかがえます。

レイを放っている領域にはコーンと球とボックスの衝突物体が置かれていまして
オブジェクト全体が Y軸でゆっくりと回転していくようにコーディングされています。
衝突判定をこれら画素ごとのレイすべてに対して行い、衝突していた場合は法線方向から色を計算して画素の色を設定しています。
といったデモなので、どうやってその衝突位置と法線を求めたのか見ていきたいと思います。
lowlevelRaytest, singleObjectRaytest, worldRaytest 関数の中身を順にのぞいてみましょう。

グローバル変数を利用しているから可読性は低いのですが、わかっていることだけお伝えします。
初期化の initPhysics 関数でグローバルの transforms 配列と shapePtr 配列は既に設定済みです。
それぞれには衝突形状のコーンと球とボックスの姿勢と形状情報が入っています。
それを踏まえて読んでいってください。
まずは当たり判定の対象の姿勢から getAabb 関数で AABB最小値と AABB最大値を取得しています。
AABBとは 境界ボックス：Axis-Aligned Bounding Box のことです。
AABBがわからない？接触しているかどうかを簡単に知るための図形でして、基本なのでここで覚えておきましょう。
ひとまず btRayAabb 関数を使って大域処理にてヒットする可能性を探ります。（AABB判定なので高速）

当たっているかもしれないとき(true を返したとき)、btSubsimplexConvexCast を作成しています。
コンストラクタで半径が0の球と当たり判定を行う形状、そして btVoronoiSimplexSolver を渡しています。

次に、レイの始点と終点姿勢と判定対象の始点と終点の姿勢(同じ姿勢を渡しているので今当たっているかどうかを返すはず)を
btConvexCast::calcTimeOfImpact 関数に渡して、詳細な判定結果を取得します。
この関数の戻り値はヒットしている場合 true を返します。
参照引数の btConvexCast::CastResult 構造体に目的のレイキャストの結果が含まれています。

さて、当たり判定を行うオブジェクトは一つではないので、一番最初にレイがヒットしたオブジェクトを特定するため
closestHitResults 変数を利用して判定します。レイの視点から衝突点までの比率が最も小さいものを選択するためです。
ワールド座標系における、衝突点の法線を求めるにはオブジェクトのベース行列をかけないといけない模様です。
この辺は、コードを参照してください。
びっくりする話、ワールド座標系における衝突点の位置はすっぽかしている模様。（なんてデモじゃ！）

そのほかのレイキャスト方法も気になるので
続いて singleObjectRaytest 関数を見てみましょう。

先ほどと違う点と言えば、btCollisionWorld::rayTestSingle で btCollisionWorld::ClosestRayResultCallback
を得ているあたりですね。hasHit 関数で詳細判定で当たっているかどうか調べています。
あれ？一番最初に当たったかどうかの判定が抜けてますね。
とにかく、最後に当たっていると判定した衝突物体との衝突点における法線を返します。
これは法線にベース行列を掛けなくて良い模様。

最後に worldRaytest 関数を見てみましょう。

btCollisionWorld::RayResultCallback 構造体を継承した構造体を定義し
addSingleResult 関数をオーバーライドしています。
この関数内を見てみると m_hitNormalWorld に結果を代入しているのがわかります。
これが使い方が一番単純でわかりやすいかもしれません
btCollisionWorld::rayTest 関数で コールバックを取得し
hasHit で衝突の有無を判断して、衝突点の法線を取得しています。
ただし、記述が簡単な半面、これは btCollisionWorld の衝突物体すべてに対して当たり判定を行っているため
これまで見てきた判定オブジェクトを指定する方法と違って、無関係の衝突物体が多数ある場合は
パフォーマンスが出ないと思います。

いかがでしたでしょうか？
レイキャスト判定にもいくつか手法があって、それぞれの具体的な使い方が明らかになったと思います。
レイキャストの実装の予備知識としてこの辺は忘れないようにしておきたいところですね。

次のデモは衝突予測に使えるデモです。
早速確認してみたいと思います。

Continuous Convex Collision

物体と物体がそれぞれ移動していて、あるとき衝突する現象を想像してください。
たとえば boxA が1秒後に回転しながら遠くに移動して、その進路を遮るように
boxBが横切るとします。それぞれの速度、回転速度が決まっていた場合衝突が予測できるでしょう。
いつ、どんな状況でぶつかるのか？
それを教えてくれるのが今回のデモです。

さて、今回のコードはそんなに長くないです。
上記のイメージで読んでみて下さい。

実行結果はこんな感じです↓

ピンク？色で表示されているオブジェクトが、始点と終点間を移動しているバーの軌跡（予測位置）です。
（白色の画面右上のバーが始点の姿勢ですね。中央のボックスも白色のが確認できると思いますが、
これは横切るボックスの始点の姿勢です。
ボックスも奥から手前に向かってゆっくり移動し、バーの進路を遮る形になっています。）

読んでその通りなのですが、次のコードでバーの開始位置と終了位置の姿勢を決定しています。

これを補間するように、速度と回転速度を求める便利機能が次の calculateVelocity です。

タイムステップごとに、姿勢を求める便利機能は次の integrateTransform ですね。

これで簡単に任意のタイムステップにおける物体の姿勢が取得できます。
アニメーションしている物体の姿勢予測には便利な機能かもしれませんね。

そして、今回の肝となる衝突位置を返すコードが次の箇所です。

btContinuousConvexCollision を衝突に使う２つのシェイプと任意の solver から作成し
２つのオブジェクトそれぞれの始点と終点の姿勢から calcTimeOfImpact 関数で衝突結果を取得します。
（衝突する場合、関数は true を返します。ていうか、この感じの使い方もう何回か出てきていますね。）
結果に入っている、始点と終点間の内分比を使って、衝突時のバーとボックスを描画しているコードも書かれていますね。
実行結果の緑色の物体が衝突時のバーで水色の物体が衝突時のボックスです。

そのほかのコードは、ボックスの開始と終点における回転を決めるものだったりします。
赤色の物体ですが、これは rayResult1 を利用すると表示されます。
Drawer を渡しているでしょう。それが原因です。
詳細についてはドキュメントが無いからAPIリファレンスでソースを追わないとちょっとわかりません。
興味があったら調べてください。（あんまり重要ではないです。）

ビリヤードの球が当たる場所を予測して表示するとか、使い方は考えればいろいろありそうなデモですね。
今回の衝突予測判定方法も、覚えておこうと思います。

User Collision Algorithm

衝突判定のアルゴリズムをユーザから設定することもできます。
厳密な判定ではなく、速度重視のものに変更するなど、パフォーマンスを求めるときなどに
あったらいいなと思う機能です。

サンプルでは球体同士の当たり判定にユーザ独自のアルゴリズムを設定する例が示されています。

実行結果はこんな感じになります。

とても自然なシミュレーション結果です。
コンピュータ言語が苦手な方も、物理に強い理系の方であれば興味湧く分野ではないでしょうか。
どっちもダメと思っている方は、勉強を始める良い機会ととらえてください。
私が両方ダメな人間なので今回を機に勉強してみようと思います。
（しばらくユーザアルゴリズムは使わないから、あとでまたここを更新すると思います。）

衝突グループの設定（フィルタリング）

追記です。最後に衝突グループの設定について説明します。

一通り Bullet について勉強して、いざ使ってみようと思ったら
お互いに衝突判定してほしくないシェイプが隣接するという問題に、いきなり直面してしまいました。
たとえば、指の関節一つ一つに円柱または四角柱のシェイプを設定したとして、ヒンジ結合で
回転角度を指定して動作させるとお互いぶつかりますよね。
こんな状況は、お互いに衝突判定を行ってほしくないです。

そこで必要になってくるのが、衝突判定を行わないシェイプ同士を設定する方法です。（グループ設定といいます。）
ではそのグループ設定というものを確認してみましょう。

特に説明の必要はないですね…、そう登録時に第2,3引数にグループと、マスクを指定するだけなのですから。
衝突判定を行うかどうかの判定には次のビットフラグ一致判定が使われます。

& 演算子はお互い同じ桁のビットが立っているか調べるものです。
判定方法からわかる通り、登録時に衝突判定したくないグループのビットをマスク指定にて伏せること
こうすることで、そのビットのみ立っているグループオブジェクトに対して衝突判定を行わなくなります。

重要度、使用頻度ともに高い機能ですので、今後忘れないようにします。

まとめ

ひとまず衝突判定関係のデモを一通り眺めたところで、今回の衝突判定のお話を締めくくりたいと思います。
次は、さまざまな衝突物体の導入方法について確認する予定です。
お楽しみに！

2011/08/21 初記。
2011/10/16 更新。