Graphics Reference
In-Depth Information
Inline Exercise 25.6:
The point-versus-plane test involves a point subtraction,
a dot product, and a comparison. Assuming that all points are stored as triples
of coordinates, we can consider the special point
Z
=(
0, 0, 0
)
and rewrite the
test as
((
P
n
. Assuming that
this computation appears in the innermost loop of your program so that you're
willing to ignore the point-versus-vector distinction, and assuming further that
you're willing to do more precomputation, how few operations can you use to
do this computation for each new test point
P
? (Answer: three multiplies, two
adds, one compare. Your job is to verify this.)
−
Z
)
−
(
Q
−
Z
))
·
n
>
0, or
(
P
−
Z
)
·
n
>
(
Q
−
Z
)
·
One final data structure for meshes—and one that is particularly useful for
meshes that will remain mostly topologically static, that is, for which addition and
removal of faces is very rare—is an enhancement of the triangle mesh in which
row
i
of the face table stores the indices of the three vertices for triangle
i
,but
also
stores the indices of the three triangles that are adjacent to triangle
i
. (If triangle
i
has one or two edges on the boundary of the mesh, then the corresponding index
is set to
invalid
.) This structure speeds up coherent searching of the mesh data
structure, especially for processes like contour finding. (If edge
e
is a contour edge
as seen from some viewpoint, then the edges that meet
e
are very good candidates
to also be contour edges.)
Figure 25.8: The star of a simplex
consists of all simplices contain-
ing it.
There are analogous structures for quad meshes. The difference between tri-
angles and quads may seem small, but it's nontrivial. If you can replace a pair of
adjacent triangles with a quad, you've turned five edges into four, and that may
mean a 20% speedup in your program.
V
The
star of a vertex
consists of the vertex itself and the set of edges and faces
that contain that vertex (i.e., like a “neighborhood” of the vertex). The
star of an
edge
consists of the edge itself and any faces that contain the edge. Figure 25.8
shows the star of a red vertex in red tones and the star of a green edge in green
tones. The
link of a vertex
is the boundary of the star. Suppose
V
is a vertex in
a closed mesh. Each vertex in the link of
V
is separated from
V
by a single edge.
These vertices are therefore called the
1-ring
of
V
; those separated by a distance
of two edges are called the
2-ring
(see Figure 25.9). The vertices of the 1-ring
of an interior vertex can always be organized into a cycle; that follows from the
definition of a surface mesh. For the 2-ring, bad things can happen. For instance,
in a tetrahedron, the 2-ring of any vertex is empty; in an octahedron, the 2-ring of
any vertex is a single vertex. Figure 25.10 shows a mesh in which the 1-ring of a
vertex is nice, but the 2-ring forms a figure-eight shape.
Figure 25.9: The 1-ring of V is
drawn in large red dots; the 2-
ring in smaller green dots.
When we compute the boundary of a mesh, the boundary edges form chains;
each such chain is called a
boundary component,
and the number of boundary
components is often denoted by the letter
b
.
If a mesh surface
M
has
v
vertices,
e
edges, and
f
faces, the number
Figure 25.10: The star of the top
vertex is drawn in brown; the
1-ring, which forms an octagon
in the middle level, in red. The
2-ring, at the bottom drawn in
bright green, is connected into a
figure-eight shape.
=
v
−
e
+
f
is called the
Euler characteristic
of
M
, and it measures the “complexity”
of the surface: A spherical topology has characteristic 2; a torus has characteristic
0; a two-holed torus has characteristic
χ
−
2; and in general, an
n
-holed torus has
characteristic
2
n
.Ifthe
n
-holed torus also has
b
boundary components,
then the formula becomes
χ
=
2
−
χ
=
2
−
2
n
−
b
.
