Graphics Reference
In-Depth Information
In graphics, however, the structure of a vertex table and “face table” or “trian-
gle table” is well established. As in the 1D case, insertion of vertices and triangles
is fast, and deletion of vertices is slow (because all associated triangles must be
found and deleted). If we store a neighbor list for each vertex, deletion becomes
faster. Because the neighbor list of triangles meeting a vertex is unordered, the
insertion cost is low, but the deletion cost is high. When additional constraints are
imposed on the mesh, the triangle list for a vertex can be ordered, slightly increas-
ing insertion and deletion costs, but simplifying other operations like finding the
two faces adjacent to an edge.
What about edges? While we cannot insert an edge, we can ask questions like
“Is this pair of vertices an edge of the mesh?” In other words, is it the edge of
some triangle of the mesh? And given a triangle with vertices
i
,
j
, and
k
, we can
ask, “What are the other triangles that contain the edge
(
i
,
j
)
? These questions
are O
(
T
)
, in the sense that answering them requires an exhaustive search of the
triangle list. In special cases, which we discuss in the next section, they can be
made faster.
If you are eager, at this point, to get on with making objects and pictures of
objects, you can safely skip the remainder of this chapter and use the vertex- and
triangle-table structure for meshes until you encounter problems with space or
efficiency, at which point the remaining sections will be of use to you. If, on the
other hand, you'd like to know more about how to work with meshes effectively,
read on.
A finite 2D mesh is a
manifold mesh
if the edges and triangles meeting a vertex
v
can be arranged in a cyclic order
t
1
,
e
1
,
t
2
,
e
2
,
,
t
n
,
e
n
without repetitions such
that edge
e
i
is an edge of triangles
t
i
and
t
i
+
1
(indices taken mod
n
). This implies
that for each edge, there are exactly two faces that contain it.
We can store a manifold mesh in a data structure analogous to the one we
described for 1D meshes, consisting of a vertex table, a triangle table, and a
neighbor-list table.
The neighbor list for vertex
i
consists of the triangles surrounding vertex
i
,in
some cyclic order (so the
k
th and
k
+
1st triangles in the list share an edge). (One
can no longer disambiguate between the two possible cyclic orderings around a
vertex with a notion like “counterclockwise,” unfortunately, unless the manifold
is
oriented,
which we describe in the next section.)
...
3
(1, 2, 3)
1
Manifold meshes unfortunately don't admit insertions or deletions of trian-
gles: Any insertion or deletion ruins the manifold property. But it
is
easy to find
the vertices adjacent to a given vertex (i.e., given a vertex index
i
, we can find all
vertex indices
j
such that
(
i
,
j
)
is an edge): We simply take the set of all vertices of
all triangles in the neighbor list for vertex
i
, and then remove vertex
i
.
It's also fairly easy, given a triangle containing edge
(
i
,
j
)
, to find the other
triangle containing that edge.
2
Figure 8.7: Two adjacent trian-
gles in a mesh with consistent
normal vectors (i.e., the normal
vector tips are on the “same
side” of the mesh). Note that
the edge
(
i
,
j
)
is an edge of one
triangle, but
(
j
,
i
)
is an edge
of the other. In general, in a
consistently oriented mesh, each
edge appears twice, in opposite
directions.
8.3.1.1 Orientation
We'll often have reason to care about the
orientation
of triangles in a mesh
(see Figure 8.8) so that the triangles
(
1, 2, 3
)
and
(
2, 1, 3
)
are considered dif-
ferent (the triples are listings of vertex indices). One use of an orientation is in
the determination of a
normal vector:
If the vertices of a nondegenerate triangle
