Game Development Reference
In-Depth Information
Figure 16.5 Removing an edge.
There is a limitation to the edge contraction-based technique where an
unconnected mesh is involved. Because we only allow for edge
contraction, the model can change dramatically in the volumes perceived.
In a low polygon game, the perceived volumes are the most important
aspect of the display. A useful way to avoid the problem of changing
volume when reducing polygons is to allow for two vertices that are close
together to be regarded in the same way as an edge. The human eye
works in much the same way, with distant detail merging together.
Determining the limiting distance for such vertex pairs has to be handled
with care, but the resulting models hold their volume much more
effectively.
Deciding who can stay and who must go
The algorithm we use must determine an error for the removal of an edge.
If by removing the edge we retain a similar shape to the original, after this
contraction then this edge can be safely removed. We do this by
calculating a quadric matrix, Q , for each vertex. The error at a vertex is
then given by v T Q v . When calculating the effect of merging two vertices,
we create a new matrix by using the sum of the matrices for each
vertex:
Q
= Q 1 + Q 2