Graphics Reference
In-Depth Information
25.2 Mesh Topology
The topology of meshes—what's connected to what—is of primary importance
in many mesh algorithms, which often proceed by some kind of adjacency search
like depth-first or breadth-first search. In this section we'll discuss the intrinsic
topology of meshes (i.e., those aspects that can be determined by looking only
at the face table), and we'll briefly touch on the topic of embedding topology
for meshes that are embedded in 3-space (i.e., for which there's a vertex table
specifying positions of vertices, and for which the resultant mesh has no self-
intersections, which we'll define precisely).
To specify the topology of a triangle mesh, we typically choose a collection
of vertices (usually represented by vertex indices, so we speak of vertex 7, or
vertex 2), a collection of edges, with each edge being a pair of vertex indices,
and a collection of faces, with each face being a triple of vertex indices. We'll
put additional constraints on these in a moment. Because a vertex consists of one
index, an edge consists of two indices, and a face consists of three indices, it's
useful to have a term that encompasses all three. We say that a k -simplex is a set
of k + 1 vertices. Thus, a vertex is a 0-simplex, an edge is a 1-simplex, and a face
is a 2-simplex. (These ideas can be generalized to describe tetrahedral meshes, in
which 3-simplices are allowed, and to even higher-dimensional meshes.)
For nontriangle meshes, a face may consist of a sequence of more than three
vertices. All the algorithms presented here become substantially more complex
when nontriangular faces are allowed in the mesh, so we'll generally consider
only triangle meshes.
The degree of a vertex is the number of edges that contain the vertex. The term
valence is also used, by analogy with atoms in a molecule. The vertex is said to be
adjacent to the edges containing it, and vice versa. We generalize to say that the
degree of an edge is the number of faces that contain the edge. (The edge is said
to be adjacent to the faces, and vice versa.) We'll restrict our attention to meshes
in which each edge has degree one, in which case it's called a boundary edge, or
degree two, in which case it's called an interior edge (see Figure 25.3). An edge
that's adjacent to no faces at all is called a dangling edge and is not allowed in
our meshes.
Figure 25.3: A small mesh with
interior edges drawn in green and
boundary edges drawn in blue.
The red edge, which is not adja-
cent to any faces, is a “dangling”
edge and is not allowed in our
meshes.
25.2.1 Triangulated Surfaces and Surfaces
with Boundary
To make our algorithms clean and provably correct, we will restrict the class of
triangle meshes that we allow. We've already restricted our attention to meshes
where each edge has one or two adjacent faces, but we will need some additional
restrictions.
1. Each face may occur no more than once, that is, no two faces of the mesh
can share more than two vertices.
2. The degree of each vertex is at least three.
 
 
 
 
Search WWH ::




Custom Search