高度な物理ソルバーによるシミュレーションとパフォーマンスの向上
2016年、私たちは多様な新しい物理制約のサポートを追加し、開発者が新しいソルバーへ移行するよう促すとともに、物理エンジンの創造的な機能を拡張しました。新規に作成される場所では、デフォルトでPGSソルバーが使用されるようになりましたが、従来のソルバーに戻すオプションも用意されています。
2018年半ばには、ハイブリッドLDL-PGSソルバーを導入することで、質量差が大きい場合や複雑なメカニズムに関連する安定性の問題を解消しました。これにより旧ソルバーは不要となり、2019年に完全に無効化され、すべての「プレイス」が自動的にPGSへ移行されました。
2019年には、シミュレーションを相互接続されたシミュレーションパーツの「アイランド」からなるジョブに分割するマルチスレッド化により、パフォーマンスがさらに向上しました。LDLに関連するパフォーマンスの問題は依然として残っていましたが、2020年初頭にようやく解決しました。
物理エンジンは現在もパフォーマンス向上のために改良・最適化が進められており、今後も新機能の追加を予定しています。
物理法則の実装
物理エンジンの主な目的は、仮想環境における物体の動きをシミュレートすることです。当物理エンジンでは、剛体であり、互いに衝突し、制約関係を持つ物体に焦点を当てています。
物理エンジンは、衝突検出と解法の2つのフェーズで構成されています。衝突検出では、剛体に関連付けられたジオメトリ間の交点を検出し、衝突点、法線、貫通深度などの適切な衝突情報を生成します。その後、ソルバーは、検出された衝突やユーザーによって指定された制約の影響下で、剛体の運動を更新します。
この動きは、エネルギーや運動量の保存則といった物理法則をソルバーが解釈した結果です。しかし、これを100%正確に行うには莫大なコストがかかるため、リアルタイムでシミュレーションを行う際の秘訣は、結果が物理的に現実的である限り、パフォーマンスを向上させるために近似を行うことです。運動の基本法則が妥当な許容範囲内で維持されている限り、このトレードオフはコンピュータゲームのシミュレーションにおいては完全に許容できるものです。
小さなステップで
物理エンジンの主な考え方は、タイムステップを用いて運動を離散化することです。拘束された剛体や拘束されていない剛体の運動方程式を、直接かつ正確に積分することは非常に困難です。離散化では、運動を小さな時間ステップに分割し、そこで方程式を簡略化・線形化することで、近似的な解を求めることを可能にします。つまり、各タイムステップにおいて、拘束に関与する剛体の関連部分の運動が線形近似されることになります。
線形化された問題は解きやすいものの、回転運動のような非線形挙動を含むシミュレーションでは、ドリフトが生じます。後ほど、このドリフトを低減し、シミュレーションをより現実的なものにするための緩和策について見ていきます。
解法
このアニメーションは、PGSソルバーが反復プロセスの各ステップで物体の位置をどのように変更するかを示しています。その目的は、各ステップで重心を維持しつつ、ボール・アンド・ソケット制約を満たす位置を見つけることです（これはIKドラッガーで使用される位置決定型ソルバーの一種です）。 この例には単純な解析解が存在しますが、PGSの背後にある考え方をよく示しています。各ステップで、ソルバーは制約条件の1つを固定し、もう1つは違反したままにします。数回の反復後、物体は正しい位置に非常に近づきます。この手法の特徴として、特に重い物体との相互作用を結合させた場合、一部の剛体が最終位置の周囲で振動しているように見える点が挙げられます。 反復回数が不十分だと、黄色の部品は2つの拘束条件のうち1つが著しく破綻した、明らかに不適切な状態のまま残ってしまう可能性があります。これは「高質量比問題」と呼ばれ、不安定性や爆発を引き起こすため、物理エンジンの長年の悩みの種となってきました。反復回数を多くしすぎるとソルバーの処理速度が低下し、少なすぎると不安定になります。この両者のバランスを取ることは、苦難に満ちた長いプロセスでした。
緩和策
ソルバーには、不正確さの主な原因が2つあります。それは、時間ステップと反復計算です（浮動小数点数のドリフトもありますが、これら2つに比べれば軽微です）。これらの不正確さはシミュレーションに誤差をもたらし、正しい軌道から逸脱させてしまいます。この逸脱の中には、わずかに異なる速度やエネルギーの損失など許容できるものもありますが、不安定化、大きなエネルギーの増加、制約条件のずれなど、許容できないものもあります。
したがって、ソルバーの複雑さの多くは、計算上の不正確さによる影響を最小限に抑えるための手法の実装に起因しています。最終的な実装では、従来の手法と新しい緩和策を組み合わせています：
- ウォームスタート：反復ソルバーの収束速度を高めるため、前の時間ステップの解から開始する
- 事後安定化：制約ドリフトを防ぐために、システムを制約多様体へ再投影する
- 正則化：制約に順応性を付加し、解が存在し一意であることを保証する
- 事前条件付け：線形部分系の正確な解を用いて、複雑なメカニズムの安定性を向上させる
戦略1、2、3は比較的伝統的な手法ですが、3については我々が改良と完成を行いました。また、4は前例がないわけではありませんが、実用的な実装例はこれまで見当たりませんでした。 我々は、大規模な疎な制約行列に対して独自の因数分解法を用い、これをPGSと組み合わせる新しい効率的な手法を採用している。その結果得られた実装は、純粋なPGSと比較してわずかに遅くなるのみだが、等式制約から生じる線形システムが正確に解かれることを保証する。その結果、等式制約が受けるドリフトは、時間離散化に起因するものに限定される。我々の手法の詳細は、私のGDC 2020での発表に含まれている。現在、不等式制約や衝突に対する直接法について調査を進めている。
詳細情報
従来、多関節機構には2つの数学的モデルが存在します。1つはFeatherstoneが提唱した「縮小座標法」で、各関節の自由度をパラメータ化します。もう1つはラグランジュ形式を用いる「完全座標法」です。
我々は、制約が少なく、数学的処理や実装がはるかに単純であるため、後者の形式を採用している。
Robloxエンジンは、以前使用されていたペナルティ法とは対照的に、解析的手法を用いて拘束の動的応答を計算します。解析的手法は当初、Baraff 1989で導入され、等式制約と不等式制約の両方を一貫した方法で扱うために使用されました。Baraffは、接触モデルを二次計画法を用いて定式化できることを指摘し、ヒューリスティックな解法（これは我々のソルバーで使用している手法ではありません）を提示しました。
我々は力ベースの定式化ではなく、Mirtich-Canny（1995）によって最初に導入され、Stewart-Trinkle（1996）によってさらに改良された速度空間におけるインパルスベースの定式化を採用している。この手法は、異なる接触タイプの扱いを統一し、摩擦を伴う接触に対する解の存在を保証するものである。 各時間ステップにおいて、拘束インパルスによる速度の瞬間的な変化を適用することで、拘束条件と衝突が維持されます。インパルスベースのシミュレーションが優れている理由については、Catto（2014）のGDCプレゼンテーションに優れた解説が掲載されています。
無摩擦接触は、Baraff (1994) に記述されているように、線形補完問題（LCP）を用いてモデル化される。摩擦は、投影ガウス・ザイデル法の反復計算と交互に実行される、摩擦円錐への非線形投影として追加される。
拘束に位置誤差をもたらす数値的ドリフトは、Cline-Pai 2003によって導入された擬似速度を用いた事後安定化手法によって解消される。これには、位置空間における第2のLCPを解くことが含まれ、これによりシステムは拘束多様体へと投影される。
LCPは、Catto (2005) によって普及したPGS / インパルスソルバーを用いて解かれる（Catto (2009) も参照）。この方法は反復的であり、個々の制約を順次検討し、それぞれを独立して解く。多くの反復を経て、理想的な条件下では、システムは全局解に収束する。
さらに、等式制約における高い質量比の問題は、等式制約の制約行列の疎LDL分解を用いてPGSを事前条件付けすることで解消される。制約行列の密な部分行列は、我々が「ボディ・スプリッティング」と呼ぶ手法を用いて疎化される。これはBaraff 1996で使用されたLDL分解に類似しているが、より一般的な機械系に対応可能であり、制約空間でシステムを解く。 詳細については、私のGDC 2020でのプレゼンテーションをご覧ください。
本ソルバーのアーキテクチャは、Guendelman-Bridson-Fedkiwの考え方に従っており、速度および位置のステップ計算と制約の解法を分離しています。時間順序は以下の通りです：
- 速度のステップ計算
- 速度空間および位置空間における制約の解法
- 位置の更新
この方式には、有効な速度のみを積分できるという利点があり、外力の適用におけるレイテンシを抑制しつつ、数値的なドリフトによるわずかな制約違反を許容します。
剛体シミュレーションに関する優れた参考文献として、最近無料で公開されたErleben 2005という書籍があります。また、物理ベースのアニメーションに関するオンライン講義、Nilson Soutoによる物理エンジンの構築に関するブログ、Erin Cattoによる現代的なソルバー手法に関する非常に優れたGDCプレゼンテーション、そしてBullet Physics ForumやGameDevといった、質問をするのに最適なフォーラムも利用できます。
まとめ
ゲーム物理シミュレーションの分野には、刺激的かつ挑戦的な興味深い問題が数多く存在します。高度な数学や物理学を学び、最新の最適化技術を活用する機会も豊富にあります。これは、数学、物理学、ソフトウェア工学が密接に結びついたゲーム開発の領域です。
Robloxには優れた剛体物理エンジンが搭載されていますが、改善や最適化の余地がある領域も存在します。また、我々は破砕、変形、ソフトボディ、布、空気力学、水シミュレーションといった、エキサイティングな新プロジェクトにも取り組んでいます。
Roblox Corporationおよび本ブログは、いかなる企業やサービスも推奨または支持するものではありません。また、本ブログに含まれる情報の正確性、信頼性、完全性について、いかなる保証や約束も行うものではありません。
この記事は、もともとRoblox Tech Blogに掲載されたものです。
