1. Local Simplification Strategies

Local error: Compare new patch with previous iteration

• Fast
• Accumulates error
• Memory‐less

The Basic Algorithm

（1） Select the element with minimal error
（2） Perform simplification operation (remove/contract)
（3） Update error (local/global)
重复（1）-（3）Until mesh size / quality is achieved

顶点删除的误差度量

点越尖锐越重要。(Laplace,一圈夹角等)

• Measures
  • Distance to plane
  • Curvature
• Usually approximated
  • Average plane
  • Discrete curvature

边收缩的误差度量

QEM,二次误差度量

用二次曲面拟合这条边。拟合得到系数矩阵，用矩阵性质度量扭曲。

（1） Choose point closest to set of planes (triangles)

（2） Sum of squared distances to set of planes is quadratic \(\Rightarrow\) has a minimum

用二次曲面来拟合，得到系数矩阵，用二次曲面性质来度量 [Garland & Heckbert 1997]

Given a plane, we can define a quadric Q

$$ Q=(A,b,c)=(nn^T,dn,d^2) $$

measuring squared distance to the plane as

$$ Q(V)=V^TAV+2b^TV+c $$

$$ Q(V)=\begin{bmatrix} x & y&z \end{bmatrix}\begin{bmatrix} a^2 &ab &ac \\ ab& b^2&bc \\ ac & bc &c^2 \end{bmatrix}\begin{bmatrix} x\\ y\\ z \end{bmatrix}+2\begin{bmatrix} ad & bd &cd \end{bmatrix}\begin{bmatrix} x\\ y\\ z \end{bmatrix}+d^2 $$

Garland and Heckbert. Surface Simplification Using Quadric Error Metrics. Siggraph 1997.

• Sum of quadrics represents set of planes

$$ \sum _i(n_i^TV+d_i)^2=\sum _iQ_i(V)=\begin{pmatrix}\sum _iQ_i \end{pmatrix}(V) $$

• Each vertex has an associated quadric
  • Error\((v_i) = Q_i (v_i)\)
  • Sum quadrics when contracting \((v_i,v_j) \to v’\)
  • Cost of contraction is \(Q(v’)\)

$$ Q=Q_i+Q_j=(A_i+A_j,b_i+b_j,c_i+c_j) $$

• Sum of endpoint quadrics determines v’
  • Fixed placement: select \(v_1\) or \(v_2\)
  • Optimal placement: choose v’ minimizing \(Q(v’)\)

$$ \nabla Q({V}' )=0\Rightarrow {V}' =-A^{-1}b $$

• Fixed placement is faster but lower quality
• But it also gives smaller progressive meshes
• Fallback to fixed placement if A is non‐invertible

Contracting Two Vertices

• Goal: Given edge e=(\(v_1, v_2\)), find contracted

\(v=(x, y, z)\) that minimizes \(\Delta(v)\):

$$ \partial \Delta / \partial x=\partial \Delta / \partial y=\partial \Delta / \partial z=0 $$

• Solve system of linear normal equations.

$$ \begin{bmatrix} q_{11} &q_{12} &q_{13} &q_{14} \\ q_{21} & q_{22} &q_{23} & q_{24}\\ q_{31} & q_{32} &q_{33} & q_{34}\\ 0& 0 & 0 &1 \end{bmatrix}V=\begin{bmatrix} 0 \\ 0\\ 0\\ 1 \end{bmatrix} $$

If no solution - select the edge midpoint

Visualizing Quadrics

• Quadric isosurfaces
  • Are ellipsoids (maybe degenerate)
  • Centered around vertices
  • Characterize shape
  • Stretch in least‐curved directions

简化后的折叠、翻转现象

Selecting Valid Pairs for Contraction

• Edges:

{\((v_1, v_2):(v_1v_2)\). is in the mesh }

• Close vertices:

{\((v_1,v_2):||v_1-v_2||<T\)}

• Threshold T is input parameter

Algorithm

• Compute \(Q_v\) for all the mesh vertices
• Identify all valid pairs
• Compute for each valid pair (\(v_1, v_2\)) the contracted vertex \(v\) and its error \(\Delta(v)\)
• Store all valid pairs in a priority queue (according to \(\Delta(v)\))
• While reduction goal not met
  • Contract edge (\(v_1, v_2\)) with the smallest error to \(v\)
  • Update the priority queue with new valid pairs

Artifacts by Edge Collapse

收缩后会出现边的翻转

Pros and Cons

• Pros
  • Error is bounded
  • Allows topology simplification
  • High quality result
  • Quite efficient
• Cons
  • Difficulties along boundaries
  • Difficulties with coplanar planes
  • Introduces new vertices not present in the original mesh

Appearance‐based metrics

• Generalization required to handle appearance properties
  • color
  • texture
  • normals
  • etc.
• Treat each vertex as a 6‐vector [x,y,z,r,g,b]
  • Assume this 6D space is Euclidean
    • Of course, color space is only roughly Euclidean
  • Scale xyz space to unit cube for consistency

Generalized Quadric Metric

$$ Q(V)=V^TAV+2b^TV+C $$

本文出自CaterpillarStudyGroup，转载请注明出处。 https://caterpillarstudygroup.github.io/GAMES102_mdbook/