Transcript Computer Animation and Special Effects

Chap 7
Physically Based Animation
Animation (U) Chap 7 Physically Based Animation
1
CS Dept., NCTU, J. H. Chuang
Physically Based Animation

Forces are typically used to maintain
relationships among geometric elements

Accuracy vs. physical realism


Animators is not necessarily concerned with being
accurate but rather with believabibity
Some forces may not relate to physics at all

They may model constraints that an animator may wish
to enforce on the motion
Animation (U) Chap 7 Physically Based Animation
2
CS Dept., NCTU, J. H. Chuang
Physically Based Animation

When modeling motion using physics
principles, we need to decide the level at
which to model the process

Procedure
Computationally less expensive, easier to program
 Lacks flexibility


Purely physics
Computationally expensive
 More flexible

Animation (U) Chap 7 Physically Based Animation
3
CS Dept., NCTU, J. H. Chuang
Physically Based Animation

When physical models are used, animator


is relieved of lower level specification of motions
Needs to be concerned with specifying high-level
relationships or qualities of the motion
Animation (U) Chap 7 Physically Based Animation
4
CS Dept., NCTU, J. H. Chuang
Outline
Basic physics
 Spring meshes
 Particle systems
 Rigid body simulation
 Enforcing soft and hard constraints
A Good reference:


Read Witkin and Baraff’s SIGGRAPH’01 course notes:
Physics-based modeling at
http://www.pixar.com/companyinfo/research/pbm2001/index.html
Animation (U) Chap 7 Physically Based Animation
5
CS Dept., NCTU, J. H. Chuang
Basic physics

Newton’s laws of motions
f  ma
f
a
m
v'  v  at
1
p'  p  (v  v' )t
2
m1m2
f G 2
d
Animation (U) Chap 7 Physically Based Animation
6
CS Dept., NCTU, J. H. Chuang
Basic physics
Spring force : f s  k s ( Lcurrent  Lrest)
Damper force : like a spring, but is negatively
proportion al to the velocity of the spring length :
f d   k d vs
Viscosity : similar to damper, resists velocity
thr ough a medium, such as air
f v  kv v
Momentum : mv
Animation (U) Chap 7 Physically Based Animation
7
CS Dept., NCTU, J. H. Chuang
Basic physics
Torque : rotational force
angular ve locity
angular accelerati on
moment of inertia : a measure of an object' s resistance
to change in orientatio n; a 3x3 matrix I describing
object' s distributi on of mass about its mass' s center
  rF
  I
Animation (U) Chap 7 Physically Based Animation
8
CS Dept., NCTU, J. H. Chuang
Spring meshes

Flexible objects

Flexibility is modeled by a spring-mass-damper
simulation simulating the reaction of the body to
external forces.

Each vertex: a point mass



Each edge: a spring


Assigned by animators
Evenly distributed among object’s vertices
Rest length is original edge length
Spring constants

Arbitrary, assigned uniformly throughout the object
Animation (U) Chap 7 Physically Based Animation
9
CS Dept., NCTU, J. H. Chuang
Spring meshes

Spring-mass-damper simulation

As external forces are applied to specific vertices

Vertices will be displaced relative to other vertices


The displacement induces spring forces, which will impart
forces to the adjacent vertices and reactive forces back to initial
vertices.
Force propagation one time step at a time
f  k s ( Lcurrent  Lrest)  kd vs
Animation (U) Chap 7 Physically Based Animation
10
CS Dept., NCTU, J. H. Chuang
Spring meshes
A simple example
Instant force F applied to V2.
Length of springs E12 and E23
changes.
Spring forces impart restoring
forces to V1 and V2, and V2 and V3
Since external force is wrongly
assumed constant throughout
the time step, a spring simulation
may numerically explode
(the motions get larger and larger).
A smaller time step, or smaller
spring constant, or larger masses
can be used; but slow down the
simulation.
A common method: add dampers.
Animation (U) Chap 7 Physically Based Animation
11
CS Dept., NCTU, J. H. Chuang
Spring meshes
Dampers

A damper introduces an additional force in the
spring that works against the velocity of the
spring length, thus helping to limit the speed at
which a spring changes length.

Help to control the change in length and keep it
within some range that does not allow the
simulation to explode.
f  k s ( Lcurrent  Lrest)  kd vs
Animation (U) Chap 7 Physically Based Animation
12
CS Dept., NCTU, J. H. Chuang
Spring meshes

Modeling with only object edges with spring
dampers can result in a model that has more
than one stable configuration.

Additional spring dampers can help to stabilize the
shape.
If a cube’s edges are modeled with spring
dampers, during applications of extreme
external force is applied, the cube can turn
Inside out.
Animation (U) Chap 7 Physically Based Animation
13
CS Dept., NCTU, J. H. Chuang
Spring meshes
Angular spring dampers

angular spring resists deviation to the rest
angle between faces and imparts a torque
along the edge that attempts to restore the rest
angle.
Animation (U) Chap 7 Physically Based Animation
14
CS Dept., NCTU, J. H. Chuang
Spring meshes
Virtual springs

Virtual springs introduce forces into the
system that do not directly model physical
elements. For example,



Example on the last page
Virtual springs with zero rest lengths can be used
to constrained one object to lie on the other
Virtual springs with non-zero rest lengths can be
used to maintain separation between moving
objects.
Animation (U) Chap 7 Physically Based Animation
15
CS Dept., NCTU, J. H. Chuang
Particle systems

Particles have been used to animate many
behaviors, such as gases, water, fire, rubber,
clothes, flocking, hair.
Animation (U) Chap 7 Physically Based Animation
16
CS Dept., NCTU, J. H. Chuang
Particle systems
Assumptions





Particles do not collide with other particles
Particles do not cast shadow on each other,
except in an aggregate sense
Particles only cast shadow on the rest of
environment
Particles do not reflect light
Particles often have a finite life span
Animation (U) Chap 7 Physically Based Animation
17
CS Dept., NCTU, J. H. Chuang
Particle systems
Steps in a frame





Generate any new particles
Each new particle is assigned attributes
Any particles that have exceeded their life
span are terminated
The remaining particles are animated and their
shading parameters changes according to the
controlling process
The particles are rendered
Animation (U) Chap 7 Physically Based Animation
18
CS Dept., NCTU, J. H. Chuang
Particle generation

For each frame, particles are generated
according to a controlled stochastic process


User-specified distribution centered at the desired
average number of particle per frame
Can be function of time
# of particle  n  Rand() r
where Rand() returns a random number
from - 1.0 to 1.0, and r is a scale factor.
Animation (U) Chap 7 Physically Based Animation
19
CS Dept., NCTU, J. H. Chuang
Particle attributes

Particle properties:
mass
 position
 velocity
 force accumulator
 age, lifespan
 rendering properties (shape parameters, color,
transparency)


Each of the attributes is initialized when the
particle is created.
Animation (U) Chap 7 Physically Based Animation
20
CS Dept., NCTU, J. H. Chuang
Particle life span
At each new frame, each particle’s lifetime is decremented by one
When the attribute reaches zero, the particle is removed from the system.
Animation (U) Chap 7 Physically Based Animation
21
CS Dept., NCTU, J. H. Chuang
Particle animation

Each particle is animated throughout its life.


Position and velocity


Includes position, velocity, and rendering
attributes
Users consider forces and compute the resultant
particle acceleration, update its velocity, and
update the position.
Color and transparency can be a function of
time, its own life span remaining, its height,
and so on. Shape can be a function of its
velocity
Animation (U) Chap 7 Physically Based Animation
22
CS Dept., NCTU, J. H. Chuang
Particle animation
Forces on particles

Forces can be unary, particle pair, or
environmental.

Unary forces


Particle pair forces


Gravity, viscous drag
Can be represented by springs and dampers, if desired.
Environmental forces

Arise from a particle’s relationship to the environment
Animation (U) Chap 7 Physically Based Animation
23
CS Dept., NCTU, J. H. Chuang
Forces on particles


Particles respond to forces
We represent this using differential equations
phase space
f
x 
m
2nd order ODE
Animation (U) Chap 7 Physically Based Animation
x  v
f
v 
m
1st order ODEs
24
CS Dept., NCTU, J. H. Chuang
Unary Forces

Forces that only depend on one particle
fdrag
v
Gravity
Viscous Drag
Wind Fields
f = mg
f = -kdv
f = kvwind
Animation (U) Chap 7 Physically Based Animation
25
CS Dept., NCTU, J. H. Chuang
n-ary Forces


Forces that depend on n particles
Example: binary forces between two particles
- spring and damper
x a  xb
f a  k s (| x a  x b | l0 )
| x a  xb |
fa
fb
 ( v a  v b )  (x a  x b )  x a  x b

 kd 
| x a  xb |

 | x a  xb |
Springs
Animation (U) Chap 7 Physically Based Animation
26
CS Dept., NCTU, J. H. Chuang
n-ary Forces: Spring Force

If particle is located farther than the rest position, the
spring force needs to pull it back


f a  kl , k  0
 
xa  xb  r  0

If the particle is located nearer than the rest position,
the spring force needs to push it away


f a  kl , k  0
 
xa  xb  r  0

Combine two cases:


 
f a  ks ( xa  xb  r )l , ks  0
 
 
xa  xb
 ks ( xa  xb  r )  
xa  xb
Animation (U) Chap 7 Physically Based Animation
27
xa
 x  x
l  a b
xa  xb
CS Dept., NCTU, J. H. Chuang

xb
n-ary Forces: Damping Forces

According to the law of energy conservation, a
particle system consists of only masses and
springs keep bouncing from each other after
external forces disappear

Damping/viscous drag force resist motion,
making a particle system gradually come to
rest in the absence of external forces
Animation (U) Chap 7 Physically Based Animation
28
CS Dept., NCTU, J. H. Chuang
n-ary Forces: Damping Forces (cont.)

It is highly recommended that at least a small
amount of damping is applied to each particle

Excessive damping, however, makes a particle
appear that floating in molasses (energy
dissipates out too quickly, not responsive)
Animation (U) Chap 7 Physically Based Animation
29
CS Dept., NCTU, J. H. Chuang
n-ary Forces: Damper Force

If two particles are departing, the damper force needs
to pull them back


f a  kl , k  0
  
(va  vb )  l  0

If two particles are approaching, the damper force
needs to push them
away



 
(va  vb )  l  0

f a  kl , k  0

va
cases: 
Combine two

 
vb
f a  kd ( va  vb  l )l , kd  0
 
   
(va  vb )  ( xa  xb ) ( xa  xb )  xa  xb
 kd
 
  l  
xa  xb
xa  xb
xa  xb
Animation (U) Chap 7 Physically Based Animation
30
CS Dept., NCTU, J. H. Chuang
Spatial Forces

Forces that depend on nearby particles within a
local region
Gravity, Lennard-Jones and electric potentials
Spatial data structures can optimize computations
Animation (U) Chap 7 Physically Based Animation
31
CS Dept., NCTU, J. H. Chuang
Particle rendering

Several methods

Model each particle as a point light source
Each particle is rendered to a small graphical primitive
(blob).
 Particles that map to the same pixels in the image are
additive - the color of a pixel is simply the sum of the
color values of all the particles that map to it


Model each particle as a textured billboard


Polygon facing the viewer, texture
Rendered as Metaballs in off-line rendering;
isosurfaces computed from particle-metaballs
make quite convincing liquids.
Animation (U) Chap 7 Physically Based Animation
32
CS Dept., NCTU, J. H. Chuang
Particle rendering
Particle
Animation (U) Chap 7 Physically Based Animation
33
CS Dept., NCTU, J. H. Chuang
Particle rendering
Particle
Animation (U) Chap 7 Physically Based Animation
34
CS Dept., NCTU, J. H. Chuang
Particle rendering
Billboard texture
Animation (U) Chap 7 Physically Based Animation
35
CS Dept., NCTU, J. H. Chuang
Particle rendering
Billboard texture
Animation (U) Chap 7 Physically Based Animation
36
CS Dept., NCTU, J. H. Chuang
Particle rendering
Billboard texture
From Mark Harris’s work
http://www.markmark.net/clouds/
Animation (U) Chap 7 Physically Based Animation
37
CS Dept., NCTU, J. H. Chuang
Particle rendering
Billboard texture

An impostor replaces a cloud with a billboard
textured with an image of the cloud from a
certain viewpoint.

Image is updated only when translation of the
viewpoint introduces enough error in the image


Impostors can be reused for many frames.
By using impostors, we are able to render
cloudy scenes of hundreds of clouds and
hundreds of thousands of particles at very high
frame rates.
Animation (U) Chap 7 Physically Based Animation
38
CS Dept., NCTU, J. H. Chuang
Particle rendering
Billboard texture
Figure 6: Impostor generation and
translation error
metric.
Impostor generation and translation error metric
Animation (U) Chap 7 Physically Based Animation
39
CS Dept., NCTU, J. H. Chuang
Particle rendering
Video
Cloud rendering by Niniane Wang
http://www.ofb.net/~niniane/clouds/
Animation (U) Chap 7 Physically Based Animation
40
CS Dept., NCTU, J. H. Chuang
Particle rendering
Metaballs and isosurface
From “Screen Space Fluid Rendering with Curvature Flow “
http://industrialarithmetic.blogspot.com/2009/01/
our-paper-screen-space-fluid-rendering.html
Animation (U) Chap 7 Physically Based Animation
41
CS Dept., NCTU, J. H. Chuang
Collision Detection

Determine when a particle has collided an
object
Object’s surface
N
Nx  0
Nx  0

Particle has collided if and only if N  x  0
Animation (U) Chap 7 Physically Based Animation
42
CS Dept., NCTU, J. H. Chuang
Collision Response



What should we do when a particle has
collided?
The correct thing to do is rollback the
simulation to the exact point of contact
Easier to just modify positions and velocities
vt
vn
v
After the collision:
N
v
new
v
new
  v n  v t
coefficient of restitution
Animation (U) Chap 7 Physically Based Animation
43
CS Dept., NCTU, J. H. Chuang
Contact Forces

When the particle is on the collision surface a
contact force resists penetration
c
f  (N  f ) f
(N f )  0

Contact forces do not resist leaving the surface

fc  0
(N f )  0
Simple friction can be modeled
f  k f (N  f ) vt
f
Animation (U) Chap 7 Physically Based Animation
44
(N f )  0
CS Dept., NCTU, J. H. Chuang
Structure of Particle Systems

Separate the data structures and integration
state
Particle System
particles time
send data as
6n vectors
state/derivatives
Particle x
x
v v
f f
m m
x
v
f
m

Solver
state
derivatives
x
v
f
m
Animation (U) Chap 7 Physically Based Animation
45
CS Dept., NCTU, J. H. Chuang
Structure of Particle Systems
Implementation

Solver Interface
Solver
System
GetDim
x
v
f
m
Get/Set State
Deriv Eval
Animation (U) Chap 7 Physically Based Animation
46
6
x
v
v
f/m
CS Dept., NCTU, J. H. Chuang
Structure of Particle Systems
Implementation

Solver Interface
Solver
System
6n
GetDim
particles
Get/Set State
n
time
Deriv Eval
Animation (U) Chap 7 Physically Based Animation
47
x1
v1
x2
v2
v1 v2
f1/m1f2/m2
xn
vn
vn
fn/mn
CS Dept., NCTU, J. H. Chuang
Physics Engines for Dynamics Simulation

Open Dynamics Engine (ODE)





Free software http://www.ode.org/
high performance library for simulating rigid body
dynamics.
It is fully featured, stable, mature and platform
independent with an easy to use C/C++ API.
It has advanced joint types and integrated collision
detection with friction.
ODE is useful for simulating vehicles, objects in
virtual reality environments and virtual creatures.
Animation (U) Chap 7 Physically Based Animation
48
CS Dept., NCTU, J. H. Chuang
Physics Engines for Dynamics Simulation

Havok




Commercial software
“Reactor” in 3ds MAX
State-of-the-art game physics solution, for use with
in-house game animation systems
Havok Destruction™ is the cross-platform tool for
simulation of rigid body destruction.
Animation (U) Chap 7 Physically Based Animation
49
CS Dept., NCTU, J. H. Chuang
Physics Engines for Dynamics Simulation

NVIDIA PhysX



A powerful physics engine which enables real-time
physics in leading edge PC and console games.
Is widely adopted by over 150 games, is used by
more than 10,000 registered users.
Designed specifically for hardware acceleration by
powerful processors with hundreds of cores.
Combined with the tremendous parallel processing
capability of the GPU, PhysX will provide an
exponential increase in physics processing power
Animation (U) Chap 7 Physically Based Animation
50
CS Dept., NCTU, J. H. Chuang
Physics Engines for Dynamics Simulation

AGEIA PhysX accelerator


The world’s first dedicated physics processor
designed to support extreme physical gaming
interactions.
Its highly parallel, interactive PhysX cores are
optimized for dynamic, large-scale, physics
processing to accelerate physical motion and
interaction at a scale and quality far beyond that of
general purpose processors.
Animation (U) Chap 7 Physically Based Animation
51
CS Dept., NCTU, J. H. Chuang
Rigid Body Simulation


Various forces to be simulated are modeled.
When the forces are applied to objects, they
induce



linear acceleration (based on object’s mass)
angular acceleration (based on mass’s distribution)
These accelerations are integrated over a delta
time step to get changes of object’s velocities,
which in turns integrated over a delta time step
to produce changes in position and orientation.
Animation (U) Chap 7 Physically Based Animation
52
CS Dept., NCTU, J. H. Chuang
Rigid Body Simulation


Various forces to be simulated are modeled.
When the forces are applied to objects, they
induce



linear acceleration (based on object’s mass)
angular acceleration (based on mass’s distribution)
Read Witkin and Baraff’s SIGGRAPH’01
course notes: Physics-based modeling

http://www.pixar.com/companyinfo/research/pbm2
001/index.html
Animation (U) Chap 7 Physically Based Animation
53
CS Dept., NCTU, J. H. Chuang
Rigid Body Simulation
Update cycle
Animation (U) Chap 7 Physically Based Animation
54
CS Dept., NCTU, J. H. Chuang
Rigid Body Simulation

Continuous process vs. discrete time simulation



Assume acceleration is constant over the delta time
step
These accelerations are integrated over a delta time
step to get changes of object’s velocities, which in
turns integrated over a delta time step to produce
changes in position and orientation.
How to update?
Euler integration method
 Runge –Kutta method: Second-order in magnitude of
error term

Animation (U) Chap 7 Physically Based Animation
55
CS Dept., NCTU, J. H. Chuang
Physics-based Simulation

A procedure that generates a sequence of the
states of a system based on physics laws
xi
Newtonian laws
elastic forces
wind
gravity
friction
…
xi+1
xi
xi+1= xi+ △x
△x
Animation (U) Chap 7 Physically Based Animation
56
CS Dept., NCTU, J. H. Chuang
Differential Equations

Differential equation describes the relation
between an unknown function and its
derivatives

Solving a differential equation is to find a
function that satisfies the relation

Numerical solution of differential equations is
based on finite-dimensional approximation
Animation (U) Chap 7 Physically Based Animation
57
CS Dept., NCTU, J. H. Chuang
Ordinary Differential Equations

Ordinary differential equation (ODE)

All derivatives are with respect to single
independent variable, usually representing time
Known function
dx
 f (x(t ))  f (x, t )
dt
Unknown function
that evaluates the
state given time
Time derivative of
the unknown function
x(t0 ) : state vector at time t0
*We’ll show that a higher ODE can be transformed into
this 1st order system soon!
Animation (U) Chap 7 Physically Based Animation
58
CS Dept., NCTU, J. H. Chuang
Higher-Order ODEs

Order of ODE determined by highest-order
derivative of solution function appearing in
ODE

Equations with higher derivatives can be
transformed into equivalent first-order system
Animation (U) Chap 7 Physically Based Animation
59
CS Dept., NCTU, J. H. Chuang
Higher-Order ODEs (cont.)


Given k-th order ODE
d (k ) y
 f ( y ( k 1) , y ( k 2 ) ,..., y ' , y, t )
dt
 Original ODE equivalent to first
Define
order system
x1 (t )  y
x2
 x '1  

x2 (t )  y'
 x'  

x
3
 2 

x3 (t )  y"
  



 

x 'k 1  
xk


( k 1)
xk (t )  y
 x 'k   f ( y ( k 1) ,, y ' , y , t )
Animation (U) Chap 7 Physically Based Animation
60
CS Dept., NCTU, J. H. Chuang
Visualizing Solution of ODE
x2
dx
x 
 f ( x, t )
dt
x(t ) : a moving point
f (x, t ) : x' s velocitie s
x1
Animation (U) Chap 7 Physically Based Animation
61
CS Dept., NCTU, J. H. Chuang
Vector Field

The complete set of all solutions to the
differential equation x  f (x, t ) defines a
vector field over (x, t) plane.
x2
Think of this vector field as
the sea, and the velocity of
current at different places
and time is defined by f(x,t)
x1
Animation (U) Chap 7 Physically Based Animation
62
CS Dept., NCTU, J. H. Chuang
Initial Value Problem
Given x  f (x, t ) and x0  x(t0 ), find x(t )

For a particular initial value, the solution is a
curve.

Given the starting point, follow the integral curve
x2
Release a ball at any starting
point and let it drift following
the current. The trajectory
swept out by the ball is an
integral curve.
x1
Animation (U) Chap 7 Physically Based Animation
63
CS Dept., NCTU, J. H. Chuang
Numerical Solution of ODEs



Instead of true integral curve, numerical solution
follow a polygonal path
Each leg is obtained by evaluating the derivative
at discrete time steps
x2
Bigger steps, bigger errors
x1
Animation (U) Chap 7 Physically Based Animation
64
CS Dept., NCTU, J. H. Chuang
Issue I: Inaccuracy

Error turns x(t) from a circle into the spiral of
your choice!

May jump to other circles
x2
x1
Animation (U) Chap 7 Physically Based Animation
65
CS Dept., NCTU, J. H. Chuang
Issue II: Instability

May diverge!
x2
to Neptune!
x1
Animation (U) Chap 7 Physically Based Animation
66
CS Dept., NCTU, J. H. Chuang
Euler’s Method


Simplest numerical solution method
Bigger time steps, bigger errors
x2
x ( t  h )  x ( t )  h  f ( x, t )
x1
Animation (U) Chap 7 Physically Based Animation
67
CS Dept., NCTU, J. H. Chuang
Euler’s Method (cont.)
Given x  f (x, t ) and x0  x(t0 ), find x(t )

Solves ODE using one-term Taylor-series
2
h
x(t0  h)  x(t0 )  hx (t0 )  x( )
2
O(h2):
x  f (x, t )
2nd order accurate
x 0  x(t0 )
x(t  h)  x(t )  h  f (x, t )
x n1  x n  hx n
Animation (U) Chap 7 Physically Based Animation
68
CS Dept., NCTU, J. H. Chuang
Euler’s Method (cont.)


Truncation error in s single step : O(h2)
The error in a complete solution is an
accumulation of all the single step errors
To compute x(t0  T ), we need T/h steps
2
where each step acquires an error of O(h ).
T
2
So total error is O(h )
h
Animation (U) Chap 7 Physically Based Animation
69
CS Dept., NCTU, J. H. Chuang
Rigid Body Simulation
Euler integration method (Book)

Explicit Euler integration method
xn 1  xn  h
yn 1  yn  hf ' ( xn , yn )
Animation (U) Chap 7 Physically Based Animation
70
CS Dept., NCTU, J. H. Chuang
Drawbacks of Euler’s Method


Too inaccurate to be used in practice
Inefficiency



Need to use small time-steps to avoid divergence
Example:
http://www.cse.uiuc.edu/iem/ode/eulrmthd/
Improvement using the midpoint method

Slope at midpoint is used
Animation (U) Chap 7 Physically Based Animation
71
CS Dept., NCTU, J. H. Chuang
Runge-Kutta method
The Midpoint Method
a. Compute an Euler step
Assume f depends on t only
indirectly through x
x  h  f (x(t0 ))
b. Evaluate f at the midpoint
x
f mid  f (x(t0 )  )
2
h  f (x(t0 )) 

 f  x(t0 ) 

2


c. Take a step using the
midpoint value
Animation (U) Chap 7 Physically Based Animation
x2
x(t0  h)  x(t0 )  h  f mid
72
CS Dept., NCTU, J. H. Chuang
x1
Runge-Kutta method
The Midpoint Method (cont.)


Solves ODE using two-term Taylor-series
h2
h3
x(t0  h)  x(t0 )  hx (t0 )  x(t0 )  x( )
2
3
d
d
dx
x  x 
f (x, t )  f ' (x)
 f ' ( x) f ( x)
dt
dt
dt
Approximating f by Taylor-series
h
f (x0  x)  f (x0 )  x f ' (x0 ) where x  f (x 0 )
2
h
h
h
f (x 0  f (x 0 ))  f (x 0 )  f (x 0 ) f ' (x 0 )  f (x 0 )  x0
2
2
2
Animation (U) Chap 7 Physically Based Animation
73
CS Dept., NCTU, J. H. Chuang
Runge-Kutta method
The Midpoint Method (cont.)
h
h
f (x 0  f (x 0 ))  f (x 0 )  x0
2
2 Turning O(h ) to O(h )
h2
h


x0  h  f (x 0  f (x 0 ))  f (x 0 )
2
2


h2
h3
x(t0  h)  x(t0 )  hx (t0 )  x(t0 )  x( )
2
3
h


 x(t0 )  hf (x 0 )  h  f (x 0  f (x 0 ))  f (x 0 )  O (h 3 )
2


h
 x(t0 )  hf (x 0  f (x 0 ))  O (h 3 )
2
2
Animation (U) Chap 7 Physically Based Animation
74
CS Dept., NCTU, J. H. Chuang
3
Runge-Kutta method
The Midpoint Method (Book)

Runge –Kutta method


Symmetric w.r.t. the time interval
Second-order in magnitude of error term
xn 1  xn  h
h
h '
yn 1  yn  hf ( xn  , yn  f ( xn , yn ))
2
2
Note that : the derivative at the middle of interval
is evaluated using explicit Euler method.
'
Animation (U) Chap 7 Physically Based Animation
75
CS Dept., NCTU, J. H. Chuang
Runge-Kutta 4th Order Method
1
5
x(t0  h )  x(t0 )  (k1  2k2  2k3  k4 )  O (h )
6

Using a weighted average of slopes obtained at
four points
x
f (x0  k3 , t0  h)
k1  hf (x0 , t0 )
k1
h
k2  hf (x 0  , t0  )
2
2
k2
h
k3  hf (x 0  , t0  )
2
2
k4  hf (x0  k3 , t0  h)
Animation (U) Chap 7 Physically Based Animation
f (x 0 
k1
h
, t0  )
2
2
f (x 0 
x(t0  h)
k1
h
, t0  )
2
2
f (x 0 , t0 )
76
CS Dept., NCTU, J. H. Chuang
t
Runge-Kutta 4th Order Method (Book)

Fourth-order Runge –Kutta method
xn 1  xn  h
k1  hf ' ( xn , yn )
h
k1
k 2  hf ( xn  , yn  )
2
2
h
k2
'
k3  hf ( xn  , yn  )
2
2
k 4  hf ' ( xn  h, yn  k3 )
'
1
yn 1  yn  k1  2k 2  2k3  k 4   O(h 5 )
6
Animation (U) Chap 7 Physically Based Animation
77
CS Dept., NCTU, J. H. Chuang
xn 1  xn  h
k1  hf ' ( xn , yn )
h
k1
k 2  hf ( xn  , yn  )
2
2
h
k2
'
k3  hf ( xn  , yn  )
2
2
k 4  hf ' ( xn  h, yn  k3 )
'
k1 k 2 k3 k 4
yn 1  yn      O(h 5 )
6 3 3 6
Animation (U) Chap 7 Physically Based Animation
78
CS Dept., NCTU, J. H. Chuang
Adaptive Step Size


Ideally, we want to choose h as large as
possible, but not so large as to cause big error
or instability
We can vary h as we march forward in time
Animation (U) Chap 7 Physically Based Animation
79
CS Dept., NCTU, J. H. Chuang
Adaptive Step Size for Euler’s Method

What is optimal h if we want to have an error
of as much as ε, and the current error is e?

e
h
* Let h'  kh.
h' 2


2
2
e( )  ek    k   k 
h
e
e
Animation (U) Chap 7 Physically Based Animation
81
CS Dept., NCTU, J. H. Chuang
Take Home Message
x2

Don’t use Euler’s method




Inaccuracy
Inefficiency (or unstable)
Do use adaptive step size
Read Witkin and Baraff’s SIGGRAPH’01
course notes: Physics-based modeling

x1
http://www.pixar.com/companyinfo/research/pbm2
001/index.html
Animation (U) Chap 7 Physically Based Animation
82
CS Dept., NCTU, J. H. Chuang
Motion equation for a rigid body

To develop the equations of motion for a rigid
body, we need to discuss

Linear force vs. rotational force




Torque
Linear momentum vs. angular momentum
Inertia tensor
Equations
Animation (U) Chap 7 Physically Based Animation
83
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
angular velocity

Angular velocity w(t)



Direction: Axis of rotation,
Speed of orientation in revolutions per unit of time
For linear motion, x(t) and v(t) are related by
d
v(t )  x(t )
dt

How are R(t) and w(t) related?

We need to find how the derivative of a vector in a
rigid body is related to w(t)
Animation (U) Chap 7 Physically Based Animation
84
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
angular velocity of a particle

Angular velocity of a point
p(t )  x(t )  r (t )
r (t ) is represnted in world space.
w(t )  angular ve locity of p (t )
p
r(t )  w(t )  r (t )
r(t )  w(t ) r (t ) sin 
Animation (U) Chap 7 Physically Based Animation
85
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
angular velocity of a particle
Why r(t )  w(t )  r (t ) ?
Write r (t )  a(t )  b(t ), where a (t ) is parallel to w(t ) and
b(t ) is perpendicu lar to w(t ).
Suppose angular ve locity is constant, then " a" traces out
a circle centered on the w(t ) axis. So the instantane ous
change of r (t ) is perpendicu lar to both b and w(t ) ,
and the instantane ous change of r (t ) has magnitude
b w(t ) . Putting this together, we can write
r(t )  w(t )  r (t )
Animation (U) Chap 7 Physically Based Animation
86
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
angular velocity of a particle
Let r (t )  a  b(t ),
where a is parallel to w(t )
r(t )  w(t )  r (t )
 w(t )  (a  b(t ))
 w(t )  a  w(t )  b(t )
 w(t )  b(t )
Note :
Direction of r(t )  w(t )  r (t )
Animation (U) Chap 7 Physically Based Animation
87
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
angular velocity of a rigid body

Angular velocity of a rigid body


Position and orientation of a rigid body are
represented by x(t), and R(t)
x(t), and R(t) are used to transform the body-space
description into world space
Animation (U) Chap 7 Physically Based Animation
88
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
angular velocity of a rigid body

R(t) specifies a rotation of the body about the
center of mass


It is a matrix of 3 orthogonal column vectors
At time t,
1
 
R(t )  0   R1 (t ), where R(t )  R1 (t ) R2 (t ) R3 (t )
 0
 
represents the x-axis of body space in world space
Animation (U) Chap 7 Physically Based Animation
89
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
angular velocity of a rigid body
Animation (U) Chap 7 Physically Based Animation
90
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
angular velocity of a rigid body

At time t, the derivative of the first column of
R(t) is the rate of change of this vector. So
R (t )  w(t )  R1 (t ) w(t )  R2 (t ) w(t )  R3 (t )
 w(t )* R(t )


R
(
t
)

R
(
t
)
R
(
t
)
*R1 (t )
2
3
where w(t ) is the matrix such that w(t )* Ri (t )  w(t )  Ri (t ).
 (t )  w(t )  R (t ) w(t )  R (t ) w(t )  R (t )
R
1
2
3
Note :
 a y bz  by a z   0
 a z a y  bx 
 
 

0  a x  by   a *b
a qb(t)  Ra(tx b)qz  bxx(at )z    a z

 a b  b a    a
q(t )  Rx(t )yq  xx (ty)  R(t )q y v(ta)x w(t0) (qb(tz ) x(t ))  v(t )
Animation (U) Chap 7 Physically Based Animation
91
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
angular velocity of a rigid body

A point Q on the rigid body with body-space
coordinate q.

Then the world-space location of q(t) is the result of
first rotating q about the origin and then translating it:
q(t )  R(t )q  x(t )
This separates the velocity of a point
on a rigid body into two components:
A linear component v(t)
A angular component w x (q(t)-x(t))
and the velocity of q(t ) :
q (t )  R (t )q  x (t )
 R (t )q  v(t )
 w(t )* R(t ) R 1 (t )( q(t )  x(t ))  v(t )
 w(t )* (q(t )  x(t ))  v(t )  w(t )  (q(t )  x(t ))  v(t )
Animation (U) Chap 7 Physically Based Animation
92
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Center of mass

Integration of the differential mass times its
global position in the object
M   mi
m q (t )

x(t ) 
i i
M
Animation (U) Chap 7 Physically Based Animation
93
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Forces and torque

Linear force vs. rotational force
F (t )   Fi (t )
 (t )   i (t )
where
 i (t )  (qi (t )  x(t ))  Fi (t )
Animation (U) Chap 7 Physically Based Animation
94
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Linear momentum


Linear momentum p of a particle with mass m
and velocity v: P(t )  mv(t )
Linear momentum of a rigid body
P(t )   mi ri (t )
  mi v(t )  mi w(t )  (ri (t )  x(t )) 
  mi v(t )  w(t )   mi (ri (t )  x(t ))
  mi  v(t )
Total linear momentum of a rigid body
is the same as if the body is simply a
particle with mass m and velocity v(t).
 M v(t )
Animation (U) Chap 7 Physically Based Animation
95
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Linear momentum

Derivative of linear momentum and force
M is constant :
P (t )  mv(t )  ma(t )  F (t )

Instead of v(t), we use P(t) as a state variable for
the rigid body.

Be more consistent with the way we deal with
angular velocity and acceleration.
Animation (U) Chap 7 Physically Based Animation
96
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Angular momentum (book)_

Angular momentum of a particle
For a particle on the object, with local vector r (t ),
mass m, and velocity r(t ), its angular momentum
is
L(t )  r (t )  mr(t )
Animation (U) Chap 7 Physically Based Animation
97
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Angular momentum (book)

Angular momentum of an object
Total angular momentum of the object :
L(t )   ri (t )  mi ri (t )
  (qi (t )  x(t ))  mi (qi (t )  v(t ))
  {R(t )q)  mi [ w(t )  (qi (t )  x(t ))]}
  {R(t )q)  mi [ w(t )  ( R(t )q)]}
  {mi [( R(t )q)  ( w(t )  R(t )q)]}
L (t )   (t )
Animation (U) Chap 7 Physically Based Animation
98
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Angular momentum

Angular momentum of a rigid body

Similar to linear momentum
L(t )  I (t ) w(t )
where I(t) (called inertia tensor) is a 3x3 matrix that
describe how the mass in the body is distributed
relative to the body’s center of mass.
 I(t) depends on orientation of the body; but does not
depend on the body’s translation
Animation (U) Chap 7 Physically Based Animation
99
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Inertia tensor

At a given time t, let ri ' (t ) be the displacement of
particle i from body’s mass center x(t) by
ri ' (t )  r (t )  x(t ) .
I(t) is expressed in terms of r’i as the symmetric
matrix
Animation (U) Chap 7 Physically Based Animation
100
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Inertia tensor

How to compute I(t) for a rotated dody?


Compute at run-time? Too expensive!
Pre-computed I(t) in body-space coordinates and
then compute it at run time after rotation.
I (t )  R(t ) I body (t ) R(t )T
Animation (U) Chap 7 Physically Based Animation
101
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Inertia tensor
,T ,
i
i
,2
ix
,2
iy
,2
iz
Using r r  r  r  r , I (t ) can be rewritten as
Taking the outer product of ri, with itself :
Animation (U) Chap 7 Physically Based Animation
102
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Inertia tensor
I (t ) can be rewritten as
Since ri (t )  R(t )r0i  x(t ) where ri (t )  R(t )r0i and R(t ) R(t )  I ,
,
Animation (U) Chap 7 Physically Based Animation
103
T
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Inertia tensor
Since r0Ti r0i is a scalar, we can rearrange I (t ) as
Constant over the
simulation
Let
We have
Animation (U) Chap 7 Physically Based Animation
104
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Inertia tensor
Animation (U) Chap 7 Physically Based Animation
105
CS Dept., NCTU, J. H. Chuang
Orientation and rotational movement
Inertia tensor

Linear momentum and linear velocity
P(t )  M v(t )

Angular momentum and angular velocity
L(t )  I (t ) w(t )

I(t): inertia tensor, describes how the mass is
distributed about the center of mass in space
For an un-transformed object: Iobject
 For a transformed object (depends only on orientation)

I (t )  R(t ) I object (t ) R(t )T
Animation (U) Chap 7 Physically Based Animation
106
CS Dept., NCTU, J. H. Chuang
Motion Equation

The state of a rigid body

Spatial information
Position
 Orientation


Velocity information
Linear momentum
 Angular momentum


Known information


Mass
Body-space inertia
Animation (U) Chap 7 Physically Based Animation
107
CS Dept., NCTU, J. H. Chuang
Motion Equation
 x(t ) 
 x(t )   v(t ) 
 R(t )
 R(t )  w(t ) * R(t )
d
d 




S (t ) 
S (t ) 
 P(t )
dt
dt  P(t )  F (t ) 



 

 L(t ) 
 L(t )    (t ) 
P(t )
v(t ) 
M
T
I (t )  R(t ) I body R(t )
w(t )  I (t ) 1 L(t )
Animation (U) Chap 7 Physically Based Animation
108
CS Dept., NCTU, J. H. Chuang
Bodies in collision

Objects moving in a dynamic scene




Objects in collision – need to do the detection
Objects sliding against on other object
Objects resting on each other
Need to calculate forces for computing
accurate reaction
Animation (U) Chap 7 Physically Based Animation
109
CS Dept., NCTU, J. H. Chuang
Bodies in collision

Ultimate goal in VR


At a minimum


Real and virtual objects need to behave like real
ones.
Objects should not pass through each other, and
things should move as expected when pushed,
pulled, or grasped.
Overall

Physical simulation in VR must run reliably,
seamlessly, automatically, and in real time.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Collision detection
Computer Animation
Animation (U) Chap 7 Physically Based Animation
111
Collision detection
Haptic Interaction
From J.C. Latombe’s notes
Animation (U) Chap 7 Physically Based Animation
112
Collision detection
Motion/Path Planning
From J.C. Latombe
From James Kuffner
Animation (U) Chap 7 Physically Based Animation
113
Collision detection
Crowd Simulation
From J.C. Latombe’s notes
Animation (U) Chap 7 Physically Based Animation
114
Bodies in collision
To prevent interpenetration
 Collisions must be detected.
 Velocities must be adjusted in response to
collisions.
 Collision response must be computed.

If the collision response does not cause the objects
to separate immediately, contact forces must be
calculated and applied until separation finally
occurs.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Problems of Collision Detection

A naive collision detection has




Fixed-timestamp weakness
All-pair weakness
Pair-processing weakness
Features that current methods have





Interactive rate
Handle polygon soaps
Models can undergo rigid-body motion
Provide well-fit bounding volume
Collision detection only occurs at discrete times.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Performance of a naive method

All-pair weakness



If the scenario contains n moving objects and m
static objects, total object test for each frame is
Pair processing
Note:

 n
nm   
 2
weakness
Performance evaluations for collision detection are
extremely difficult since algorithms are sensitive to
the actual scenarios, and there is no algorithm that
performs best in all cases.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Speed Up Methods

Bounding volume for object level and polygon level.



Spatial coherence


Pure bounding volume
Hierarchical bounding volumes
 Support progressive collision detection.
Usually large regions of the space are occupied by only one object or
none at all. If some objects share the same region, they are likely
intersecting.
Time coherence

Moving objects usually move on a continuous path. Results of earlier
collision query can be exploited.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Two-level Collision Detection
Two-level Collision Detection


Globally searching pairs of objects that have
potential collision

Spatial partition

Dimension reduction and sorting (Sweep-and-Prune)
Collision detection on a pair of objects


Hierarchical CD based on OBBTree, AABBTree,…
Polygon-polygon overlap test
Animation (U) Chap 7 Physically Based Animation
119
119
CS Dept., NCTU, J. H. Chuang
Two-level CD system
Pruning MultiBody pairs
(Sweep/Prune)
Exact collision
Detection
(OBB tree)
Simulation
Collision
response
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Space Partition

Spatial coherence is usually exploited by
partitioning the space.


All-pair weakness can be resolved by the use of
spatial coherence.
Space partition methods differ in fast
neighbor-finding (for static environments) and
fast updating for moving objects.



Grid (uniform partition)
Octree
Binary space partition
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Temporal Coherence
One or Two-Dimension Sweep and Prune

Sorting objects in 3-D space by dimension
reduction



If two objects collide in a 3D space, their orthogonal
projections onto the xy, yz, and xz-planes and x, y,
and z-axes must overlap.
Project bounding volume of objects.
Based on Axis-aligned bounding boxes (AABB).


Fixed-size bounding cube: large enough to contain the
object at any orientation.
Dynamically-resized rectangular bounding boxes
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
One or Two-Dimension Sweep and Prune


Project each 3D box onto x, y, and z axes.
Construct 3 lists, one for each dimension.


Each list contains the values of the endpoints of
the projected interval corresponding to that
dimension.
Determine which intervals overlap by sorting
these lists.


Utilize temporal or frame coherence by changing
only the values of the interval endpoints.
Bubble sort or insertion sort work well for
previously sorted lists.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
One or Two-Dimension Sweep and Prune
Implementation issues - -1


Fixed-sized cubes are preferred over
dynamically-resized boxes, except for the class
of oblong objects.
Which sorting method is better?



Bubble sort works better for environments where
only a few objects move, such as walkthrough
Insertion sort works better for environments where
large number of objects move.
Overlap status consists of a Boolean flag for
each dimension. Whenever all three of these
flags are set, the bb of objects pair overlap.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Bounding Volumes

Bounding volume is used to do a pre-check
before doing any further collision detection.




Bounding sphere (BS)
Fast overlapping check, not a tight fit.
Axis-aligned bounding box (AABB)
Fast overlapping check, a better tight fit.
Oriented bounding box (OBB)
Tight fit,
but with relatively expensive overlapping test.
K-DOPS (direct oriented polytopes)
OBB + more cutting axes
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Bounding Volumes
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical Bounding Volumes

Hierarchical bounding volume is useful



For efficiently resolving the pair-processing
weakness, and
Providing a basis for the hierarchical or timecritical scheme for collision detection.
Three types:



Hierarchical Axis-aligned bounding box
Hierarchical Oriented bounding box
Hierarchical Bounding sphere
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
General Hierarchical Collision
Detection Scheme

Common denominators of these schemes


A hierarchical bounding volume is built for each
object.
High-level code for a collision query is similar,
regardless of the BV type used.


BV-BV overlapping tests and primitive-primitive
overlapping tests are different depending on what BVs
and primitives are used.
A simple cost function can be used to trim,
evaluate, and compare performance.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical Collision Detection
Hierarchy Building

Common hierarchy used:




K-ary tree, where each node may at most have k
children.
At each internal node, there is a BV enclosing all
its children.
At each leaf, there are one or more primitives.
Three ways of building a hierarchy



Bottom-up
Incremental tree insertion
Top-down
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical Collision Detection Bottomup Hierarchy Building

Start


Grouping


Starts by combining a number of primitives and
finding a BV for them.
This BV is grouped with one or more BVs
constructed in a similar way, thus yielding a new,
larger parent BV.
Recursive grouping

Repeat the grouping until only one BV exists,
which becomes the root of the hierarchy.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical Collision Detection
Hierarchy Building by Incremental tree-insertion


Start with an empty tree
All other primitives and their BVs are added one at a time to
the tree.


To make an efficient tree, an insertion point should be selected so that
the total tree volume increase is minimized.
Little is known about this scheme in the context of collision
detection.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical Collision Detection
Top-Down Hierarchy Building

Start


Recursively apply a divide-and-conquer strategy


Find a BV for all primitives of the object, which is then acts as the root
of the hierarchy.
First to split the BV into k or fewer parts and find all included
primitives for each such part. A BV is then created for each part.
Potential advantage


A hierarchy can be created on an as-needed basis, i.e., we can construct
the hierarchy for those parts of the object where it is actually needed.
Used by majority of hierarchical CD.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical Collision Detection

K-ary tree


K =2 minimizes the work to be done when
traversing a path from root to the worst-case leaf,
and it is easier to compute the hierarchy than the
case of higher k.
Higher k gives a tree with lower height, but it
requires more work at each node.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical Collision Detection

Challenges





Find tight-fitting bounding volume.
Find hierarchy construction that creat balanced and
efficient tree.
Efficient BV-BV overlapping test.
Efficient primitive-primitive overlapping test.
Notes
Balanced trees are expected to perform best in all
cases, since the time of CD query will not vary.
 But, it does not mean that it is best for all inputs,
e.g., those parts that seldom or never be queried for
collision
can Animation
be located deep in theCShierarchy.
Animation (U)a
Chap
7 Physically Based
Dept., NCTU, J. H. Chuang

Hierarchical Collision Detection
Collision testing between Hierarchies -1

Collision detection


Test whether or not two objects collide, and may
terminate whenever a pair of triangles has been
found to be overlapping.
Collision determination


In some cases, all pairs of overlapping triangles
might be wanted.
Can be solved with small alterations of the code
for collision detection.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical Collision Detection
Collision testing between Hierarchies -2
FindFirstHitCD(A, B)
return({TRUE, FALSE});
if (not-overlap(ABV, BBV) return FALSE;
else if(isLeaf(A)) /* try to reduce tested pairs */
if(isLeaf(B))
for each triangle pair TA in AC and TB in BC
if(overlap(TA, TB)) return TRUE;
else for each child CB in BC
FindFirstHitCD(A, CB)
else for each child CA in AC
FindFirstHitCD(CA, B)
return FALSE;
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical Collision Detection

Cost function -1
t  nv cv  n p c p  nu cu
Cost function
where
nv : number of BV-BV overlap tests
cv : cost of BV-BV overlap test
n p : number of primitive -primitive overlap tests
c p : cost of primitive -primitive overlap test
nu : number of BVs updated due to model' s motion
(if the BV is resized at run - time)
cu : cost for updating a BV
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical Collision Detection
Cost function -2

Conflicting goals



Creating a better hierarchical representation results
in lower values of nv, np, and nu.
Creating better methods for BV-BV or primitiveprimitive tests would lower cv, cp.
Bounding volume examples




Sphere, AABB, OBB
K-DOPS (direct oriented polytopes)
Pie slices
Spherical shells: good fits for Bezier surfaces
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical OBBTree

Why OBBTree?


Sphere tree and AABBTree do very well in
performing rejection tests, whenever two objects
are far apart; but do poorly for objects in close
proximity and having multiple contacts.
OBBTree was designed to perform especially well
if parallel close proximity is found during collision
detection.


Parallel close proximity: Two surfaces are very close
and nearly parallel.
A fast overlapping test for OBB-OBB is provided.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Hierarchical OBBTree
Collision detection based on OBBTree
 Preprocessing

Building an OBBTree for each object.
Top-down
 Bottom-up


Detection computation

Perform recursively the separating-plane test for
each pair of objects.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Building an OBBTree
Top-down approach

Split the polygon soap along the longest axis
of the OBB.




Pass through the OBB’s center
 OBBTree may not balanced.
 If the split fails, the next longest axis can be used.
Pass the point that corresponding to the median of the projection of all
triangle centroids onto this axis.
 OBBTree can be balanced.
Partition the polygons into two sub-groups
based on their centroids.
After split, an OBB is found for each subgroup.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Building an OBBTree
Top-down approach
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Building an OBBTree
Derive a good-fit OBB -1

For a given triangle soap, compute an
orientation of the triangles vertices (via the
first and second order statistics):



 = average of all vertices
C = the covariance matrix
Based on C


The normalized orthogonal eigenvectors of C are
used as a basis - axes of the OBB.
External vertices along each axis yields sizes of the
OBB.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Building an OBBTree
Derive a good-fit OBB -2

OBB for a polygon soap can also be found by
computing an orientation of the triangles of the
convex hull


The OBB will be less dependent on the distribution of polygons.
The convex hull of an object is computed.




Can be done by, e.g., Quickhull algorithm.
In return, we have n triangles, and based on which a covariance matrix
is derived.
 Centroid of the convex hull
 Covariance matrix
Normalized eigenvectors of C as the OBB’s axes.
Min-max extent on each axis.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Building an OBBTree
Derive a good-fit OBB -3
1 n 1 i
C   (m  m H )( m i  m H )T  [Cij ]
n j 0
 1
  H
 

ak
H
i
k k 
k k
k k
k k
(9mi m j  pi p j  qi q j  ri rj )   (m  m )

k  0 12


n 1
where
p k q k r k : triangle, k  0, , n  1
n 1
a   a k , where a k is the area of triangle k
H
k 0
m i  ( p i  q i  r i ) / 3 : the centroid of triangle i
1
mH  H
a
n 1
a m
k
k
k 0
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
Handling Rigid-Body Motions


In OBBTree, each OBB is stored with a rigidbody transformation (a rotation R and a
translation vector t ) matrix MA.
When testing CD of OBBs A and B,

The overlap test should be done in the coordinate
system of one of OBBs, say A.
So A is now a AABB.
 Transform B into A’s coordinate system with

TAB  M A1M B
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
Separating Axis Theorem


A naïve algorithm requires 144 edge-face test
6 faces x 2 boxes)
Separating axis theorem



(12 edges x
For any two arbitrary, convex, disjoint polyhedra, A and B, there exists
a separating axis where the projections of A and B are also disjoint.
Checking for disjoint OBBS involves searching for a separating axis.
If A and B are disjoint, then they can be separated by a separating axis
that is orthogonal to either
 A face of A, or
 A face of B, or
 An edge from each polyhedron.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
Separating Axis Theorem
Axes p and q are orthogonal to faces of A.
Axes s and t are orthogonal to faces of B.
It is sufficient to find one axis that separates the projection in
order to know that the OBBs do not overlap.
Here, q is the only axis that separates the projections.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
Separating Axis Theorem

General separating-plane test: 15 tests




Sequentially test for each axis candidate





Three axes of A,
Three axes of B, then
Nine axes from A and B (9 axes).
Do axis projection and form the interval on the axis.
Two objects are disjoint if their intervals don't overlap.
If the intervals overlap, boxes may or may not be disjoint. Further tests
on other axes may be needed.
More efficient way?
What are the axes and in which order?
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
A fast separation test -1
Assume that a potential separating axis is l.
 Radii of the OBBs A and B on the axis l
A i
rA   hi a  l

iu ,v , w
rB 
B i
h
 i b l
iu ,v , w
If and only if l is a separating
axis, then the intervals on l
should be disjoint. i.e.,
t  l  rA  rB
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
A fast separation test -2

Done in the coordinate system of A

Formed by A’s center and axes



ac, axes au, av , aw
B is assumed to be relative to A
By separating axis theorem

It is sufficient to find one axis that separates A and
B to be sure that they are disjoint.

Fifteen axes have to be tested
3 from the faces of A (axes of A: au, av , aw)
 3 from the faces of B (axes of B: bu, bv , bw)
 3x3=9 from combinations of edges from A and B
(cij= ai x bj, i,j=u,v,w)

Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
A fast separation test -3
Simplify the expression by working in the
coordinate system of A: Case 1
Let l  a u  (1 0 0)T ,
where
t  l  t  au  tx
rA 
h



i u ,v , w
A
i
a l 
i
h



i u ,v , w
A
i
a a
i
u
 huA
rB 
B i
h
 i b l 
iu ,v , w
u
x
B
v
v
x

r01 r02 

r11 r12 
r21 r22 
B i
u
h
b

a
i
iu ,v , w
h b h b h b
B
u

R  bu bv b w
 r00

  r10
r
 20
B
w
w
x
 huB r00  hvB r01  hwB r02
Animation (U) Chap 7 Physically Based Animation
So the test becomes
t x  huA  huB r00  hvB r01  hwB r02
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
A fast separation test -4
Simplify the expression by working in the
coordinate system of A: Case 2
Let l  b u ,
t  l  t  b u  t x bxu  t y byu  t z bzu  t x r00  t y r10  t z r20
rA 
A i
h
 i a l 
iu ,v , w
A i
u
h
a

b
i
iu ,v , w
 huA bxu  hvA byu  hwA bzu  huA r00  hvA r10  hwA r20
rB 
B i
h
 i b l 
iu ,v , w
B i
u
B
h
b

b

h
i
u
iu ,v , w
So the test becomes
t x r00  t y r10  t z r20  huA r00  hvA r10  hwA r20  huB
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
A fast separation test -5
Case 3
ua u vb v ,
Let
l

Let l  a  b ,
u
v
v
v T
v
v
t  tl l t  t(a (ua bvb) ) t  t(0 (0 bvbzb vb)Ty )  t bt zvby t bt yvbz t rt z r11
 t rt y r21
z
y
z y
y z
z 11
y 21
Ah A i a i  l 
Ah A i a i  (ua u vb v ) 
Ah Avb v  (ua u i a i )
r

rA A 
hi ai  l  
hi ai  (a  b )  
hi bi  (a  a )
iui,vu, w,v, w
A v
w
A v
w
u
u
iui,vu, w,v, w
A v
v
A v
v
w
w
iu ,v , w
iu ,v , w
B u
w
B u
w
u
u
iu ,v , w
iu ,v , w
B u
u
B u
u
w
w
iui,vu, w,v, w
A v
A
A v
A
w y
v 21
w y
v 21
A v
A
Ah vb  h b  h r Ah r

h
b

a

h
b

a

z h b h r h r
w 11
 h b  a  h b  a  hv bv z 
w 11
B i
B i
u
v
B u
i
v
Bh i b  l 
Bh i b  (ua vb ) 
Bh ua  (i b vb )
r

rB B 
hi bi  l  
hi bi  (a  b )  
hi ai  (b  b )
iu ,v , w
iu ,v , w
B u
B
B u
B
w x
u 02
w x
u 02
B w
B
Bh wb  h b  h r
Bh r

h
a

b

h
a

b


 h a  b  h a  b  hu bu x x h b  h r  hw rw00 00
test
becomes
SoSothethe
test
becomes
A
A
B
B
A
A
B
B
t
r

t
r

h
r

h
r

h
r

h
t z r11z 11
 t y r21y 21 hv rv21 21 hw rw11 11 hu ru02 02 hw rw00r00
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
A fast separation test -6


If any of these 15 tests is positive, the OBBs
are disjoint.
Number of operations


Maximum 180, or 240 if transformation of B
into A’s coordinate system in included.
Order of axes


Has an impact on performance.
First test three axes of A


They are orthogonal and thus reject the overlap
faster, and the simplest tests.
Then three axes of B, followed by the axes
formed by axes of A and B.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Fast Overlap Test for OBBs
Another fast separation test -7

Simply skip the last 9 axis tests can speed
up the overlapping test,



Geometrically, this is amount to doing two
AABB-AABB tests.
But sometimes report two disjoint OBBs as
overlapping.
In these cases, the recursion in the OBBTree
will go deeper than necessary.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Two-level CD system

Globally searching pairs of objects that
have potential collision.



Spatial subdivision
Sweep-and-Prune
Collision detection on a pair of objects


Hierarchical CD based on OBBTree,
AABBTree,…
Polygon-polygon overlap test
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Two-level CD system
Pruning MultiBody pairs
(Sweep/Prune)
Exact collision
Detection
(OBB tree)
Simulation
Collision
response
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang
Time-critical collision detection


Time critical computing needs to consider all
computations involved in each frame update.
Two major computations


Time-critical collision detection



Rendering and Collision detection
Progressive refinement on the discrete-time
collision detection using hierarchical
representations, such as
Sphere tree, box tree (axis-aligned or oriented).
Hard to estimate the allocated time.
Animation (U) Chap 7 Physically Based Animation
CS Dept., NCTU, J. H. Chuang