mesh_simplification
mesh_simplification copied to clipboard
astaka-pe
Python script for "Quadric Edge Collapse Decimation"
English 🇺🇸 / [Japanese 🇯🇵]
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
tqdm
Installation
# Clone
git clone https://github.com/astaka-pe/mesh_simplification.git
cd mesh_simplification
# Docker
docker image build -t astaka-pe/mesh-simp .
docker run -itd --gpus all --name mesh-simp -v .:/work astaka-pe/mesh-simp
docker exec -it mesh-simp /bin/bash
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%) |
 |
 |
|
|
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%) |
 |
 |
|
|
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.
astaka-pe