i
i
i
i
i
i
i
i
12.1. Triangle Meshes 263
a surface in which a small neighborhood around any point could be smoothed out
into a bit of flat surface. This idea is most clearly explained by counterexample:
if an edge on a mesh has three triangles connected to it, the neighborhood of a
point on the edge is different from the neighborhood of one of the points in the
interior of one of the triangles, because it has an extra “fin” sticking out of it
(Figure 12.1). If the edge has exactly two triangles attached to it, points on the
Figure 12.1. Non-manifold
(left) and manifold (right) in-
terior edges.
edge have neighborhoods just like points in the interior, only with a crease down
the middle. Similarly, if the triangles sharing a vertex are in a configuration like
the left one in Figure 12.2, the neighborhood is like two pieces of surface glued
Figure 12.2. Non-manifold
(left) and manifold (right) in-
terior vertices.
together at the center, which can’t be flattened without doubling it up. The vertex
with the simpler neighborhood shown at right is just fine.
Many algorithms assume that meshes are manifold, and it’s always a good
idea to verify this property to prevent crashes or infinite loops if you are handed a
malformed mesh as input. This verification boils down to checking that all edges
are manifold and checking that all vertices are manifold by verifying the following
conditions:
• Every edge is shared by exactly two triangles.
• Every vertex has a single, complete loop of triangles around it.
Figure 12.1 illustrates how an edge can fail the first test by having too many tri-
angles, and Figure 12.2 illustrates how a vertex can fail the second test by having
two separate loops of triangles attached to it.
Manifold meshes are convenient, but sometimes it’s necessary to allow meshes
to have edges, or boundaries. Such meshes are not manifolds—a point on the
boundary has a neighborhood that is cut off on one side. They are not necessarily
watertight. However, we can relax the requirements of a manifold mesh to those
for a manifold with boundary without causing problems for most mesh processing
algorithms. The relaxed conditions are:
OK OK bad
Figure 12.3. Conditions at
the edge of a manifold with
boundary.
• Every edge is used by either one or two triangles.
• Every vertex connects to a single edge-connected set of triangles.
Figure 12.3 illustrates these conditions: from left to right, there is an edge with
one triangle, a vertex whose neighboring triangles are in a single edge-connected
set, and a vertex with two disconnected sets of triangles attached to it.
Finally, in many applications it’s important to be able to distinguish the “front”
or “outside” of a surface from the “back” or “inside”—this is known as the ori-
entation of the surface. For a single triangle we define orientation based on the
order in which the vertices are listed: the front is the side from which the trian-
gle’s three vertices are arranged in counterclockwise order. A connected mesh is
A
B
C
D
A
B
C
D
OK bad
Figure 12.4. Triangles
(B,A,C) and (D,C,A) are
consistently oriented,
whereas (B,A,C) and
(A,C,D) are inconsistently
oriented.