Transcript 1 - Graphicon`2002

Structured Methods in
Physical Modeling for Games
Àëeêcaíäp Peøeòoâ & Michael Shantz - Intel Corporation
• Pros and Cons
• The Basics:
– Spatial Vectors & Coordinate Frames
– Inertia, F = Ia, Gravity, Contact Forces
– Numerical integration
• Articulated Bodies, Joints & Joint Limits
• Forward Dynamics via Structural Recursion
• Kinematic Loop Constraints - Mechanisms
• Hybrid Dynamics & Controllers
• Game Engines & Performance Issues
Physical Modeling for Games
Physical Modeling Pros & Cons
• Difficult - steep learning curve
• Compute Intensive: collisions, dynamics
– floating point limited
– cache miss sensitive!
• Controllers are difficult
– cars are ok but try walking
• Long term potential - this is gonna be great!
• Incremental design - start modestly
• There are many ways to cheat
Physical Modeling for Games
Forward Dynamics
• Given joint torques and external forces
compute the resulting joint accelerations
– Reduced or Generalized coordinate methods
O(n) Structural Recursion (Featherstone, Brandl)
joint space 1..3 DOF versus motion space 6DOF
most efficient in flops, eliminates “drift”
• Solve a system of constraints
– Maximal coordinate methods
O(n) Lagrange Multipliers (Baraff)
most efficient in memory access?
Handles general constraints. Serious drift problems.
Physical Modeling for Games
Articulated Body Tree
frame 0, body 0
3
6 DOF joint
2
body 1
6
7
4
5
i
p(i)
8
9
The bodies form a tree with the bodies numbered such that the predecessor number
p(i) is less than the body’s number. Structural recursion operates on this tree.
Physical Modeling for Games
Basics: Rigid body i “link”
Bodyi
P
y r
s
Center of
Mass
x
z
framei
Bodyi has coordinate framei fixed in the body. The body may
experience angular and linear velocity and acceleration. These spatial
vectors may be expressed in framei or in other frames. s is a vector
to bodyi’s center of mass expressed in framei
Physical Modeling for Games
Articulated Body Joint Frames
2A
2’
, z2  q
body 1
2’R
1
, c1
body 2
y
y
x
y
z
x
y
z
frame 1
frame 2’
inner
joint
frame
6 DOF joint
x
z
frame 2
outer
joint
frame
x
z
frame 0, “inertial frame”,
world coordinates
The joint variables q are zero when the inner frame and outer frame are coincident.
Frame 1 is fixed in body 1, frame 2’ is fixed in body 1 but is associated with body 2.
Joint action moves frame 2 wrt frame 2’ (by rotation matrix A, translation vector z).
Physical Modeling for Games
Basics: Spatial Vectors - Velocity
jVelocity
i
=
x
y
z
x
y
z
Angular Velocity
 vector specifies axis
of rotation.
Length of  is radians
per second


Linear Velocity
 vector specifies
direction
Length of  is meters
per second
The spatial velocity jvi of body i expressed in coordinate frame j
includes both angular and linear components. Notation is critical.
Physical Modeling for Games
Basics: Spatial Vectors - Acceleration
jAcceleration
i
=
x
y 
z
ax
ay a
az
Angular Acceleration
 vector specifies axis of
rotational acceleration.
Length of  is radians per
second2.
Linear Acceleration
a vector specifies
direction.
Length of a is meters
per second2.
The spatial acceleration jai of body i expressed in coordinate frame j
includes both angular and linear components.
Physical Modeling for Games
Basics: The Cross Operator ~
Vector Cross Product:
~
a =
0 -az ay
az 0 -ax
-ay ax 0
a~ b = a x b
=-~
aT
The cross operator gives a matrix algebra representation of the
vector cross product. Note that its transpose is its negation.
For 6-vector
a 
s= 
b 
let
~

~s = a 0 
~ ~ 
b a 
Physical Modeling for Games
Basics: Spatial Vectors - Force
jForce
i
=
x
y
z
fx
fy
fz
Torque: Moment of Force

f
 vector specifies axis of
torque.
Length of  is
newton meters: kilogram
meters2 per second2.
Linear Force
f vector specifies direction.
Length of f is newtons:
kilogram meters per
second2.
The spatial force jfi on body i expressed in coordinate frame j includes
both torque and linear force components.
Physical Modeling for Games
Basics: Force applied at a point
iforce
i
=

f

~
=
rf
f
f
y
z
r
P
x
frame i
The spatial force ifi on body i expressed in coordinate framei resulting
from a linear force f applied at point P (line of force) in framei where
r is the vector to P, has a torque  = r x f (right hand rule) and a linear
component f.
Physical Modeling for Games
Basics: Gravitational Force on Body i
0g
~i
s
g
i
if = m
g
ig
ig
= [0,-9.8 meters/sec2,0]T
= iR0 0 g
y
Trick:
0a
0
=
-0g
s
i
z
x
frame i
Center of
Mass
ig
The acceleration of gravity 0g in frame 0 (world coordinates) is a 3x1
vector eg. [0, -g, 0]T. iR0 is the 3x3 rotation matrix that transforms it
to frame i. si is the vector in frame i to the center of mass of body i.
if is the spatial force expressed in frame i which is exerted on body i
g
due to gravity. Cheap trick: just give frame0 a fake acceleration -0g.
Physical Modeling for Games
Basics: Transforming Spatial Vectors
kf
kf
kC jf
=
i
j
i
i =
R
0
~
-Rr R
y
R

f
x
r
y
z
frame k
x
z
frame j
A spatial vector jfi expressed in coordinate frame j may be expressed
in frame k by transforming the spatial vector by the 6x6 matrix kCj
where R is the 3x3 rotation matrix st. kv = kRj jv transforms a 3 vector
expressed in frame j into a vector expressed in frame k. r is a 3
vector from the origin of frame j to frame k expressed in frame j.
Physical Modeling for Games
Basics: Inertia Matrix Ii , F = Ia
if
i

f
= Ii iai
=
Ii
~
~
hi
-hi Mi

a
 ( y2  z2 ) dv
 
Ii     (xy) dv
   (xz) dv

The force ifi on body i expressed in frame i is
equal to the inertia matrix of body i times the
spatial acceleration of body i. mi is the mass
of body i in kilograms, s is the vector in frame
i to the center of mass of body i. Use the
Lien/Kajiya method to get I, m, s.
Physical Modeling for Games
  (xy) dv

 
(x
2
2
 z ) dv
(yz) dv
  (xz) dv 

  (yz) dv 

2
2
 ( x  y ) dv
0 -sz sy
~
hi = mi sz 0 -sx
-sy sx 0
Mi =
mi 0 0
0 mi 0
0 0 mi
Basics: Contact Forces from Collisions
• Spring damper

if = -k x
d - k sx
• Nonlinear spring/damper

if = -k xnx - k xn
d
s
~
if
r
i
if =
c
if
y
frame i
x
z
x
ri
body i
if
P
The contact force on body i due to a collision at point P which is
penetrating another object by a depth of x can be modeled as a spring.
The 3x1 vector if has direction based on normal to the surface and the
velocity of body i (to simulate friction) . See Marhefka and Orin
Physical Modeling for Games
Basics: Contact Forces kill Integrators
y
• If time step is too large,
collision may cause integrator
instability.
frame i
if
body i
x
z
•Delayed reaction for
articulated body
ri
x
P
Physical Modeling for Games
Basics: Numerical Integration
• Euler or Verlet:
.
qi += qi t;
.
..
qi += qi t;
• Runge-Kutta Fehlberg (adaptive step size)
.
q
.
qi
.
.
.
qi-1
ti-1
t
ti
If the error computed from
the pair of estimates is too
large, reduce t.
Estimate 1
Estimate 2
t
The exact solution (white curve) is estimated at t time steps. See Numerical
Recipes in C and excellent survey by Enright et al.
Physical Modeling for Games
More about Joints
2A
2’
, z2
body 1
2’R
1
, c1
body 2
y
y
x
y
z
x
y
z
frame 1
frame 2’
inner
joint
frame
6 DOF joint
x
z
frame 2
outer
joint
frame
x
z
frame 0, “inertial frame”,
world coordinates
If the joint variables q are zero then the inner frame and outer frame are coincident.
Frame 1 is fixed in body 1, frame 2’ is fixed in body 1 but is associated with body 2.
Joint action moves frame 2 wrt frame 2’ (by rotation matrix A, translation vector z).
Physical Modeling for Games
The Joint Transform iCi-1
z
Rigid bodies
connected by
joints.
q1= 
y
outer jointi frame
framei
jointi
x
zi
i
inner jointi frame
Ci’
link bodyi
If zi expressed in framei’ (in API) then
i
framei’
iC
i-1
transform
i’
Ci-1
ci
z
C i 1  i C i ' i' C i 1
0  1 0 R 0  1 0
 A
T
T
0 A  ~
z i ' 1  0 R  ~
c i 1 
AR
0
  A ~ T R + AR ~ T AR 
 z i

ci
framei-1



If zi expressed in framei-1 (internal) then
i
y
x



1
0
AR 0 
T
T
~
C i  1  0 AR  ~
 z i  c i 1 
jointi-1
link bodyi-1
iC
transforms spatial vectors from framei-1 to framei. R is a rotation
matrix that rotates vectors from framei-1 to framei’. A is the matrix
associated with joint rotation, zi is for sliding (prismatic) joints.
i-1
Physical Modeling for Games
Revolute (Hinge) Joint
Joint space parameter q0 = radians about z axis
cos(q0)
sin(q0)
0
0
1
-sin(q0) cos(q0)
Rotation matrix iAi’ =
0
Translation zi = 0
0
Project Joint space into Motion space:

i q0 =
0
0
1
0
0
0
y

q0
, zi
y
x
z
Physical Modeling for Games
iA
i’
frame i’
inner
joint
frame
x
z
frame i
outer
joint
frame
Prismatic (Sliding) Joint
Joint space parameter q0 = meters along z axis
Rotation matrix iAi’ =
Translation zi = <0 0 q0>
1
0
0 0
1 0
0
0
1
Project Joint space into Motion space:

i q0 =
0
0
0
0
0
1
y

q0
, zi
y
x
z
Physical Modeling for Games
iA
i’
frame i’
inner
joint
frame
x
z
frame i
outer
joint
frame
Spherical Joint
“Joint space parameters” qe0 qe1 qe2 qe3 = quaternion rotation
~ ~
~
Rotation matrix iAi’ = 1 + 2(qe qe - qe3 qe); where qe = <qe0 qe1 qe2>
and 1 is identity. Normalized Euler: | qe0 qe1 qe2 qe3| = 1.
Translation zi = 0
 qe = 0.5  t for qe(0) = 0
Project Joint space into Motion space:
1
0


i q =
= 0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0

q0
y

q1

q2
Physical Modeling for Games
iA
i’
, zi
y
x
z
frame i’
inner
joint
frame
x
frame i
z outer
joint
frame
Articulated Body Joint Limits
• Use counteracting torques to limit joints.
q
•
r = ks(q-qmax) - kdq
qmax
r = 0
qmin
•
r = ks(q-qmin) - kdq
Given joint position q and limits qmin qmax, compute limit torques to
prevent joint from exceeding its range.
Physical Modeling for Games
Articulated Body Forward Dynamics
External
forces:
collisions, fE
gravity
Joint space
accelerations
Controller
generated
joint torques
i
Joint
parameters,
mass, inertia
Ii...
Structurally
Recursive
Forward
Dynamics
..q
i
Body
Transforms
Integrator
O(n) computational complexity
Physical Modeling for Games
qi
Articulated Body Tree
frame 0, body 0
3
6 DOF joint
2
body 1
6
7
4
5
i
p(i)
8
9
The bodies form a tree with the bodies numbered st. the predecessor number p(i) is
less than the body’s number.
Physical Modeling for Games
Articulated Body Recursion
vi =
iC
i-1
vi-1 + vrel
..
ai = i-1 ai-1 + i qi + i
iC
fi = 
j  s(i)
.
vrel = i qi =
T
jC
i fj
i =
+ Ii a i -  i
rel
rel
~  )
AR(
i-1 rel
~ (
~ r + 2 ))
AR(
i-1
i-1 i
rel
i = fEi -
_
~
i Ii i
~ s)
~ (
mi
i
i i
The velocity of bodyi is just the velocity of bodyi-1 expressed in framei plus the
relative velocity due to joint motion. Acceleration is similar except for the centripetal
acceleration term i. Force is similar except that recursion is from successor bodies
s(i), plus bodyi force Ia, minus external, Coriolis, and centrifugal forces i . i is the
angular velocity of bodyi , si the vector to center of mass, ri = ci + zi .
Physical Modeling for Games
Structurally Recursive Forward Dynamics
input : t ; q ; q ;  ; a 0 ; link and joint parameters
output : 
q ;  c ( if desired )
Brandl
algorithm for
case with no
loops.
Structurally
recursive
O(n)
algorithm
for i=1,2,...,nB
i
*
v i ; C p ( i ) ;  i ; Ii  Ii ;
// forward kinematics, compute:
 *i   i ;
endfor
for i = nB, nB-1,...,1
T *
Hi   i Ii  i
// backward dynamics
Velocity dependent terms
if p(i) != 0
*
*
1 T *
N i  Ii  Ii  i H i  i Ii
 i  Ni i  I*i  i Hi1 ( i   iT  *i )   *i
i
*
T
i
Ip(i)   C p (i ) Ni C p (i )

*
p (i )
i
 C
endfor
for i = 1,2,...,nB
T
p (i )
“felt” inertias
i
// forward accelerations
i  H [   I ( Cp ( i ) a p ( i )  i )   i   iT  *i ]
q
 i   i
ai  i C a   q
accelerations
cT
*
 ic   i {I*i a i   i }
1
i
p(i)
T * i
i i
p(i)
i
endfor
Physical Modeling for Games
Matrix and Vector info
Size of matrix
variables
assuming
joints have ni
DOF; no
kinematic
loops
input : t ; q ; q ;  ;6x1
a 0 ; link and joint parameters
c
output : 
q ;  ( if desired )
for i=1,2,...,nB
// forward kinematics, compute:
*
i
*
v i ; C p (i ) ; i ; Ii  Ii ;  i   i ;
6xni
endfor
for i = nB, nB-1,...,1
T *
6x6
Hi   i Ii  i
// backward dynamics
nix1
if p(i) != 0
*
*
1 T *
Ni  Ii  Ii  i H i  i Ii
nixni
 i  Ni i  I*i  i Hi1 ( i   iT  *i )   *i
6x6
Rows x Columns
i
*
T
i
Ip(i)   C p (i ) Ni C p (i )
6x1
 *p (i )   CTp (i )  i
i
endfor
for i = 1,2,...,nB
// forward accelerations
i  H [   I ( Cp ( i ) a p ( i )  i )   i   iT  *i ]
q
i   i
ai  i C a   q
1
i
p(i)
nix1
T * i
i i
p(i)
i
cT
*
 ic   i {I*i a i   i }
6-nix1
endfor
6-nix6
Physical Modeling for Games
Create Dynamic Model from Static
Modeling work
by Sonja Jeter,
Nola Donato
The “Mechanic” toolkit for interactively creating dynamic models
from art obtained from modelers such as 3DStudio MAX.
Physical Modeling for Games
Forward/Inverse Dynamic Walking
Modeling
work by
Sonja Jeter,
Nola Donato
The “Mechanic” toolkit for interactively creating dynamic models
from art obtained from modelers such as 3DStudio MAX.
Physical Modeling for Games
Kinematic Loops
• Body
Joint & Rigid Body
Set Joint Torques
Set External Forces
• BaseBody
Compute Body
Accelerations
• Loop Joint
Breaks Cycles
Base
Body
Joint

Body
Loop Joint
Behav
Kinematic Loop Objects
 Body : TransformGroup
BaseBody
Joint & Rigid Body
Set Joint Torques
Set External Forces
 BaseBody : Body
Compute Dynamics
Body

G
 Loop : Body
loop constraint equations
Behav
Body
Body
G
Loop
G
Mechanisms
Modeling by Sonja Jeter, Jill Hunt, Nola Donato
Steam engine with 3 kinematic loop constraints. The
crankshaft, the rocker arm pivot, the valve and piston
cylinders are all fixed to the base.
Physical Modeling for Games
Hybrid Dynamics & Controllers 1
(t)
f(t)
Physical Modeling for Games
Hybrid Dynamics & Controllers 2
•
Forward Dynamics
-h2  2

ih

 V( x )  ( x , t )
2
t
•
Inverse kinematics
•
Hybrid dynamics
2m x
Physical Modeling for Games
Hybrid Dynamics & Controllers 3
i  Hi1[ iT I*i(i Cp(i) ap(i)  i )   i   iT  *i]
q
a = f/m


x = -kdx - ksx
Physical Modeling for Games
Hybrid Dynamics & Controllers 4
opt f(p)
min f(p)
Physical Modeling for Games
Performance

Equipment
Intel 400 MHz Pentium II Processor

Dynamic Models
Raptor:
1500 polygons, 50 DOF,
12 inverse dyn.
40K-80K floating ops per frame
25 fps dynamics + render + skin
300+ fps dynamics only.
Steam Engine:
1000 polygons, 11 joints, 3 loops
70K floating ops per frame
50 frames per second.
Physical Modeling for Games
Optimizations
Behaviors: behavioral culling, stop/start, freeze/resume
 Collisions: OBB inner loop: Parallel float optimize

Hierarchical Sphere bounds, Collide sets,
kinetic prediction, interval arithmetic
 Dynamics: Linear Algebra: Parallel float opt.
Occlusion: Portals, Visibility map (UNC), Switch, app cull
 Scaleable: LOD, Billboards, Grid Sort, BSP
 Render:
Threads - Behavior, Cull, Draw, Audio
Property sort, Tri-strips, Flatten

Physical Modeling for Games
Math Library
Templated Matrix Library
#define e4(i, j, l, m, n, a, b) \
flm(0, i, j, m, n, a, b) \
flm(1, i, j, m, n, a, b) \
flm(2, i, j, m, n, a, b) \
flm(3, i, j, m, n, a, b) \
__asm faddp st(1), st(0) \
__asm fxch st(2)
\
__asm faddp st(1), st(0) \
__asm faddp st(1), st(0) \
__asm fstp dword ptr [eax + mi(l, 0, i, j)]
Resizable Matrix Library
ftable_mmm(Add, operator+);
inline ISMXTmpMatrix& __fastcall operator+(const ISMXMatrix& A, const ISMXMatrix& B) {
void* pf = AddPool[ISMXMatrix::lutSizes[A.nr]][ISMXMatrix::lutSizes[A.nc]];
pf = ((PVOIDMX2&)pf)(A, B);;
(int&)((ISMXTmpMatrix*) pf)->nr = (int&)A.nr;
return *(ISMXTmpMatrix*) pf;
}
Physical Modeling for Games
Key References 1

Andy Witkin, Dave Baraff, and Michael Kass
http://www.cs.cmu.edu/afs/cs/user/baraff/www/pbm/pbm.html
 B. Mirtich, Multibody Dynamics Package
http://www.merl.com/people/mirtich/multibodyDynamics.html
 Chris Hecker's Rigid Body Dynamics Information
http://www.d6.com/users/checker/dynamics.htm
 This presentation
http://www.cgdc.com/1998/vault/wcd00506.doc
Physical Modeling for Games
Key References 2
Brandl et al ‘86, ‘87
 Featherstone ‘87

Structurally recursive methods
Spatial vectors
Lien & Kajiya ‘84
Integral properties of polyhedra
 Marhefka & Orin ‘96 Contact forces
http://www.merl.com/people/mirtich/multibodyDynamics.html
 Roberson
& Schwertassek ‘87
Great reference text
 Baraff ‘96
Lagrange Multipliers

Walker & Orin ‘85
 Enright et al ‘95

Classic robotics paper
Runge-Kutta Integrators
Physical Modeling for Games
Acknowledgments
Animation&Vision Group @ MGL @Intel
Baining Guo
Demetri Terzopoulos
Feng Xie
Gary Bradski
John Funge
Mark Holler
Radek Grzeszczuk
Xiaoyuan Tu
NSTL
Àëeêceé Ñóïèêoâ
Physical Modeling for Games