Graphics Reference
In-Depth Information
(i.e., one with a nonzero area) are at locations
P
i
,
P
j
, and
P
k
, then we can compute
(
P
j
−
j
P
i
)
, which is a vector perpendicular to the plane of the triangle.
1
Note that if we exchange vertices
P
j
and
P
k
, the resultant vector is negated. Since
we often use the normal to a triangle in a mesh to determine what's “inside” or
“outside” the mesh, the ordering of the vertices is critical.
P
i
)
×
(
P
k
−
h
(
h
,
j
,
i
)
(
i
,
j
,
k
)
k
If two adjacent triangles (see Figure 8.7) have consistently oriented normal
vectors, then the edge they share will appear as
(
i
,
j
)
in one triangle and as
(
j
,
i
)
in the other. And if a manifold mesh can have its triangles oriented so that this is
true, it can also be given consistently oriented normal vectors. This is a nontrivial
theorem from combinatorial topology.
When a manifold is oriented, the triangles around a vertex have a natural
order. Suppose that surrounding vertex 1 there are the triangles
(
5, 1, 2
)
,
(
4, 3, 1
)
,
(
1, 5, 4
)
, and
(
1, 3, 2
)
. We can cyclically permute each to put vertex 1 first:
(
1, 2, 5
)
,
(
1, 4, 3
)
,
(
1, 5, 4
)
, and
(
1, 3, 2
)
. Now starting with the first triangle, we
can consider its “first” and “last” edges,
(
1, 2
)
and
(
5, 1
)
. We choose, as our next
triangle, the one whose first edge is the opposite,
(
1, 5
)
, of this last edge. That's
(
1, 5, 4
)
. And the last edge of
(
1, 5, 4
)
is
(
4, 1
)
;
(
1, 4
)
is the first edge of
(
1, 4, 3
)
,
whose last edge is
(
3, 1
)
;
(
3, 1
)
is the first edge of
(
1, 3, 2
)
, and we've ordered the
triangles:
(
1, 2, 5
)
,
(
1, 5, 4
)
,
(
1, 4, 3
)
,
(
1, 3, 2
)
.
i
Figure 8.8: The triangles of this
mesh are
oriented
; the circular
arrows indicate the cyclic order-
ing
of
the
vertices.
Note
that
(
)
the
vertex
triples
1, 2, 3
and
(
)
indicate the same ori-
ented triangle (i.e., there are
three equivalent descriptions of
every oriented triangle).
2, 3, 1
8.3.1.2 Boundaries
More interesting than manifold meshes (and more common as well) are meshes
whose vertices are manifold or
boundarylike
(see Figure 8.9), in the sense that
instead of the adjacent triangles forming a cycle, they form a chain, whose first
and last elements share only one of their edges with other triangles in the chain;
the
other
edge of the first triangle that meets the vertex is contained
only
in the first
triangle, and not in any other triangle of the mesh. (The same condition applies to
the last triangle.) This unshared edge is called a
boundary edge,
and the vertex
is called a
boundary vertex.
Vertices that are not boundary vertices are called
interior vertices.
Figure 8.9: (left) A manifold
vertex has a cycle of triangles
around it; (right) by contrast, a
boundarylike vertex v has a chain
of triangles around it—the start-
ing and ending triangles of the
chain each share only one of
their edges with other triangles
of the chain. The other edges of
those triangles that contain v are
boundary edges
.
8.3.1.3 Boundaries and Oriented 2D Meshes
Just as we defined the boundary of an edge from vertex
i
to vertex
j
to be the formal
sum
v
j
−
v
i
, we can define the boundary of a triangle in a mesh with vertices
i
,
j
,
and
k
to consist of the formal sum of edges
(
i
,
j
)+(
j
,
k
)+(
k
,
i
)
.
(8.2)
Furthermore, we can define an algebra on these formal sums in which the vertex
(
i
,
j
)
is identified with
−
1
(
j
,
i
)
so that the boundary above could be written
(
i
,
j
)+(
j
,
k
)
−
(
i
,
k
)
(8.3)
instead. We can define the boundary of a collection of oriented triangles as the
formal sum of their boundaries.
For an oriented manifold mesh, this boundary will be zero (i.e., the coefficient
of each edge will be zero), because if
(
i
,
j
)
is part of the boundary of one face, then
(
j
,
i
)=
−
(
i
,
j
)
is part of the boundary of another.
1. The description of the cross product and further discussion of normal vectors was given
in Chapter 7.
