Last Updated November 20, 2013
Simple Z-Buffer Hidden surface removal is unsuitable for processing complex scenes. We need a system to quickly remove objects and polygons from processing if the are not visible in the current frame. We do not want to have to clip every single polygon in a scene comprising millions of faces.
Z-Buffer Deficiencies
We will create a structure to organise the elements of a scene in such a way to allow efficient visibility processing. Most scenes are characterized by having relatively few objects, but the objects are composed of many polygons. To be efficient these structures will subdivide the scene down to individual polygons.
Efficient Visibility processing has two main goals
Note: Testing if an object lies inside or outside a view frustum is a form of collision detection, and the techniques discussed here can be adapted to collision detection.
The structures created to perform visibility processing are generally divided into two types;
These structures are normally very expensive to generate, so are usually pre-computed in a once-off operation.
Spatial Subdivision involves dividing space into a number of regions and labeling these regions with object occupancy. The success of such schemes depends on how finely we divide space.
A simple spatial subdivision is into regular voxels. (A voxel is the 3D equivalent of a pixel). Space can be divided in to a regular grid of cubes. Each cube can be labeled as empty or occupied by objects.
A visibility algorithm could determine which voxels lie inside the view frustum and then process objects belonging to those voxels.
A voxel based system has a major drawbacks;
Most scenes consist largely of empty space (consider a room or a landscape). Typically most (>90%) of the voxels will be empty. There exist more advanced schemes which take a more efficient approach to structuring space (Octrees & BSP).
In order to efficiently apply frustum culling and occlusion culling to a terrain patch, the rectangular patch is recursively subdivided into smaller and smaller rectangles. The amount of subdivision is controlled to achieve a balance wherein the granularity is small enough for the culling algorithms to be effective, but not so small that the number of rectangles becomes unmanageably large.
To organize the pieces of the terrain patch, a quadtree is used. This is simply a tree in which each node has four children. The root node of the quadtree contains the entire terrain patch. Successively lower levels of the quadtree contain smaller portions of the terrain patch. The leaves of the tree then contain the individual rectangles produced by the last level of subdivision.
Organizing terrain into a quadtree is useful because it allows efficient application of frustum and occlusion culling. To apply frustum culling to a quadtree, for example, one first tests the root node against the viewing frustum. If the root node is completely within the frustum it can be accepted and drawn immediately; if it is completely outside the frustum, it is rejected. If the node is partially inside and partially outside the frustum, as is evidently the more common case, it is subdivided into its four children and the process is repeated with each. The following pseudocode illustrates this algorithm:
add root_node to queue;
while (queue is not empty) {
pop node off queue;
if (node is completely inside frustum)
accept node;
else if (node is completely outside frustum)
reject node;
else // Node must be partially inside, partially outside
for each child of node
add child to queue;
}
Octrees subdivide space in a hierarchical manner. The approach proceeds as follows;
Note that the interior of an object is considered empty space. Only surfaces count as 'objects'
The generated set of cubes can be efficiently stored in a tree whose node have at most 8 branches (hence the name OCTree).
There will be two types of terminal nodes in the tree, some nodes correspond to regions of empty space, other nodes will be nodes of minimum size and contain part or all of an object.
This structure provides an representation of the entire scene and at high resolution will require an enormous amount of storage.
An alternative subdivision provides a representation of the distribution of objects in the scene. In this case we subdivide a region only if it contains more than one object.
Octrees (& BSP trees) take advantage of the concept of coherence. Coherence is a very important idea in computer graphics, simply states that an entity (location in space, pixel, point in a line, polygon, piece of carpet, person etc.) is likely to be very similar to its neighboring entities.
© Ken Power 2011