Advanced Algorithms
Hierarchical Kinematic Modeling
Rigid Body Dynamics
CMPT 466
Computer Animation
Torsten Mller
Forward Kinematics
Inverse Kinematics
Rigid Body Constraints
Basic Particle Forces
Collision
Controlling Groups of Objects
particle systems
flocking behaviour
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Reading
Rigid Body Dynamics
Chapter 4 of Parents book
Foley, van Dam, etc.; Angel; Watt;
Glassner; Hill; Baker + Hearns
Keyframing can be tedious - especially to
get realism
Simulate physics by
programming equations of motions
setting initial conditions
Animator gives up control
Animator gets realistic motion
automatically.
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Simulation Update Cycle
Forces
Object properties
Position, orientation
Linear and angular velocity
Linear and angular momentum
mass
Update object properties
Particle Under Forces
Calculate forces
Calculate accelerations
Using mass, momenta
Gravity
Wind
Springs
Collision avoidance
Soft constraints
Calculate acceleration due to forces
Calculate update to object velocity &
position
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Forces - Basic Physics
Friction
Friction - static and kinematic
Gravity
Viscosity
Springs (Hookes law)
Damping
Supporting object
Resting contact
Normal force
Static friction
Fs
F
Fs = usFN
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Friction (2)
Supporting object
Resting contact
Normal force
Static friction
Kinetic friction
Gravity
Fgravity =
Fk
aobject =
F
FN
mobject
Gmearth
2
2
2 = 32 ft /s = 9.8m /s
rearth
Fs = usFN
Fk = uk FN
!
Gm1m2
r2
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Viscosity
Springs (Hookes Law)
Fv = "k v nv
Springs rest length: exerts zero force
kv - depends on shape of object
n viscosity depends on properties of liquid
v- velocity
(should be low)
!
For spherical object: kv = 6"r
Terminal velocity - viscosity and gravity
balance
mg = 6"rnv
E.g., for sphere:
!
Mller/Parent/Machiraju
Fspring = k spring (x " x rest )
xrest
F
Mller/Parent/Machiraju
Spring Mesh
Damping
Edges => springs
Internal springs to stabilize shape
Calm down spring oscillations
Fdamping = "k damping v
!
F = (x " x rest )k spring " vkdamping
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Mass-Spring-Damper System
Define point masses
postion
velocity
mass
force
fixed?
Define springs
point 1
point 2
rest length
kspring
kdamper
Multiple time samples per frame?
Mller/Parent/Machiraju
Mass-Spring-Damper System
For each point
Initialize force with wind
For each spring
Calculate spring-damper force
[Link] += force
[Link] -= force
For each point
acc = gravity
acc += force/mass
newVel = velocity + acc*dt
position += dt*(velocity+newVelocity)/2
Velocity = newVelocity
Mller/Parent/Machiraju
Examples
1, 4, 16 time samples per frame
Examples (2)
Multiple connectivity; fixing a node adding
gravity and wind
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Examples (3)
Randomize
Adding damping; making a flag
Use controlled random numbers to add
interest
Controlled randomness adds more interest
To initial values (positions, velocities)
To force fields (wind direction, wind speed)
To spring constants, masses
To joint angles
Proximal joints: lower amplitude
Distal joints: higher amplitude
Coordinate frequency and phase
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Angular Springs
Constrain Forces (soft
constraints)
Use angles (cosine) between normals
Place a linear spring between ends of
triangles
F
F
F
Fix to surface
Non-penetration
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Particle Under Forces
Particle under Linear Force
Forces
Gravity
Wind
Springs
Collision avoidance
Soft constraints
Calculate acceleration due to forces
Calculate update to object velocity &
position
Mller/Parent/Machiraju
Given: a(t)
Point: x(t)
v(t)
x(t + "t) = x(t) + v(t)"t
v(t + "t) = v(t) + a(t)"t
(v(t) + v(t + "t))
x(t + "t) = x(t) +
"t
2
1
x(t + "t) = x(t) + v(t)"t + a(t)"t 2
2
Uses acceleration at start of interval for
entire interval!
!
Mller/Parent/Machiraju
Euler Integration
Euler Integration (2)
Derivative field
g(t i+1 ) = g(t i ) + g"(t i )#t
g"(t i )
!
g(t i )
!
!
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Numeric Approximation
Numeric Approximation (2)
Cos(x) is velocity function
Euler method
Step size = 0.2
Underlying fuction: Sine
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Numeric Approximation (3)
Euler method
Numeric Approximation (4)
Euler method
Step size = 5.0
Step size = 2.0
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Midpoint Method
Numeric Approximation
A.k.a. 2nd order Runga Kutta
g(t
i+
h
2
g"(t
g"(t i )
!
i+
g(t i+1 ) = g(t i ) + g"(t
i+
h
2
)#t
g(t!i )
!
Mller/Parent/Machiraju
h
2
Midpoint method
Mller/Parent/Machiraju
Step size = 2.0
4th Order Runge Kutta
k2
k3
k1
g(ti+1)
k4
g (ti)
g(t i+1 ) =
Equations of Motion
Linear force
Angular force: torque
Linear momentum
Conserved in a
closed system
Angular momentum
Resistance to linear force: mass
Resistance to angular force: inertia tensor.
k1 k 2 k 3 k 4
+ + +
6 3 3 6
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Rotational Movement
Rotational Movement (2)
Represent orientation with rotation matrix:
R(t)
Represent angular velocity with vector: !(t)
direction is axis of rotation
magnitude is speed of rotation
Angular velocity insensitive to distance
from center or rotation
!(t)
a = b + r(t)
r (t)
"
b
r(t) = " (t) # r(t)
r(t) = " (t) r(t) sin(# )
!
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Rotational Movement (3)
Rotational Movement (4)
R(t) = [ R1(t) R2 (t) R3 (t)]
q is on object and x(t), R(t) is position,
orientation of object
R (t) = [" (t) # R1 (t) " (t) # R2 (t) " (t) # R3 (t)]
!
R (t) = " (t)* R(t)
Define the following for notational convenience:
& Ay ( Bz ' Az ( B y # & 0
$
! $
A ) B = $' (Az ( Bx )' Ax ( Bz ! = $ Az
$ Ax ( B y ' Ay ( Bx ! $' Ay
%
" %
' Az
0
Ax
q(t) = R(t)q + x(t)
q(t) = " (t) # (R(t)q) + v(t)
q(t) = " (t) # (q(t) $ x(t)) + v(t)
Ay # & Bx #
!
' Ax ! $$ B y !! = A* B
0 !" $% Bz !"
It is the dual notation !
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Center of Mass
Force and Torque
Points are often used in CG for masses and
objects
Integration of differential mass times
position in object
F = ma
a = F /m
F(t) = " f i (t)
M = " mi
# i (t) = (q(t) $ x(t)) % f i (t)
m q (t)
"
x(t) =
# (t) = " # i (t)
i i
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Linear Momentum
Angular Momentum
p = mv
L(t) = $ ((q(t) " x(t)) # mi (q(t) " v(t))
P(t) = " miq i (t)
= $ (R(t)q # mi (% (t) # (q(t) " x(t))))
If the center of mass is at the origin:
= $ (mi (R(t)q # (% (t) # R(t)q)))
P(t) = Mv(t)
P (t) = Mv(t) = F(t)
L(t) = I(t)" (t)
L (t) = # (t)
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Inertia Tensor
Iobject
Ixx =
!
!
"Ixx
$
= $Ixy
$#Ixz
Ixz %
'
Iyz '
Izz '&
Ixy
Iyy
Iyz
2
Inertia Tensor (2)
Ixx =
### "(q)(qy + qz )dxdydz
I(t) = R(t)Iobject R(t)
### "(q)(q
Mller/Parent/Machiraju
+ qz )dxdydz
Ixy = " mi x i y i
Ixz = " mi x i zi
Iyz = " mi y i zi
Ixx = " mi (y i + zi )
Iyy = " mi (x i + zi )
Izz = " mi (x i + y i )
2
y
Mller/Parent/Machiraju
Inertia Tensor for a Cuboid
Inertia Tensor for a Sphere
With sides a, b, and c
Iobject
" M (b 2 + c 2 )
%
0
0
$
'
1
2
2
= $
0
M (a + c )
0
'
12 $
0
0
M ( a 2 + b 2 )'&
#
"1 0 0%
2MR $
'
=
0
1
0
'
5 $
$#0 0 1'&
2
Iobject
!
Mller/Parent/Machiraju
Mller/Parent/Machiraju
The Equations - State Vector
Update State Vector
S (t) =
x (t)
Update with velocity
R (t)
Update with angular velocity
P (t)
Update with force
L (t)
Update with torque
" x(t)% " v(t) %
$
' $
'
*
d
d $R(t)' $( (t) R(t)'
S(t) =
=
dt
dt $P(t)' $ F(t) '
$
' $
'
# L(t)& # ) (t) &
v(t) = P(t) / M
" (t) = I(t)#1 L(t)
P (t) = Mv(t) = F(t)
L (t) = $ (t)
I(t) = R(t)Iobject R(t)T
Mller/Parent/Machiraju
R (t) = " (t)* R(t)
Mller/Parent/Machiraju
Update Orientation
! (t) * R(t) and renormalize
Extract axis-angle from ! (t) and rotate
columns of R(t)
Use quaternions
Now, what about collisions?
Detecting them (kinematics)
Finding response (dynamics)
Baraff 1991
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Collisions
Collision Detection
Collision Avoidance
force fields, steer to avoid, etc.
as in flocking
Collision Detection
calculating when objects overlap
during a time interval
Collision Response
Collisions
Distribution of mass important
Localized forces
computation v. accuracy
back up time v. after-the-fact
Mller/Parent/Machiraju
Either back time up to point of collision and
go from there
OR
Respond to collision only at time steps
forward (penalty method)
Multiple collisions?
d1
t collision = t i + "t
d2
Mller/Parent/Machiraju
d1
d1 + d2
Collision Resp. Strategies
Strictly kinematical response
quick and easy
good visual results for (spherical) particles
Penalty method
Kinematic Response
Detect Collision - Point-Plane
Every time step, see if point is one wrong
side of plane
Detect collision by planar equation
used when no backing up in time is enforced
easy to use, however, forces can be unnatural
E ( p) = ax + by + cz + d < 0
Impulse forces
Usually used when time is backed up
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Kinematic Response (2)
Kinematic Response (3)
Negate velocity component in direction of
normal
v " = v # 2(v $ N)N
N
(v " N)N
The role of k:
K=0.8 get bounces
Not physically based, but reasonable visual
response
Using damping: v " = v # (1+ k )(v $ N)N
!
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Penalty Method
Testing Planar Polyhedra
Associate closest point of object with spring
Penalize when interpenetration occurs
Spring force F = k*d
Apply F to point
Compute acceleration and effect velocity along
normal
Point inside a convex/concave polyhedron
test
Edge-plane intersection
Temporal aliasing can occur
d
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Swept Volumes
After collision is detected
Compute motion of one relative to other
Compute swept volume
Determine if other object intersects swept
volume
Tractable only for simple motion
Mller/Parent/Machiraju
Consider applying a force to both bodies
nature simulates collisions like this
Interpenetrating objects will remain so for at
least one more time step
Cannot instantaneously change velocity
Forces need time to be integrated to accelerations
and velocities
Mller/Parent/Machiraju
After collision is detected
Still, we need instantaneous change in
velocity => Impulse
A hack for impenetrable bodies exist
Generalization of subtle surface properties
Simulates a large force for a small time step
Will change velocity like we need
Calculating impulse
Duration of impulse is no time
Actually a small amount of time
Other forces ignored during this period
No friction too !
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Time of Impact
2D Collisions
Must apply impulse exactly at time of
impact
After detecting interpenetration, use binary
search (or more sophisticated) to fine tune
Linear time approx
Beware of tunneling when dt is so large
collisions are missed
Mller/Parent/Machiraju
Were in 2D collisions are:
Vertex / edge
Vertex / vertex
Edge / edge
Compute normal to collision
v/e: perpendicular to edge (pointing towards A by
convention)
e/e: perpendicular to edge
v/v: something reasonable (perhaps use an edge-pert)
Mller/Parent/Machiraju
More Remarks
Edge/edge collisions are modeled as
point/point in this system
Only two colliding bodies at a time
3D is harder because of variety of collision
types
Impulse Force of Collision
Compute change in momentum
J = F"t = Ma"t = M"v = "(Mv) = "P
Impulse is in the direction of the normal:
J = jN
!
!
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Calculating an impulse
Relative Velocity
Solve for one number, j
Apply j in direction of N to A Equal and
Apply j in direction of N to B opposite
rA ( t ) = pA " x A (t )
p A ( t ) = v A (t ) + " A ( t ) # rA ( t )
rB ( t ) = pB " x B (t )
p B ( t ) = v B (t ) + " B ( t ) # rB ( t )
v rel = p A (t ) " p B ( t )
!
!
!
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Relative Velocity (2)
Update Velocities after Collision
Determine contact normal
jN
MA
jN
v B+ = v "B "
MB
v A+ = v "A +
AxB
A
Velocity of a point is sum of linear + angular
velocities
# A+ = # "A + IA"1 (t)(rA $ jN)
x A (t) = v A (t) + " A (t) # rA (t)
# B+ = # "B " IB"1 (t)(rB $ jN)
Relative velocity is difference of velocity of 2
points of contact
Mller/Parent/Machiraju
Mller/Parent/Machiraju
Coefficient of restitution
Computing Impulse
1st: Assume objects cannot rotate
Coefficient of resitution
q A+ = v A+ = v "A +
Models complex compression
+
v rel
= "#v "rel
& restitution of impacting bodies
+
v rel
" N = #$v #rel " N
Models dissipation of energy
jN
MA
q B+ = v B+ = v "B "
jN
MB
2nd: Use definition of coeff. of rest. to derive
a second set of v+ equations
# = 1 " superball (perfectly elastic)
!
# = 0 " clay (perfectly inelastic)
!
(v
+
A
" v B+ ) # N = "$(v "A " v "B ) # N
3rd: Use substitution to solve for j
j
j
v "A # N +
N # N " v "B # N +
N # N = "$(v "A " v "B ) # N
MA
MB
!
% 1
1 (
"
j'
+
* = "(1+ $)v rel # N
Mller/Parent/Machiraju
& MA MB )
Mller/Parent/Machiraju
Computing impulse
Accounting for rotation
Things to note:
Consider velocity of collision point P after
collision
N doesnt have to be normalized
A or B can be fixed by setting mass to infinity
If MA = 1, MB = inf, vB = 0, #=1
q A (t) = v A (t) + " A (t) # rA
Derived from two equations
Computes reflection of vA about N
Mller/Parent/Machiraju
Accounting for rotation (2)
Use definition of coeff. of rest. to derive a
second set of v+ equations
N " (q A+ # q B+ ) = #$N " (q #A # q #B )
Use substitution to solve for j
!
j=
"(1+ #) N $ (q " q
"
A
"
B
1
1
+
+ N $ IA"1 (t)(rA % N) % rA + N $ IB"1 (t)(rB % N) % rB
MA MB
q A (t) = v A (t) + " A (t) # rA
jN
jN
v B+ = v "B "
MA
MB
+
"
"1
+
"
"1
# A = # A + IA (t)(rA $ jN) # B = # B " IB (t)(rB $ jN)
v A+ = v "A +
Mller/Parent/Machiraju
Computing Impulse Forces
Given: two points of contact and normal of contact
Compute velocities of points of contact: va, vb
Compute relative velocities in direction of normal
If Vrelative > threshold
Compute j
PA += J
PB -= J
// actually colliding
LA += rA x J
LB -= rB x J
Else if Vrelative < -threshold, then resting contact
Else they are moving away from each other
Mller/Parent/Machiraju
Mller/Parent/Machiraju