Gamasutra - Features - "Fast Occlusion Culling for Outdoor Environments" [07.17.02]


				\|\|\|\|

By Michal Bacik
Gamasutra
[Author's Bio]
July 17, 2002

Moving Games Outdoors

Node Volumes

The View Frustum

Detecting Occlusion

	Printer Friendly Version

Game Developer Magazine Back Issues four CD Set.
Every issue 1994 to April 2002.
Price: $189.00 + S&H

This feature originally appeared in the April 2002 issue of Game Developer magazine

Letters to the Editor:

Write a letter

View all letters

Features

Rendering the Great Outdoors:
Fast Occlusion Culling for Outdoor Environments

Detecting Occlusion

To detect if an object is occluded, we will utilize the object’s bounding volume. To find out if the object is inside of the occlusion frustum, we’ll make a simple test to check if its bounding sphere is inside of the frustum. Figure 8 shows possi-ble situations that may arise. Here we see that only sphere C passed the test and is fully occluded. Listing 3 shows the func-tion that may be used for such a computation. This process detects whether a bounding sphere is occluded. It’s fast, but not as accurate as detection using bounding boxes. With this technique, some objects may be detected as visible after the bounding sphere test succeeds, but their bounding box is still fully occluded, so we would end up rendering them even though they’re fully occluded. Figure 9 illustrates this possibility.



	Figure 8: Sphere A is outside of at least one plane. Sphere B is inside all planes, but its radius is greater than the distance from one of the planes. Sphere C is behind all planes and a sufficient distance from all planes. Figure 9. A case when the bounding sphere is not fully occluded but the bounding box is, thus the object should not be rendered.

Detecting if the bounding box is inside the occlusion frus-tum is another very simple task: detect if all eight corner points of the bounding box are inside of the frustum (Listing 2). Note that we use oriented bounding boxes in world coor-dinates, so we must transform local AABBs to world OBBs (as explained previously). If any vertex is outside of the volume, the box is not occluded. This test can take eight times more dot products than the sphere test, so it is less efficient. Ideally you would use it only when you detect that the center of the bounding sphere is inside the occlusion frustum but the sphere is still not occluded. This minimizes the chances of wasting time checking box-versus-frustum collision, at the same time getting more accurate occlusion tests, resulting in fewer objects being rendered.

bool AreAllVerticesInVF(const vector<S_plane> &planes, const S_vector *verts,int num_verts){ for(int i =0;i <num_verts;i++){ for(int j =planes.size();j —;){ float d =planes [j ].d +planes [j ].normal.Dot(verts [i ]); if(d >=0.0f) return false; } } return true; }	bool IsSphereInFrustum(const vector<S_plane>&planes, const S_vector &sphere_pos,float sphere_radius,bool &clip){ clip =false; for(int i =planes.size();i —;){ float d =planes [i ].normal.Dot(sphere_pos)+planes [i ].d; if(d >=sphere_radius) return false; if(d >=-sphere_radius) clip =true; } return true; }
Listing 2: Detects if a set of all points is inside of the viewing frustum. This is just a variation of Listing 1, checking multiple points instead of one.	Listing 3: Detects if a sphere is inside the frustum (convex hull). Notice that this function also computes clipping flag, which is set whenever a sphere collides with one hull’s plane (that is, it is neither fully inside nor fully outside of the volume).

Editing Support

Computing the occlusion volume and detecting whether an object is occluded is half of the work that needs to be done. Another task is finding a way to edit occluders comfort-ably in an evolving 3D scene during development. It may be done in several ways; I’ll discuss some of them here.

Editing occlusion volumes in a modeling package.This is a con-venient way of starting with occluders quickly and testing func-tionality. You may use 3DS Max, Maya, or whatever modeling program you prefer, to build an occluder skeleton from vertices and faces and import that into your engine.

Integrating an occluder editor into your game editor.This is a harder way to do it, but it’s preferable over editing in a model-ing package. The geometry inside occluders may change, and occluders must match geometry in order to be effective, so an “edit and see” approach is the best bet here.

Because an occluder is simply a convex hull, once you’ve implemented and tuned your convex hull code, you can call it with a set of points and you’ve got it.

Figures 10 shows occlusion techniques in a real game project, including numbers about rendered triangles. Note that the terrain is specially modeled so that occlusion is efficient; it con-tains high hills that are suitable for occluding objects behind them. But the areas of possibility for occluder utilization are much wider: cities with plenty of buildings, fences (solid, not transparent), and so on.



	Figure 1 The original in-game screenshot, the same screenshot in wireframe mode, with 7,000 triangles rendered at 50 fps, and with cclusion is switched off. The number of rendered triangles rose to 17,300, the frame rate dropped to 20 frames per second.

Finally, fine-tune editing support by visually displaying occluders in edit mode while designing your missions or modi-fying the occluder’s shape in the editor.

Take It Outside

This article provides some insight into rendering possibilities for outdoor scenes, and shows some new directions for optimizations. The model described here has worked — and continues to work — for games I have been working on (used with other HSR techniques, such as sectors and portals) and has undergone many changes to get to this point. As we contin-ue to improve our methods for rendering all kinds of environ-ments in games, soon there will be no boundaries as to what kinds of worlds we can provide players.

______________________________________________________

[Back To] Moving Games Outdoors