論文読み: Projective Dynamics: Fusing Constraint Projections for Fast Simulation (SIGGRAPH 2014)

SIGGRAPH 2014 CG 論文

Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, Mark Pauly
Projective Dynamics: Fusing Constraint Projections for Fast Simulation
SIGGRAPH 2014

全体の概略

物理シミュレーションのための time integration の手法として、projective implicit Euler integration という新しい手法を提案しています。

これは implicit Euler integration の派生版で、特殊な potential energy と、projection の操作を含む Jacobi 法のような反復最適化が採用されています。

これによって高速でロバストで連続体力学ベースな物理シミュレーションを実現することができます。

実は Position-Based Dynamics (PBD) [Muller et al., 2006] とも計算方法が非常によく似ており、その違いについて論文内で非常に詳しく議論されています。

Matthias Muller, Bruno Heidelberger, Marcus Hennix, John Ratcliff
Position Based Dynamics
VRIPhys 2006

背景

物理シミュレーションを使って弾性体アニメーションを生成する方法はいくつかありますが、

  1. 連続体力学に基づいた有限要素法 (FEM)
  2. 幾何学的制約に基づいた Position-Based Dynamics (PBD) [Muller et al., 2006]

の２つが主流です。前者は昔からある方法で様々な改良 [Martin et al., 2011] がなされてきました。後者は近年急速に発展している [Bender et al., 2013] 比較的新しい手法で、PhysX, Maya nCloth, Havok Cloth, Bullet など様々な物理エンジンで採用されています。

Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, Markus Gross
Example-Based Elastic Materials
SIGGRAPH 2011
http://graphics.ethz.ch/publications/papers/paperMar11.php

Jan Bender, Matthias Muller, Miguel A. Otaduy, Matthias Teschner
Position-based Methods for the Simulation of Solid Objects in Computer Graphics
Eurographics 2013 (State of the Art Reports)

今回提案されているのは、両者の良いとこ取りをしたような新しい手法 (= Projective Dynamics) となっています。

今回の手法のメリット

FEM の持つメリット

  • 連続体力学に基づいている (物理的に正しい)

を持ちながらも、PBD のメリットである

なども持ち合わせています。

手法について

手法は local/global optimization (または block coordinate descent) [Liu et al., 2013] というアプローチに基づいています。これは、まずは local な問題を個別に解いて、続いて全体としてのつじつまが合うように global な問題を解く、といったものです。

Tiantian Liu, Adam W. Bargteil, James F. O’Brien, Ladislav Kavan
Fast Simulation of Mass-Spring Systems
SIGGRAPH Asia 2013

local

通常の FEM によるシミュレーションでは弾性ポテンシャル W を計算してそれを最小化する (= rest shape に近づくような内力を計算する) ということが行われます。それに対し、今回の手法では constraint (C) に現在の configuration (q) を projection するという操作を行います。つまり、constraint manifold (C = 0) 上に存在する configuration (p) と現在の configuration (q) の距離 (d(p, q)) を考え、それを最小にするような configuration (p) を求める (= projection) ということを行います。これは特殊な potential を定義することで実現可能となります。また距離関数 (d(p, q)) を単純な quadratic function としてモデル化することで projection は非常に高速に計算可能です。

ちなみに制約は１つのシーンの中に沢山あって、それぞれ独立に projection することができるため、並列化が可能です。

実はこれは PBD で行われている projection という操作そのものだったりします。

global

では PBD と Projective Dynamics の何が違うかというと、次の global のステップ、つまり個別の projection によって得られた解をどう統合するかという部分が、決定的に違ってきます。

そもそも PBD では解の統合方法は

  • Gauss-Seidel 法
  • Jacobi 法

の２種類のうちどちらかが使われており、例えばオリジナルの PBD の手法は Gauss-Seidel、最新の論文 [Macklin et al., 2014] では Jacobi 法が使われています。今回の Projective Dynamics は Jacobi 法を使っています。

Miles Macklin, Matthias Muller, Nuttapong Chentanez, Tae-Yong Kim
Unified Particle Physics for Real-Time Applications
SIGGRAPH 2014
http://blog.mmacklin.com/flex/

PBD で Jacobi 法を使う際には単純に local の解の平均をとって global な解として使います [Macklin et al., 2014]。ここで、この global な解には慣性が考慮されていないことが問題となってきます。これによって、反復最適化を回せば回すほど、慣性とのバランスが不自然な結果になってしまいます。

そこで Projective Dynamics では global な解を探す際に運動方程式に基づいて慣性を考慮します。このおかげで慣性が保たれるだけでなく、弾性体の固さが反復の回数に依らず物理的に自然に表現できるそうです。

またこの global ステップは線形問題に帰着されますが、その行列はシミュレーション中は (制約が変わらない限りは) 不変のため、事前計算として行列分解をして持っておくことができます。

手法の限界

メリットだけ見ると非常に良い手法のように見えますが、

  • implicit Euler integration に特有の damping が発生する
  • メッシュの解像度が高いと外力の伝播のせいで収束に時間がかかる
  • 制約の状態が変わるたびに巨大な行列の分解を行う必要が出てくる
  • hard constraint を扱えない (全て soft constraint)

などの制約があります。また

  • まだ線形の物質しか定式化していない (非線形の材質はまだ)
  • rigid body はまだ扱えない
  • 流体はまだ扱えない (制約が動的に変わるので難しい)

などの課題があります。また PBD と異なり巨大な行列を保持しておく必要がある点も、状況によってはデメリットとなるかもしれません。



細かい部分まで読み込めていないので間違えて理解している部分もあるかもしれません。