中川さんのPosition-Based-Dynamics-Comboのスライドを読む（その1）

karino2 commented 7 years ago

中川さんがcedecで発表した、と言っていたので、スライドを見る。
有料会員になるとセッションの動画も見られるらしいが、無職たるものスライドくらいで。

https://github.com/nobuo-nakagawa/cedec2017

スライドの内容はスライド見ればわかると思うので、その内容をここでまとめたりはしません。
ここでは、自分が読んで思った事などを書いていく。

karino2 commented 7 years ago

Position Based Dynamics入門

まずはスライドの以下の式を考える。

karino2 commented 7 years ago

ここでノーテーションに注意として、$$ p_1 $$ と $$ p_2 $$ は位置を表している。運動量じゃない。

karino2 commented 7 years ago

さて、この式の意味をちょっと考えてみよう。
まずは2つの式を引いてみると、前のwの項は足して1となって、以下のようになる。

karino2 commented 7 years ago

この式の第一項、下の図で緑の下線を引いた部分は、2つの点の距離から制約のdを引いたので、はみ出ている部分の長さ、という事になる。

karino2 commented 7 years ago

で、第二項の方は向きとしてはp2からp1へのベクトルで、長さで割ってるからこの方向の単位ベクトル、という事になるだろう。

karino2 commented 7 years ago

つまり、dという拘束条件からの差分のベクトルになっていて、それを2つの点にどう配分するか、という時に質量の逆数を使うという事のようだ。重い物は動きにくくて軽い物はすごい動くだろうから、逆数の比に分配するのは直感的には良さそう。

karino2 commented 7 years ago

より一般的な拘束条件への拡張

次の(6), (7), (8), (9)はぱっと見よくわからない。上のテイラー展開の式から考えてみよう。

karino2 commented 7 years ago

拘束条件が無い状態にまず移動させて、そこから拘束条件を満たすように動かす、という二段階で考えるのがPBDの考えとの事なので、そういう前提で考える。

先程の単純な棒以外でも、もっと違う制約条件は考えられて、次のスライドをちら見すると曲げとかの場合が出ている。

さて、C(p)=0が拘束条件を満たされている状態として、そこからずれると、戻すように調整が入り、それは拘束条件=0としてデルタpで展開出来る、とあるが、このgradはそんな自明でも無い。

karino2 commented 7 years ago

勾配を定義する為には、C(p)=0の点だけじゃなくて、そこからずれた点pでのCの値が必須だ。実際、一次テイラー展開の式の右辺では、0になる点では無いpの値が入っている。これの値は、ここまでは無限大であるかのように話が進んでいたが、ここではsoft constraintsというか、少しずれても大丈夫なように見える。

追記: あー、力場じゃなくて位置に直接働きかける場なのだから、無限大じゃなくてもhardなconstraintsになるのか。なるほど。

karino2 commented 7 years ago

細かい説明は無いが、拘束場のような物を考えるのだろう。すべての点に対して、拘束場の値が定義されていて、これこそが拘束、という物の数学的表現である、という事なんだろうなぁ。

で、これを0とする点でこの拘束場の値は最小となる。それはいい。問題はゼロじゃない点でのこの値は何を意味するのか？

karino2 commented 7 years ago

C(p)=0となるすべてのpの場所が定義されていれば、それ以外の値はこのテイラー展開の式から出るのか？
少し考えてみよう。

pがゼロの点から外れた時に、デルタpは最も近いゼロとなる点への最短距離のベクトルとして決まるだろう。で、そのデルタpを満足するようにC(p)とそのgradは定義される。これは一意に決まるか？

…うーん、たぶん決まらないな。C(p)の値とgradの満たすべき制約条件までは決まるが、両方の値を決める所までは行かないだろう。逆にどちらか一方を決めると、もう一方は制約条件から出る気がする。

karino2 commented 7 years ago

これはちょっと妙な気がするな。だってC(p)をすべての点で定義してしまえば、gradも決まってしまう。制約条件を満たすようにgradを決める訳には行かない。

ん？これは微分方程式になって、答えが一意に定まってるのか？

よくわからんが、問題の理解は進んだので(6)〜(9)式をもう一度見直して見よう。

karino2 commented 7 years ago

(6)はただ多数の点に拡張しただけに見える。(7)はそれを一次のテイラー展開の式がゼロになる、という条件に代入すると出るように見える。

(8)は各点に違う重さを導入した場合の式に見えて、(9)はそれをテイラー展開の式をゼロとする条件に当てはめた結果出る物となる。

うーん、C(p)の場の満たすべき制約条件だけでC(p)を求める事が出来るかどうかはこれだけじゃよくわからないな。

karino2 commented 7 years ago

厳密な話は数学的にちょっと大変そうだからおいといて、少なくとも幾つかの場でこれらの条件を満たす物は、まぁたぶん探せるだろう。そしてstretchやbendがそれを満たしそうなのも、なんとなく納得は出来るのでいい。

さて、そういう場が定義出来るとすれば、あとは実際に位置を求める、という話になる。これがスライド16枚目のアルゴリズムの話だろう。

karino2 commented 7 years ago

突然ここで位置がpからxになるが、大人になるって事はそういう事なんだよ。 (追記: xは全部のpをまとめた物だそうです。)

ステップ3でfor文が居るのはなぜだろう？そもそも2点のstretchなら厳密解は一発で出そうだが、多点の場合は出るだろうか？
なるほど、多点を考える時に、別の点の事を考えると、点が増えたらあっという間に破綻する。だから場を導入して、各点を考える時には、他の点の事は考えないのか。

で、各点を拘束場から求まるように動かす。でもそれは当然一次の近似なので、全部の点でそれをやって帳尻が合う事は保証されない。だから全部の点をばらばらに動かして、また拘束場の値を見てみるのだろう。

karino2 commented 7 years ago

この記述だと、例えば $$ p_{i+1} $$ を更新する時に、 $$ p_i $$ の値は更新後の奴を使うか更新前のを使うかが書いていないな。

感覚的には更新前の値を使う方が安定するが、更新後の値を使う方が収束は早そう(不安定にはなりそうだが）

＞スライド20にその話があった。後述。

karino2 commented 7 years ago

そういう重箱の隅の話を置いておけば、基本は理解出来る。まずプレイヤーの操作なりなんなりで $$ x_{predict} $$ が決まる。

で、そこから制約条件を満たす所まで動かす訳だ。これは拘束場にそって、軽い物を多く動かして重い物はちょっと動かすような感じでちょうどゼロになるようにgrad見ながら各自が動いていく。

で、最終的に次のステップの位置が確定すると、その位置の差分で速度が決まる。 Fからmvが決まって位置が決まるのとは順番が違う。これがPBDという事だろう。

karino2 commented 7 years ago

三角形の例

スライド19のあたりに具体的な話があった。やはり多点で一気に全部を動かしてすべての拘束条件を満たすようにするのは難しいので、それぞれの拘束条件を満たすように順番にやっていきましょう、という話がある。

これはちょっとスライド14の(6)式などのような一般的な書き方とは随分様子が違うな。スライド14ではすべての点を元に拘束場が定義されるような書き方をしているが、スライド19では一度に二点しか見ないかのように書いてある。

やはり一般的な場を定義するのはちょっと難しいので、幾つかうまく行くと分かっている場を組み合わせて拘束場を定義する、ということか。

これでは収束や振動どころか、発散する例も作れそうだな。learning rateに相当する物が無いので。
ただ一つ一つ条件に従って動かす、というのが一番シンプルなやり方なのは理解出来る。

karino2 commented 7 years ago

更新する方法

スライド20で先程考えた、次の点を求める時に他の点は更新した値を使うか前の値を使うのか、という話の答えがある。

動かした値を使う物をガウス-ザイデル法と呼び、前の値を使う方法をヤコビ法と呼ぶらしい。

karino2 commented 7 years ago

長くなってきたので、まずはPBD入門までで一旦投稿。

karino2 / karino2.github.io