Graphics Reference
In-Depth Information
a menagerie of wild meshes, like the non-locally-flat example of Figure 25.14, and
the highly wrinkled example of Figure 34.11, and a mesh built from an array of
pieces shaped like Figure 25.32, where no two adjacent normal vectors are similar,
and see whether the claims hold up. Another good test case is two large spheres
that have been joined by removing a small triangle from each and either gluing the
edges together directly, or splicing in a small triangular-prism-shaped “corridor”
between them. (The boundary of the 2-ring of a vertex of that prism may well not
be connected, for instance!)
C
A
D
B
I
1.0
G
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
E
2
1
F
H
0.0
0
5
1
4
3
2
1
0
Figure 25.32: An eight-triangle
building block.
Exercise 25.1:
Our algorithm for computing the boundary of a triangle mesh
involved iterating through all the faces, and it runs in
O
(
f
)
time. Describe a con-
nected triangle mesh with
O
(
f
)
boundary edges, thus showing that the
O
(
f
)
run-
time is as good as possible.
Exercise 25.2:
If we have a one-dimensional
path mesh
(i.e., each vertex has
one or two edges meeting it), we can place it in the plane by assigning random
locations to the vertices. In general, the result will not be an embedding: Edges
will tend to cross one another. In 3-space, however, there's plenty of room, and
with high probability the use of randomly assigned locations will result in an
embedded path mesh. In this exercise, you'll show that for any surface mesh,
there's an embedding in
some
Euclidean space. The idea is simple: For an
n
-vertex
mesh, we'll place the mesh in
R
n
by placing vertex 1 at location
(
1, 0,
...
)
,vertex
2 at location
(
0, 1,
)
, etc. We then place edges and faces in the obvious way,
using linear interpolation.
(a) Explain why the embeddings of triangles
(
i
,
j
,
k
)
and
(
i
,
j
,
k
)
do not intersect
unless the sets
S
1
=
...
i
,
j
,
k
}
{
i
,
j
,
k
}
and
S
2
=
{
have nonempty intersection.
(b) Show that if
S
1
∩
S
2
contains a single index
p
, then the associated embedded
triangles intersect only at vertex
p
.
(c) Show that if
S
1
∩
, then the associated embedded triangles intersect
in the embedded edge associated to
S
2
=
{
p
,
q
}
.
Exercise 25.3:
Consider the mesh shown in Figure 25.32. By replicating it to
the left and right, and then replicating the resultant strip in the front and back
directions, we get a mesh in which no more than two adjacent triangles have
remotely similar normal vectors. Show that such a mesh is likely to be a worst-
case challenge to the polygon ordering algorithm of Nehab et al., as described in
Section 25.6.2.
Exercise 25.4:
(a) We sketched an algorithm for computing the boundary of
a surface mesh by hashing edges. Adapt this to detect all
contours
of a mesh,
where a contour edge is one where the normals to the two adjacent faces have dot
products, with a view vector
v
, of opposite signs, and the contour is the set of all
contour edges.
(b) Contour edges can be generally formed into loops, although as we said, two
loops may share one or more vertices. Design an
O
(
E
)
algorithm for assembling
the
E
contour edges into loops. Hint: Use hashing again.
Exercise 25.5:
The paper by Nealen et al. [NISA06] suggests using the mean
curvature to compute weights. Make an argument for using the absolute value of
the mean curvature instead. Can you think of any argument against this, or any
rationale for why it might be an unimportant improvement, even if it works?
{
p
,
q
}
