剛体の物理シミュレーション は難しい？ 佐藤研助手 長谷川晶一.

Presentation on theme: "剛体の物理シミュレーション は難しい？ 佐藤研助手 長谷川晶一."— Presentation transcript:

1 剛体の物理シミュレーション は難しい？ 佐藤研助手 長谷川晶一

2 物理ベースモデリング 物理法則に基づいて物体を動かす CGが映画やゲームに応用される CG物体が実物体と同じように振舞ってほしい
Monster INC DOOM III, Half-Life 2

3 剛体の運動 ならばただ回って進むだけ シミュレーションするまでもない m: 質量 I: 慣性テンソル f: 外力 r: 外力の作用点の位置
v: 速度 ω:角速度 (すべて絶対座標系) ならばただ回って進むだけ シミュレーションするまでもない

4 剛体に働く力 kx mg fn ft 重力→ f=mg… 定数 バネ→ f=kx… 位置に比例 拘束力 拘束力の計算が難しい
力の大きさは不明 剛体同士の位置・速度関係が決まっている 蝶番：2物体の相対位置が一定 抗力：2物体が互いに侵入しない 静止摩擦力：物体が滑らない 拘束力の計算が難しい kx mg fn ft

5 拘束力の計算 f A pA B pB 拘束： の線形結合 運動方程式： からfを求められる

6 抗力の計算 運動方程式 は同じ： 拘束： B fn pB pA A 抗力は，反発だけ： 離れはじめたら，力を加えない：

7 行列を解くので，行列の次数nに対して，計算量はo(n3)
立方体に働く抗力 f2n f1n Aの次元＝fの次元 行列を解くので，行列の次数nに対して，計算量はo(n3) 立方体の面接触１つ：４次元 １０個つむと：４０次元

8 拘束を解くための計算量

9 ペナルティ法 バネの伸びl，相対速度v f=k l+bv 拘束を解かない． 拘束を侵した分だけ罰として力を加える．
そのうち，拘束を満たすでしょう，多分そのうち 力が直接決まるので，計算量はo(n) バネの伸びl，相対速度v f=k l+bv

10 まとめ 剛体の運動そのものは簡単 拘束力（関節・抗力・摩擦力）を求めるのがちょっと面倒． 抗力の計算量は接触点数nにたいして，o(n3)

11 衝突 実世界の物体は 互いに侵入しない． 跳ね返る． 再現するためには 衝突検知 剛体間に働く力の決定

12 衝突検知 衝突の検出 衝突しているかどうかすべての剛体について調べる． 剛体の形状は，多面体で表現されている．
衝突検知を簡単にするため，凸形状に分割しておく

13 凸形状 凸形状の便利な性質 凸形状 非凸形状 凸形状 距離が極小となる点が1点 最近傍点が簡単に求まる GJK algorithm
E. G. Gilbert, D. W. Johnson and S. S. Keerthi A Fast Procedure for Computing the Distance between Complex Objects in Three-Dimensional Space (1988) 凸形状 非凸形状

14 凸形状（GJK） 凸形状A上の点から，凸形状B上の点へのベクトルを 原点を始点に並べると ベクトルの終点の集合も凸形状になる

15 凸形状（GJK2） １ ２ ３ ４ V0 : 凸形状内の任意の点 Wi :OViとOWiの内積が最小の点
Vi :三角形Wi-2 Wi-1 Wi内の点で原点に 一番近い点 ２ ３ ４

16 凸形状２ 凸形状の便利な性質２ 凸形状の交差部分も凸形状 交差部分の形状が簡単に求まる
D. E. Muller and F.P.Preparata: “Finding the intersection of two convex” (1978) Half space representation