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