Game Development Reference
Figure 16.6 The benefits of allowing merging of close vertex pairs in addition to edge
The location of the merged vertex can be found using the inverse of this
matrix if it is invertible or some point along the current edge if it is not. The
effect of merging a vertex pair is found using this vertex location and the
sum of the two vertex quadrics:
In their paper, Garland and Heckbert summarized the algorithm as:
1 Compute the Q matrices for all the vertices in the mesh.
2 Select all valid pairs, edges and unconnected vertices that are within
the distance parameter.
3 Compute the position of the vertex when a vertex pair is merged.
4 Compute the error for these new vertices using v T ( Q 1 + Q 2 ) v .
5 Place the pairs on a heap based on the error calculated in step 4.
6 Iteratively merge a pair and update the costs of any other vertices
affected by this change.
7 Repeat until the desired polygon total is reached.
Deriving the quadric matrix
Each vertex in the mesh is one corner of a number of triangles. If we think
of the triangles as planes, then the vertex represents the intersection of a
group of planes. If these planes are almost in line with each other, then the
effect of removing this vertex will be minimal. If the planes are at a sharp