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

Search Nedrilad ::

Custom Search