Graphics Reference
In-Depth Information
When we assign locations to the vertices of a surface mesh (and to the rest of
the mesh by linear interpolation), we want the resultant shape to resemble a sur-
face that has an interior and an exterior, and no self-intersections. To distinguish
between the abstract surface mesh (a list of vertices numbered 1,
,
n
, and a list
of “faces,” or triples of vertex indices) and the geometric object associated to it,
we'll use lowercase letters like
i
and
j
to indicate vertex indices, and
P
i
and
P
j
to indicate the geometric locations of vertices
i
and
j
. We'll also use
C
(
P
i
,
P
j
)
to
denote all convex combinations of
P
i
and
P
j
, that is, the (geometric) edge between
them, and
C
(
P
i
,
P
j
,
P
k
)
to denote all convex combinations of the vertex locations
P
i
,
P
j
, and
P
k
, that is, the (geometric) triangle with those points as vertices.
With this terminology, we'll define an
embedding
of a surface mesh as an
assignment of distinct locations to the vertices, extended to edges and faces by
linear interpolation and satisfying one property: The triangles
T
1
=
C
(
P
i
,
P
j
,
P
k
)
and
T
2
=
C
(
P
p
,
P
q
,
P
r
)
intersect in
R
3
only if the vertex sets
...
}
intersect in the abstract mesh. If the intersection is a single vertex index
s
, then
T
1
∩
{
i
,
j
,
k
}
and
{
p
,
q
,
r
T
2
=
C
(
P
s
,
P
t
)
; and if the intersection is all three vertex indices, then
T
1
must be iden-
tical to
T
2
. (Note that we're assuming that
i
,
j
, and
k
are distinct and
p
,
q
, and
r
are
distinct; otherwise, either
T
1
or
T
2
would not be a triangle.)
Figure 25.11 shows examples of nonembedded meshes. In the first example,
two triangles intersect in their interiors. In the second, two triangles intersect at a
point that is a vertex of one triangle, but is mid-edge on the other triangle. In the
third, the intersection (shown in aqua) of two shaded triangles is only part of an
edge of the left one (a situation known as a
T-junction
).
T
2
must be
P
s
; if the intersection has two vertices
s
and
t
, then
T
1
∩
When we have both a face table and a vertex table, we can test whether the
resultant geometric mesh is embedded or not, but the operation is expensive and
prone to numerical errors. First, the entries of the vertex table (i.e., the vertex loca-
tions) must all be distinct. Second, for every pair of faces the geometric intersec-
tion of the faces must be empty unless the abstract faces share an edge or a vertex,
in which case the geometric intersection should match the abstract intersection.
Good modeling software is designed to ensure that only embedded meshes get
produced so that such tests are not necessary.
Ifameshis
closed,
that is, its boundary is empty, and if it's embedded, then
(1) the mesh must be orientable, and (2) the embedded mesh divides 3-space into
two parts: a bounded piece called the
interior
and an unbounded piece called the
exterior.
The first statement is proved by Banchoff [Ban74]; the second, which
may seem obvious, is really quite subtle, and is a consequence of the Alexander
Duality Theorem [GH81], which is far beyond the scope of this topic. To deter-
mine whether a point
P
that's not on the mesh itself is in the interior or exterior,
we can create a ray
r
that starts at
P
and travels in some direction
d
, missing all
vertices and edges of the mesh. If the ray
r
intersects
k
faces of the mesh, then
P
is inside if
k
is odd and outside if
k
is even. The direction
d
can be produced by
picking a direction at random; with probability one the ray
r
will miss all vertices
and edges of the mesh.
A closed embedded mesh is, from a geometric and algorithmic point of view,
an ideal object. It's suitable for use in ray tracing, in rendering with backface
culling, for shadow-volume computations, etc. Furthermore, if a closed mesh is
embedded and we move the vertex locations by a small enough amount, the
Figure 25.11: (Top) A mesh with
bad self-intersections. (Middle) A
mesh in which a vertex of the pink
face at the right lies in the middle
of an edge of the green face at the
top right. (Bottom) The red vertex
marked with a dot is a T-junction.
