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)

Search Nedrilad ::

Custom Search