Game Engine Architecture

466 10. The Rendering Engine

objects explicitly is usually incredibly wasteful. Instead, we would like to de-

vise a data structure that manages all of the geometry in the scene and allows

us to quickly discard large swaths of the world that are nowhere near the cam-

era frustum prior to performing detailed frustum culling. Ideally, this data

structure should also help us to sort the geometry in the scene, either in front-

to-back order for the z prepass or in material order for full-color rendering.

Such a data structure is oft en called a scene graph , in reference to the graph-

like data structures oft en used by fi lm rendering engines and DCC tools like

Maya. However, a game’s scene graph needn’t be a graph, and in fact the data

structure of choice is usually some kind of tree. The basic idea behind most

of these data structures is to partition three-dimensional space in a way that

makes it easy to discard regions that do not intersect the frustum, without

having to frustum cull all of the individual objects within them. Examples

include quadtrees and octress, BSP trees, kd-trees, and spatial hashing tech-

niques.

Quadtrees and Octrees

A quadtree divides space into quadrants recursively. Each level of recursion

is represented by a node in the quadtree with four children, one for each

quadrant. The quadrants are typically separated by vertically oriented, ax-

is-aligned planes, so that the quadrants are square or rectangular. However,

some quadtrees subdivide space using arbitrarily-shaped regions.

Quadtrees can be used to store and organize virtually any kind of spa-

tially-distributed data. In the context of rendering engines, quadtrees are of-

ten used to store renderable primitives such as mesh instances, subregions of

terrain geometry, or individual triangles of a large static mesh, for the pur-

poses of effi cient frustum culling. The renderable primitives are stored at the

Figure 10.46. A top-down view of a space divided recursively into quadrants for storage in a

quadtree, based on the criterion of one point per region.