Lecture 3D Geometry Processing
Parameterization
Computer Graphics Group
Motivation
- Texture Mapping
Motivation
- Normal Mapping
Motivation
- Remeshing
Motivation
- Shape Interpolation
Motivation
- Geometric pattern synthesis
Mesh Parameterization
- Find a one-to-one (bijective) mapping between a given surface mesh and a 2D parameter domain
Unfolding the World
Spherical Coordinates
\[ \matrix{\theta \\ \phi} \mapsto \matrix{\sin \theta \sin \phi \\ \cos \theta \ \sin\phi \\ \cos \phi} \]
Desirable Properties
- Bijective mapping
- Low distortion
- How to measure distortion?
- Can distortion be avoided completely?
Cartography
preserves angles
preserves area
More Maps
Dymaxion Map
Dymaxion Map
New Maps
Differential Geometry
- Parametric surface representation
\[ \begin{eqnarray} \vec{x} \colon \Omega \subset \R^2 & \to & \set{S} \subset \R^3 \\[2mm] \of{u,v} & \mapsto & \matrix{x\of{u,v} \\ y\of{u,v} \\ z\of{u,v}} \end{eqnarray} \]
- Regular if
- Coordinate functions \(x\), \(y\), \(z\) are smooth
- Tangents are linearly independent: \(\vec{x}_{,u} \times \vec{x}_{,v} \neq \vec{0}\)
Distortion Analysis
- Jacobian transforms infinitesimal vectors
\[ \func{d}\vec{x} = \mat{J} \func{d}\vec{u} \quad \quad \mat{J} = \matrix{ x_u & x_v \\ y_u & y_v \\ z_u & z_v } \]
\[\norm{\func{d}\vec{x}}^2 \;=\; \left(\func{d}\vec{u} \right)^T \mat{J}^T \mat{J} \, \func{d}\vec{u} \;=\; \left(\func{d}\vec{u} \right)^T \mat{I} \, \func{d}\vec{u} \]
First Fundamental Form
- Example \(\vec{f},\vec{g} \colon [0,1]^2 \to \R^3\)
\[\vec{f}(u,v) = \matrix{\sin u \\ \cos u \\ v} \]
\[\vec{g}(u,v) = \matrix{\sin u \\ \cos u \\ v^2} \]
First Fundamental Form
- Example \(\vec{f},\vec{g} \colon [0,1]^2 \to \R^3\)
\[\vec{f}(u,v) = \matrix{\sin u \\ \cos u \\ v} \]
\[\vec{g}(u,v) = \matrix{\sin u \\ \cos u \\ v^2} \]
Cartography
preserves angles
= conformal
= conformal
preserves area
= equiareal
= equiareal
Conformal Maps
- A regular parameterization \(\vec{x}(u,v)\) is conformal, iff its first fundamental form is a scalar multiple of the identity:
\[\mat{I}\of{u,v} \;=\; s\of{u,v} \cdot \matrix{ 1 & 0 \\ 0 & 1 }\]
Conformal Maps
- Riemann Conformal Mapping Theorem
- Any two simply connected compact planar regions can be mapped conformally onto each other
- Close relationship to circle packings
Conformal Maps
Conformal Flow
Equiareal Maps
- A regular parameterization \(\vec{x}(u,v)\) is equiareal, iff the determinant of its first fundamental form is 1:
\[ \det\of{\mat{I}\of{u,v}} \;=\; 1 \]
Example
- Least-Squares Conformal Map
- tries to minimize angle distortion and non-uniform scalings
- implemented in many tools, e.g. matlab, blender, meshlab, libigl, etc.
Harmonic Maps
- Isometric maps are conformal, conformal maps are harmonic:
isometric ⇒ conformal ⇒ harmonic - Harmonic maps are easier to compute than conformal maps
- Harmonic maps are not conformal in general, i.e. do not necessarily preserve angles
Discrete Maps
- Piecewise linear map of a discrete 3D triangle mesh onto a planar 2D polygon
- Given a mesh \(\set{S}\) compute the mapping \(\vec{u} \colon \set{S} \to \Omega \subset \R^2\), i.e., for each vertex \(v_i\) find parameter values \(\vec{u}_i \in \R^2\).
Discrete Harmonic Maps
- Map the boundary \(\partial \set{S}\) homeomorphically to some (convex) polygon \(\partial \Omega\) in the parameter plane
- Solve \(\laplace_{\set{S}} \vec{u} = 0\) through a linear system
\[\forall v_i \in \set{S} \;:\; \sum_{v_j \in \set{N}_1\of{v_i}} w_{ij} \left( \vec{u}\of{v_j} - \vec{u}\of{v_i} \right) = 0\]
\[w_{ij} \;=\; \func{cot} \alpha_{ij} + \func{cot} \beta_{ij}\]
Example: Discrete Harmonic Map
- Uniform Laplace discretization \(w_{ij} = 1\)
- Boundary vertices: \(\{1,2,3,4\}\), interior vertices: \(\{5,6,7\}\)
- Map boundary to convex polygon (unit square)
Example: Discrete Harmonic Map
- Solve linear system \(\vec{L}\vec{u} = \vec{b}\) to find parameters \(\vec{u}\) \[ \tiny \mat{L} \;=\; \matrix{ 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & -5 & 1 & 1\\ 1 & 0 & 0 & 1 & 1 & -4 & 1\\ 1 & 1 & 0 & 0 & 1 & 1 & -4\\ } \quad \mat{b} \;=\; \matrix{ 0 & 0\\ 1 & 0 \\ 1& 1 \\ 0 & 1 \\ 0 & 0 \\ 0& 0 \\ 0& 0} \quad \mat{u} \;=\; \matrix{ 0 & 0 \\ 1 & 0 \\ 1 & 1 \\ 0 & 1 \\ 0.53 & 0.53 \\ 0.25 & 0.45 \\ 0.45 & 0.25} \]
Discrete Harmonic Maps
- Importance of proper discretization of Laplace Operator
Convex Combination Maps
- Uniform barycentric weights \[ w_{ij} \;=\; 1 / \func{valence}\of{v_i}\]
- Cotangent weights (\(> 0\) only if \(\alpha_{ij} + \beta_{ij} < \pi\)!) \[w_{ij} \;=\; \cot\of{\alpha_{ij}} + \cot\of{\beta_{ij}}\]
- Mean value weights (always > 0) \[w_{ij} \;=\; \frac{ \tan\of{\delta_{ij}/2} + \tan\of{\gamma_{ij}/2} } {\norm{ \vec{x}_j - \vec{x}_i }}\]
Convex Combination Maps
- Comparison
Fixing the Boundary
- Basic Approach
- Choose a simple convex shape, e.g. triangle, square, circle
- Distribute points on boundary, e.g. use arc length parameterization
- Solve Laplace equation
- Problem: Fixing the boundary can create high distortion
Open Boundary Mappings
- Include boundary vertices in the optimization
- Produces mappings with lower distortion
Open Boundary Mappings
- Need disk-like topology
- Introduce cuts on the mesh
Open Boundary Mappings
- Need disk-like topology
- Introduce cuts on the mesh
- Naive cut introduces large distortions
Open Boundary Mappings
- Need disk-like topology
- Introduce cuts on the mesh
- Smart cuts reduce distortion
Texture Atlas Generation
- Split model into number of patches (atlas)
- to reduce distortion
- to avoid self-intersections
- to improve texture packing
Real-World Example
Real-World Example
Real-World Example
Literature
- Botsch et al., Polygon Mesh Processing, AK Peters, 2010
- Chapter 5
- Floater & Hormann, Surface Parameterization: A Tutorial and Survey, Advances in Multiresolution for Geometric Modeling, Springer 2005
- has all the concepts
- Hormann et al., Mesh Parameterization, Theory and Practice, SIGGRAPH 2007 Course
- has all the proofs