論文読み: Unified Particle Physics for Real-Time Applications (SIGGRAPH '14)

論文 SIGGRAPH CG 2014

ゲーム物理エンジンに関する技術の集大成的論文

今回取り上げるのは今年の SIGGRAPH で発表される予定の論文です。正式な publication date は７月ですが、既に著者らがウェブ上で論文と動画を公開しています。

Miles Macklin, Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim.
Unified Particle Physics for Real-Time Applications.
SIGGRAPH '14 (to appear)
http://blog.mmacklin.com/flex/

この論文はこれまで個別に提案されてきたゲーム物理の技術を統合的に扱うという手法を提案しており、まさに集大成的な論文と言えると思います。公開されている動画も非常に印象的なものとなっています。

論文概要

短いので論文概要 (Abstract) を全て日本語訳してみようと思います。やや意訳している箇所があります。

我々は、リアルタイムな視覚的効果を演出するための統合的なダイナミクスの枠組みを提案する。基本要素として、制約によって接続されたパーティクルを用いることで、接触や衝突を統一的に扱うことを可能にした。ガス、液体、柔軟物体、剛体、布を、それらの相互作用も含めてモデル化するにあたって、この表現形式が十分な柔軟性を持つことを示す。我々は、パーティクルに基づく従来手法に共通するいくつかの問題に取り組み、またリアルタイムなアプリケーションでも十分高速に動作する、Position Based Dynamics に基づく並列制約ソルバーについても述べる。

この手法のメリット・強み

以下の点が挙げられます。

  1. 接触や衝突も上手く考慮できている
  2. ガス、液体、柔軟物体、剛体、布を全て表現できる
  3. 異なる表現（ガスと布、液体と剛体など）の相互作用 (two-way interaction) も扱うことができる

これらの条件を全てクリアした上でちゃんと動作する手法は初めてではないでしょうか。

パーティクルに基づく手法

この手法はパーティクル（粒子）ベースの手法です。つまり、全ての物体はパーティクルの集合として表現されます。

他の可能性としては、メッシュによる表現（表面メッシュや、ボリューメトリックな四面体メッシュ、ボクセル状メッシュなど）や、空間をグリッドで分ける表現（オイラー的手法）などがあり得ます。計算コストを抑えることが求められるゲーム向けのリアルタイム物理においては、パーティクルベースの手法が多い気がします。

Position Based Dynamics に基づく手法

Position Based Dynamics とは、今回の論文の第二著者の Matthias Müller 氏を筆頭著者として 2006 年に提案された手法です。リアルタイム処理に向いた手法です。

M. Müller, B. Heidelberger, M. Hennix, J. Ratcliff
Position Based Dynamics
VRIPhys '06
著者のページ

これについては、過去に書いた以下の記事で少しだけ詳しく解説しています。

論文読み: Position Based Fluids (SIGGRAPH '13) - yuki-koyama's blog
Unity 上に自分で物理エンジンを実装したい - yuki-koyama's blog

よくある手法では、力を計算して、加速度を計算して、速度を計算して、位置を計算するという流れを取ります。流体や弾性体などの振る舞いをモデル化する際には、力に関する制約としてモデル化することになるので、Force Based と呼んだりします。

それに対し Position Based Dynamics では、物体の振る舞いを位置に関する制約としてモデル化します。これが Position Based と呼ばれる所以です。したがって、位置を計算して、位置から速度を逆算するようなアルゴリズムになっています。これによって数値安定性が得られるのも特徴の一つです。

いままでに提案されてきた個別の技術

この論文は、いままでに提案されてきた個別の技術を統合的に扱っている点が最大の特徴です。

個別の技術の例としては、以下の２つの手法が有名です。

柔軟物体 (Shape Matching 法)

柔軟物体は Shape Matching 法と呼ばれる手法を用いて表現できます。

Matthias Müller, Bruno Heidelberger, Matthias Teschner, Markus Gross.
Meshless Deformations Based on Shape Matching.
SIGGRAPH '05

Shape Matching 法に関してはその後多くの拡張手法が提案されています。

また、2011 年の CEDEC においてシリコンスタジオ株式会社が発表した技術デモとその資料がウェブで公開されています。ありがたいです。
4Gamer.net ― ［CEDEC 2011］シリコンスタジオが紹介するゲームの未来。次世代型弾性体表現技術「Shape Matching」とは
http://www.siliconstudio.co.jp/presentations/

液体 (Position Based Fluids)

液体については昨年の SIGGRAPH で発表されました。以下のデモ動画は非常に有名になったため、見たことがある人も多いと思います。

Miles Macklin, Matthias Mueller Fischer
Position Based Fluids
SIGGRAPH '13

NVIDIA PhysX Lab

この論文は NVIDIA PhysX Lab というところから出た論文です。NVIDIA といえば有名な GPU メーカですが、そこが開発しているゲーム向け物理エンジン PhysX も有名です。ゲームエンジンとして有名な Unity でも採用されていますね。

今回の論文で発表した技術も、いずれは（既に？）PhysX に組み込まれるものだと考えられます。

関連研究

同じ SIGGRAPH 2014 で発表された研究論文に、この研究と非常に関連性の高い論文がありました。

論文読み: Projective Dynamics: Fusing Constraint Projections for Fast Simulation (SIGGRAPH 2014) - yuki-koyama's blog

細かいメモ

  • 制約を解くのを並列に計算するために、Gauss-Seidel 法から Gauss-Jacobi 法に変更している。その際に positive definite じゃなくても収束するようにするために、constraint averaging [Bridson et al. 2002] とか mass-splitting [Tonge et al. 2012] とかいうアイデアを活用している。これによって、運動量保存則が破れてしまっている。
    • 論文では言及されていないが、これは Lattice Shape Matching (LSM) [Rivers and James 2007] などでも使われていたアイデアで、実は LSM は運動量を保存していなかったということになる？
      • 追記 (2014/05/18): そもそも shape matching の制約は角運動量の保存は保証していなかったような。
  • Position Based Dynamics でガスを表現したのは初めて。
  • いままでは post processing 的に扱われていた摩擦の表現が、ちゃんと制約として解かれている。
  • 衝突判定を高速化するために、シーン中の全てのパーティクルの半径は同じに設定されている。
  • 剛体 (rigid bodies) もメッシュではなくパーティクルで表現されている。その制約としては Shape Matching 法が使われている。
    • Position-Based Rigid Body Dynamics [Deul et al. 2014] は違うアプローチ？
  • Interlocking という、物体同士が突き刺さった状態になってしまう問題を、Signed Distance Field (SDF) を各パーティクルに保存しておき衝突処理で活用することで解決している。
  • Maya の Nucleus [Stem 2009] も実は Position Based Dynamics とよく似た計算方法をとっているが、そのことが論文中で簡単に触れられている。
    • 特許とかどうなってるんだろう？Autodesk と NVIDIA で喧嘩になったりしないの？