論文紹介 - Highly Adaptive Liquid Simulations on Tetrahedral Meshes -

SIGGRAPH 2013 流体セッションの論文紹介2本目です。
数少ない日本人著者による論文です。
実は今年出たSIGGRAPHの論文で一番最初に読みました。

参照元
Highly Adaptive Liquid Simulations on Tetrahedral Meshes

この論文ではPIC(Particle In Cell)法とFLIP(FLuid Implicit Particles)法の新しいアダプティブな手法を提案しています。

前提知識

PICとFLIPは粒子法と格子法を組み合わせて、非圧縮性流体の支配方程式であるナビエ・ストークス方程式の数値解を計算する手法です。これらは前回紹介したPosition Based Fluids(PBF)法のように粒子を用いて流体の動きを表現しますが、非圧縮性を適用するための圧力の計算を格子上で行います。粒子と格子の両方を用いてシミュレーションを行うため、粒子と格子の間で速度情報のやり取りが発生します。PICとFLIPの最も簡単なアルゴリズムは次のようになります。

1. 各粒子の速度を最も近い格子点に振り分ける(この時点では速度を割り振られた格子点の持つ速度は非圧縮性を満たしていない)

2. 格子上で圧力の計算を行う(非圧縮性を満たすような圧力を求める)

3. 計算された圧力を用いて、格子上の速度を更新する(格子点の持つ速度が非圧縮性を満たす)

(PICの場合) 4. 格子上の速度を各粒子に振り分ける

(FLIPの場合) 4. 格子上の速度の変化量(1→3の変化量)を各粒子に加える

5. 粒子の速度に従って粒子の位置を更新する

6. シミュレーションが終わるまで1~5の繰り返し

上記の通り、PICとFLIPの違いは格子上で計算した非圧縮場の速度を粒子にどう配分するかという点のみです。詳しい説明は割愛しますが、同じ条件でシミュレーションを行うと、PICではネバネバとした液体、逆にFLIPはさらさらとした液体が生み出されます。したがって、もっともらしい水の動きを表現するために、２つの手法で得られた結果をある割合で混ぜ合わせる、PIC/FLIPという手法が存在し、本論文でもPIC/FLIPが用いられています。

本論文の著者は昨年の論文Preserving Fluid Sheets with Adaptively Sampled Anisotropic Particlesで、液面からの距離に応じて粒子の大きさを変更することで計算の効率化を図る手法を提案していましたが、圧力の計算を行う格子はすべて大きさの等しいボクセル(MAC格子)を用いていました。従って、粒子の数を減らして移流のステップ数を減らすことは出来ても、圧力計算の効率化までは未達でした。

提案手法の概要

上記の圧力計算の問題を解決するため、この論文では空間の離散化手法をこれまでのボクセル(MAC格子)から四面体メッシュへと変更しています。また圧力計算はこれまでの有限差分法的アプローチでなく、有限要素法のようなエネルギーの最小化問題として考えています。四面体メッシュを用いることで、MAC格子と比較して圧力を求める際の未知数変数が少なくなり、圧力計算を効率的に行うことができます。加えて、四面体の切り分け手法が既に確立されているため、格子の大きさの変更を容易に行うことができるようになります。したがって、格子の数自体も削減することができ、さらに未知変数を減らすことができるようです。また論文中では、四面体メッシュを用いた際の二次精度の境界条件の離散化手法についても述べられています。

メッシュの大きさは、サイジング関数(Sizing Function)を用いて決定されます。これは

• 粒子が液面からどれくらい離れているか
• カメラからその粒子が見えるか
• 液面の曲率がどれくらいなのか

等の項目が評価されます。粒子の大きさはメッシュのサイズが決まった後に計算されます。すべての粒子を調べて、大きい四面体内部の中の粒子は大きく、小さい四面体内部の粒子は小さくなるように、マージと分割を繰り返します。

提案手法の面白いところは、液面上の粒子の大きさが均一でなくばらばらになっている点です。既存手法では液面からの距離に応じて粒子の大きさが決定されていたので、液面の粒子の大きさはほぼ均一に保たれていました。この論文のビデオを見るとわかるのですが、同じ液面上でも障害物の近くだったり、液面の変化が激しい箇所ほど粒子が細かくなっていき、逆に細かい挙動を必要としない地点では大きな粒子が用いられています。今回のような粒子を用いた流体シミュレーションでは、不連続な粒子の集まりから、実際の流体のような連続的な液面を再現する必要があります。本論文では、液面上にある異なる大きさの粒子から液面を構築する手法も提案しています。簡単に説明すると、「ある距離以内にある3つの粒子の組に外接する平面を構築する」という作業を液面にあるすべての粒子に対して行います。

この論文では、粒子と格子の両方をアダプティブにできたという点で、PIC/FLIPの完全なアダプティブシミュレーションが達成されています。しかしながら、メッシュを切り分ける処理が並列化できない点が高速化のネックになっているようです。

個人的には、カメラから見えない障害物の裏側等で大きいメッシュ・粒子が用いられていて、サボれるところはサボっている感じがとても面白いと思います(ビデオの0:45～）。

論文紹介 - Position Based Fluids -

SIGGRAPH2013 流体系論文紹介第1回目

公開されたばかりの頃に、はてブなどでも話題になっていた、"Position Based Fluid"の紹介です。

参照元
Miles Macklin's blog » Publications

Position Based Fluids - Supplemental Video - YouTube

これがリアルタイムでレンダリングまでされているという事ですから、驚きです。

この論文ではこれまで布や弾性体などのシミュレーションに用いられていた、PBD(Position Based Dynamics)という手法を水などの非圧縮性流体に適用できるように拡張された手法が提案されています。PBDは現在の位置と速度を用いて次の物体の位置を計算するのではなく、現在の位置からバックトレースで速度を決定するという手法です(間違ってるかも）。PBDはタイムステップを大きくとってもシミュレーションが破綻しにくいため、リアルタム性が要求されるゲーム業界等で用いられているようです。

前提知識

論文中では、提案手法の比較対象としてSPH(Smoothed Particle Hydrodynamics)が登場しています。SPHは流体を粒子の集まりで表現する「粒子法」の一種で、CGの分野のみならず、工学的にもよく知られた手法です。SPHは質量保存則などの物理的性質も満たしており直感的にも理解しやすいのですが、流体の非圧縮性を担保するため、シミュレーションを進める度に粒子密度の計算を行い、粒子分布の修正を行う必要があります（粒子同士が近づき過ぎていれば離し、離れ過ぎていれば近づける）。ここで、SPH特有の問題が生まれます。液面や固体などの境界付近では計算に必要な粒子の近傍粒子が不足し、その結果として不自然な結果を生んでしまうのです。この問題を解決するには大きく以下の2通りのアプローチがあります。

1. 十分小さなタイムステップでシミュレーションを行う
2. 多くの粒子を用いる

これらの方法は、いずれもシミュレーションに要する時間を増加させるアプローチであるため、リアルタイムシミュレーションには不向きです。

論文の概要

ここからがこの論文の要点です。
提案手法ではSPHとPBDを組み合わせることで、こういった問題に対処しリアルタイムのシミュレーションを可能にしています。基本的なアルゴリズムはPBDと同じであるため、大きなタイムステップを取りつつもシミュレーションの安定性は担保しています。

具体的には、

1. 前述の非圧縮性を適用するためにSPHの密度計算とPBDの位置修正を組み合わせ、反復法（ヤコビ法）により密度の計算を行う。

2. 負の圧力によって粒子が集まってしまわないように、人工的な圧力を導入する

3. vorticity confinementを用いて不自然なエネルギーロスを抑える

4. SPHの人工粘性を用いて粒子同士の相互作用をよりリアルにする

といった感じです。

提案手法はすべてのステップが並列化可能であるため、GPGPUのような並列アーキテクチャ上で効率的に実行させることができます。本論文での実装はCUDAを用いているとのことです。また、リアルタイム性が重視されているため、密度計算を行う反復法では、解の収束を待つのではなく、固定の回数だけ反復を繰り返して、得られた値を解とする、という手法をとっています。言い換えると、この反復回数を増減させることは、非圧縮性とパフォーマンスのトレードオフになります。

Limitation
1. 境界と粒子が接触した際に、境界にそって粒子がたまってしまう
2. ヤコビ法では粒子数が増えるほど収束に時間がかかってしまう。
3. 人工圧力が空間の解像度とタイムステップに依っているので個々のパラメータを調整するのが難しくなってしまっている。

Future Work
1. Limitation(3)で挙げたパラメータをそれぞれ独立させる
2. 筆者らは布と流体のインタラクションのプロトタイプを作っているところ。

iOS版のOpenCV利用でリンクエラーが出る時の対処法

安定しているのかどうかが良く分からないiOS向けOpenCVの動作を確認するため、
最新版のOpenCV2.4.3(バイナリ版)を導入し以下のサンプルをXcodeでコンパイル＆実行してみました。

OpenCV iOS - Video Processing — OpenCV 2.4.9.0 documentation

さて、このサンプルプログラムを動かそうと思った時に残念ながら若干はまってしまいましたので、需要は多くないと思いますが、起きた問題とその解決方法を記録しておきます。

問題 : リンクエラーでコンパイルが失敗してしまう

次のようなエラーメッセージが出てコンパイルが停止します。典型的なリンクエラーですね。

Undefined symbols for architecture i386:
"std::__1::__vector_base_common::__throw_length_error() const", referenced from:
__ZNSt3__16vectorImNS_9allocatorImEEE6assignIPmEENS_9enable_ifIXsr21
__is_forward_iteratorIT_EE5valueEvE4typeES7_S7_ in opencv2(matrix.o)
std::__1::vector >::vector(unsigned long) in opencv2(matrix.o)
std::__1::vector >::__append(unsigned long) in opencv2(matrix.o)
std::__1::vector, std::__1::allocator > >::vector(unsigned long) in opencv2(matrix.o)
...
(中略)
...
ld: symbol(s) not found for architecture i386
clang: error: linker command failed with exit code 1 (use -v to see invocation)

不思議だったのは、opencv2.frameworkは当然のこと、サンプルページに書かれていたframeworkをすべてプロジェクトに追加しているにも関わらずリンクエラーが出てしまっていることでした。

解決方法

Xcodeのプロジェクトの設定からC++ Standard Libraryを "LLVM C++ standard library with C++ 11 support" に変更する。

おまけ : 考えられる原因

今回の問題は主に次の２つの要因が重なって起きたものだと考えられます。

1. OpenCVを自前でビルドせず（自分の環境では失敗）、プリビルドされたバイナリ版のOpenCVを使っていたこと
2. いくつかのWebサイトのアドバイスに従って、ext/atomicity.hが見つからないエラーを回避するために、Xcodeのプロジェクト設定の項目であるc++ Language DialectとC++ Standard LibraryをCompiler Default にしていたこと

iOS向けのOpenCVのプリビルド版は当然(?)、apple標準のappale-llvm-compilerでビルドされているわけですが、不幸にも自分の環境ではCompiler DefaultがLLVMではなくGCCになっていたので、LLVMでビルドされて生成されていたオブジェクトファイルをGCC側から参照できなかったというわけです。ちゃんちゃん。