How to read these slides?

Navigate via arrow keys between slides Overview

Click on the menu bar items to navigate to chapters

SCIENCE PASSION TECHNOLOGY

VU Fundamentals of
Geometry Processing

Mesh Decimation

Julian Rakuschek

26.03.2026

In this lecture

Given a highly dense mesh how can we reduce
the amount of triangles while preserving features?

Supplemental Reading

pmp-book.org 7.1 Vertex Clustering 7.2 Incremental Decimation

Acknowledgment

This lecture is based on a talk by Mark Pauly on Mesh Decimation
and a previous lecture by Prof.in Dr.in Ursula Augsdörfer.

Application: Oversampled 3D scan data

Application: Overtesselation, e.g. iso surface extraction

Application: Multiresolution hierarchies

• efficient geometry processing
• level-of-detail (LOD) rendering

Application: Adaptation to hardware capabilities

Size-Quality Tradeoff

Problem Statement

Given $\mathcal{M} = (\mathcal{V}, \mathcal{F})$ find $\mathcal{M}' = (\mathcal{V}', \mathcal{F}')$ s.t.

1. $|\mathcal{V}'| = n < |\mathcal{V}|$ and $||\mathcal{M} - \mathcal{M}'||$ is minimal, or
2. $||\mathcal{M} - \mathcal{M}'|| < \epsilon$ and $|\mathcal{V}'|$ is minimal

$\mathcal{M}$

$\rightarrow$

$\mathcal{M}'$

Step 1

Divide space around mesh into cells, $\epsilon \times \epsilon$, where $\epsilon$ is the approximation tolerance.

Inspired by [M. Pauly, "Mesh Decimation", 2006] -- Modified Example

Step 2

Compute the cell representative $p$ for each cell cluster: Assign all vertices $p_1, \dots, p_k$, within this cell to $p$.

In this case, the center of each cell has been chosen.

Step 3

Then connect $p$ and $x$ if $p_i \in {p_1, \dots, p_k}$ was connected to any $x_i \in {x_1, \dots, x_l}$

Step 4

Many cells can become degenerate faces.

Step 5

In the final step we therefore remove any degenerate faces.

Cell Representatives

There are several options to position the new cell reprsentative $p$:

• Taking the cell center.
• Taking the average position of the associated vertices.
• Taking the median of the associated vertices.
• Finding optimal vertex position as a least-square approximate.

When using the average position:

Original Decimated

When using the median position:

Original Decimated

When using the error quadric position:

Original Decimated

Error Quadrics (1)

Imagine a cell with three faces and two vertices.

Error Quadrics (2)

We can now elongate the supporting planes of each face.

Error Quadrics (3)

The resulting cell representative is the point that minimizes the (squared) distance to all supporting planes.

Computing Error Quadrics (1)

Consider one triangle $t_i$ within the current cell of interest.

Let $P_i = (\textbf{x}_i, \textbf{n}_i)$ be the supporting plane of this triangle.

• $\textbf{x}_i$ is an arbitrary point on this plane.
• $\textbf{n}_i$ is the unit normal vector of $t_i$.

The squared distance of a point $\textbf{x}$ from the plane $P_i$ can be computed as

Remember: $\textbf{x}_i$ is a point on the plane, while $\textbf{x}$ can be any point in space.

Computing Error Quadrics (2)

($\text{dist}^2$ is copied from previous slide)

Using homogeneous coordinates $\bar{\textbf{x}} = (\textbf{x}, 1)$ and $\bar{\textbf{n}}_i = (\textbf{n}_i, − \textbf{n}_i^T \textbf{x}_i)$
the above equation simplifies to

Computing Error Quadrics (3)

The sum of the quadratic distances to the supporting planes $P_i$ of all triangles $t_i$ within a cell $C$ is given by

quadric error metric (QEM)

The final cell representative $\textbf{x}_c$ is computed by finding an $\textbf{x}$ that minimizes $E$:

Computing Error Quadrics (4)

To derive a solution, we first now decompose the matrix $\textbf{Q}$ again:

Nota bene — this is not a $2 \times 2$ matrix, it is a symmetric $4 \times 4$ matrix:

Computing Error Quadrics (5)

We can now simplify the notation again:

The QEM is then rewritten as follows:

Computing Error Quadrics (6)

This is a quadratic function.

To find the minimal value of this function, we take the derivative and set it to zero.

Computing Error Quadrics (7)

This is a least squares system.

Comparison

Discussion

• Quality of result depends on choice of representative
• Not always efficient
  • vertex clustering always keeps one vertex for every $\epsilon$-cell, i.e. planar mesh could be decimated down to a triangle
• Topological changes may occur: Result might not be manifold.

The Basic Idea (1)

The Basic Idea (2)

The Basic Idea (3)

The Basic Idea (4)

The Basic Idea (5)

Remove one vertex at a time as long as

In each step the best candidate for removal is determined.

• Binary: Either we remove it or keep it (similar to the convexity check in the assignment).
• Continuous: We compute a measure to see how much effect the removal has on the resulting mesh.

Decimation Operators

Each of the listed decimation operators is reversible.

How to Remesh?

Coming back to this: How can we triangulate the hole?

Convexity Check (1)

We strongly prefer convex holes.

In a planar convex polygon, all internal angles are at most 180°. Convex polygons can be easily triangulated from any vertex.

If a polygon is non-convex, that is there are internal angles > 180°, then extra care has to be taken to avoid creating overlaps and self-intersections.

green edges are safe, red edges cause problems

Convexity Check (2)

Assume we want to check if the neighborhood of vertex $x$ is convex.

The m-sided hole which appears in a mesh by removing a vertex usually does not lie exactly in a 2D plane, so the notion of convexity does not make sense. Simple solution: Analyse 2D image of 3D hole.

Convexity Check (3)

To do that, we first need a suitable viewing angle on the neighborhood.

Looking at it from the side is probably not a good idea ...

... but the front is much better!

Convexity Check (4)

We need to find a direction from which we look at the hole. For this we compute the average normal vector of all adjacent faces of a vertex.

\[ n = \frac{\sum_i A_i n_i}{\sum_i A_i} \]

Where $A_i$ is the area of each adjacent face with $n_i$ being the normal. This is an area-weighted average.

Convexity Check (5)

Looking in the direction of $n$ gives us the 2D image of the neighborhood.

Convexity Check (6)

Suppose the cyclic ordering of vertices $v_0, v_1, \dots, v_{m-1}$ of a planar $m$-gon is such that the polygon is traversed counter-clockwise.

Then the internal angle $\alpha_i$ is computed from

\[ \sin \textcolor{purple}{\alpha_i} = \sin(180° - \textcolor{purple}{\alpha_i}) = \left< \left( \left( \textcolor{blue}{\frac{v_i - v_{i-i}}{|v_i - v_{i-i}|}} \right) \times \left( \textcolor{red}{\frac{v_{i+1} - v_i}{|v_{i+1} - v_i|}} \right) \right), \frac{n}{|n|} \right> \]

where the normal vector $n$ is pointing towards the eye of the viewer.

Convexity Check (7)

• The cross product is a vector orthogonal to the successive edges \(v_{i-1}v_i\) and \(v_iv_{i+1}\).
• The vector \(\vec{n}\) is likewise orthogonal to these two edges.
• The cross product points in the same direction as the normal vector if the vertex is convex, and it points in the other direction if the vertex is concave (see Figure on the left).
• For the final convexity check, it suffices to check if the dot product is non-negative for all vertices.

Halfedge Collapse (1)

Halfedge Collapse (2)

Halfedge Collapse (3)

Halfedge Collapse (4)

Halfedge Collapse (5)

Halfedge Collapse (6)

Halfedge Collapse (7)

Halfedge Collapse (8)

Halfedge Collapse (9)

Halfedge Collapse (10)

Illegal Halfedge Collapses (2)

If both $p$ and $q$ are boundary vertices, then the edge $(p, q)$ has to be a boundary edge.

Illegal Halfedge Collapses (3)

For all vertices $r$ incident to both $p$ and $q$ there has to be a triangle $(p, q, r)$. In other words, the intersection of the one-rings of $p$ and $q$ consists of vertices opposite the edge $(p, q)$ only.

Vertex Ranking

How do we find the best removal candidate?

Incremental mesh decimation ranks all removal operations. Ranking may be defined by

• Distance measure
• Fairness measure
  • Triangle shape, i.e. rank by ratio of circum circle radius to shortest edge of all incident triangles after removal
  • Visual smoothness, i.e. rank by maximum or average normal jump. (We have to compute normal in any case to detect flipping!)
  • Colour decimation
  • Texture distortion

Incremental Decimation can be done in two ways

The error control stops the decimation when the quality becomes too bad.

Error Metrics (1)

[U. Augsdörfer, "Mesh Decimation", 2020]

Formula for $D$ can be found in the assignment sheet.

1. Compute the normal vector of each adjacent plane.
2. Compute the average normal vector $n_{avg}$.
3. Compute the barycentric average of all faces $p_{avg}$.
4. $n_{avg}$ and $p_{avg}$ define the average plane.
5. Finally compute distance $D$ of vertex $v$ to the average plane.

The distance to the average plane is a local error metric: Measures the distance between a face and a subpatch.

Error Metrics (2)

Remember: We want to remove vertices whose absence is barely noticeable. Removing the spike would remove an important feature that can make the difference in ML models (for example).

Error Metrics (3)

The Hausdorff Distance — a global error metric

This distance measure is defined to be the maximum minimum distance. If we have two sets $A$ and $B$, then $H(A,B)$ is found by computing the minimum distance $d(a,B)$ for each point $a \in A$ and then taking the maximum of those values: \[ H(A,B) = \max_{a \in A} \min_{b \in B} \lVert a - b \rVert . \] Notice that, in general, $H(A,B) \neq H(B,A)$. The symmetric Hausdorff distance is defined as the maximum of both values: \[ d_H(A,B) = \max\big(H(A,B),\, H(B,A)\big). \]

Error Metrics (4)

Computing the Hausdorff distance for a mesh:

• We compute the one-sided Hausdorff distance $H(A, B)$.
• $A$ are the points of the original mesh.
• $B$ are the points of the decimated mesh.
• Goal: Efficient computation of the Hausdorff distance during mesh decimation.
• Track vertex–triangle assignments
  • Maintain a mapping from original mesh vertices to triangles of the decimated mesh.
• During an edge collapse
  • Removed vertices p and q (or only p in the case of a half-edge collapse).
  • Assign these vertices to the nearest triangle in the local neighborhood.

Error Metrics (5)

• Update affected regions
  • An edge collapse changes the geometry of adjacent triangles.
  • Vertices previously assigned to these triangles must be re-distributed to appropriate nearby triangles.
• Every triangle $t_i$ of the decimated mesh at any time maintains a list of original vertices belonging to the currently associated patch $S_i$.
• The Hausdorff distance is then evaluated by finding the most distant point in this list.

Discussion