Graphics Reference
In-Depth Information
Exercise 8.2:
Implement a form of the 1D mesh structure that's suitable for
implementing a
subdivision
operation on
manifold
meshes. Given such a mesh,
M
,
the associated subdivision mesh
M
has one vertex for each vertex
v
of
M
:Ifthe
neighbors of
v
are
u
and
w
, the new vertex is at location
2
u
+
2
w
+(
1
)
v
.
M
also has one vertex for each
edge
of
M
: If the edge is between vertices
t
and
u
, the associated vertex of
M
is at
− α
1
2
(
t
+
u
)
. Vertices in
M
are connected by an
edge if their associated vertices and/or edges in
M
meet (i.e., the vertex associated
to the edge from
u
to
v
is connected to the vertex associated to
u
and to the vertex
associated to
v
). Figure 8.5 shows an example. The parameter
determines the
nature of the subdivision. The example shown in the figure uses
α
=
0. 5; on
repeated subdivision, the square becomes a smoother and smoother curve. What
happens for other values of
α
? Use the standard 2D test bed to make a program
with which you can experiment. Note: Not every manifold mesh has just a single
connected component.
Exercise 8.3:
Draw examples to show how adding a triangle to a mesh can
cause each of the four changes described in the nonmanifold vertex representation.
Exercise 8.4:
Write pseudocode explaining how, given a vertex reference in a
directed-edge data structure, to determine the list of all directed edges leaving that
vertex in time proportional to the output size.
Exercise 8.5:
Explain, in pseudocode, how, given a reference to a face in the
winged-edge data structure, one can find all the edges of the face.
Exercise 8.6:
Suppose that
M
is a connected manifold mesh with no boundary.
M
may be
orientable
without being
oriented:
It's possible that there's a consistent
orientation of the faces of
M
, but that some faces are oriented inconsistently.
(a) Assuming that
M
is connected, describe an algorithm, based on depth-first
search, for determining whether
M
is orientable.
(b) If
Mis
orientable, explain why there are, at most, two possible orientations.
Hint: Your algorithm may show why, once a single triangle orientation is chosen,
all other triangle orientations are determined.
(c) If
M
is orientable, explain why there are exactly two orientations of
M
.
(d) Now suppose that
M
is not connected, but has
k
α
≥
2 components. How many
orientations of
M
are there?
Exercise 8.7:
The 2D test bed was designed to aid in the study of things like
meshes. Use it to build a program for drawing polylines in a 2D plane, getting
mouse clicks, and reporting the closest vertex to a click (perhaps by changing the
color of the vertex).
Exercise 8.8:
Add a feature so that a shift-click on a vertex initializes edge
drawing: The starting vertex is highlighted, and the next vertex clicked is con-
nected to the starting vertex with an edge; if there's already an edge between the
two, it should be deleted. And if the next click is
not
on a vertex, a vertex is created
there and an edge from the preselected vertex to the new one is added. Modify the
program to handle 2D meshes (i.e., vertices and
triangles
) by allowing the user to
control-click on three vertices to create a triangle (or delete it if it already exists).
