Game Development Reference
In-Depth Information
mesh surface models. The objects represented using other models thus need to be con-
verted into objects represented by polygonal meshes. Broadly speaking, we will also
present some algorithms which can be used to construct surfaces from a scattered
plot of non-structured points. These algorithms are also useful when we digitalise real
objects.
14.4.1 Transformation of a volume into surface
When we are dealing with medical data like scanned sections, we first use segmen-
tation techniques to extract the useful outlines which characterise the volumes to be
reconstructed, and then the volume is created, i.e. a solid model, as described in
14.2, is constructed. It is necessary to convert this model into a triangle-based surface
model to view it in real time. The reference technique is the Marching Cubes algo-
rithm, designed by Lorensen and Cline (1987). Though not perfect, this algorithm
is nonetheless recognised worldwide. The following section presents this Marching
Cubes algorithm.
It involves dividing the space into a regular grid of cubes, determining the topology
of the surface inside the cube, constructing connected triangles and then moving on to
the next cube. A cube is constructed using four points of a section and four points of
an adjacent section. Then, values are assigned to the vertices of the cube. Each vertex
gets 1 if the value of the section at this point is more than the threshold, else 0. Each
cube thus gets 8 numbers equal to 0 or 1, which gives 2 8
=
256 possible cases. Using
all the symmetries between the cube and the problem to our advantage, we can restrict
the study to 14 cases, of which two are described in figure 14.12. We can construct 0 to
4 triangles per cube by using a straight-line interpolation to determine the intersection
points of the intended surface and the edges of the cube. Though the algorithm was
improved a number of times, the basic principle remains the same. The limitations of
Marching Cubes have to do with the possibility of generating aberrant triangles.
Figure 14.13 shows a scanned section of a human jaw digitalised for the Visimplant
project. The scanned sections are segmented to separate the different materials present.
The entire set of scanned sections is used to reconstruct a three-dimensional model of
the jaw using the Marching Cubes algorithm modified to avoid generating aberrant
triangles. Figure 14.14 shows a view of this reconstruction (Dutreuil, 2001).
Figure 14.12 Example of the construction of triangles by assigning values to the vertices of cubes (the
vertices with value 1 are shown with a black point)