Features

Rendering the Great Outdoors:
Fast Occlusion Culling for Outdoor Environments

The View Frustum

A viewing frustum is a 3D volume. For practical reasons, we can treat it as a convex hull, simplifying further computa-tions. The viewing frustum is typically a cut pyramid (if a pro-jection transformation is used) or a cube (if an orthogonal transformation is used). This article assumes that projection transformation is used, and many times the camera’s position will form one of the points of the frustum’s hull.

Making Sense of Occluders

Occluders in the real world may be thought of as objects which occlude (or obstruct) your view of other objects behind them (Figure 3). Take an example of an occluder — a building, a hill, or a car — all these things occlude your view to objects physically located behind them. Transparent or translu-cent objects are not good view occluders, because as light rays pass through the material, so we’ll ignore transparent objects as occluders in 3D rendering.

	Figure 3: An example of occlusion in the real world. The house occludes the view onto the tree; the shaded area represents the volume that the viewer cannot see.

Objects in the real world consist of atoms and molecules, and pretty much every atom can either be occluded by another atom or not (in which case a viewer can see it). In computer graphics, however, objects are built from vertices and polygons, and these vertices and polygons are usually grouped into primi-tives, which are rendered together in order to achieve good graphics throughput. Our task consists of rejecting as many of these primitives as possible in the early (preprocessing) phase of our pipeline, without affecting the viewer’s experience by reject-ing objects that should be rendered.

In practice, this means finding which objects are fully occlud-ed by other objects and rejecting these occluded objects from any further processing. A solid object, sufficiently big to be worth the additional computations associated with occlusion testing, is an ideal occluder.

In an ideal 3D engine, we could detect occlusion of even the smallest primitive behind any object in a scene. In reality, however, we must find some algorithm that allows fast detec-tion of occlusion for a sufficient number of potentially visible primitives. For that reason, we’ll simplify the occlusion vol-umes to convex hulls.

Convex hulls allow for sufficient approximation of a 3D object in most cases. When it is not possible to represent the shape of an object with a convex hull, you can use more hulls to accomplish the task. The occlusion hull doesn’t need to copy the exact shape of visual object it works with. In many cases, an occluder may consist of many fewer faces than the visual primitive itself, roughly copying the shape of the visual (Figures 4 and 5). The rule to keep in mind here is that an occluder’s shape shouldn’t be bigger than the shape of visuals it represents; otherwise your engine will end up rejecting primitives that should be rendered, resulting in an ugly graph-ical artifact.

	Figure 4: A house, suitable for occluding other objects in 3D scene. Figure 5: The occluder object (drawn in green wire-frame), representing the simplified shape of the house.

The Occluder ’s Place in the Pipeline

In determining HSR, occluders should be processed first. Because the position of a camera (viewer) changes constantly in 3D games, so does the occlusion frustum, the 3D volume cast by the occluder. Our task is to compute the occlusion volume at the beginning of rendering from a particular camera view. (If you render multiple views in a single frame, a mirror for example, this step must be done for each rendered view.) After this prepro-cessing step, you should collect all occluders on the screen, against which you’ll test other potentially visible primitives. Some optimization tips: Minimize the number of occluders you include in the test list, done by determining if a particular occluder is occluded by another occluder. Figure 6 shows this possibility. Also, don’t consider occluders that may potentially hide only a small amount of primitives. You should reject occluders that occupy a small area of screen space.

	Figure 6: Image showing an occluder hidden by another occluder. Any visual occluded by the occluder B is also occluded by occluder A, so we include only occluder A in our list of occluders we test against.

Once we have a list of on-screen occluders, we can move on to the next preprocessing step: traversing the scene hierarchy tree and using the list of occluders to check if a particular object is visible.

Building Occlusion Volumes

Let’s have a closer look at the information needed in order to detect whether an object is occluded. Looking closer at the occlusion volume, we see that occlusion volume is actually another kind of convex hull, expanded from the viewpoint into infinity. The occlusion volume is built from all of the occluder’s polygons facing the camera, and from contour edges (as seen from the camera) expanded away from the camera (Figure 7).

	Figure 6: An Oocclusion frustum built from an occluder, using current viewer position.

Actually, this volume is open — there’s no back plane that would cap the volume — because the occluder hides everything behind it into infinity. And any plane we save will speed up fur-ther computations.

To build contours from a convex hull, we use a simple algo-rithm utilizing the fact that each edge in a convex hull connects exactly two faces. The algorithm is this:

1. Iterate through all polygons, and detect whether a polygon faces the viewer. (To detect whether a polygon faces the viewer, use the dot product of the polygon’s normal and direction to any of the polygon’s vertices. When this is less than 0, the polygon faces the viewer.)
2. If the polygon faces viewer, do the following for all its edges: If the edge is already in the edge list, remove the edge from the list. Otherwise, add the edge into the list.

After this, we should have collected all the edges forming the occluder’s contour, as seen from the viewer’s position. Once you’ve got it, it’s time to build the occlusion frustum itself, as shown in Figure 7 (note that this figure shows a 2D view of the situation). The frustum is a set of planes defining a volume being occluded. The property of this occlusion volume is that any point lying behind all planes of this volume is inside of the volume, and thus is occluded. So in order to define an occlusion volume, we just need a set of planes forming the occlusion volume.

Looking closer, we can see that the frustum is made of all of the occluder’s polygons facing the viewer, and from new planes made of edges and the viewer’s position. So we will do the following:

1. Add planes of all facing polygons of the occluder.
2. Construct planes from two points of each edge and the view-er’s position.

If you’ve gotten this far and it’s all working for you, there’s one useful optimization to implement at this point. It lies in minimizing the number of facing planes (which will speed up intersection detection). You may achieve this by collapsing all the facing planes into a single plane, with a normal made of the weighted sum of all the facing planes. Each participating normal is weighted by the area of its polygon. Finally, the length of the computed normal is made unit-length. The d part of this plane is computed using the farthest contour point. Occlusion testing will work well without this optimization, but implementing it will speed up further computations without loss of accuracy.

______________________________________________________

Detecting Occlusion

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy | terms of service