Transcript Cloth Simulation

Interactive Animation of
Structured Deformable Objects
Qiong Han
2/11/2002
Overview – Main problem


Few techniques are currently able to
handle the animation in interactive rates
so far
Both efficiency and stability are desired
Overview


A stable and efficient algorithm for
animating mass-spring system based
cloth
Focus is the cloth modeling and the
interaction between cloth and different
environments based on this technique
Overview - Outline





Principle of implicit integration
Integration scheme
Post-step modification
Cloth simulation in virtual environment
Results
Implicit integration – 1D



Each discrete mass point i of mass m at
position xi moves at speed of vi
Adjacent points are connected by spring
of stiffness k
Subscript indices indicate the current
step number
Implicit integration – 1D

The explicit Euler integration looks like
dt
v  v  Fi
m
n 1
n
n 1
xi  xi  vi dt
n 1
i

n
i
n
Assuming the force Fi is constant over a
time step
Implicit integration – 1D


The time step should be inversely
proportional to the square root of the
stiffness k [Courant condition]
System is stable only for small time
steps
Implicit integration – 1D

The implicit integration is
dt
v  v  Fi
m
n 1
n
n 1
xi  xi  vi dt
n 1
i


n
i
n 1
Replacing the forces at time t by for
forces at time t+dt
Why?
Implicit integration – 1D


How to compute Fn+1 without knowing the
exact position of next time step?
By a first-order approximation
F
n 1
F n 1
F 
 x
x
n
Implicit integration – 1D

Notice
F
H
x


H is the negated Hessian matrix of the system
H is CONSTANT (for 1D case) and symmetric
Implicit integration – 1D


Re-write n1 x  (v n  n1v)dt
Put everything together
dt
v  v  Fi
m
xin 1  xin  vin 1dt
n 1
i
F

n 1
n 1
n
i
F n 1
F 
 x
x
Then we have
n
dt 2
dt
 v  (I 
H ) 1 ( F n  dtHv n )
m
m
n 1
Implicit integration - Comparison
dt 2
dt
 v  (I 
H ) 1 ( F n  dtHv n )
m
m
force added to Fn as
n 1

Extra
~
~
F  dtHv , F i  kdt


n
 (v
j
j|( i , j )Edges
 vi )
It’s used as artificial viscosity: a mass point
is influenced by the motion of its neighbors
It’s proportional to dt and k
Implicit integration – Comparison
dt 2
dt
 v  (I 
H ) 1 ( F n  dtHv n )
m
m
n 1



dt 2
W  (I 
H ) 1
m
Where
acts like ‘filters’
The bigger the stiffness k is, the wider filters
are. The resulting force on a mass point will
take into account more forces around
For example: pulling a stick
Implicit integration – Notes




Stable and smooth animation without tuning
damping coefficients
Allowing bigger step, more efficient
Gaining stability by losing accuracy
In 2D/3D, the Hessian matrix H changes for
each time step. Need to solve a large linear
system
Integration Scheme - Extension


Extension 1D to 2D/3D
A mass point i is connected to all the other
0
l
points j with springs of rest length ij and
stiffness kij
Integration Scheme - Extension

H is not CONSTANT any more, instead
T
 || xi  x j || lij0
(
x

x
)
( xi  x j ) 
F (i, j )
i
j
0
H
 kij 
I 3  lij

3
xi
||
x

x
||
||
x

x
||


i
j
i
j

It’s a 3n x 3n matrix and needs to be solved
at each time step
Integration Scheme - Splitting

By decomposing the forces into 2 parts, a
linear and a nonlinear one:
F (i, j )  F linear (i, j )  F nonlinear (i, j )
F

linear
(i, j )  k ij ( xi  x j ), F
nonlinear
(i , j )  k l
0
ij ij
( xi  x j )
|| xi  x j ||
Do approximate integration of two parts
Integration Scheme – Linear part

From above analysis, it’s easy to solve this
linear part cause the 3n x 3n Hessian
matrix H is CONSTANT
 H ij  k ij , i  j

 H ii    k ij

j i

Calculate once, use it regardless of what
the time step is
Integration Scheme – Nonlinear part


The nonlinear part always has the same
magnitude between t and t+dt, which
means it only rotates
An angle error is introduced, which needs
to be balanced with a straightforward
displacement later
Integration Scheme – Nonlinear part

After the internal forces have been filtered,
compute resulting global torque T as
n
T   ( xG  xi )  Fi filtered
i 1

xG is the center of gravity. Because the
sum of all internal forces is 0, re-write T as
n
T   Fi filtered  xi
i 1
Integration Scheme – Nonlinear part

T is supposed to be 0, so we can modify
the integration output to balance it. Simply
add the correction force on each mass
point i
Fi correction  ( xG  xi )  Tdt
2
dt
Fi correction
m

This is not a zero-error scheme. In
practice the result becomes implausible
only for big k or dt: wrinkled mesh
Post-step Modification - Motivation


Mass-spring is not perfect to model cloth
The elongation is proportional to the force
applied but the natural force/deformation
curve is normally nonlinear
Post-step Modification – Inverse dynamics process



Over-stretched spring?
Move the extreme mass points together
along their axis
No forces involved, no stability problem
Post-step Modification – Implementation


A force/deformation ratio threshold for each
spring as dmax. Iterate over stretched spring
and shrink them
When to stop?



After fixed iteration steps
Convergence is reached
Time is up
Post-step Modification – Inverse dynamics process
Virtual Environment

To increase the realism of the simulation, we
could make the cloth model interact with
complex environments through some
external forces like wind, or through
collisions with complex objects
Virtual Environment – Wind/Fluid


External forces are usually much smaller
than the internal forces
Explicitly integrate these forces (standard
Euler integration)
Virtual Environment – Wind/Fluid

Assign a drag force to a mass point i
Fi drag  K drag || viwind || ( ni  viwind )ni

Where Kdrag is user-specified, viwind is the
wind/fluid velocity at mass point i, and ni is
the normal of the simulated surface at i
Virtual Environment – Collision detection




Bounding box for objects
Divide boxes to voxels, whose size depends
on user-defined accuracy
Classify voxels as inside, outside and surface
(partially inside/outside) voxels
Check a mass point against an object’s
voxels, if it’s not outside, need to handle
collision with certain response
Virtual Environment – Collision response

For each voxel, store CP and VC, which are
the closest surface point to the voxel
center and the voxel center point,
respectively, along with the surface normal
N at CP
Virtual Environment – Collision response


N could be approximated as
where it’s 1 if VC is outside the object and
0 otherwise
Virtual Environment – Collision response

Once a mass point xi is actually inside the
object, we project it onto the surface
tangent plane at CP
Virtual Environment – More responses



Offsetting the surface outward a small
amount
Attenuate the tangential component speed
to simulate the friction on the surface
Attenuate the normal component velocity
significantly to simulate the loss of energy
during the impact
Results – Overall algorithm




Internal forces: implicitly integrating
internal forces with the linear part only
Angular correction
External forces: explicit integration
Post modification: inverse dynamic
iterations
Results



The system simulates different stiffness
ranging from 0 to 106
For the explicit scheme the required
time step could be of the order of 10-6s
to get stable results
For the new system, dt=0.02s was used,
which is corresponding to 50f/s
Results

10-12 times faster than the Conjugate
Gradient based system
Results
Results
Summery





Implicit predictor/corrector scheme
Efficient constraint/collision handling
Enhancing realism by using non-linear
spring
Not accurate enough
Not a scheme for general mass-spring
system simulation
References

M. Desbrun, P. Schröder, and A. Barr,

M. Meyer, G. Debunne, M. Desbrun, and A.
Barr, Interactive Animation of Cloth-like


Interactive Animation of Structured
Deformable Objects, GI99.
Objects in Virtual Reality.
D. Baraff and A. Witkin. Large steps in cloth
simulation. SIGGRAPH 98.
Xavier Provot. Deformation Constraints in a
Mass-spring Model to Describe Rigid Cloth
Behavior. GI 95.