Scene Culling

I can't speculate why, but on the way to a party yesterday NDM called me (I was puppy sitting, no party for me) and asked me about how video games render their images and we started talking about occlusion. As with any software junk, it was a little challenging to talk about with someone who has occasionally described my work as computer plumbing. This is a slightly more thoughtful but still math-free explication for her...one which will probably keep her from ever asking me about video game graphics again :-)

Rendering all of the terrain and objects in a 3D scene can be a very resource-intensive task. It is very helpful to be able to ignore anything that won't impact your final rendering. For example, if a person in the scene is standing behind a building from our point of view, we won't have to bother figuring out how to draw the person. There are a small number of basic techniques that we can use to throw out information to make everything simpler when we finally have to draw.

The Frustum Cull

One thing we can do is throw away anything that is not in our current field of view. Our field of view is generally described by a frustum, which is a section cut out of a pyramid by parallel front and back planes. If an object in our three dimensional world falls outside the area of our frustum, we can ignore it when we draw our scene. This is also called clipping.

We can also make our drawing task easier by moving the back plane closer to our point of view, reducing the volume we have to be concerned with. That back plane is why in many video games you can suddenly see objects pop into existence at a certain distance (and there are several techniques, including simple level design tricks, that are used to prevent you from noticing that distracting pop).

The Insignificance Cull

If there is an object inside our frustum that would be drawn so small that it would have little impact on our final image, we can safely ignore it. This is often called contribution culling.

The Back-Face Cull

This elegant method of ignoring objects is performed automatically by modern rendering technologies. If all of the objects in our scene are closed volumes described by a set of adjoining polygons (as above), then we know that any polygon which doesn't face our point of view can't be seen. Back-face culling takes the point of view vector and each polygon's normal vector, and if the angle between those two vectors is over ninety degrees it ignores the polygon.

You can see the effects of this sort of culling in video games when the point of view is somehow forced inside a supposedly solid object; in many games this is easy to accomplish by entering confined spaces using third-person camera. When inside an object the back-face cull doesn't work any more, and you can see the undefined interior of the polygons making up the object your point of view has entered.

The Mighty Occlusion Cull

This is where we figure out that we don't have to draw the person standing behind the opaque building. Occlusion culling is a meaty topic in the realm of simplifying our drawing, and is always about partitioning our frustum into areas (called cells) which are only viewable through a certain number of two dimensional portals. If we can figure out that all of a cell's portals are occluded, we can safely ignore everything in that cell. There are many subtly different ways of doing that, but the principle is always the same. With the occlusion cull, it is nice to rely on predetermined computations done for your environment's known geometry to speed things up.

You can apply several different occlusion culling passes before rendering your scene. Perhaps the first is based on precomputing what rooms of the house are visible from the room your point of view is located in -- in this case each room is a cell and the doors and between them are portals. After we've done that, we might start partitioning our visible areas into smaller and smaller portions and checking for occlusion among the objects they contain. This final step is called potentially visible set rendering.

Punting

After we've done all the culling we care to do on our scene, there is a final rendering trick to make sure things look OK even if we've screwed up and are trying to draw an object which is partly hidden by something else. We know the three dimensional coordinates of the anchor of every object we're drawing, so we can determine each object's distance from our point of view. By drawing the most distant objects first, the nearer objects will be drawn over them. Since this drawing doesn't happen in human-noticeable time (in fact, the whole scene is "drawn" to computer memory first and only when complete is it sent to the display), everything still looks great to the viewer.

Despite this trick, when doing real-time rendering you really want your culling to be as comprehensive as possible. That is because when we think we can see one of the polygons describing an object's surface, we still have a lot of work to do for drawing it -- figuring out how to color and pattern the surface, applying different optical effects for special surfaces, etc.

Now, as computers (and especially their video cards) get more and more powerful, one of two things happen. We can get lazier with all of our culling, because our video card is able to render more objects in the same amount of time; who cares if we render some stuff that doesn't end up visible. Alternately, we can keep making our frustum larger and larger; video game frustums do tend to have disturbingly close horizons when you are out of doors. We've seen a bit of both over the last decade of video card performance increases.