2010-10-28
SiggraphAsia2010論文読み（Free-Flowing Granular Material with Two-Way Solid Coupling）
研究室の論文読み会の準備として，砂のシミューションについての以下の論文を読んでみました．かなりテキトーに感想を書いておきます．いつもどおり，いい加減に読んでるので内容は間違っているかもしれません．
Free-Flowing Granular Material with Two-Way Solid Coupling
http://gamma.cs.unc.edu/granular/
Granular Materialとは砂のような顆粒状の物質を指します．要は砂のような物質ですね．砂が流体と違うのは
- お互いにくっ付くことなく粒粒子が離れる
- 摩擦と圧力が連成している
の２点らしいです．このような砂の物質をリアルに効率よく計算するために．砂一つ一つはLagrange粒子として個別に表現されつつも，その内部にかかる応力はEuler格子を使って計算するというやり方をとるというのがこの研究の新しい所らしいです．以前にもAnimating Sand as a Fluid(pdf)という研究があったのですが，これはSPH粒子だけで格子は使わずに砂を表現しようとしていて，これよりはより改善されてリアルな砂が実現できているらしいです．DEM(Discrete Element Method)といって砂一つ一つについて，別の砂との連成をまともに解く方法もあるのですが，あまりにも計算コストが高すぎます．それよりは砂のマクロ的な動きを連続体として表現してそれを解いて計算した法が楽そうです．Euler格子とLagrange粒子やExplicit Surfaceとの連成はかなりCG系でもかなりホットな話題で，この流れを組んでいる研究はかなり沢山あります．
さて，「お互いにくっ付くことなく砂粒子が離れる」を連続体で表現しようと思ったら，砂が散らばっている場合は砂の連続体的な速度の発散は０でない値もとることができます．このとき砂の圧力は０です．しかし，砂が詰まっている場合は密度が一定でなければならなく，圧力は０でない値もとることができます．このような条件はCG系ではLCP(Linear Complementarity Problem)と呼ばれているのでしたね．砂が最充填された密度との現在の密度との比をΦとすると
と，美しく書くことができます．LCPは剛体の接触問題ではかなりよく出てくると思います．結局制約条件付きの最小化問題に帰着させて解くことができます．
次に，「摩擦と圧力が連成している」という条件です．砂には摩擦力が働くことで，流体にはない，積み上がる(Pile)ような動きをします．この摩擦力は塑性体としての条件を課してある一定上は摩擦に耐えられないようにモデル化するそうです．この論文ではDrucker-Pragerの降伏条件が用いられていました．摩擦力のフロベニウス・ノルムが圧力の定数倍よりも大きくなれないというものです．この摩擦力自体は，力学的エネルギー最小化の原理に基づき，できるだけ力学的エネルギーが小さくなり，尚且つこの降伏条件が満たされるように選ぶらしいです．この力学的エネルギーを最小化するように何かを求めるというのはCG系独自のやり方だと思います．この方法の物理的な意味は少し薄いのですが，力学的エネルギーが小さければ発散する可能性もないですし，安定に解けて良いですね．剛体とのカップリングにも力学的エネルギーを最小化するように連成力を求める次の研究の方法が取られています．
http://www.cs.ubc.ca/nest/imager/tr/2007/Batty_VariationalFluids/
去年のSiggraph Asiaでやってた群集のシミュレーションも離散的な粒の集合の動きを連続体近似して格子を使って解くという意味でかなり関連した研究のようです．
Aggregate Dynamics for Dense Crowd Simulation
SiggraphAsia2010論文読み（Piles of Objects）
前回の論文がTwitterなどで思ったよりCGの分野内外から反応があったので，もう一つ今日のうちに論文を紹介しておこうと思います．紹介するのは，剛体を沢山積み上げるシミュレーションの高速化手法についてです．
Piles of Objects
http://students.cs.tamu.edu/swhsu/proj/piles/
剛体を沢山積み上げるシミュレーションはCG系の研究のベンチマークとしてよく採用されています．産業への応用(映画やゲームなど)でどれほど剛体を沢山積み上げるシミュレーションが重要かについては疑問の余地がありますが，これは研究なのでそこら辺はあまり深く追求しないようにします．これらのシミュレーションには複雑な形をした剛体同士の接触や摩擦を解く必要があり，非常に計算コストがかかります．そこでこの研究では安息角(angle of repose)をつかったマクロ的な積み上げのモデリングを適応しています．
砂なんかを積み上げてスキー場のような斜面を作ろうとした場合に，斜面の角度には上限があることが知られています．その角度を越えると雪崩のように斜面が崩壊して，斜面はこの角度以下になろうとします．この角度の上限を安息角といいます．この安息角は砂粒の大きさ，形，摩擦係数によって決まってくるらしいです．安息角を超えない斜面は安定だとも言えるでしょう（もちろん例外は色々ありますけど）
さて，平面上に，上の一点から剛体を落とし続けた場合は，だいたい円錐のような形になるでしょう．この円錐の角度が安息角以下だと円錐は安定だと考えられるので，円錐の中の剛体は動かないでしょう．実際は上から物を落とし続けているので，円錐の表面で雪崩が起こったり形が崩れたりします．しかし，この安息角をした円錐の内部は動かないと考えられるので解く必要がありません．この論文では，この円錐の内部は解かずに放っておく(freezeする)ことで計算を高速化できる！というものです．実際２倍程度は高速化できてるらしいです．この円錐の構築，更新の仕方などが詳しく書いてありました．
気になった点は，安息角がユーザーが与えるということ．予め前計算で実験して自動的に導出して欲しいですね．あと雪崩が起きるときは，雪崩が起きそうな所にきっかけを適当に与えてやるとも書いてありました．もうちょっと自然に雪崩がおこって欲しかったです．あと，積み上がった形がだいたい円錐の形であると仮定していますけど，複雑な形をした剛体の上に積み上がる場合などもうちょっと汎用的な問題も解けるようにできないかとも思いました．まあ勝手な感想ですが．
