Game Development Reference

In-Depth Information

Figure 16.6 The benefits of allowing merging of close vertex pairs in addition to edge

contraction.

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:

v
T

Q

v

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

Search Nedrilad ::

Custom Search