Game Development Reference

In-Depth Information

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

Polygonal Map).

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

Search Nedrilad ::

Custom Search