Game Development Reference
Figure 14.6 Construction of a quadtree from a regular mesh of a two-dimensional space (in this
example, we have modelled the free space, i.e. the complement of the objects)
maximum limit is fixed on the subdivision so that the algorithm can end. Figure 14.6
shows an example of calculating a quadtree on the basis of an image (which itself is a
regular mesh of the space in two dimensions). The passage in a space of dimension 3
is equally obvious.
There are other more elaborate techniques of subdivision which do not divide
the cells as per the axes, but as per simple schemas; these techniques are useful to
accurately divide polyhedrons. We then talk about polytree or PM tree (PM means
The computer representation of an object's representation by enumeration is
simple: A regular grid can be represented by a three-dimensional table of Booleans.
The octree structures (generalisation of the quadtree in a three-dimensional space) are
octal tress that we construct recursively.
Using spatial enumeration structures (regular or adaptive) is very simple from
the point of view of an algorithm, the complexities are often very less and even the
geometric Boolean operators are easy to implement. The problems arise when the scale
is changed (when the scale factor is not a multiple of 2) or when there are rotations
(angles other than 90 degrees).
From the point of view of the properties mentioned in 14.1.2, we can state that:
the field of objects represented is very large if we do not fix a margin of error which
is strictly zero. On the other hand, the field of exact representation is particularly
limited. However, the precision of modelling is known in advance;
the model is suitable for simple algorithms;
uniqueness of models is not verified since the models are sensitive to the orientation
of the object;
On the whole, the models are easy to manipulate even though the rotations and
scale adjustments can create serious problems;
The structures of data are particularly heavy since the precision is a cube root of
the number of cells used. This complexity can be reduced by using tree structures
like octrees .
As we mentioned earlier, the meshes are widely used not only in the medical field
(MRI, scanner), but also in geophysics (for example, the French Institute of Petroleum
uses them to show the cubes of seismic data). Figure 14.7 shows a reconstruction of