Graphics Reference
In-Depth Information
edge contains references to two vertices and three edges, using 20 bytes. Triangu-
lar faces are not explicitly represented. So the memory use is
v
a
v
b
16
V
+
40
E
≈
8
T
+
60
T
=
68
T
(8.6)
bytes. Note that in the analysis above, we assumed that a vertex or edge reference
required only a single byte; for more complex meshes, this byte count may have
to to be increased to roughly
Figure 8.14: The edge from ver-
tex a to vertex b is collapsed;
the edge itself and the two adja-
cent faces are removed from the
data structure; and the other two
edges of the upper face, drawn in
blue, become one, as do the two
edges of the lower face, drawn
in red. Nothing else changes. The
two vertices
v
a
and
v
b
become a
single vertex.
log
2
(
3
2
)
.
One of the advantages of triangle meshes is that their homogeneity makes certain
operations easy to perform. For manifold meshes, the homogeneity is even greater.
In mesh simplification, for instance, one of the standard operations is an
edge
collapse,
in which one edge is shrunk until it has length zero, resulting in the two
adjacent triangles disappearing. In mesh
beautification
(where we try to make a
mesh have nearly equilateral triangles and other nice properties), the
edge-swap
operation helps turn two long and skinny triangles into two more nearly equilateral
ones. Both involve minimal operations on the data structure itself.
In the
edge-collapse
operation (see Figure 8.14), a single edge of a mesh is
removed [HDD
+
93]. The two triangles that contain this edge are both eliminated,
and the other two edges of each of them become a single edge in the new mesh.
The vertices at the end of the eliminated segment become a single vertex.
The description above is purely topological; there's a geometric question as
well: When we merge the two vertices, we must choose a
location
for the merged
vertex. The location we choose depends on the goal of our simplification (see
Figure 8.15). If computation is at a premium, simply using one of the old vertices
as the new one is very fast. If we want to preserve some sort of shape, averaging
the two vertices is easy. If such an averaging process moves a lot of points, and
this will be visually distracting, we can choose a new location that minimizes the
average or extreme distance between the old and new meshes. There is no one
“right answer.” As in most of graphics, the choice you make depends on your
intended use of the data structure.
Q
AB
Figure 8.15: Different geometric
choices for an edge collapse in
2D. The edge AB is collapsed;
one can (a) place the collapsed
vertex at A for computational
simplicity, (b) at the midpoint of
the segment AB, or (c) at a point
Q that minimizes the maximum
(or average) distance from every
old mesh point to the nearest new
mesh point. Other goals are pos-
sible as well.
Meshes that get distorted or deformed in the course of an application's use of them
may eventually get so deformed that individual triangles are long and skinny. Such
triangles are characterized by their bad
aspect ratios
. In general, one can define an
aspect ratio
for a planar shape (see Figure 8.16) by finding, among all rectangles
that enclose the object and touch it on all four sides (these are called
bounding
boxes
), the one whose length-to-width ratio is greatest. This ratio is then called the
aspect ratio. High-aspect-ratio triangles produce bad artifacts in many situations,
so it's nice to be able to eliminate them when possible. An
edge-swap
operation
(see Figure 8.17) can convert two adjacent high-aspect-ratio triangles to two with
lower aspect ratios. (It can also, done in reverse, do the opposite: Selecting the
right edge to swap in order to beautify a mesh requires examining the impact of
each possible swap.)