Skip to main content

高度物理ソルバーによるシミュレーションと性能の向上

9月

02, 2020

by chefdeletat


テック

2015年の半ば、Robloxは物理エンジンである射影ガウス・ザイデル(PGS)物理ソルバーへの大規模なアップグレードを公開しました。 最初の年は、この新しいソルバーは任意のもので、以前に使用されていたスプリングソルバーと比較して信頼性とより良い性能を提供してくれました。

2016年に、多様な一連の新しい物理拘束へのサポートを追加し、開発者が新しいソルバーにマイグレーションし、物理エンジンの創造能力を助長するようなインセンティブを与えました。 どの新規のプレースも、古典的なソルバーに戻すオプションつきで初期設定でPGSソルバーを使用していました。

2018年半ばのLDL-PGSソルバー導入による高質量差と複雑なメカニズムと関連した安定性の問題を解決しました。 これは、古いソルバーを廃れたものにして、2019年には完全に無効化され、すべてのプレースを自動的にPGSにマイグレーションさせました。

2019年に、シミュレーション中のパーツの連結したアイランドから構成されたジョブにマルチスレッドを使ってシミュレーションを振り分けることで性能がさらに向上しました。 LDLに関連した性能の問題がありましたが、これは2020年の始めについに解決しました。

物理エンジンの性能はまだ向上し続けて最適化されている最中で、近い将来に新しい機能を追加する予定です。

物理の法則の導入

物理エンジンの主な目的は、バーチャル環境でボディの動きをシミュレーションすることです。 当社の物理エンジンでは、衝突してお互いに制限があるボディの硬さを気にします。

物理エンジンは、衝突検知と解決という2つの段階から編成されています。衝突検知は、剛体と関連性のあるジオメトリの間の交差点を見つけ、衝突ポイント、標準、浸透の深さのような適切な衝突情報を生成します。 それから、ソルバーは検知された衝突とユーザーによって提供された拘束の影響下にある剛体の動きをアップデートします。

動きは、ソルバーがエネルギーの節約や慣性など物理の法則を解釈した結果です。 しかし、これを100%正確にすることは手が出ないほど高価で、リアルタイムでシミュレーションする裏技は、結果が物理的に現実的である限り性能を向上させるために概算することです。 妥当な許容範囲内で基本的な運動の法則が維持されている限り、コンピュータゲームシミュレーションにはこの妥協は完全に許容可能です。

ささやかな行動を起こす

物理エンジンの主要な概念は、時間ステップを使った運動の離散化です。 拘束済みと拘束されていない剛体の運動方程式は、直接的に正確に統合するのは非常に難しいです。 離散化は、方程式が単純化されて線形化されて、大まかに解決することが可能になっているとき、動きを小さな時間増分に細分化します。 これは、それぞれの時間ステップの間、拘束に関与した剛体に関連するパーツの動きは直線的に概算されるという意味です。

線形化された問題は解決するのがより簡単ですが、回転運動など非線形の動作を含むシミュレーションでのずれを起こします。 後ほど、ずれを削減してシミュレーションを妥当にする緩和メソッドを見ます。

解決

時間ステップのために運動方程式を線形化したところ、線形システム線形相補問題 (LCP) を解決する必要が出てきました。 これらのシステムは恣意的に大きくすることができ、それでもまだ正確に解決するにはかなり高価です。 ここでも、より早い手法を使って大まかな解決方法を見つけるのがコツです。 良い収束性でLCPを大まかに解決するモダンな手法は、射影ガウス・サイデル(PGS)です。 これは反復手法であり、これはそれぞれの反復を使って大まかな解決方法を真の解決方法の近くにもたらすという意味で、その最終的な正確さは反復の数によります。

このアニメーションは、PGSソルバーが反復プロセスのそれぞれのステップでどのようにボディの位置を変更するかを表していて、オブジェクトがそれぞれのステップ(これは、IKドラッガーによって使用される位置ソルバーの一種)で質量の中心を保持しながらボールとソケット拘束を尊重する位置を見つけようとします。 この例には、単純な分析的な解決方法がありますが、PGSの背景にある考え方のいい実演になります。 それぞれのステップにおいて、ソルバーは拘束の一つを修正し、もう一つは規則を破ったままにしておきます。 いくつかの反復の後、ボディはその正しい位置にかなり近くなっています。 この手法の特性は、剛体のいくつかが特により重いボディと結合交流をしたときに、どれだけ最終的な位置の周囲を振動しているように見えるかということです。 反復を十分にしない場合、2つの拘束のうちの1つが劇的に規則違反になって、黄色いパーツは明らかに無効な状態に置かれたままになるかもしれません。 これは高質量率問題と呼ばれ、これは不安定さと爆発の原因となるため物理エンジンの破滅の元となってきました。 もし、反復をしすぎると、ソルバーは遅くなりすぎ、しないと不安定になります。 2つの側のバランスを取るのは、苦労が長い時間のかかるプロセスでした。

緩和戦略

ソルバーの主な不正確さには、2つの根源があります。時間ステップと反復解決(不動少数のずれがありますが、これは最初の2つと比べると小規模なもの)です。 これらの不正確さは、シミュレーションにおけるエラーを導入し、正しいパスからずれる原因となります。 このずれの中には、わずかに違う速度やエネルギーの浪費など許容可能なものもありますが、不安定さや大きなエネルギー増加や拘束の転移などはそうではありません。

そのため、ソルバーの複雑さの多くは、計算の不正確さの影響を最小限に抑えるための導入メソッドから来ています。 最後の導入では、従来の緩和戦略と新しい戦略をそれぞれ使っています。

  1. ウォームスタート: 反復ソルバーの収束率を増加させるために前の時間ステップからの解決から始める
  2. 安定化後: 拘束のずれを防ぐためにシステムを拘束多様体に再投影
  3. 正則化: 解決法が存在し、それが固有のものであることを確認する拘束への遵守を追加
  4. 事前調整: 線形サブシステムに対する厳密な解決方法を使用し、複雑なメカニズムの安定性を向上させる

戦略1、2、そして3はかなり伝統的なものですが、3は私たちが改善し、完成させました。 また、4は前代未聞で、その実用的な導入を見たことがありません。 私たちは、大きな低密度拘束行列のための元の因数分解の手法とPGSで新しい効率的な結合方法を使っています。 結果となる導入は、純粋なPGSに比べてわずかに遅いだけですが、等式拘束から来る線形システムを確実に正確に解決させます。 結果として、等式拘束は時間離散化からのみ来るずれに苦しみます。 メソッドについての詳細は、私のGDC 2020での講演内容に入っています。 現在、不等式拘束と衝突に適用される直接的な手法を調査しています。

さらなる詳細

従来、2つの明瞭化された数学的モデルがあります。それぞれの結合での自由度をパラメータ化し、ラグランジュ形式を使うフル座標方式があるFeatherstoneが推進した減少座標方式があります。

より制限が少なく、もっとシンプルな数式と導入を必要とする2つめの構築方法を使っています。

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も参照)。 この手法は、反復処理であり、それぞれの拘束をシーケンスにあるものとみなし、個別に解決します。 数多くの反復処理で理想的な条件下では、システムはグローバル解決に集中します。

加えて、等式拘束における高質量率問題はPGSを等分拘束の拘束行列の低密度LDL分解を使ってあらかじめ調整することによって解決します。 制限行列の密集した小行列は、ボディ分割と呼んでいる方法を使って疎行列化されています。 これは、 Baraff 1996で使われるLDL分解に似ていますが、さらに一般的な機械的なシステムを許容し、拘束スペースでシステムを解決します。 詳しくは、私のGDC 2020講演で見れます。

当社のソルバーの構築は速度と位置ステッピングが拘束解決によって分離されているGuendelman-Bridson-Fedkiwのアイディアに則っています。 当社の時間シーケンス

  1. 速度の詳細
  2. 速度空間と位置空間での拘束の解決
  3. 位置の詳細

この構想は、有効な速度だけを統合する利点があり、外部の力の適用において潜在性を制限しますが、数値的なずれによって認知される少々の拘束違反を許容します。

剛体シミュレーションについての優れた資料は、最近になって無料で利用できるようになった Erleben 2005という本です。 物理ベースアニメーションについてのオンライン講演、物理エンジンの構築についての Nilson Soutoのブログ、モダンソルバーメソッドについてのエリン・カット(Erin Catto)によるとてもいいGDC講演、そして弾丸物理フォーラム(Bullet Physics Forum)のようなフォーラムと質問を聞くのに秀逸な場所であるGameDevをネット上で見つけることができます。

結論として

ゲーム物理シミュレーションの分野は、エキサイティングで取り組みがいのある数々の面白い問題をもたらしてくれます。 膨大な量のクールな数学と物理を学び、モダンな最適化テクニックを使う機会があります。 これは数学と物理とソフトウエア工学を強く結びつけるゲーム開発の領域です。

Robloxが優れた硬いボディ物理エンジンを持っていたとしても、改善して最適化できる分野があります。 また、破砕、変形、軟体、布、航空力学、水シミュレーションなどのエキサイティングな新しいプロジェクトの作業をしているところです。


Robloxコーポレーションとこのブログは、いかなる企業もサービスも推奨も支持もしません。 また、このブログに含まれる情報の正確さや完全性について、いかなる保証または約束もしません。

このブログ記事は、元はRobloxテックブログ に掲載されたものです。