Graphics Reference
In-Depth Information
with that individual cell. When increasing the size of the grid, more vertices are likely to fall
into each cell intersected by the surface; hence, the decimation ratio is increased. The accuracy
of the decimation is guaranteed to be less than the size of the cell. The mesh edges and triangles
that have more than one incident vertex falling into a cell become degenerate. Those elements
are removed, and the mesh representation is adjusted accordingly. The representative vertices
are possibly selected as the centers of the cells, means or medians of the vertices falling into
the cells. However, a more accurate result can be achieved when assigning the representative
vertices on the basis of the quadratic error metric (QEM). (Garland and Heckbert, 1997). The
QEM minimizes the squared distances from the optimal vertex to the planes
P
on which the
+
+
+
=
triangles incident to the vertex reside. Let the
i
th plane be
a
i
x
b
i
y
c
i
z
d
0, where
[
n
i
d
i
]
, and the vertex position
v
equals
[
v
1]
. The optimal vertex position
v
o
is shown as the following:
=
1 is represented by the vector
p
i
=
[
a
i
b
i
c
i
]
v
∀
v
)
p
i
(
p
i
v
o
=
arg min
v
(2.22)
p
i
∈
P
v
∀
p
i
∈
P
v
p
i
p
i
=
arg min
v
(2.23)
v
(
∀
p
i
p
i
)
v
=
arg min
v
(2.24)
p
i
∈
P
v
Qv
=
arg min
v
.
(2.25)
By taking partial derivatives of
v
Qv
with respect to the
x
-,
y
- and
z
-coordinates of
v
and
equating to zero, it can be shown (based on Equation 2.25) that the optimal vertex position is
shown as the following closed form solution, where
q
ij
is is the
ij
th element in
Q
.
⎡
⎤
⎡
⎤
−
1
q
11
q
12
q
13
q
14
q
21
q
22
q
23
q
24
q
31
q
32
q
33
q
34
0001
0
0
0
1
⎣
⎦
⎣
⎦
.
v
o
=
(2.26)
Vertex removal:
The algorithm by Schroeder et al. (1992) is the first and probably the most
well-known in this class of algorithms. In general, mesh decimation algorithms of this class
iteratively remove vertices on the basis of some metric criteria. The removal of a vertex results
in a surface hole, which is then filled by retriangulating the surface patch corresponding to the
hole. (This can easily be achieved by iteratively splitting the patch until all of the splits become
triangles.) The mesh is then updated accordingly. Schroeder et al. used the distance from a
candidate vertex to a local plane (computed by taking average of all the triangles incident to
vertex weighted by their areas) and the distance from the mesh edge (for near border vertices)
as the criteria for prioritizing vertex removal; vertices with the least distances are removed
first. Iterative decimation is terminated when a certain decimation ratio is achieved or a certain
decimation error is exceeded. This decimation algorithm is fast and can adapt (adjust) vertex
