読者です 読者をやめる 読者になる 読者になる

アルゴリズム忘備録

競技プログラミングとかデータ分析とか

人間の髪のような変形可能な複雑な物体を今までより現実的にシミュレートする論文を読む

shiropen.com

 

論文はここ。

http://cs.stanford.edu/~michels/publications/michels_2017_stiffly-accurate-integration/michels_2017_stiffly-accurate-integration.pdf

 

質点同士の相互作用の物理モデルとして減衰振動モデルというのがあります。

減衰振動 - Wikipedia

簡単に言うと質点の座標を p=(x, y, z) とおくとpの2階常微分方程式になるものです。Wikipediaの数式だと外力なしですが、右辺にf(p)等を置くことで外力を考えた減衰振動モデルになります。

 

この減衰振動モデルを高次元化、つまりp=(x1, x2, x3, ....) とし、それぞれの係数を行列に置き換えることで剛体の減衰振動モデルが構成できます。この剛体の減衰振動モデルは人間の髪の毛等の変形モデルなど複雑な物体のシミュレーションモデルとして使えることがよく知られています。

 

この論文ではそのようなモデルに対して、より正確にpの数値計算を行うアルゴリズムを提示しています。既存の手法だと、例えばニュートン法を用いて微分値を初期値にどんどん足していく、と言った単純な手法がありますが、この方法では大域的に見ると徐々に解析解とのずれが積み重なり現実の動きと遠いモデルになってしまいます。

そこでこの論文ではまず元のモデルの数式をちょっと改良し(論文中ではReforming Elastdynamic Systemsとかいてあります)、時間積分を指数関数的に行う(同様にExponential Integration)方法を構築し、そのモデルをクリロフ射影アルゴリズムと言う既知のアルゴリズムに最適化することで計算量を抑えるという構成にしています。

 

かなり意訳すると、今までの手法では一次近似の繰り返しであったため、局所的にはシミュレートできても大域的には現実と程遠い挙動になってしまったところを、指数関数的な時間発展を考えることで高次の項もかんがられた時間発展ができるようになった、という感じでしょうか。

 

論文の最後の方に簡単な擬似コードも乗っており、親切な論文です。