Game Development Reference

In-Depth Information

written by Leif Kobbelt et al. (2000). Before reconstructing a surface, we must ask

ourselves a few questions as the result depends on the quality of sampling. Certain

methods would not work if the sampling is not sufficiently dense. If it is not suffi-

ciently precise, the reconstruction will be of poor quality, whereas if it is too precise,

the volume of data to be generated will be too large and it will be necessary to use

decimation techniques. It is equally important to analyse the properties of the surface

we want to reconstruct: are we trying to maintain the topological characteristics of the

structure? And lastly, the type of surface also has its importance: we will concentrate

here on polygonal meshing, but there are other methods too. Polygonal meshing main-

tains the topological properties but does not give a smooth appearance. Here we will

describe four types of methods in brief. The last type of problem will not be covered

here since it is a full-fledged field of research which clearly exceeds the scope of this

book: generally, laser scanners are used several times on the environment or the object

to be modelled. This way we obtain several 3D scatter plots; adjusting these plots with

an absolute reference can generate defects. Without covering the actual problem of

adjusting, the algorithms of surface construction must take into account the errors in

adjusting the scatter plots.

14.4.2.1 Methods of spatial subdivision

The principle of these methods involves partitioning the bounding box of
P
into a

set of disjoint cells (regular grids, octrees, tetrahedrons). The second step consists of

selecting the cells that the surfaces cut through, then calculating a surface from the

selected cells.

The simplest method requires dividing the bounding box of
P
into voxels (elements

of a regular 3D grid). Then the voxels containing at least one point of
P
are determined.

The surface is then constructed using the quadrilaterals external to the selected voxels.

We can then divide the quadrilaterals into two triangles and use different methods of

smoothing to obtain better visual appearance. If required, we can deform the surface

obtained to take it closer to the points of
P
. We can also use the Marching Cubes

algorithm explained in 14.4.1.

Edelsbrunner and Mücke suggest using
α
-shapes. We start by constructing a

Delaunay tetrahedralization (Boissonnat & Yvinec, 1995) of
P
, then the tetrahedrons,

triangles and edges are
erased
using
α
-balls: All tetrahedrons, triangles or edges whose

minimum bounding sphere is not in the erasing ball of radius
α
are erased. The result

is called an
α
-shape. The third step consists of extracting the triangles by using the

following rules: we consider the two spheres of radius
α
passing through the three

points of a triangle. If at least one of the two spheres does not contain any other point

of
P
, the triangle belongs to the surface. The main problem of this method is in the

selection of
α
. It is a global parameter, if
α
is too small, then it can create holes in the

surface and disconnect certain elements.

We can also use a volume-oriented division of the space into cells, where we

eliminate the cells that do not belong to the volume demarcated by the surface. These

methods are essentially based on Delaunay tetrahedralization. Boissonnat suggests

eliminating certain tetrahedrons (he begins with those with 2 faces, 5 edges and 4

points). This approach cannot be used to reconstruct surfaces with holes. Isselhard sug-

gests modifying the procedure of erasing the tetrahedrons, which allows the elimination

Search Nedrilad ::

Custom Search