Transcript Deformation Transfer - 法政大学 [HOSEI UNIVERSITY]

Point based animation
Point based animation
Project Website:
http://www.pointbasedanimation.org
Introduction



Recent paper of M. Müller, R. Keiser, A. Nealen, M. Pauly, M. Gross, and M. Alexa,
Point Based Animation of Elastic, Plastic and Melting Objects,
Eurographics/ACM SIGGRAPH Symposium on Computer Animation (2004)
presents a method for modeling and animating a wide spectrum of volumetric
objects, with material properties anywhere in the range from stiff elastic to highly
plastic.
In mesh based approaches, complex physical effects, such as melting, solidifying,
splitting or fusion, pose great challenges in terms of restructuring.
Additionally, under large deformations the original meshes may become arbitrarily
ill-conditioned.
Motivation

The goal is to unify the simulation of materials ranging from stiff elastic to highly
plastic into one framework, using a mesh free, point-based volume and surface
representation, which omits explicit connectivity information and, thus, implicitly
encompasses the complex physical effects
Motivation

Point-based approach for physically-based simulatio


Point based volume (physics)
“Phyxels” = physical elements
Point based surface (appearance)
“Surfels” = surface elements
→ No connectivity needed
→ Inspired by Mesh Free Methods
→ Inspired by mathematically motivated methods:
→ All the simulation quantities, such as location xi, density ρi,
deformation ui, velocity vi, strain εi, stress σi and body force fi, are
carried by the physically simulated points
Mesh Free Physics

Advantages



No tetrahedral mesh needed
Natural adaptation to topological changes
Disadvantages


Difficulty of getting sharp fracture lines
Neighboring Phyxels are not explicitly given

Throughout this work Spatial Hashing [Teschner et al. 03] for
fast neighbor search (when needed, i.e. when the
neighborhood changes) is used
Main points of the approach

Point
based
elasticity
continuum mechanics



model
derived
Smooth Particle Hydrodynamic designed for the simulation of
stars/galaxies
Lennard-Jones designed for molecular interactions
Dynamically adapting, point sampled surface animation



from
Densely sampled surface
Coupled with coarse physical model (phyxels)
High quality visuals at no simulation cost
Hooke low
From [Hooke 1678] De Potentio
Restitutiva
“Ut Tensio sic vis”
The Power of any spring is in the
same proportion with the tension
thereof.
→ The stress linearly depends on the strain
F = ku
... a Continuum Elasticity Primer
Continuum Elasticity Basics
(1)

Deformation and Force(s)
Undeformed Rest State length
L
L
L
F
F
Elongation ∆L due to External
Force F
1 Newton = 1 N = 1 Kg·m/s2
F
F
Discretization (or Cutting Open) reveals Body Forces F
(and F = F for Static Equilibrium)
Continuum Elasticity Basics
(2)

Strains and Stresses
L
L
F
F
σ = F/A
Any deformation (i.e.
elongation, compression) is
termed the STRAIN (ε) of the
spring and generally defined
(dimensionless) as ∆L/L
Any force applied to a crosssectional surface is termed the
STRESS (σ) acting on this
surface and is measured as
force per unit area (N/m2)
Continuum Elasticity Basics
(3)
Reference configuration
x
u(x)
Deformed configuration
x+u(x)
x’
u(x’)
= Elastic Memory
x’+u(x’)
Displacement (vector) field:
u(x) = [ u(x,y,z) v(x,y,z) w(x,y,z) ]T
Strain Measures (1)

Some Definitions
Gradient Operator
(Nabla, Del, Grad)
  


 , , ,
xi  x y z
 u
 x
Deformation Gradient u
i
F


- Spatially Varying!
x j  v
- Not Symmetric
 x
- Jacobian of u(x)




T
u 
y  u, x u, y 
T T

   u 
v  v, x v, y 
y 
Strain Measures (2)
 Geometric
y, v
Interpretation of F
 :x  xu
d X2
x, u
d X1
x

u, y
d x2
1  v, y
xu
d x1
v,x
1  u, x
Material
Coordinates
Spatial Coordinates
Jacobian of  Describes Local Mapping
i ( x  u ), x ( x  u ), y  1  u, x u, y 
J


 IF
1  v, y 
x j ( y  v), x ( y  v), y  v, x
Strain Measures (3)

Definition: Change of Scalar Product between
any two Pairs of Vectors
d x d x 2  d X d X 2   Jd X1  Jd X 2  d X1T d X 2
T
1
T
T
1
 d X1  J T J  I  d X 2
Green Strain Tensor
 I  u    I
  u u 
εGreen  J J  I   I  u
T
T T
T
εGreen  u   u
T
T
T
T
T
T
Nonlinear Term(s)
Strain Measures (4)
Geometric Interpretation of εGreen
y, v
0 
d X2   
1 
x, u
1 
d X1   
0 
x

 u, y 
d x2  

1

v

,y 

1  u, x 
d x1  

v
 ,x 
 :x  xu
xu
Pairwise Scalar Products of Deformed Coordinate
System (Spatial Coordinates)
 xx  xy   dx1T dx1 dx1T dx 2 
εG  
 T
I
T
 yx  yy   dx 2 dx1 dx 2 dx 2 
Strain Measures (5)

Properties of εGreen

Zero under Rigid Body Transformations
 dx1T dx1
εG   T
 dx 2 dx1
dx1T dx 2 
I  II  0
T
dx 2 dx 2 

Symmetric

Therefore, εGreen has 3 Independent Components in 2D, and 6
independent Components in 3D
 xy  dx1T dx2  dx2T dx1   yx
 xx  yy  zz
Normal Strains
 xy  xz  yz
Shear Strains
Linearized Strain Measure

Drop Quadratic Terms for Small u(x)

Engineering Applications (infinitesimal strain)
 xx

u
2
x
 yy
v
2
y
 xy
u v


y x
Problem: Artifacts under (too) large Rotational
Transformation

Consider 90 Degree Rotation (from red to blue in 2D)
y, v
x, u
u  X Y
v  X Y
and
 xx   yy  2
 xy  0
???
Stress (Force per Area)

The Stress – Strain Relationship (2D)


Most commonly used: Cauchy‘s Stress Tensor
Linear Stress-Strain relationship (Hookean material)
 yy
 yy
 xy
 xy
 xx
 xx
 xx
 xx
 yx
Constitutive
 yx
 yy
Material Law
 yy
σ  Cε
1 
E 
C
 1
2 
1 
0 0


0

(1  ) / 2 
0
Youngs
Modulus

E  N
2
 mm 
Shear
Modulus
G  0.5E /(1  )
Simulation Loop

Start with undeformed object and apply external
forces (per phyxel)
ft ,ext
ft
Body
Gradient
forces
of
(from
displacement
elastic
energy)
field
Add
external
forces
Stress
Strain
Time
(Hookean
(Greens
integration
material)
strain)
ut t
ut t
εt t
Bodywith
forces
+ elasticity,
new external
We start
pure
and forces
add = next
integration step
plasticity/flow thereafter
σt t
Elastic Strain
u(x)
strain
→ Strain depends on the spatial
derivatives of u(x)
no strain
 u 
T
T
 u, x

  v, x
 w, x

u, y
v, y
w, y
u, z 

v, z 
w, z 
ε Green  u   u
T
u
Next: Compute spatial derivatives of the x component u
T
 
 u 
T
T
T
T
Estimation of Derivatives (1)

xi
xj
Computation of the unknown u,x, u,y and u,z
at xi by Linear approximation
 u, x 
2
 
u (xi  x)  ui  u, y   x  O ( x )
 u, z 
u, x 
 
u j  ui  u, y   (x j  xi )
 u, z 
ui
x = xij
uj

Minimize
 (u~j  u j )  wij
2
j
→
The differences are weighted because only phyxels in the
neighborhood of phyxel i should be considered and,
additionally, fade in and out smoothly.
Estimation of Derivatives (2)
Vector
of Unknown
Linear approximation
Actual
value
of uj atPartial
point
of ujxDerivatives
as
j seen from xi
u j  ui  xij u
T
xi
u
xi
 u, x u, y u, z 
T
e   (u j  u j )  wij
2
xi
xj
j
ui
x = xij
Set partial derivatives of e with respect
to u,x, u,y and u,z to zero to obtain
minimizer of e
uj
1
u
xi

 

T
   xij xij wij     u j  ui  xij wij 
 j
  j

the number of phyxels within the support radius h in
the neighborhood of phyxel i is less than 4 (including
phyxel i) or if these phyxels are co-planar or co-linear A
is singular and cannot be inverted.
Use SVD for the 3x3 Matrix inversion for stability
If
Updating Strains and Stresses



We compute for each simulated phyxel i the spatial
derivatives of the deformation field at the phyxel’s
location xi based on the displacement vectors uj of
neighboring phyxels j.
The Jacobian Ji, the strain εi, and the stress σi at
phyxel i can all be computed from these derivatives.
For each simulated phyxel we have positions xi in
body space, defining what we call the reference
shape, and their deformed locations xi + uj the
deformed shape.
Discrete Energy Density


Strain from u
εGreen  u   u
T
T

T
 u
u 
Stress via material law (Hooke)
σ  Cε

T
Energy density (scalar)
3
3
U i   εij σij
i 1 j 1
T
T
Discrete Elastic Energy

Use Smoothed Particle Hydrodynamics (SPH) Method
•
•
•
•
As a basic unit, analogous to a finite element in FEM, we consider a
phyxel i and all i-ts neighbors j that lie within i-ts support radius hi.
Mass of each Phyxel mi is fix during the simulation
Distribute the mass around the Phyxel using a polynomial weighting
kernel wij with compact support
The density around Phyxel i is
i   m j wij
j
•
From which we compute the volume vi as
vi  mi / i
Elastic Forces

Estimate volume vi
represented by phyxel i via
SPH.
In continuum mechanics, quantities are measured
per unit volume.
•



Elastic energy of phyxel i
U i  viU
Depends on ui and
uj of all neighbors j
Phyxel i and all neighbors j receive a force
U
f j  vi
u j
f i   f j
j
Time Integration

Verlet (Explicit) Time Stepping
•
Newtons Second Law of Motion
 2 ui
fi
 ai 
2
t
mi
u  t  t   u  t   v  t  t  1 2  a  t  t 2  1 6  b  t  t 3  O  t 4 
+
u  t  t   u  t   v  t  t  1 2  a  t  t 2  1 6  b  t  t 3  O  t 4 
=
u  t  t   2u  t   u  t  t   a  t  t 2  O  t 4 
Simulation Loop Revisited
External Forces (Gravity,
Interaction)
ft ,ext
Verlet Integration
(=
new displacements)
ft
ut t
ut t
Estimation of
Derivatives
Computation of
Strains, Stresses,
Elastic Energy and per
Phyxel Body Forces
εt t
σt t
Plasticity

An elegant way of simulating plastic behavior, is by using strain state
variables. Strain State Plasticity [O’Brien et al. 02]
•
Reference frame stays fixed
εactual  ε measured  εstate

Change of reference frame (flow)
• After each time step:
εstate  εstate  ε measured
•
Copy deformed frame to reference frame:
xi  xi  ui
ui  0
Benefits and Limitations

Pros



Approach based on continuum elasticity
Strain- and stress tensors can be used
for plasticity and fracture
Cons



Sparse phyxel sampling → MLS problems
Currently only works well for volumetric objects
Close phyxels always interact
→ Extension needed for fracture simulation
So what about the Surface?
The volumetric,
physical model
The detailed
surface model
phyxels (in
surfels in blue
This works, as
previously
discussed
Two methods...
yellow)
Surface Animation

Motivating Factors



Animation of surface along with phyxels at no additional
simulation overhead
Trade-off quality – speed
Simulate topological changes (splitting, merging): Surfels
combined with an implicit surface provide a suitable
representation
Displacement Approach

Displace Surfels along with phyxels


Approximation of surfel displacement based on
displacement vector field u(x)
Must be invariant under rigid body transformations
u sfl 

1
  (r )
i
T

(
r
)(
u


u
 i i
i ( x sfl  xi ))
i
Reuse firsti order approximation of u
 :x  xu
Displacement Approach
Deforming Reference Frame (30 FPS, P4 3GHz)
Displacement Approach
+ Fast, easy to implement (in Pointshop3D)
+ Handles very detailed surfaces
+ Explicit surface model
- Doesn’t support topological changes
- Needs self-collision detection / response
Multirepresentation Approach

Combination of explicit and implicit representations
(explanation to follow…)

Idea: Animate explicit Surfel model, but reduce detail
to implicit (i.e. blobby) representation where
topological changes occur

Apply a plausible heuristic to estimate local changes of
the phyxel model (= change of reference frame)
Implicit Representation LI (1)



Implicit surface LI coats the phyxels
Initialization: project Surfels onto LI

Root finding problem:

Resample surfels
Animation of Surfels
 Estimate new position using displacement approach
 Project onto LI and resample
 :x  xu
Implicit Representation LI (2)


Drawback: can only represent blobby models
Observation: projection onto LI only necessary in
areas of insufficient surfel information (i.e. fracture)
 :x  xu
Detail Representation LD

Initialization: original, detailed Surfels



In each sim. timestep, blend these positions (and normals) with implicit
representation LI based on local changes of the phyxel model, and resample
LD gradually loses detail as blending occurs (which is what we want)
How do we plausibly estimate local changes of the phyxel model ?
 :x  xu
LD,t
LD,t+Δt
Topological Changes (1)

Idea



Fracturing: Inside phyxels -> outside phyxels
Merging: Outside phyxels -> inside phyxels
Use Eigenanalysis



Inside phyxels: similar Eigenvalues
Outside phyxels: one small Eigenvalue
Probability P that a phyxel is an outside phyxel:
where C is the local covariance matrix
Topological Changes (2)

Estimation of local topological change at time step t:

Blend detail representation LD to LI

Result: L’D
Blend both
position and
normal vector
Multirepresentation Approach
Offline simulation at ca. 5 sec./frame
Multirepresentation Approach
Offline simulation at ca. 8 sec./frame
Multirepresentation Approach
+ Can handle arbitrary topological changes
+ Very detailed models
+ Interpolation of attributes (Zombie surfels, see
paper)
- Not interactive
Future directions of work






Adaptive phyxel resampling
Collision detection and response
Physical modeling of fracture
Surface modeling of fracture
Physical modeling of surfaces and strands
Model Editing Operations