Graphics Reference
In-Depth Information
barycentric coordinates in that triangle and use these to place it in the mesh
M
,
treating the vertex
v
s
as the location for both
v
s
and
v
t
in
M
.
We can now outline almost the entire progressive meshes algorithm (see
Listing 25.2).
Listing 25.2: The core of Hoppe's progressive meshes algorithm.
Input: a mesh
M
=
M
n
with
n
vertices, and a set of points
X
distributed on
M
.
Output: A sequence of meshes
M
n
,
M
n
−
1
,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
...
,
M
0
, where
M
k
has
k
vertices, approximating the
original mesh
M
.
E
←∞
for each edge
e
of
M
:
compute the cost of optimal collapse of edge
insert (edge, cost) into a priority queue,
Q
for
k
=
n
downto
1
:
extract the lowest-cost edge
e
from
Q
collapse
e
in
M
k
to get
M
k
−
1
for each edge
e
that meets
e
:
compute a new optimal collapse of
e
and its cost
update the priority of
e
in
Q
to the new cost
. Hoppe defines the ratio
r
of
the number of points in the neighborhood of the edge to the number of faces in
the neighborhood, and then sets
One final detail remains: the spring constant,
κ
=
10
−
2
if
r
=
10
−
4
if 4
κ
<
4,
κ
≤
r
<
8, and
=
10
−
8
if
r
κ
8.
The algorithm, as described so far, shows how to simplify a mesh while con-
sidering its geometric structure. But meshes often have other attributes, specified
on a per-vertex level, such as color, material, etc. Some of these attributes, like
color, lie in continuous spaces, where it makes sense to measure differences and to
compute averages. Others, like material, can be considered to be more discrete—
you're either on the metal part of the engagement ring or on the diamond; there's
no halfway point between these materials. The first group consists of the
scalar
attributes and the second group consists of the
discrete attributes.
To assign a scalar attribute to a vertex that results from an edge collapse, we
try to pick a value with the property that for each point
x
i
∈
≥
X
on the original
surface, with corresponding point
b
i
on the simplified mesh, the scalar value
s
(
x
i
)
and the corresponding value
s
(
b
i
)
(which may have to be interpolated from values
at nearby vertices) are as close as possible. More explicitly, we choose a scalar
value at the new vertex to minimize
E
scalar
(
V
)=
2
.
i
s
(
x
i
)
−
s
(
b
i
)
(25.8)
Even scalar attributes can require special handling: Consider a cube in which
each face is given a different color. At each vertex, there are three color attributes,
one for each face corner at the vertex, instead of just one; a complete implemen-
tation of the algorithm must address this “distinguished-corner” situation as well.
For discrete attributes like material, Hoppe characterizes an edge as
sharp
if
it's a boundary edge, its two adjacent edges have different discrete attributes, or its
adjacent corners have different scalar attributes, in the sense of the preceding para-
graph. The set of sharp edges on the mesh form “discontinuity” curves between
regions of constant discrete attributes (or between faces that meet with distin-
guished corners). Hoppe then either disallows or penalizes the collapse of any
