Garland-Heckbert algorithm

The Garland-Heckbert algorithm is a computer graphics process with which the level of detail of a 3D body modeled as a triangular network can be reduced in a controlled manner without changing the basic appearance of the body. This is done incrementally , always deleting one edge of the triangular network and combining the two adjacent nodes into a single node. The edge is always deleted, the removal of which causes the slightest visual change in the body.

The algorithm was presented in 1997 in a publication by Michael Garland and Paul Heckbert .

algorithm

Edge contraction

In a triangular mesh, deleting an edge and merging the remaining nodes is called edge contraction or collapse. The algorithm provides information about which edge has to be deleted and where the newly created node will be placed.

For this purpose, a square of errors is used that is assigned to each node and edge. This provides information on how large the resulting optical error would be if the corresponding edge were to be contracted. At the same time, it can be used to calculate where the newly emerging node must be placed so that precisely this error (and not a larger one) occurs.

Pseudocode

Compute initially for each node b _i the associated initale Fehlerquadrik Q _{b i} . See further below.

Then iterate until the desired level of detail is achieved:

1. Each edge receives as quadric Q _{E j} the sum of the quadrics of its two end points.
2. Using the quadric, calculate for each edge at which point the contracted node would have to be created in order to cause minimal errors when the edge collapses.
3. Find the edge among all the edges whose error would be the smallest when collapsing. Collapse this edge.
4. The new point created during the collapse is assigned the quadric that belonged to the collapsed edge.

Detailed description

Initial error squares

The error of two when combining node v ₁ and v ₂ to a new v _newly formed, is defined as: the square of the sum of the distances, the v _newly to all surfaces , has the triangles are defined by any of which at v ₁ or v ₂ limits.

To v initially the distance of a point _re- calculate to an area F, the following formula may be used:

${\displaystyle dist(v_{\text{neu}},F)=n^{T}\cdot (v_{\text{neu}}-b)}$

Here b is any point in the surface (e.g. one of the corner points of the triangle that lies in the surface), and n ^T is the normal vector of the surface ( transposed to the line vector ).

If you now square this distance as intended, you get:

${\displaystyle {\begin{aligned}dist(v_{\text{neu}},F)^{2}&=(n^{T}\cdot (v_{\text{neu}}-b))^{2}\\&=(n^{T}\cdot (v_{\text{neu}}-b))\cdot (n^{T}\cdot (v_{\text{neu}}-b))\\&=(n^{T}v_{\text{neu}}-n^{T}b)\cdot (n^{T}v_{\text{neu}}-n^{T}b)\\&=(n^{T}v_{\text{neu}})^{2}-n^{T}v_{\text{neu}}\cdot n^{T}b-n^{T}b\cdot n^{T}v_{\text{neu}}+(n^{T}b)^{2}\\&={v_{\text{neu}}}^{T}n\cdot n^{T}v_{\text{neu}}-b^{T}n\cdot n^{T}v_{\text{neu}}-{v_{\text{neu}}}^{T}n\cdot n^{T}b+b^{T}n\cdot n^{T}b\end{aligned}}}$

If homogeneous coordinates are used , this calculation is equivalent to:

${\displaystyle dist(v_{\text{neu}},F)^{2}=(v_{{\text{neu}}_{x}}v_{{\text{neu}}_{y}}v_{{\text{neu}}_{z}}1)\cdot {\begin{pmatrix}nn^{T}&-nn^{T}b\\-b^{T}nn^{T}&b^{T}nn^{T}b\end{pmatrix}}\cdot {\begin{pmatrix}v_{{\text{neu}}_{x}}\\v_{{\text{neu}}_{y}}\\v_{{\text{neu}}_{z}}\\1\end{pmatrix}}}$

The matrix is called the square of errors of area F. ${\displaystyle Q_{F}={\begin{pmatrix}nn^{T}&-nn^{T}b\\-b^{T}nn^{T}&b^{T}nn^{T}b\end{pmatrix}}}$

If one now considers a node b of the triangular network, the sum of the quadrics of its adjacent triangular areas F _{i can be} assigned to it as the error quadric Q _b .

${\displaystyle Q_{b}=\sum _{i}Q_{F_{i}}}$

The quadric Q _b is calculated to initialize the algorithm for each node of the triangular network.

Iteration step

Calculation of the edge to be contracted

Each edge e _{j of} the triangular network receives as quadric Q _{e j} the sum of the quadrics of its end points b ₁ and b ₂ :

${\displaystyle Q_{e_{j}}=Q_{b_{1}}+Q_{b_{2}}}$

If the edge e _j was not previously assigned a quadric (only in the first iteration step), or if the quadric has changed compared to the last iteration step (because one of the end points was moved by edge contraction), the following must now be calculated:

• Which point v _new when contracting e _j would cause the smallest possible error
• How big the error would be.

To the optimum point v _newly determine, so you have the minimum value of the error function are found, d. H. all partial derivatives of must be 0. ${\displaystyle ({v_{\text{neu}}}^{T}\quad 1)\cdot Q_{e_{j}}\cdot {\begin{pmatrix}v_{\text{neu}}\\1\end{pmatrix}}}$

If these derivatives are calculated, the following system of equations to be solved is obtained:

${\displaystyle {\begin{pmatrix}&nn^{T}&&-nn^{T}b\\0&0&0&1\end{pmatrix}}\cdot {\begin{pmatrix}v_{{\text{neu}}_{x}}\\v_{{\text{neu}}_{y}}\\v_{{\text{neu}}_{z}}\\1\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}}$

Several cases can arise:

• The matrix can be inverted : The point v _new can easily be calculated using the system of equations. ${\displaystyle {\begin{pmatrix}&nn^{T}&&-nn^{T}b\\0&0&0&1\end{pmatrix}}}$
• The matrix cannot be inverted: The optimal value for v _new can be found on the link between the two edge endpoints b ₁ and b ₂ . We then describe v _new as a linear combination of the two end points: and instead look for the minimum of with respect to λ. This is done by simply deriving the function according to λ and setting this derivation = 0. ${\displaystyle {\begin{pmatrix}&nn^{T}&&-nn^{T}b\\0&0&0&1\end{pmatrix}}}$ ${\displaystyle {v_{\text{neu}}}^{*}(\lambda )=(1-\lambda )\cdot b_{1}+\lambda \cdot b_{2}}$ ${\displaystyle dist(v_{\text{neu}},F)^{2}=(({v_{\text{neu}}}^{*})^{T}\quad 1)\cdot Q_{e_{j}}\cdot {\begin{pmatrix}{v_{\text{neu}}}^{*}\\1\end{pmatrix}}}$
• If the second method does not produce a result either, the midpoint between b ₁ and b _{2 is} used, or b ₁ or b ₂ itself.

Now that v is _newly known, the resulting error is calculated. This error is entered in a priority queue , with the lowest error being the top element of the queue. ${\displaystyle ({v_{\text{neu}}}^{T}\quad 1)\cdot Q_{e_{j}}\cdot {\begin{pmatrix}v_{\text{neu}}\\1\end{pmatrix}}}$

Contract the edge

The top element is removed from the queue. This element corresponds to the edge whose contraction causes the least error. The edge is now contracted, and the newly created point v _new is assigned the error square of the edge destroyed in the process. This has the effect that the error in the following iteration steps not only depends on the current triangular network, but also includes the previous changes.

credentials

1. ↑ M. Garland and P. Heckbert. Surface Simplification Using Quadric Error Metrics. In Proceedings of SIGGRAPH 97. ( PDF )