Combi2k2

Polygonal Representations

Motivation
Mesh
Mesh Denoising
Mesh Simplification

Motivation

Meshes nicely represent shapes
- in medicine, CAD, GIS, entertainment
- and engineering & simulation
Old concept:
- planar triangulation & tessellation (Voronoi, Delaunay, etc...)
- mixes topology & geometry (connectivity vs. embedding in space)

Also, this is a very special type of graph...

Mesh: nomenclature

Definition:

A set of vertices, straight edges and faces (triangle, or even polygons) defining a piecewise-flat surface embedded in 3D:

\begin{align*} V &= \{1,2,3,\dots\}\\ E &= \{(i,j), (k, l), \dots\}\\ F &= \{(i,j,k), (j,i,l), \dots\} \end{align*}

Simplicial complex:

Topological realization: identify $V$ with unit vector in $\mathbb{R}^N$ :

|K| = \bigcup_{\sigma\in K} |\sigma|

The term on RHS is convexhull of vertex images

Closure, Star and Link:

\begin{alignat*}{3} &\text{Subcomplex } &&\quad \text{Cl }L = \{\rho | \rho \preceq \sigma, \sigma\in L\}\\ &\text{Incidence } &&\quad \text{St }L = \{\rho | \sigma \preceq \rho, \sigma\in L\}\\ &\text{1-ring } &&\quad \text{Lk }L = \text{Cl St }L - \text{St}(\text{Cl }L - \empty) \end{alignat*}

Topological Structure

Every point has an open, (half-)disk-like subset surrounding it
the mesh is 2-manifold iff $|\text{St }v|\sim\mathbb{R}^2$ (homeomorphic to plane)
boundary: half-plane this time

Discrete Differential Geometry

Discrete notion of curvature(s) quite obvious

mean curvature $H$ at edges: dihedral angle
Gaussian curvature $\kappa$ at vertices:

\kappa = 2\pi - \sum_{i\in\text{St }v}\theta_i

Still, we need to be careful (like sometimes we should "normalize" it by dividing by something). The "something" that is being ubiquitous today is the Voronoi area

\mathcal{A}_{Voronoi} = \frac{1}{8}\sum_{j\in N(i)}(\cot\alpha_{ij} + \cot\beta_{ij})\|x_i-x_j\|^2

Topological Invariant of Surfaces

Euler Characteristic: $\mathcal{X} = V - E + F$

$V$ : number of vertices
$E$ : number of edges
$F$ : number of faces between edges

Euler formula: $V-E+F=2(c-g)+b$

$c$ : number of connected components
$g$ : number of genus (holes) in surfaces
$b$ : number of boundary edges

The later is true for arbitrary complexes (this can be proved by induction)

Recall about turning number theorem: Gauss-Bonnet

For a boundary-less surface, we get:

\int_S\kappa ds = 2\pi\mathcal{X}

And with boundary:

\int_S\kappa dA + \oint_{\partial S} \kappa_g ds = 2\pi\mathcal{X}

Mesh Denoising

How to remove noise from surfaces???

By using the non-linear diffusion:

\Delta\textbf{x} = -\kappa\textbf{n}

This brings us to Laplace-Beltrami operator;

-\kappa\textbf{n} = \Delta_B\textbf{x}

gradient of triangle area w.r.t. top vertex
explicit formula in a convenient form

Not so surprising: LBO is an intrinsic Laplacian:

extends the usual stencil to arbitrary sampling for flat domains…
- second order derivative (trace of Hessian) of functions
and treats piecewise-linear non-flat domains seamlessly
- proper treatment requires finite-element analysis...
- but this only changes the “mass” matrix
  - the particular form we used is called mass lumping

I know this part is just a bunch of text, I will comback here later to edit this (or I may never come back :v)

Mesh Simplification

Large mesh is expensive
Too simple mesh cause information loss

$\to$ should think of a mesh that “best bang for your buck”.

Problem formulation

geometric & combinatorical optimization
- full problem too hard in practice
- a few existing slow solutions
alternate:
- vertex optimization
- combinatorical optimization
- or both, interleaved!

History:

Functional approximation $[y=f(x)]$
PWL curve approximation
Height field (terrain) triagulation

Existing Approaches:

Manual simplification: too complex, require users with expertise
Automatic methods:
- vertex clustering
- vertex decimation
- iterative contraction

Vertex Clustering:

Partition space into cells
Merge all vertices within the same cell
Triangles can degenerate

Vertex Decimation:

Starting with original model, iteratively
- rank vertices according to importance
- remove unimportant vertex, retriangulate
Used to be a fairly common technique

Iterative Contraction:

Contraction operates on set of vertices (faces, edges are also used)
Starting with original model, iteratively
- rank all edges with some cost metric
- contract minimum cost edge
- update edge costs

Cost metrics

To evaluate vertices, or edges based on importance, or cost, we must have something to measure those value.

Some heuristics ok (e.g. edge length, dihedral angle...)
Sample distances to original surface better (projection to closest point)
Alternative characterizations of error
- quadratic error metrics
- local volume preservation
- much faster

Duc Nguyen

Shape Analysis #4: Triangle Mesh