Game Development Reference
In-Depth Information
14.4.2.4 Surface expansion methods
Incremental construction of surface involves constructing surfaces on the basis of points
and their surface oriented properties. This can be done in several different ways.
We can start by connecting two points close to a place of P and add the triangles
whose vertices are close to the already connected points. This is what even Boissonnat
suggests: Start by connecting the two points closest to P . To connect a new triangle
to these points (and later to the edges of the boundary), we locally estimate a tangent
plane using the neighbouring elements. The points neighbouring the boundary are
projected on the tangent plane; the new triangle is obtained by connecting one of these
points to the boundary (the one that maximises the angle from where the two other
points of the triangle are seen).
Mencl & Müller (1998) suggest an approach that uses the recognition of
characteristics in the scatter plot. This technique can be divided into various steps:
Calculation of an EMST, i.e. a Euclidean minimum spanning tree, which will serve
as the basis of the surface description graph;
This graph is stretched to the leaves of the tree, by connecting each leave to its
closest neighbours;
Characteristic recognition: This involves integrating different recognition algo-
rithms in the main algorithm, maintaining the structural coherence of a surface
description graph. This helps adjusting to the differences in density of the scatter
plots, the different types of surfaces that come across, or even reconstructing a
Möbius strip.
14.4.3 Decimation of meshes
For using them in a virtual reality application, the polygonal meshes must have a
reasonable number of polygons. The models created by a mesh of a volume or a
scatter plot often have too many polygons. Simply put, to be seen in real time, the
meshes created by CAD software have a very high level of detail. We thus try to reduce
the number of triangles of a model. This technique is called decimation. Remember
that this technique can also be applied to generate the levels of detail (refer to 14.5.2,
page 362).
In general, we can say that decimation is the creation of a polygonal approximation
of a complex model with a precision sufficient for the application considered. This
creates some general problems:
What is the starting data? There are different approaches to create smaller size
meshes; some of them do not use a mesh, but propose decimation based directly on
scatter plots. For example, Hoppe et al. (1993) suggest minimising a cost function
on a mesh from a scatter plot. The initial mesh is used simply as a starting point
for the optimisation algorithm.
Which geometric properties of the models should be considered? Should one look
for precision of lighting, contact between the surfaces or rough appearance of a
surface?
The concept of approximation requires defining an approximation error;