Graphics Reference
In-Depth Information
Notice that the swap removes two triangles from the mesh structure and
replaces them with two others. In the simple vertex- and triangle-table structure,
this operation is trivial. In the directed-edge structure, the implementation is more
complex, because (a) some vertex may point to the edge that's being swapped out,
and this edge pointer needs to be found and replaced; and (b) it makes sense to
replace the two old triangles with the two new ones, but there's substantial shuf-
fling of directed edges in this process, and making sure that the new directed edges
point to the correct new triangles is messy.
W
L
Triangle mesh representations and other representations for nontriangle meshes,
for planar graphs, and for
simplicial complices
—assemblies of vertices, edges,
triangles, tetrahedra, etc.—are widely studied in areas other than graphics; each
representation is tuned to the application area. We've described a few representa-
tions here that are particularly suited to work in graphics, but those who develop
CAD programs, for instance, may have to deal with computing the union and
intersections of shapes represented by meshes. Unfortunately, the union of two
manifold meshes (e.g., two cubes) may not be a manifold mesh (if the cubes share
just one vertex, or just one edge), so structures suitable for nonmanifold represen-
tations may be essential. Those working in finite-element modeling of mechanical
structures or fluid flow have their own constraints, such as the need for triangles
and tetrahedra to be nicely shaped (no small angles in any triangles), or to have
their size vary depending on the region in which they lie (e.g., turbulent flow may
require a fine triangulation, while smooth flow may be adequately represented by
a coarse one).
For most elementary graphics, the vertex- and triangle-table representations
are adequate; their incredible simplicity makes them very versatile, and if you're
implementing your own mesh structures, they're very easy to program properly.
As your needs evolve, more complex structures may be suitable; be certain that
you evaluate the more complex structures to ensure that their complexity solves
your particular problem.
One structure we've completely ignored is the “list each triangle separately as
atripleof
xyz
-coordinates structure.” Although this is simple, it has so many dis-
advantages that we can never recommend its use. In particular, the only way to tell
whether two triangles or edges share a vertex is with floating-point comparisons:
If you move one copy of a vertex, you must move all others if you want to pre-
serve the adjacency structure of the mesh; and determining any sort of adjacency
information is, in general, O
(
T
)
.
Figure 8.16: The aspect ratio
of a planar shape is determined
by finding the bounding box for
the object for which the ratio of
length to width is greatest.
v
b
v
b
v
c
v
d
v
c
v
d
v
a
v
a
Figure 8.17: The triangles adja-
cent to the edge from
v
a
to
v
b
both have bad aspect ratios. By
replacing the edge
v
a
v
b
with the
edge
v
c
v
d
, we get a new pair of
triangles whose aspect ratios are
better.
Exercise 8.1:
Suppose you know that triangle
(
i
,
j
,
k
)
is one of the triangles of a
manifold mesh that's represented by a vertex table and a face table. Then edge
(
i
,
j
)
is in the mesh. Describe how to find the other triangle containing edge
(
i
,
j
)
.
Express the running time of this operation in terms of
T
, the number of triangles
in the mesh. Draw an exemplar class of meshes that shows that the upper bound
you found is actually realized in practice.
