i
i
i
i
i
i
i
i
566 12. Polygonal Techniques
This cost function can be modified in various ways. Imagine two trian-
gles that share an edge that form a very sharp edge, e.g., they are part of a
fish’s fin or turbine blade. The cost function for collapsing a vertex on this
edge is low, because a point sliding along one triangle does not move far
from the other triangle’s plane. The basic function’s cost value is related
to the volume change of removing the feature, but is not a good indicator
of its visual importance. One way to maintain an edge with a sharp crease
is to add an extra plane that includes the edge and has a normal that is
the average of the two triangle normals. Now vertices that move far from
this edge will have a higher cost function [381]. A variation is to weight
the cost function by the change in the areas of the triangles [112].
Another type of extension is to use a cost function based on maintaining
other surface features. For example, the crease and boundary edges of a
model are important in portraying it, so these should be made less likely
to be modified. See Figure 12.24. Other surface features worth preserving
are locations where there are material changes, texture map edges, and
color-per-vertex changes [565]. Radiosity solutions use color per vertex to
record the illumination on a meshed surface and so are excellent candi-
dates for reduction techniques [560]. The underlying meshes are shown in
Figure 12.25, a comparison of results in Figure 12.26.
The best edge to collapse is the one that makes the least perceptible
change in the resulting image. Lindstrom and Turk [780] use this idea to
produce an image-driven collapse function. Images of the original model
are created from a set of different view directions, say 20 in all. Then all
potential edge collapses are tried for a model and for each one a set of
Figure 12.25. Simplification of radiosity solution. Left is the original mesh (150,983
faces); right is simplified mesh (10,000 faces). (Images courtesy of Hugues Hoppe, Mi-
crosoft Research.)
i
i
i
i
i
i
i
i
12.5. Simplification 567
Figure 12.26. Simplification of a radiosity solution, shaded results. (Images courtesy of
Hugues Hoppe, Microsoft Research.)
images is generated and compared to the original. The edge with the least
visual difference is collapsed. This cost function is expensive to compute,
and is certainly not a technique that can be done on the fly. However,
simplification is a process that can be precomputed for later use. The
advantage of the scheme is that it directly evaluates the visual effect of
each collapse, versus the approximations provided by simpler functions.
One serious problem that occurs with most simplification algorithms is
that textures often deviate in a noticeable way from their original appear-
ance [801]. As edges are collapsed, the underlying mapping of the texture
to the surface can become distorted. A related concept is the idea of turn-
ing a surface’s original geometry into a normal map for bump mapping.
Sander et al. [1104] discuss previous work in this area and provide a so-
lution. Their idea is to split the mesh into reasonable submeshes, each of
which is to give a local texture parameterization. The goal is to treat the
surface position separately from the color and bump information.
Edge-collapse simplification can produce a large number of level of
detail (LOD) models (see Section 14.7) from a single complex model. A
problem found in using LOD models is that the transition can sometimes
be seen if one model instantly replaces another between one frame and
the next [371]. This problem is called “popping.” One solution is to use
geomorphs [560] to increase or decrease the level of detail. Since we know
how the vertices in the more complex model map to the simple model, it is
possible to create a smooth transition. See Section 14.7.1 for more details.
One advantage of using VIPM is that a single vertex buffer can be cre-
ated once and shared among copies of the same model at different levels
of detail [1232]. However, under the basic scheme, a separate index buffer
i
i
i
i
i
i
i
i
568 12. Polygonal Techniques
Figure 12.27. Symmetry problem. The cylinder on the left has 10 flat faces (including
top and bottom). The middle cylinder has 9 flat faces after 1 face is eliminated by
automatic reduction. The right cylinder has 9 flat faces after being regenerated by the
modeler’s faceter.
needs to be made for each copy. Another problem is efficiency. Static
LOD models can undergo stripification to improve their display speeds.
For dynamic models, basic VIPM does not take into account the under-
lying accelerator hardware. Because the order of collapses determines the
triangle display order, vertex cache coherency is poor. Bloom [113] and
Forsyth [351] discuss a number of practical solutions to improve efficiency
when forming and sharing index buffers.
DeCoro and Tatarchuk [239] present a method of performing simplifi-
cation itself using the GPU pipeline, obtaining a 15–22× increase in per-
formance over the GPU.
Polygon reduction techniques can be useful, but they are not a panacea.
A talented model maker can create low-polygon-count objects that are bet-
ter in quality than those generated by automated procedures. One reason
for this is that most reduction techniques know nothing about visually im-
portant elements or symmetry. For example, the eyes and mouth are the
most important part of the face [852]. A naive algorithm will smooth these
away as inconsequential. The problem of maintaining symmetry is shown
in Figure 12.27.
12.5.2 View-Dependent Simplification
One type of model with unique properties is terrain. The data typically
is represented by uniform heightfield grids. View-independent methods of
simplification can be used on this data, as seen in Figure 12.20 on page 561.
The model is simplified until some limiting criterion is met [378]. Small
surface details can be captured by color or bump map textures. The re-
sulting static mesh, often called a triangulated irregular network (TIN), is
i
i
i
i
i
i
i
i
12.5. Simplification 569
a useful representation when the terrain area is small and relatively flat in
various areas [1302].
For other outdoor scenes, continuous level of detail techniques can be
used to minimize the number of vertices that must be processed. The idea
is that terrain that is in view and close to the viewer should be shown with
a greater level of detail. One type of algorithm is to use edge collapses and
geomorphing, as described in the previous section, but with a cost function
based on the view [561, 563]. The entire terrain is not represented as a
single mesh, but rather as smaller tiles. This allows techniques such as
frustum culling and potential visible sets to be used to quickly remove tiles
from further consideration.
Another class of algorithms is based on using the underlying structure
of the heightfield grid itself. The method by Lindstrom et al. [779], and
the ROAM scheme by Duchaineau et al. [278, 1278] are two pioneering
papers in this area. While these schemes are relatively inefficient on mod-
ern GPUs, many of the concepts presented are relevant to most terrain
rendering systems.
The idea is to impose a hierarchical structure on the data, then evaluate
this hierarchy and render only the level of complexity needed to sufficiently
represent the terrain. A commonly used hierarchical structure introduced
in ROAM is the triangle binary tree (bintree). Starting with a large right
triangle, with vertices at the corners of the heightfield tile, this triangle
can be subdivided by connecting its centerpoint along the diagonal to the
opposite corner. This splitting process can be done on down to the limit
of the heightfield data. See Figure 12.28. In the ROAM algorithm, an
error bound is created for each triangle. This error bound represents the
maximum amount that the associated terrain heightfield varies from the
plane formed by the triangle. In other words, three points on the heightfield
define a triangle, and all the heightfield samples covered by this triangle are
compared to the triangle’s plane and the absolute value of the maximum
difference is the error bound. The vertical error bound and the triangle
Figure 12.28. The triangle bintree. On the left, the heightfield is represented by two
triangles at the topmost level. At each successive level, every triangle is split into two,
with splits shown by the thick lines.
i
i
i
i
i
i
i
i
570 12. Polygonal Techniques
Figure 12.29. A ROAM view-dependent subdivision of the terrain. At top, the yellow
dot on the left is the viewer. The blue areas are outside the view frustum, the light
green are inside, and the dark green overlap the frustum’s edges. (Images courtesy of
Mark Duchaineau, LLNL.)
together define a pie-shaped wedge of space that contains all the terrain
associated with that triangle.
During run-time, these error bounds are projected on to the view plane
and evaluated for their effect on the rendering. For example, looking edge-
on through a wedge means that the silhouette of the terrain is visible
through that wedge, so a highly tessellated version of the terrain is needed.
Looking top down through the triangular part of the wedge means the ge-
ometry itself is not critical. Due to projection, a distant wedge will have a
smaller projected error, and so will be tessellated less. Blow [119] discusses
improved error metrics for ROAM.
Once the subdivision level of each visible triangle is computed, tessella-
tion can occur. Crack avoidance and repair is a major part of any terrain
rendering algorithm. That is, if one triangle is highly subdivided and its
neighbors are not, cracks or T-vertices can develop between the levels. The
bintree structure lends itself to avoiding such splits. See Figure 12.29.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.