SIGGRAPH,simulationお久しぶりです!開発室のVladimirと申します。久々に記事を書いてみましたが、今回、面白くて必ず役に立てる情報を伝えさせていただきたいと思います。簡単に線形システムの演算を高速化できる方法を紹介させていただきたいと思います。2015で発表され、こちらで公開されています。dynamicsです。方法の魅力を十分に把握する為、まずはCGにおける物理シミュレーションの基礎を理解するのが必要なので、簡単にその説明からはじめたいと思います。例としては髪の毛のシミュレーションを題材とします。物理シミュレーションのブレイクダウン運動学的な動きのみを扱うのであれば、シミュレーションは必要ではありません。対しての速度と位置を簡単に計算できます。弾性力や圧力などの現象を扱う場合、物体の位置を即決定する方程式を簡単に求めることができません。equation)を使います。ある変数の変化率の関係を表します。弾性シミュレーションのdynamicsは次の方程式を基づいて行われています:一般的に髪の毛は弾性物体としてシミュレーションされているので、ここから弾性エネルギーを例として見て行きましょう。方程式であらわされている現象はシステムの全体エネルギーの固定性です(外力はゼロの時)。運動エネルギーの変化率と内弾性エネルギーの変化率は同じです。シミュレーションされている頂点は動き始めると、その動作をキャンセルするための弾性エネルギーが蓄積されていきます。連続体を扱っているので、方程式の答えは単純な関数で表すことができません。正しい挙動を近似できる方法を採用するのが必要です。有限差分法にて、ドメイン(x,y,z,t)を分離して、連続微分式をサンプルした微分式に変形します。連続微分はその位置の関数値とoffsetした位置の関数値を持って近似されています。時間軸方向に考えれば、経過時間のhを与えると、t+hでの形状はtとt-hでの形状から求められます。今と前の形状を持っていれば、次の形状をcomputeできます。近似なので【次の形状】は完璧に正しいとはいえません。timestepは小さければ小さいほど、完璧な結果に近づきますが1秒のシミュレーションをする為、必要な反復回数は増加します。マシンの精度の問題もありますので、精度とスピードのバランスを考えて最適なtimestepを探すことが重要です。Dynamics式はもう一つの連続微分があります。(gradient)です。こちらもFDMを使うことが可能ですが、3D空間を分離することが必要です。structureで分離されており必ずしも均一とは限りません。Hairの場合であれば髪の長さが不均一であったりするため、FDMを応用するのが困難になりますので別方法を使います。system)と有限要素法(FEM)などがあります。P(x,y,z,t)のエネルギーはその頂点に繋がっている頂点のみに依存しています。次の式は各頂点のエネルギーと隣接する頂点の線形的な依存性をあらわしています。dynamics式を時間軸と3D空間で分離した結果、各頂点に対して一つの線形式で表すことができます。systemを取得できました。注目してほしい所が一つあります。エネルギーの勾配は3D空間(x,y,z)に対しての微分なので、時間の変数は自由です。線形システムを解決する時、【今のt】を使えばすぐにその頂点のエネルギーを計算することができます。Method)として知られています。実装はシンプルですが、精度は不十分です。非常に小さいtimestepを使わないと安定さを確保できません。別のattribute値によって不安定になることもあります。精度が高くて安定している方法があります。陰解法ではエネルギーを求める時、【今のt】ではなく【次のt】の情報を使用します。【次のt】での頂点Pの位置は【次のt】での近傍にある頂点Pの位置に依存するようになります。線形システムを解決する難易度はあがりますが精度とtimestepの大きさのバランスを考慮すると陽解法よりメリットがあります。陰解法にて得られた線形システムはこの形です:さらに、行列式として書き直せば、次になります:この様なシステムの解決について少し紹介させていただきたいとおもいます。行列式で書き直すと解答は明らかになります。行列のAの逆行列を求めて両方を乗算すれば、【次のt】の形状が得られます。method)といいます。逆行列を求める為のコストは高く、この方法はあまり現実的ではありません。method)がよく使われています。反復法は、初期に設定された解答を再計算しつつ、誤差を減少する方法です。計算の繰り返しで正しい解答を近似できます。反復法はあくまで近似を求めるので、スピードと精度のバランスを探すことが必要です。行列システムの反復はシミュレーションの反復の中で行われるので、行列の反復回数はperformanceに大きく影響します。反復法はいくつかありますが、一つだけ紹介したいと思います。詳細はWikipediaを参照ください。ヤコビの一つの利点としては並列化が容易なためGPU実装に向いているといえます。他の方法と比べて精度の面ではあまり良くありません。gradientの様な別方法をappendできますが、内積の計算が多くて、GPU実装として不適切になります。そこで、この記事のメインとなる手法です!Chebyshev法Chebyshev法はヤコビ法の精度を高くした上で、必要な反復回数をかなり低下させられる手法です。内積が不要なのでGPU実装にも最適です。Chebyshev法は数学界において昔から存在していましたが、CG業界においては比較的最近登場しました。ASIAで発表された論文は細かく説明されていますので、詳細を知りたい方は参考にしてみてください。今までCG業界であまり登場する場がなかったのかを説明させていただきたいと思います。前述の通りChebyshev法の利点は大きいのですが、逆に大きな短所もあります。valuesを求めるのは、逆行列を求めるのと同様にコストが高いです。valueを求めるのは難しくなります。Hairをシミュレーションする場合、行列は小さいですがその数が多くなります。これらの理由からChebyshev法は今までCG業界であまり採用されてこなかったとのことです。そんな中、2014年のSIGGRAPHで新たな論文が発表されました。(PD)という手法です。PDはこの記事で説明しているシミュレーションの方法に基づいています。systemsやFEMなどはシミュレーションの反復毎に行列の更新が必要になりますが、PDではシミュレーションしている物体のtopologyが変わらない場合、行列は固定となります。valuesを一回だけ求めればよいのでchebyshev法の短所を補うことができるようになりました。以下のChebyshev法:有り・無しの結果をご覧ください。dataはコチラに提供されています。hairというデータから24570本数のシミュレーション結果です。ここまで紹介させていただいた物理シミュレーションのボトルネックは行列演算(Ax=b)です。この結果からもヤコビ法のみを利用すれば反復回数が多くないと安定にならないので、シミュレーションは全体的に重くなります。Chebyshev法はこのボトルネックを直接高速化できる有効な方法です。upが期待できる良い方法のひとつだと思います。CodeChebyshev法の実装は特に難しくはないです。GPU実装にする場合、細かい調整は必要ですが最終的に頂点毎に並列化できます。それを求める為に、Eigenを使っています。Chebyshev法を使うには幾つか条件がありますので、導入する前に一度論文を参考にしてください。newResult;}皆さん、Chebyshev法いかがだったでしょうか?もし固定した行列を扱っているのなら、この手法はとても有効だと思います。利用してみてください。今回は以上となります。Dynamicsの紹介をしたいと思います。公開している全ての手法・コードの有用性、安全性について、当方は一切の保証を与えるものではありません。これらのコードを使用したことによって引き起こる直接的、間接的な損害に対し、当方は一切責任を負うものではありません。自己責任でご使用ください。(※必須):Website:Comment:コメントは承認制ですので、即時に反映されません。上に表示された文字を入力してください。月別アーカイブ2018年5月2017年1月2月3月4月6月10月11月2016年1月2月3月4月5月6月7月8月10月11月12月2015年1月2月3月4月5月6月7月8月9月10月11月12月2014年1月2月3月4月5月6月7月8月9月10月11月12月2013年1月2月3月4月5月6月7月8月9月10月11月12月2012年2月3月4月5月6月7月8月9月10月11月12月2011年1月2月3月4月5月6月7月8月9月10月11月12月2010年12月Footer。