Transcript Computer Animation CPSC 426

1
Notes
2
Building implicit surfaces
 Simplest examples: a plane, a sphere
 Can do unions and intersections with
min and max
 This works great for isolated particles,
but we want a smooth liquid mass when
we have lots of particles together
 Not a bumpy union of spheres
3
Blobbies and Metaballs
 Solution is to add kernel functions
together
 Typically use a spline or Gaussian
kernel around each particle
 Still may look a little bumpy - can
process surface geometry to smooth it
out afterwards…
4
Marching Cubes
 Going back to blobby/metaball implicit
surfaces: often need mesh of surface
 Idea of marching cubes (or marching
tets):
 Split space up into cells
 Look at implicit surface function at corners
of cell
 If there’s a zero crossing, estimate where,
put a polygon there
 Make sure polygons automatically connect
up
5
Acceleration
 Efficiency of neighbour location
 Rendering implicit surfaces - need to
quickly add only the kernel functions that
are not zero (avoid O(n) sums!)
 Also useful later for liquid animation and
collisions
 Use an acceleration structure
 Background grid or hashtable
 Kd-trees also popular
6
Back to animation
 The real power of particle systems comes
when forces depend on other particles
 Example: connect particles together with
springs
 If particles i and j are connected, spring force is
 x  x
 x  x
i
j
i
j

Fi  k
1
 x  x
L
ij
j

 i

F j  Fi
 The rest length is L and the spring “stiffness” is k
 The bigger k is, the faster the particles try to snap
back to rest length separation
 Simplifies for L=0
7
Damped springs
 Real springs oscillate less and less
 Motion is “damped”
 Add damping force:
Fidamp
v  v  x  x
i
j
j
 D
 i
xi  x j

 Lij
 x  x
j
 i

 x i  x j
F jdamp  Fidamp
 D is damping parameter
 Note: could incorporate L into D
 Simplified form (less physical…)

Fidamp  Dvi  v j 
or even
Fidamp  Dvi
8
Elastic objects
 Can animate elastic objects by sprinkling
particles through them, then connecting them
up with a mesh of springs
 Hair - lines of springs
 Cloth - 2D mesh of springs
 Jello - 3D mesh of springs
 With complex models, can be tricky to get the
springs laid out right, with the right
stiffnesses
 More sophisticated methods like Finite Element
Method (FEM) can solve this
9
Liquids
 Can even animate liquids (water, mud…)
 Instead of fixing which particles are
connected, just let nearby particles interact




If particles are too close, force pushes them apart
If particles a bit further, force pulls them closer
If particles even further, no more force
Controlled by a smooth kernel function
 Related to numerical technique called SPH:
smoothed particle hydrodynamics
 With enough particles (and enough
tweaking!) can get a nice liquid look
 Render with implicit surface
10
Noise
 Useful for defining velocity/force fields,
particle variations, and much much more
(especially shaders)
 Need a smooth random number field
 Several approaches
 Most popular is Perlin noise
 Put a smooth cubic (Hermite) spline patch in every
cell of space
 Control points have value 0, slope looked up from
table by hashing knot coordinates
 You can decide spatial frequency of noise by
rescaling grid
11
Time integration for particles
 Back to the ODE problem, either
dxi
 v x i,t 
dt
dxi
 dt  v i
or dv
1
i
 
F x i ,v i,t 
 dt mi
 Accuracy, stability, and ease-ofimplementation are main issues

 Obviously Forward Euler and Symplectic
Euler are easy to implement - how do they
fare in other ways?
12
Stability
 Do the particles fly off to infinity?
 Particularly a problem with stiff springs
 Can always be fixed with small enough time
steps - but expensive!
 Basically the problem is extrapolation:
 From time t we take aim and step off to time t+∆t
 Called “explicit” methods
 Can turn this into interpolation:
 Solve for future position at t+∆t that points back to
time t
 Called “implicit” methods
13

Backward Euler
 Simplest implicit method: very stable,
not so accurate, can be painful to
implement
x
n 1
 x  t v(x
n
n 1
,t
n 1
)
 Again, can use for both 1st order and 2nd
order systems
 Solving the system for xn+1 often means
Newton’s method
(linearize as in Gauss-Newton)
14
Simplified Backward Euler
 Take just one step of Newton, i.e. linearize
nonlinear velocity field:
n

v
x


n 1
n
n 1
n
v x   v x 
x

x


x
 Then Backward Euler becomes a linear
n


system: n 1 n

v
x


n
n 1
n

 x  tv x 
x


n



v
x


x  tv x n 
x
x




 v 
n
I  x  t v x 
 x 
x
x
 x 

