Title

Geometry Processing
Shape Deformation
Prof. Edward Chien
Computer Graphics & Geometry Processing

Shape Deformation

Original model
Local deformation
Global deformation

Shape Deformation

Deform face scan through motion tracking

Recap: Fairing

Membrane Surfaces

  • Minimize surface area \[\int_\set{S} \func{d}A \;\to\; \min \quad\text{with}\quad \delta\set{S}=\bar{\vec{x}}\]
  • Simpler energy using partial derivatives \[\int_\Omega \norm{\vec{x}_{,u}}^2 + \norm{\vec{x}_{,v}}^2 \func{d}u\func{d}v \;\to\;\min\]
  • Variational calculus gives \[ \begin{align} \laplace_{\set{S}} \vec{x} &= \vec{0}, & \vec{x} \in \set{S} \setminus \partial\set{S} \\ \vec{x} &= \bar{\vec{x}}, & \vec{x} \in \partial\set{S} \end{align} \]
cylinder_c0.png

Calculus of Variations Derivation

(see whiteboard)

Thin Plate Surfaces

  • Minimize surface curvature \[\int_\set{S} \kappa_1^2 + \kappa_2^2 \,\func{d}A \to \min \;\text{with}\; \begin{cases} \delta\set{S}=\bar{\vec{x}} \\ \vec{n}\of{\delta\set{S}}=\bar{\vec{n}} \end{cases}\]
  • Simpler energy using partial derivatives \[\int_\Omega \norm{\vec{x}_{,uu}}^2 + 2\norm{\vec{x}_{,uv}}^2 + \norm{\vec{x}_{,vv}}^2 \func{d}u\func{d}v \;\to\;\min\]
  • Variational calculus gives \[\begin{align} \laplace_{\set{S}}^2 \vec{x} &= \vec{0}, & \vec{x} \in \set{S} \setminus \partial\set{S} \\ \vec{x} &= \bar{\vec{x}}, & \vec{x} \in \partial\set{S} \\ \vec{n}\of{\vec{x}} &= \bar{\vec{n}}, & \vec{x} \in \partial\set{S} \\ \end{align}\]
cylinder_c1.png

Fairness Functionals

Membrane surface
\[\laplace_{\set{S}} \vec{x} = 0\]

Thin plate surface
\[\laplace_{\set{S}}^2 \vec{x} = 0\]

Minimum variation surface
\[\laplace_{\set{S}}^3 \vec{x} = 0\]

Surface Deformation

Spline Surfaces

  • Tensor product surfaces
    • “Curves of curves”
    • Rectangular grid of control points
    • Rectangular surface patch
bezier-patch.png

  • Problems
    • Many patches for complex models
    • Smoothness across patch boundaries
    • Trimming for non-rectangular patches
deform-bmw-2.png

Subdivision Surfaces

  • Generalization of spline curves / surfaces
  • Arbitrary control meshes
  • Successive mesh refinement with simple rules
  • Converges to smooth limit surface

vw-0.png vw-1.png vw-2.png vw-3.png

Spline & Subdivision Surfaces

  • Basis functions are smooth bumps
    • Fixed support
    • Fixed control grid
  • Bound to control points
    • Initial patch layout is crucial
    • Patch design requires experts
  • Decouple deformation from surface representation!

vw-0.png
vw-1.png
vw-2.png
vw-3.png

Modeling Metaphor

  • Mesh deformation through displacement function \(\vec{d} \colon \set{S} \to \R^3\)
    • Fix some vertices (gray)
    • Interactively displace handle vertices (yellow)
    • Solve for displacement of remaining vertices (blue)

 

 

Modeling Metaphor

  • Mesh deformation through displacement function \(\vec{d} \colon \set{S} \to \R^3\)
    • Fix some vertices (gray)
    • Interactively displace handle vertices (yellow)
    • Solve for displacement of remaining vertices (blue)
flipper-0.png

\[ \begin{align*} \vec{d} \colon \set{S} &\to \R^3\\ \vec{x}_i &\mapsto \vec{x} + \vec{d}\of{\vec{x}_i} \end{align*} \]

flipper-1.png

Physically-Based Deformation

  • Nonlinear stretching & bending energies \[ \int_{\Omega} k_s \norm{\mat{I} - \mat{I}'}^2 + k_b \norm{\mat{I\!I} - \mat{I\!I}'}^2 \;\func{d}u\func{d}v \]
  • Simplified quadratic energy using partial derivatives \[ \int_\Omega k_s \left( \norm{\vec{d}_u}^2+ \norm{\vec{d}_v}^2 \right) \;+\; k_b \left( \norm{\vec{d}_{uu}}^2+ 2\norm{\vec{d}_{uv}}^2+ \norm{\vec{d}_{vv}}^2 \right) \func{d}u \func{d}v \]
  • Variational calculus gives \[ \begin{align} -k_s \laplace_{\set{S}} \vec{d} \;+\; k_b \laplace_{\set{S}}^2 \vec{d} &\;=\; \vec{0} ,& \text{in blue region} \\ \vec{d} &= \bar{\vec{d}}, & \text{in yellow handle region}\\ \vec{d} &= \vec{0}, & \text{in gray fixed region} \end{align} \]

Deformation Energies

 

\(\laplace \vec{x} = \vec{0}\)
\(\laplace^2 \vec{x} = \vec{0}\)

undeformed state
\(\laplace \vec{d} = \vec{0}\)
\(\laplace^2 \vec{d} = \vec{0}\)

Discretization

  • Discretization of Laplace & bi-Laplace \[ \begin{align} \laplace \vec{d}_i &= \frac{1}{2A_i} \sum_{j\in\set{N}_i} \left( \cot\alpha_{ij}+\cot\beta_{ij} \right) \left( \vec{d}_j - \vec{d}_i \right) \\[2mm] \laplace^2\vec{d}_i &= \laplace\of{\laplace\vec{d}_i} \end{align} \]
cotanLaplace.png
  • Leads to sparse linear system \[ \matrix{ & \color{blue}{\laplace^2} & \\ \mat{0} & \color{gray}{\mat{I}} & \mat{0} \\ \mat{0} & \mat{0} & \color{green}{\mat{I}} } \matrix{ \vdots \\ \vec{d}_i \\ \vdots } \;=\; \matrix{ \color{blue}{\mat{0}} \\ \color{gray}{\mat{0}} \\ \color{green}{\delta\vec{h}_i} } \]
deformation-constraints.png

Car Deformation

Facial Motion Capture

Linear Face Deformation

  • MoCap markers control facial deformation deform-plane-1.png deform-plane-2.png
  • Minimize quadratic bending energy by solving linear system

Nonlinear Face Deformation

Add nonlinear wrinkle effects & realistic rendering

Limitations

Problematic cases for surface-based/mesh-based deformations

Highly complex models
Topological inconsistencies
Geometric degeneracies

Space Deformation

Freeform Deformation

  • Space warp function \(\vec{d} \colon \R^3 \to \R^3\)
    • Deform each 3D point: \(\vec{p} \mapsto \vec{d(p)}\)
    • Deform each mesh vertex
    • Deform control points of freeform curves/surfaces
ffd_warp_head.png
  • Tensor product Bezier deformation \[ \vec{d}(u,v,w) = \sum_{i=0}^l \sum_{j=0}^m \sum_{k=0}^n \vec{b}_{i,j,k} B_i^l(u) B_j^m(v) B_k^n(w) \]
ffd_blocks_and_spheres.png

Sederberg & Perry, SIGGRAPH 1986

Freeform Deformation

Tensor product spline deformations allow for local control \[ \vec{d}(u,v,w) = \sum_{i=0}^l \sum_{j=0}^m \sum_{k=0}^n \vec{d}_{i,j,k} N_i^l(u) N_j^m(v) N_k^n(w) \]

civic-ffd.png

Sederberg & Perry, SIGGRAPH 1986

Spline-Based FFD

Sederberg & Perry, SIGGRAPH 1986

Direct Manipulation FFD

  • How to prescribe displacement constraints?
    • Solve linear system for control points
    • Can be over- or under-determined
    • Pseudo-inverse: least squares, least norm
civic-dmffd.png

Hsu et al, SIGGRAPH 1992

Direct Manipulation FFD

Hsu et al, SIGGRAPH 1992

Direct Manipulation FFD

  • Bad: results depends a lot on grid resolution
  • Minimize control point movement ≠ minimize physical energies!

ffd-grid-1.png ffd-grid-2.png ffd-grid-3.png

Hsu et al, SIGGRAPH 1992

Modeling Metaphor

  • Mesh deformation through displacement function \(\vec{d} \colon \R^3 \to \R^3\)
    • Fix some vertices (gray)
    • Interactively displace handle vertices (yellow)
    • Solve for displacement of remaining vertices (blue)
flipper-0.png

\[\begin{align*} \vec{d} \colon {\color{red} \R^3} &\to \R^3\\ \vec{x}_i &\mapsto \vec{x} + \vec{d}\of{\vec{x}_i} \end{align*}\]

flipper-1.png

Volumetric Deformation Energy

  • Minimize similar energies to surface case \[ \int_{\R^3} \norm{\vec{d}_{uu}}^2+ \norm{\vec{d}_{uv}}^2+ \ldots + \norm{\vec{d}_{ww}}^2 \,\func{d}V \; \to \; \min \]
  • But displacement function now lives in 3D…
    • Need a volumetric space tessellation?
    • No, same functionality provided by RBFs

Radial Basis Functions

  • Represent deformation by RBFs \[ \vec{d}\of{\vec{x}} = \sum_j \vec{w}_j \, \phi\of{\norm{\vec{c}_j - \vec{x} }} \]
  • Triharmonic basis function \(\phi(r)=r^3\)
    • Satisfy \(\laplace^3 \vec{d}=\vec{0}\) by construction
    • Therefore the deformaton minimizes \[ \int_{\R^3} \norm{\vec{d}_{uuu}}^2+ \norm{\vec{d}_{vuu}}^2+ \ldots + \norm{\vec{d}_{www}}^2 \,\func{d}u\,\func{d}v\,\func{d}w \]
    • Leads to very smooth and fair deformations
rbf-constraints.png

RBF Deformation

  • Represent deformation by RBFs \[ \vec{d}\of{\vec{x}} = \sum_{j=1}^n \vec{w}_j \, \phi\of{\norm{\vec{c}_j - \vec{x} }} \]
rbf-constraints.png
  • Preprocessing: RBF fitting
    • Interpolate displacement constraints: two rings of vertices at region boundaries (red points)
    • Solve dense \(n \times n\) linear system for \(\vec{w}_j\)
  • Deformation: RBF evaluation
    • Function \(\vec{d}\) transforms all points \(\vec{x}_i\), its Jacobian \(\left( \grad \vec{d} \right)^{-\mathsf{T}}\) transforms normals \(\vec{n}_i\)
    • Evaluation can be implemented highly parallel with GPU shaders

RBF Deformation

Complex Meshes

1M free vertices

“Bad Meshes”

deform-bmw-1.png deform-bmw-3.png

deform-bmw-2.png deform-bmw-4.png
3M triangles, 10k components, not oriented, not two-manifold

Local & Global Deformations

deform-male-0.png
deform-male-1.png
deform-male-2.png

Local & Global Deformations

deform-male-0.png
deform-male-3.png
deform-male-4.png

Limitations

Linear vs. Nonlinear

Linear surface-based deformation

Linear vs. Nonlinear

Linear RBF deformation

Linear vs. Nonlinear

Nonlinear surface-based deformation

Linear vs. Nonlinear

Linear surface deformation
Linear RBF deformation
Nonlinear deformation

Linear vs. Nonlinear

deformation-limitations.svg

Literature

  • Botsch et al., Polygon Mesh Processing, AK Peters, 2010
    • Chapter 9 (without Sections 9.1, 9.3, 9.4, 9.5.2)
pmp.png