f - Springhead

Human interface Section, P&I Lab, Titech
剛体の物理シミュレーション
は難しい?
佐藤研助手 長谷川晶一
Human interface Section, P&I Lab, Titech
物理ベースモデリング
物理法則に基づいて物体を動かす
CGが映画やゲームに応用される
CG物体が実物体と同じように振舞ってほしい
Monster INC
DOOM III, Half-Life 2
Human interface Section, P&I Lab, Titech
剛体の運動
v: 速度
ω:角速度
dmv
 f
dt
dIω

dt
m: 質量
I: 慣性テンソル
f: 外力
r: 外力の作用点の位置
(すべて絶対座標系)
mv (t  t )  mv (t )  ft
I (t  t )ω (t  t )  I (t )ω (t )  t
f  0,  0 ならばただ回って進むだけ
シミュレーションするまでもない
Human interface Section, P&I Lab, Titech
剛体に働く力
重力→ f=mg… 定数
バネ→ f=kx… 位置に比例
拘束力
mg
kx
力の大きさは不明
剛体同士の位置・速度関係が決まっている
 蝶番:2物体の相対位置が一定
 抗力:2物体が互いに侵入しない
 静止摩擦力:物体が滑らない
拘束力の計算が難しい
fn
ft
Human interface Section, P&I Lab, Titech
拘束力の計算
f
B
 B  p
 A  0
拘束: p
rA,θ A,rB,θB,rA,θ A,rB,θ B の線形結合
pA pB
A
Br  b  0
運動方程式:
 mA






IA
mB
1
 rA  

  



 θ A    (p A  rA )  
f
 r   

1
 B  





I B  θ B   (p B  rB )  
Mr  Cf
Af  b  0
からfを求められる
Human interface Section, P&I Lab, Titech
抗力の計算
B
pB
fn
運動方程式
は同じ:
拘束:
Mr  Cf
pA
A
抗力は,反発だけ:
 B  p
 A )  n  0
(p
af  b  0
f 0
離れはじめたら,力を加えない:
f (af  b)  0
Human interface Section, P&I Lab, Titech
立方体に働く抗力
f 1n
f2n
Af  b  0
f 0
 f1







( Af  b)  0
f n 
Aの次元=fの次元
行列を解くので,行列の次数nに対して,計算量はo(n3)
立方体の面接触1つ:4次元
10個つむと:40次元
Human interface Section, P&I Lab, Titech
拘束を解くための計算量
Average computation time[ms]
60
50
Proposed simulator
Open Dynamics Engine
40
30
20
10
0
0
5
10
Number of blocks
15
Human interface Section, P&I Lab, Titech
ペナルティ法
拘束を解かない. Af  b  0
拘束を侵した分だけ罰として力を加える.
f  Kr  Br  c
そのうち,拘束を満たすでしょう,多分そのうち
力が直接決まるので,計算量はo(n)
バネの伸びl,相対速度v
f=k l+bv
Human interface Section, P&I Lab, Titech
まとめ
剛体の運動そのものは簡単
拘束力(関節・抗力・摩擦力)を求めるのが
ちょっと面倒.
抗力の計算量は接触点数nにたいして,o(n3)
ペナルティ法は,拘束を解かないので, o(n3)
Af  b  0 を解くにはo(n3)だが,
近似解ならo(n)で解けるかも
Human interface Section, P&I Lab, Titech
衝突
実世界の物体は
互いに侵入しない.
跳ね返る.
再現するためには
衝突検知
剛体間に働く力の決定
Human interface Section, P&I Lab, Titech
衝突検知
衝突の検出
衝突しているかどうかすべての剛体について調
べる.
剛体の形状は,多面体で表現されている.
衝突検知を簡単にするため,凸形状に分割しておく
Human interface Section, P&I Lab, Titech
凸形状
凸形状の便利な性質
凸形状 距離が極小となる点が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)
Human interface Section, P&I Lab, Titech
凸形状(GJK)
凸形状A上の点から,
凸形状B上の点へのベ
クトルを
原点を始点に並べると
ベクトルの終点の集合
も凸形状になる
Human interface Section, P&I Lab, Titech
凸形状(GJK2)
1
V0 : 凸形状内の任意の点
Wi :OViとOWiの内積が最小の点
Vi :三角形Wi-2 Wi-1 Wi内の点で原点に
一番近い点
2
3
4
Human interface Section, P&I Lab, Titech
凸形状2
凸形状の便利な性質2
凸形状の交差部分も凸形状
交差部分の形状が簡単に求まる
Half space
representation
D. E. Muller and F.P.Preparata:
“Finding the intersection of two convex” (1978)