Game Development Reference
In-Depth Information
Once this error is defined, how would you define a precision that is sufficient for
a given application?
Lastly, the current meshes created by 3D digitizer systems are really huge (the
Digital Michelangelo project obtains models with several thousand million poly-
gons (Levoy et al., 2000)) and cannot even be loaded in the memory of a single
holder. Structuring the meshes and random access to their elements is thus one of
the new elements of research in the field of decimation.
A large variety of mesh decimation techniques, not just from the field of computer
graphics, is available in the literature. Thus, the finite element techniques which involve
meshing the surface or the volume of an object also use decimation.
Historically, we can differentiate between two types of approaches: Those who are
a sub-unit of an existing mesh and those who recreate a newmesh. Schröder's approach
(Schröder et al., 1992) appears to be the simplest approach. It includes selecting one of
the vertices of the mesh, removing it and then re-triangulating the surface around this
vertex. On the other hand, Turk (1992) prefers generating new vertices in the regions
of the surface; here the number of vertices generated depends on the local curvature of
the surface. The new points are re-triangulated. This method guarantees that triangles
with good properties are generated, but does not guarantee a good approximation of
the initial mesh.
14.4.3.1 Incremental algorithms
The incremental algorithm of Schröder (Schröder et al., 1992) is parameterised with
an error limit
which does not give a maximum, but a minimum! The general pattern
of the algorithm is as follows:
Repeat
find a region whose error is less than
a
remove the triangles from the region
re-triangulate the region
Until no acceptable region is found
Unfortunately, this method does not provide a limit on the distance between the
initial mesh and the final mesh. Besides, the transformations applied to solve a global
problem are local. There are extensions to this algorithm, which consider this prob-
lem: It involves using queue mechanisms to establish a hierarchy of transformations as
per their use. There too, no global minimisation property is provided for. The question
of the choice of triangles to be eliminated remains unresolved. Schröder differentiates
between various types of triangles, as shown in figure 14.15. He applies conditions
on the connectivity of vertices and edges. The triangles considered by his algorithm
are the first two in the figure, the other two are not considered to be acceptable.
The algorithms of decimation, just like Schröder's algorithm, very rarely process the
non-acceptable triangles.
14.4.3.2 Operators
In the previous section we saw that triangles from the selected regions are removed.
Algorithms are often limited to a small number of operators, if possible reversal (this