Graphics Reference
In-Depth Information
construction of
sphere trees
[Hub95] relatively easy. This line of work goes back
to Badler [BOT79].
One final class of objects deserves mention in the context of level of detail:
parametric curves and surfaces. In these cases, the coordinate functions
t
→
(
x
(
t
)
,
y
(
t
)
,
z
(
t
))
or
(
u
,
v
)
(
x
(
u
,
v
)
,
y
(
u
,
v
)
,
z
(
u
,
v
))
are real-valued functions, typ-
ically defined on an interval or rectangle. As such, they're amenable to Fourier
analysis (representation as sums of sines and cosines), and hence to filtering. In
specific cases (like B-splines), there are other approaches to simplification, such
as replacing a B-spline by its control-point polygon. And in other cases, bases
other than the Fourier basis may be appropriate: Finkelstein et al. [CK96] rep-
resented level of detail in a B-spline wavelet basis, which allows for both sim-
plification (by eliminating detail beyond a certain scale) and multiscale editing
(see Figure 25.19); there are similar approaches for wavelet representations of
surfaces [ZSS97] to allow multiscale editing and simplification.
→
Figure 25.19: A curve, rep-
resented in a wavelet basis,
consists of large- and small-scale
features. The small-scale
features—the “character” of the
curve—can be edited without
affecting the large-scale shape,
and
vice
versa.
(Courtesy
of
Adam
Finkelstein
and
David
H.
Salesin,
©1994
ACM,
Inc.
Reprinted by permission.)
From these generalities, we'll now move on to a specific algorithm for mesh
simplification, Hoppe's
progressive meshes.
The goal of progressive meshes is
to start from a mesh
M
n
of
n
nodes, and simplify it to a mesh of
n
u
v
1 nodes by
collapsing one edge (thus merging two adjacent nodes), as shown in Figure 25.20.
The resultant mesh is denoted
M
n
−
1
. Successive collapses of edges lead to a
sequence of meshes with fewer and fewer nodes, ending at
M
1
, which consists of
a single node. This provides a “continuous” level-of-detail representation for the
mesh. Furthermore, the change from
M
n
to
M
n
−
1
can be interpolated, in the sense
that if we define
M
t
to be a mesh with the topology of
M
n
, but with geometry
modified so that the position
u
t
of
u
is
u
t
=(
1
−
w
t
)
u
+
tw
, and similarly for
v
,
then
M
1
consists of exactly the same set of points as
M
n
−
1
; to convert one to the
other requires deleting two area-zero triangles, and renaming some vertices and
edges. This interpolation (see Figure 25.21) is called a
geomorph
(for “geometry
morph”).
−
Figure 25.20: The edge from u to
v has been collapsed to a single
new vertex, which is labeled w.
The two triangles that meet this
edge have disappeared, and the
four non-uv edges have collapsed
into two edges. The set of trian-
gles shown is called the
neighbor-
hood
of the edge.
To complete the description of the algorithm, we need to know
1. How to choose a location for the new vertex
w
2. How to choose, at each stage, which edge to collapse
For item 2 in the preceding list, Hoppe associates a cost (described below) to
each possible edge collapse, and chooses the one with least cost (i.e., he pursues
a greedy algorithm).
For item 1 in the list, Hoppe considers three possible locations for
w
:
u
,
v
, and
1
2
(
u
+
v
)
. Each choice results in a different edge-collapse cost, and he chooses the
one with the least cost.
25.4.1.1 Edge-Collapse Costs
To describe the cost of an edge collapse, we first need to describe how to measure
how well a given mesh
M
fits a set of data
X
=
R
3
:
i
=
1, 2,
.We'll
use a bunch of points from the original mesh
M
n
as the set
X
, but for now, you
can imagine that
M
n
is a nice enough mesh that we can just use its collection of
vertices as
X
. For the rest of this discussion, we'll treat the set
X
as fixed, and not
mention it explicitly.
{
x
i
∈
...
,
N
}
