i
i
i
i
i
i
i
i
562 12. Polygonal Techniques
data may also be received with more tessellation than is necessary for a
reasonable representation. Figure 12.20 gives a sense of how the number
of stored triangles can be reduced by data reduction techniques.
Luebke [800, 801] identifies three types of polygonal simplification:
static, dynamic, and view-dependent. Static simplification is the idea of
creating separate level of detail (LOD) models before rendering begins, and
the renderer chooses among these. This form is covered in Section 14.7.
Batch simplification can also be useful for other tasks, such as providing
coarse meshes for subdivision surfaces to refine [745, 746]. Dynamic sim-
plification gives a continuous spectrum of LOD models instead of a few
discrete models, and so such methods are referred to as continuous level of
detail (CLOD) algorithms. View-dependent techniques are meant for mod-
els where the level of detail varies within the model. Specifically, terrain
rendering is a case in which the nearby areas in view need detailed repre-
sentation while those in the distance are at a lower level of detail. These
two types of simplification are discussed in this section.
12.5.1 Dynamic Simplification
One method of reducing the polygon count is to use an edge collapse op-
eration. In this operation, an edge is removed by moving its two vertices
to one spot. See Figure 12.21 for an example of this operation in action.
For a solid model, an edge collapse removes a total of two triangles, three
edges, and one vertex. So a closed model with 3000 triangles would have
1500 edge collapses applied to it to reduce it to zero faces. The rule of
thumb is that a closed triangle mesh with v vertices has about 2v faces and
3v edges. This rule can be derived using the Euler-Poincar´e formula that
f − e + v = 2 for a solid’s surface. See Section 12.4.4.
The edge collapse process is reversible. By storing the edge collapses
in order, we can start with the simplified model and reconstruct the com-
plex model from it. This characteristic is useful for network transmission
of models, in that the edge-collapsed version of the database can be sent
in an efficiently compressed form and progressively built up and displayed
as the model is received [560, 1253]. Because of this feature, this simplifi-
cation process is often referred to as view-independent progressive meshing
(VIPM).
In Figure 12.21, u was collapsed into the location of v, but v could
have been collapsed into u. A simplification system limited to just these
two possibilities is using a subset placement strategy. An advantage of
this strategy is that, if we limit the possibilities, we may implicitly encode
the choice actually made [380, 560]. This strategy is faster because fewer
possibilities need to be examined, but it also can yield lower-quality ap-
proximations because a smaller solution space is examined. The DirectX