This flashcard is just one of a free flashcard set. See all flashcards!

Algorithm Overview
for each local operator:
    evaluate quality decrease
    enqueue (quality decrease, op) into priority queue
repeat:
    pop best operator from queue
    apply
    update queue
until target complexity reached or error too large

Operators

• Vertex Removal: Remove center vertex from a 1-ring and re-triangulate. Topological operator. Degrees of freedom: Triangulation.
• Edge Collapse: Merge the two end vertices of one edge into one. Topological / geometrical operator. Degrees of freedom: Vertex position.
• Halfedge Collapse: Merge the start vertex and the end vertex of one edge. New position is the position of the end vertex. Topological operator. Degrees of freedom: None (which is preferable).

Error Metrics
Local Error Metrics: Plane distance, Volume change
Global Error Metrics: Hausdorff distance, Simplification Envelopes, Error Quadrics

Error Quadrics are particularly suitable because they can be evaluated locally: On the initial mesh, compute error quadrics for every vertex from its incident triangle planes. When two vertices are merged, the error quadrics stored in the original vertices are added. Note: Not 100% correct since some planes are added twice.

Fairness Criteria
To ensure a certain mesh quality, we can forbid some operators:

• Triangle Shape: Forbid operators which would produce triangles with too small interior angles
• Valence Balance: Forbid operators which would produce a triangulation where the valence of a vertex becomes very small or very large
• Normal Approximation
• Texture Distortion