English πΊπΈ / [Japanese π―π΅]
The python script for "Surface Simplification Using Quadric Error Metrics, 1997" [Paper]
python==3.12.0
scipy==1.11.3
numpy==1.26.0
scikit-learn==1.3.0
tqdm
# 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
python simplification.py [-h] -i data/ankylosaurus.obj [-v V] [-p P] [-optim] [-isotropic]
A simplified mesh will be output in data/output/
.
-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]
Input | Result (50%) | Result (20%) | Result (1%) |
![]() |
![]() |
![]() |
![]() |
14762 vertices | 7381 vertices | 2952 vertices | 147 vertices |
29520 faces | 14758 faces | 5900 faces | 290 faces |
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.
Implementation of isotropic simplification to enhance edge length uniformity
Default (10%) | Isotropic (10%) |
![]() |
![]() |
|
|
Define the cost function of each vertex
Then iteratively remove the pair of least cost.
- 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$ .
A plane can be definedby the equation
The distance from a vertex
and, the sum of squared distances to its planes can be defined as
By introducing
the error metric can be rewritten as a quadric form
We consider only a mesh without boundary.