Game Development Reference

In-Depth Information

Figure 14.5
Regular mesh of a rabbit in 2D

•

CSG:
The CSG (Constructive Solid Geometry) is a binary tree of construction

where the leaves are geometric primitives and the nodes are Boolean operators.

14.2.1 Spatial enumeration

Here we are trying to construct a partition of the space. To simplify, we use orthogonal

division axes as the overall reference axes. Each cell is thus located with respect to the

object to be represented: if it is filled, we say that it is inside the object and if it is empty

it is outside the object. If it is partially filled, a belongingness testing function will be

provided. Figure 14.5 shows a rough mesh of a rabbit in 2D. The second image shows

that it is impossible to visually recognise a rabbit from such a large mesh. Then arises

the problem of sufficient precision of the mesh. The concept of regular mesh is easily

accepted in 3D.

The choice of mesh is very important since it is directly related to the concision of

the representation. When we work in a 3D space with a uniform mesh, the number of

cells increases with the cube of the level of subdivision. When the volume contained

in a cube with a 10 cm side is divided with a precision score of 1mm, we obtain

1 million elementary cells. This technique is widely used in medical imaging where the

image scanners have a resolution of 256

×

×

512

pixels). Each scanner section alone uses more than 65000 cells. This number is further

multiplied by the number of layers. Worse still, irrespective of the level of subdivision

of space, we can never give an exact representation of a simple oblique line (and even

more so in case of a circle or a sphere).

Then logically we think of using an adaptive mesh i.e. a rough mesh on large

volumes of the inner parts of the object and a finer mesh towards its boundaries. Using

an adaptive mesh will not increase the field of modellable objects accurately, but will

allow giving a more compact representation. We thus construct a tree representation

of an object as per a descending algorithm: if a cell is uniform, an end leaf is created;

otherwise, 2
d
(where
d
is the dimension of the space considered,
quadtrees
in 2D and

octrees
in 3D) daughter cells evenly partitioning the mother cell are created and the

algorithm is applied to each of these cells (Jackins & Tanimoto, 1980). Of course, a

256 pixels (or nowadays even 512

Search Nedrilad ::

Custom Search