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;

Search Nedrilad ::

Custom Search