Reducing Unnecessary Rendering Through Culling

Generally speaking, culling is a process through which a subset of a larger whole is selected and set aside for some purpose. This general definition applies to 3D graphics as well because many rendering algorithms attempt to extract only those polygons that are visible in a particular view. As an organism living in a 3D world, you are culling all the time. It is often helpful to consider what your brain and body do in real space to reduce the inordinate complexities of the world when considering what the computer can do as well. However, you must consider that the computer uses loops to accomplish what nature does by design.

View Frustum Culling

Because humans have eyes in the front of their heads, they don't see the majority of the visual field at all times. For many predatory animals, this is an evolutionary result of the need to focus high-resolution visual resources on objects in front of the organism. This constitutes a natural version of one of the most basic forms of 3D culling, view frustum culling. As an aside, we note that many animals have almost total surround vision and therefore perform very little of this natural view frustum culling.

The frustum (a pyramid with its top cut off) defines the shape of the viewing volume (that area of space within the user's view). The basic mantra of view frustum culling is don't render anything that lies completely outside the user's field of view. An example of basic view frustum culling is shown in Figure 10.9. In this example, objects A, B, C, and G are eliminated from further rendering of the view because they are outside the view frustum.

One efficient way to perform view frustum culling is to create a hierarchical map of the space that can be used to guide the frustum culling in an efficient manner. One popular form of the spatial hierarchy mapping is the binary space partition tree (BSP). The general approach is as follows: 1) divide the space into arbitrary halves; 2) if the subdivided half of space has an object in it, continue dividing and testing for the presence of an object in the new space; otherwise stop processing this subspace and move onto another. (Figure 10.10 in the section “Particle Systems” shows a progression through a series of space partitions.)

Occlusion Culling

After the simple view frustum culling has been performed, we can still reduce the problem of what to render in a number of different ways. One additional form of culling operations that can be done is occlusion culling. Returning to Figure 10.9, you can see that object F is occluded by objects D and E. Therefore, in this particular view, it doesn't need to be rendered. Indeed, because we are creating and viewing a model in 3D space, there will always be parts of the model that are (or rather should be) obscured by other parts of the model. When multiple objects exist in the space, they too should obscure each other, depending on the viewing direction. Occlusion culling belongs to the general class of methods known as hidden surface removal (HSR) algorithms. Hidden surface removal is also commonly called visible-surface determination.

Two fundamental approaches to HSR, called image- and object-precision methods, derive their names from the inherent precision with which they can be calculated. The easiest and most commonly used of these two general classes of algorithm is image-precision, therefore we begin with it.

Image-Precision

The most obvious and generally preferable algorithm simply loops over the 2D rendering pixel by pixel and determines which object is closest to the viewer for every pixel. This type of algorithm is often referred to as image-precision because its precision is determined by the output image (rendering) that is to be produced. The time to calculate HSR on a single rendering of 10 objects and a resolution of 800x600 would require 10x800x600=4,800,000 comparisons. This is indeed a great number of comparisons, but each comparison can be handled pretty efficiently. It should also be noted that the image-precision algorithm can be tuned to process only pixels in a given subrectangle of the image and thus can be optimized for schemes that only process of subset of the pixels.

The most conceptually straightforward image-precision method to understand is the z-buffer algorithm. The z-buffer basically creates a series of frame buffers to hold depth layers of the scene. By laying down the layers in the proper order, an algorithm can eliminate the rendering and processing of any pixels that will be covered by a subsequent layer.

Object-Precision Methods

The second approach would be considered a more object-centered approach (sometimes called an object-precision algorithm). The idea behind this class of algorithms is to remain inside the 3D space and compare individual objects with themselves and other objects in the view volume. These comparisons can be more expensive than the image-precision methods and scale with the number of objects squared.

Inside- and Back-face Culling

The first step in both of the preceding algorithms is usually to remove the inside faces (faces that are on the inside of a solid surface model) and the backfaces (surfaces that are pointing away from the viewer). Generally speaking, these operations are best performed early in the rendering pipeline and usually make a substantial reduction in the dimensionality of the rendering problem.

Execution Culling

Another relevant form of culling is execution culling. In many applications, a great deal of the CPU overhead is in calculating events in the background. For example, in an environment with a lot of behaviors, it would be useful to create a scheduling tree that is activated only when the view is in certain spatially restricted areas. Consider a game in which a lot of computational resources are spent computing the trajectories of objects and appearances of objects, and so on. When these computations have no impact on the user and can be removed from the execution schedule, the CPU can be freed to compute what is relevant to the user's view. Of course, in multiplayer games, this becomes a far more complicated issue.

The general approach of an execution culler is to make a series of Boolean operations on a collection of bounding regions that are arranged into a scheduling tree (another hierarchical structure this time for organizing event contingencies). By keeping the scheduling regions a reasonable size, we are able to reduce the number of executions the renderer must make. You will see in Chapter 12 that Java 3D's Behavior objects usually have a wakeup criterion that must be met before the object performs its behavior. The scheduler won't activate the Behavior until something (e.g. the viewing volume) intersection with the object banding volume.

Spatially Organizing the SceneGraph

From the previous discussion on culling, you can see the benefit and necessity of creating a spatially organized scene graph. If the scene graph is organized intelligently, large branches of the tree can be collapsed and removed from the list of jobs to do in creating a rendering. This can greatly increase the efficiency of scene graph traversal.