# Spatial Subdivision

As already mentioned in Chap. 8, if a virtual landscape with many plants must be rendered, several assumptions can be made concerning the data, which assist in finding an efficient rendering method. Usually the plants are arranged on the plane, which allows for the application of space partition methods. This is further simplified by the fact that the plants are local objects, meaning that the plant geometry is not distributed over large parts of the scene. in this way, the scene can be efficiently subdivided into a number of smaller regions.

For the production of such a spatial structure, the space is divided into com­pact regions, which each include about the same amount of geometric data. in Fig. 9.9 three methods are shown. Subimage (a) shows a quad tree, which di­vides the scene recursively into four subscenes. The partitioning is continued until the number of geometric objects in a subscene decreases below a given threshold or until the cell has reached a minimal size. The resulting data struc­ture is a tree whose nodes describe the cells. The children of a node are the subcells into which the respective region was divided. Accordingly, each of the inner nodes has four children, and the data structure is called a quad tree.

Figure 9.9b shows a BSP tree (BSP = binary space partition), in which the space is alternately divided in the x – and у-directions. Positioning and orien­tation of the dividing plane in this case can be performed with a higher degree of freedom. Thus, the division can at each time be fitted in such a way that in both subspaces the same number of objects are present. A similar method was used for the quantization of vectors in Fig. 8.8.

Figure 9.9

Data structure for space partitioning: (a) quad tree; (b) BSP tree; (c) grid structure

in Fig. 9.9c a simple grid partition can be seen, in which the space is divided into many cells of equal size. in contrast to the quad tree and to the BSP tree, which are dynamic data structures, and which can adjust to varying object den­sities, the grid is a flat structure that allows for a significant faster access. A grid division is always then of advantage when the density of the geometric data is more or less uniform. Fortunately, this is the case in many natural scenes with dense vegetation cover.

Several rendering algorithms such as raytracing can be performed more effi­ciently with such a space partition data structures. As an example, the calcula­tion of the first object of the scene hit by a tracing ray can be restricted to those objects whose cells were hit by the ray, instead of having to include all objects. This allows for a drastic reduction of the computing effort. However, even the

processing of a single object can be time consuming; hence a combination with so-called bounding boxes is useful in such approaches.

Updated: October 5, 2015 — 4:57 pm