Graphics Reference
In-Depth Information
3.
If
V
is a vertex, then the vertices that share an edge with
V
can be ordered
U
1
,
U
2
,
U
2
...
,
U
n
so that
{
V
,
U
1
,
U
2
}
,
{
V
,
U
2
,
U
3
}
,
...
,
{
V
,
U
n
−
1
,
U
n
}
are all
triangles of the mesh, and
(a)
U
1
{
V
,
U
n
,
U
1
}
is a mesh triangle (in which case
V
is said to be an
interior
V
vertex
), or
U
4
(b)
is not a mesh triangle (in which case
V
is said to be a
boundary vertex
),
and there are no other triangles containing the vertex
V
(see Figure 25.4).
{
V
,
U
n
,
U
1
}
U
3
U
4
In the event that such a mesh has no boundary vertices, it's called a
closed
surface;
if it has boundary vertices, it's called a
surface with boundary.
U
3
Inline Exercise 25.2:
Figure 25.5 shows three surfaces, each of which fails the
requirements for being a surface or surface with boundary. Explain the three
failures.
U
2
U
1
V
Figure 25.4: The red vertex
marked with a dot in the top mesh
is an interior vertex; the one in
the bottom mesh is a boundary
vertex.
We have not yet said anything about orientation or orientability so that, for
instance, the Möbius band is a perfectly admissible surface with boundary.
Inline Exercise 25.3:
Show that the mesh with faces (1, 2, 3), (2, 3, 4),
(
3, 4, 5
)
,
(
4, 5, 1
)
,
(
5, 1, 2
)
and vertices 1, 2, 3, 4, and 5 is a surface with bound-
ary (i.e., satisfies all the conditions above). Determine the set of boundary
edges.
The
boundary
of a simplex is gotten by deleting each vertex of the simplex
in turn, so the boundary of
{
2, 3, 5
}
consists of the three sets
{
2, 3
}
,
{
2, 5
}
, and
{
3, 5
}
. Similarly, the boundary of the 1-simplex
{
2, 4
}
consists of the two sets
{
2
}
{
}
{
}
and
4
. The boundary of the 0-simplex
8
consists of the empty set.
The basic mesh-storage structure is the face table, but adding and removing faces
from an array is slow. Storing faces in a linked list rather than a table represented
as a matrix allows low-overhead addition and deletion of faces, but operations like
detecting adjacency can be expensive. The winged-edge data structure described
in Chapter 8 makes adjacency computations very quick, but addition and deletion
are relatively heavyweight operations.
Most adjacency-determining operations can be done, in a precomputation step,
with hash tables. For instance, here's how to determine all boundary edges: First,
for any face like
, there are three edges, each of which we'll represent
with an ordered pair. But the first edge could be represented by the pair
(
2, 5
)
or
(
5, 2
)
. We'll make the choice of representing the vertices in an edge in increasing
order, so the edges are
(
2, 5
)
,
(
3, 5
)
, and
(
2, 3
)
. With this convention, finding the
boundary edges is easy: We start with an empty hash table of edges. For each face
of the mesh we compute the three edges, and for each such edge we either insert it
in the table if it's not there already or delete it from the table if it is there already.
When we've processed all the faces, the edges that remain in the table are those
that appeared only once; in other words, they are the boundary edges.
{
5, 2, 3
}
Figure 25.5: Each of these fails to
be a surface mesh in some way.
