Mesh Simplification

The python script for "Surface Simplification Using Quadric Error Metrics, 1997" [Paper]

Environments

python == 3.12.0
scipy == 1.11.3
numpy == 1.26.0
scikit-learn == 1.3.0

Usage

python simplification.py [-h] -i data/ankylosaurus.obj [-v V] [-p P] [-optim] [-isotropic]

A simplified mesh will be output in data/output/.

Parameters

-i: Input file name [Required]
-v: Target vertex number [Optional]
-p: Rate of simplification [Optional (Ignored by -v) | Default: 0.5]
-optim: Specify for valence aware simplification [Optional | Recommended]
-isotropic: Specify for isotropic simplification [Optional]

Example

Input	Result (50%)	Result (20%)	Result (1%)

14762 vertices	7381 vertices	2952 vertices	147 vertices
29520 faces	14758 faces	5900 faces	290 faces

Valence-aware simplification

Implementation of valence-aware simplification to improve the quality of triangles

Straight forward (0.5%)	valence-aware (0.5%)

Uneven valence Valence 3 occurs (Big problem)	Valence 6 increased Close to regular triangle

The further the valence is away from 6, the heavier the penalty. An excessively large penalty is set for an edge contraction that results in valence 3.

Isotropic Simplification

Implementation of isotropic simplification to enhance edge length uniformity

Default (10%)	Isotropic (10%)

Uneven edge length Feature preserved	Even edge length Feature smoothed

Algorithm

Overview

Define the cost function of each vertex $\mathbf{v}=(v_x, v_y, v_z, 1)^T$ by using the symmetric matrix $Q$

$$\Delta(\mathbf{v})=\mathbf{v}^T Q \mathbf{v}$$

Then iteratively remove the pair of least cost.

Procedure

Compute the symmetric matrix $Q$ for all the initial vertices.
Select all valid pairs.
Compute the optimal contratcion for each valid pair.

When merging $\mathbf{v}_1$ to $\mathbf{v}_2$ , the cost of the contraction is defined as $\mathbf{\bar{v}}^T (Q_1+Q_2) \mathbf{\bar{v}}$ , where $\mathbf{\bar{v}}=\frac{1}{2}(\mathbf{v}_1+\mathbf{v}_2)$ means the newly inserted vertex.

Place all the pairs in a heap.
Iteratively remove the pair $(\mathbf{v}_1, \mathbf{v}_2)$ of least cost from the heap, and update the costs of all valid pairs involving $\mathbf{v}_1$ .

Definition of Q

A plane can be definedby the equation $ax+by+cz+d=0$ where $a^2+b^2+c^2=1$ . Note that $(a, b, c)^T$ means the facet normal of the plane. When we define the barycenter of the plane as $(c_x, c_y, c_z)$ ,

$$ d = -1 \times \left[ \begin{matrix} a\\ b\\ c\\ \end{matrix} \right] \cdot \left[ \begin{matrix} c_x\\ c_y\\ c_z\\ \end{matrix} \right]. $$

The distance from a vertex $\mathbf{v}$ to the plane $\mathbf{p}=(a,b,c,d)^T$ can be defined as

$$ \mathbf{p}^T \mathbf{v} = a v_x+ b v_y + c v_z + d $$

and, the sum of squared distances to its planes can be defined as

$$ \begin{align} \Delta(\mathbf{v}) =& \sum_{\mathbf{p} \in N(\mathbf{v})}(\mathbf{p}^T \mathbf{v})^2 \\ =& \sum_{\mathbf{p} \in N(\mathbf{v})}(\mathbf{v}^T \mathbf{p})(\mathbf{p}^T \mathbf{v}) \\ =& \mathbf{v}^T \left(\sum_{\mathbf{p} \in N(\mathbf{v})}\mathbf{p}\mathbf{p}^T \right) \mathbf{v}. \\ \end{align} $$

By introducing $K_p$ as

$$ K_p = \mathbf{p}\mathbf{p}^T = \left[ \begin{matrix} a^2 & ab & ac & ad \\ ab & b^2 & bc & bd \\ ac & bc & c^2 & cd \\ ad & bd & cd & d^2 \end{matrix} \right], $$

the error metric can be rewritten as a quadric form

$$\Delta(\mathbf{v})=\mathbf{v}^T Q \mathbf{v}$$ where

$$ Q = \sum_{\mathbf{p} \in N(\mathbf{v})} K_p . $$

Limitation

We consider only a mesh without boundary.

lixingyi8947/mesh_simplification