OpenGLでゲーム向け3次元剛体シミュレーションをやる
最近こちらの本(以降参考書)を読みました。
タイトル通り、物理エンジンの内部でどのように剛体シミュレーションが行われているかについて解説している書籍となっています。一通り読み終わったので、復習も兼ねて軽く剛体シミュレーションについて解説しようと思います。
できたもの
公開されているサンプルコードを参考にしつつ、自分の環境でも剛体シミュレーションをやってみました。
シェーディングがおかしいことには目を瞑ってください...。
使ったライブラリ:
https://github.com/yubeneko/PhysicsSimulation
剛体シミュレーションとは
3次元空間にある剛体には重力がかかるので、何もしないと剛体は下に向かって落ちていきます。また、剛体が他の剛体と衝突した際はそれぞれの剛体が跳ね返り、速度や位置、姿勢が変化します(反発)。他にも、ある剛体を他の剛体の上で滑らせた場合に、滑っている方の剛体がなかなか停止しなかったり、すぐに停止したりします(摩擦)。
剛体シミュレーションとは、これらの物理現象をコンピュータでシミュレートすることを意味します。
データ構造
剛体シミュレーションでは1つの剛体を表現するために「形状」、「状態」、「属性」の3つのデータ構造が必要となります。
「形状」はその名の通り剛体の形状を表し、剛体同士の衝突検出に使用されます。衝突検出を簡単にするため、剛体の形状は基本的に凸形状で表現されます。剛体が凹形状である場合、いくつかの凸形状を組み合わせることで1つの形状を表すようにします。
「状態」は剛体の座標や並進速度、姿勢、回転速度といった情報を保持します。
「属性」は質量や慣性テンソル、反発係数などを保持します。
シミュレーションの流れ
剛体シミュレーションは1タイムステップ中に以下の処理を行います。
1. 外力の適用
重力などの剛体にかかる外部の力を剛体に適用し、時間積分により剛体の速度、回転速度を更新します。
2. 衝突検出
3次元空間内に存在する全ての剛体のペアについて衝突が発生しているかを調べます。このフェーズでは2つの剛体が衝突しているかどうかを調査し、衝突している場合はめり込み量(貫通深度)と衝突点の法線方向を求めます。この処理は剛体シミュレーションの中でもかなり重い処理で、特に凸メッシュ同士の衝突判定はポリゴン数が多いとめちゃんこ重たくなります。そのため、全ての剛体について衝突しているか詳しく調べようとするととても時間がかかってしまいます。そこで、一般的な衝突検出フェーズは、衝突しているかもしれないペアを検出し、その後でそのペアが本当に衝突しているかどうか詳しく調べるという二段構成にすることで効率化されています。それぞれ「ブロードフェーズ」、「ナローフェーズ」と呼ばれており、お互いにいくつかの手法が存在します。
ブロードフェーズでは主に軸平行バウンディングボックス(AABB: Axis-Aligned Bounding Box)が使われます。ブロードフェーズは3次元空間中に存在する剛体の数が少ないならば総当たりでも良いのですが、数が多くなってくると調べなくてはならないペアが増えてくるのでしんどくなってきます。その際は、スイープ&プルーンや AABB tree といった高速化のためのアルゴリズムを使う必要があります。
ナローフェーズでは、分離軸の理論に基づいた衝突検出法、GJKアルゴリズムといった手法が使われます。参考書では分離軸の理論に基づいた手法について説明されていました。この部分は数多くの数学から成り立っているためかなり難しいです。自分も完全に理解しきれていません。もっと詳しく知りたいならば以下の本あたりを読むと良いかもしれません。
https://www.amazon.co.jp/ゲームプログラミングのためのリアルタイム衝突判定-Christer-Ericson/dp/493900791X
値段高っけー。
3. 拘束演算
衝突検出フェーズにて衝突が検出されたペアは互いに並進速度と回転速度が変化します。これらを求めるのが拘束演算フェーズの役割です。まず、今のままでは剛体同士がめり込んだままになっているので、それを解消するような速度を剛体に与えなくてはなりません。他にも、衝突点の法線方向に対して直角となる2つの軸方向(摩擦方向)の速度も考慮する必要があります。これらの条件を満たすような数式をそれぞれの軸(衝突点の法線方向 + 摩擦方向 x 2 の 3つ)ごとに立てて、それらを解くことで並進速度と回転速度それぞれの増分を求めます。これらを前のタイムステップでの速度に足しこむことで現在のタイムステップでの速度が求まることになります。また、例えば1つの剛体に対して複数の剛体が衝突している場合、1つの剛体の並進速度と回転速度を求めることで他の衝突のめり込みを増やすことになったりしてしまいますが、これは拘束の式を繰り返し解くことにより全ての剛体の速度がイイ感じになるよう収束させることが可能です。繰り返す回数を増やすほど精度は向上しますが、その分計算時間も増加してしまうので、ゲーム向けの剛体シミュレーションでは繰り返し回数を指定してしまって、その回数だけ拘束の計算をするようにしています。
衝突に関する拘束以外にも、ヒンジジョイントやスライダージョイントといった各種ジョイントの拘束の演算もこのフェーズで行われます。
4. 位置更新
拘束演算により現在の剛体の並進速度と回転速度がもとまったので、これをもとに剛体の座標と姿勢を更新します。こうして求まった座標と姿勢をゲーム内のオブジェクトに適用することで、あたかもゲームオブジェクトが物理法則に則った動きをしているかのように見えるのです。
今回の実装の改善の余地
剛体シミュレーションの並列処理化
剛体シミュレーションのゲームへの組み込みについては Unity と同じ感じです。シミュレーションを行うクラスとシミュレーションの結果をゲームオブジェクトに適用するコンポーネントクラス(RigidBodyコンポーネント)を作成し、剛体シミュレーションの対象にしたいオブジェクトにそのコンポーネントを付けることで剛体シミュレーションを行うことができます。
シミュレーションを挟むタイミングですが、今回はゲームオブジェクトの更新処理と描画の間に挟むようにしました。シミュレーションの結果はRigidBodyコンポーネントにて更新されます。ただし、このままだとシミュレーションが重たい場合、描画されるまでの時間が延期されてしまってゲーム全体のフレームレートが落ちるといった問題が生じます。そこで、Unityのように物理シミュレーションだけは別のスレッドで一定のタイムステップ間隔で実行し続け、RigidBodyコンポーネントがシミュレーション結果をゲームループの更新タイミングで取得し、ゲームオブジェクトに適用するという感じにすると、物理シミュレーションが重たくなったとしてもゲーム全体のフレームレートは落とさずに済むようになります。
詳細はこちらの記事をご覧ください。
Cocos2d-xにおけるマルチスレッドを利用した並列処理技法―物理演算パフォーマンスの最適化に向けて― - LINE ENGINEERING
衝突検出の最適化
今回の実装では凸メッシュのみを使った衝突検出を行いました。凸メッシュを使えばかなり幅広い形状の衝突検出ができるのは間違いないのですが、球やカプセルといったプリミティブ形状でゲームオブジェクトの形状を近似することができるのであればそちらを使った方が効率的に衝突検出が行える場合があります。ただし、形状の組み合わせごとに衝突検出処理が必要になってくるのでそこは大変ですね。
また、今回のブロードフェーズの実装は総当たりでやっているので、この部分をスイープ&プルーンや AABB tree といったアルゴリズムに置き換えるとさらに効率化することができます。
まとめ
ゲームにおける剛体シミュレーションの内部実装について軽く紹介しました。書籍についてですが、理論と実践のバランスがちょうど良くまとまっていてかなり理解しやすかったと思います。物理エンジンでどのように剛体シミュレーションが実装されているのか知りたい人にはオススメの一冊です。
