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