Graphics Reference
In-Depth Information
Self-intersecting shapes like a figure eight in the plane fail to be manifolds,
because any small neighborhood of the crossing point in the middle of the fig-
ure eight looks like a small letter “x,” which cannot be made to correspond to a
unit interval in a bicontinuous way. The technicalities in defining manifolds are
quite subtle (indeed, it took several decades for them to eventually settle into their
modern form). Fortunately for us, the shapes we use in graphics are generally
“polyhedral manifolds.” The definitions are still subtle, but there are key theorems
that tell us that in the one- and two-dimensional cases, we can instead verify that
something's a manifold by using far simpler methods. Those simpler methods are
precisely the content of our notions of a manifold vertex-and-edge mesh, and a
manifold triangle mesh (which we'll define shortly).
Your goal, in reading the definitions here, should not be to gain a deep under-
standing that you could use to prove theorems—that requires a much more thor-
ough treatment. But you should, when done, be able to say, “Sure, I can look
at a simple mesh and identify it as a manifold mesh, or perhaps manifold-with-
boundary mesh.”
Manifold meshes are commonplace and particularly easy to work with (and
to prove theorems about). Note that the definition does not say that a manifold
mesh must have only one connected component; indeed, a mesh consisting of two
nonintersecting triangles is a valid manifold mesh. So is the empty mesh.
The meshes we've described, in which each edge is an
ordered
pair, are called
oriented meshes;
if we had described edges by unordered pairs, we would have
had an
unoriented mesh,
in which case the definition of “boundary” would have
made no sense. We'll have no further use for such meshes, however.
To prepare for the discussion of 2D meshes in 3-space, we'll describe a data struc-
ture for 1D meshes in 2-space first, one which has strong analogies with more
complex structures. The components are
• A vertex table, consisting of vertex indices and the associated points in the
plane
• An edge table, consisting of ordered pairs of edges
•A
neighbor-list table,
consisting of an ordered cyclic list of edges meeting
a vertex so that one can read off the list of edges at a vertex (in counter-
clockwise order)
We already encountered such a structure when we discussed subdivision of
curves (see Figure 8.5) in Chapter 4.
The operations supported by this data structure (and their implementations)
are as follows.
•
Insert a vertex: Add it to the vertex table; leave other tables untouched.
•
Insert an edge
(
i
,
j
)
: Add it to the vertex table and the edge table (both
O
(
1
)
); add it to the neighbor-list table both at vertex
i
and at vertex
j
. Inser-
tion in the neighbor list for vertex
i
can take O
(
e
)
time, where
e
is the
number of edges in the table (one must insert it in the right place in the
counterclockwise ordering of edges around vertex
i
, which might contain
all
e
edges). In a
manifold
mesh, however, where there can be, at most, two
edges at a vertex, this operation is O
(
1
)
.
