i
i
i
i
i
i
i
i
12.5. Simplification 561
be paired with the original index buffer describing the mesh’s connectivity,
to further process and display the resulting mesh.
12.5 Simplification
Research into simplification and alternate model descriptions is an active
and wide-ranging field. One area of interest is algorithms to convert surface
features into bump maps [182, 1104]. Sander et al. [1103] use bump maps
and a coarse mesh for the model, but create a higher precision silhouette.
Impostors [806], described in Section 10.7.1, are another form of alternate
rendering of the same model. Sprites and layered depth images can replace
geometry in scenes (see Sections 10.5 and 10.7.1).
Mesh simplification,alsoknownasdata reduction or decimation,isthe
process of taking a detailed model and reducing its polygon count while
attempting to preserve its appearance. For real-time work normally this
process is done to reduce the number of vertices stored and sent down
the pipeline. This can be important in making the application scalable, as
older machines may need to display lower numbers of polygons [984]. Model
Figure 12.20. On the left is a heightfield of Crater Lake rendered with 200,000 triangles.
The right figure shows this model simplified down to 1000 triangles. The underlying
simplified mesh is shown below. (Images courtesy of Michael Garland.)
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
i
i
i
i
i
i
i
i
12.5. Simplification 563
Figure 12.21. On the left is the figure before the uv edge collapse occurs; the right figure
shows point u collapsed into point v, thereby removing triangles A and B and edge uv.
utility library uses this strategy [351], as do most other systems, such as
Melax’s [852].
By using an optimal placement strategy, we examine a wider range of
possibilities. Instead of collapsing one vertex into another, both vertices for
an edge are contracted to a new location. Hoppe [560] examines the case
in which u and v both move to some location on the edge; he notes that in
order to improve compression of the final data representation the search can
be limited to checking the midpoint. Another strategy is to limit the new
placement point to anywhere on the edge. Garland and Heckbert [380] solve
a quadratic equation to find an optimal position (which may be located off
of the edge). The advantage of optimal placement strategies is that they
tend to give higher-quality meshes. The disadvantages are extra processing,
code, and memory for recording this wider range of possible placements.
To determine the best point placement, we perform an analysis on the
local neighborhood. This locality is an important and useful feature for
a number of reasons. If the cost of an edge collapse depends on just a
few local variables (e.g., edge length and face normals near the edge), the
cost function is easy to compute, and each collapse affects only a few of its
neighbors. For example, say a model has 3000 possible edge collapses that
are computed at the start. The edge collapse with the lowest cost-function
value is performed. Because it influences only a few nearby triangles and
their edges, only those edge collapse possibilities whose cost functions are
affected by these changes need to be recomputed (say 10 instead of 3000),
and the list requires only a minor bit of resorting. Because an edge-collapse
affects only a few other edge-collapse cost values, a good choice for main-
taining this list of cost values is a heap or other priority queue [1183].
The collapse operation itself is an edit of the model’s database. Data
structures for storing these collapses are well-documented [112, 351, 562,
852, 1232]. Each edge collapse is analyzed with a cost function, and the one
with the smallest cost value is performed next. An open research problem
i
i
i
i
i
i
i
i
564 12. Polygonal Techniques
u
v
edge
crossing
Figure 12.22. Example of a bad collapse. On the left is a mesh before collapsing vertex
u into v. On the right is the mesh after the collapse, showing how edges now cross.
is finding the best cost function under various conditions [801]. Depend-
ing on the problem being solved, the cost function may make trade-offs
among speed, quality, robustness, and simplicity. It may also be tailored
to maintain surface boundaries, material locations, lighting effect, texture
placement, volume, or other constraints.
Garland and Heckbert [379] introduced the idea that any pair of ver-
tices, not just edge vertices, can form a pair and be contracted into one
vertex. To limit the numbers of pairs to test, only those vertices within
some distance t of each other can form a pair. This concept of pair con-
traction is useful in joining together separate surfaces that may be close to
each other, but are not precisely joined.
Some contractions must be avoided regardless of cost; see the example
in Figure 12.22. These can be detected by checking whether a neighboring
polygon flips its normal direction due to a collapse.
We will present Garland and Heckbert’s cost function [379, 380] in order
to give a sense of how such functions work. Because of its efficiency and
reasonable results, it is the cost function used in the DirectX utility library
and a number of other simplification libraries. For a given vertex there
is a set of triangles that share it, and each triangle has a plane equation
associated with it. The cost function for moving a vertex is the sum of the
squared distances between each of these planes and the new location. More
formally,
c(v)=
m
i=1
(n
i
· v + d
i
)
2
is the cost function for new location v and m planes, where n is the plane’s
normal and d its offset from the origin.
An example of two possible contractions for the same edge is shown
in Figure 12.23. Say the cube is two units long. The cost function for
i
i
i
i
i
i
i
i
12.5. Simplification 565
e
c
c
e
Figure 12.23. The left figure shows a cube with an extra point along one edge. The
middle figure shows what happens if this point e is collapsed to corner c.Theright
figure shows c collapsed to e.
collapsing e into c (e → c) will be 0, because the point e does not move off
of the planes it shares when it goes to c. The cost function for c → e will
be 1, because c moves away from the plane of the right face of the cube
by a squared distance of 1. Because it has a lower cost, the e → c collapse
would be preferred over c → e.
Figure 12.24. Mesh simplification. Upper left shows the original mesh of 13,546 faces,
upper right is simplified to 1,000 faces, lower left to 500 faces, lower right to 150 faces.
(Images courtesy of Hugues Hoppe, Microsoft Research.)
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.