Misplaced Pages

This is an old revision of this page, as edited by 213.164.254.213 (talk) at 16:44, 25 February 2004. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Hidden Face Removal is used in 3D computer graphics for drawing a 3D scene correctly. It is also implemented to save time, because if a face cannot be seen, that means it should not be drawn in the scene, and therefore you don't have to waste CPU cycles drawing it. This article deals with several methods of hidden face removal.

Backface Culling

In Backface Culling we want to remove or "cull" the backfaces from an object we are drawing. A backface is essentially what it sounds like; the back of something. But of what? Well, that would be the backface of what are usually referred to as polygons or facets. 3D objects are made up of polygons or facets, which are made up of vertecies. One property of polygons is that they generally have a particular direction they are facing. The direction a polygon is facing is determined by its normal vector. The normal is a vector which is perpendicular to the polygon which can also be said to be a plane (as defined in mathematics.) The normal sticks out of the front of the polygon, and so, in backface culling, we only want to draw polygons that are facing us. You may be asking yourself, "Why would we want to do that?" Well, first of all, as with most hidden face removal techniques, it saves time. For example, with a cube, we can only see a maximum of three faces at any one time. Considering there are six faces in a cube, drawing only those three can save at least 50% of the work from the rest of your renderer. Also, this makes objects appear to be more solid. With a wireframe model, you can see right through it to the other side. But, if you look at your monitor, you can't see the back of it, right? That's the principle backface culling works on.

View Frustum Culling

With View Frustum Culling we set up a sort of sideways pyramid, representing the viewer's field of vision. Any polygons falling totally outside of it, are ignored in rendering. A polygon partially inside it is clipped to the view, so we only draw the parts that are actually being seen. Finally, a polygon totally inside is drawn normally. The obvious way to accomplish this, is to check every polygon with the view frustum. Well, that may work when there are only a few objects, but if you're viewing a complex scene, with numerous objects and things to be rendered, it takes up more CPU cycles than it really needs to, because there is a faster way. We can speed this process up by dividing the scene up into octrees, which is a cube split along each axis, x, y, and z. For the areas of the scene that have more objects in them, we can continue to divide each octree into smaller ones, for more precision, while fairly empty areas can make do with one big box. The reason for all these boxes, and boxes of boxes is that we can test the boxes themselves against the view frustum. But we only check the parent boxes at first (the parent boxes being the big ones that were divided.) If a parent box is totally outside the view frustum, we don't need to check any of the smaller boxes inside it, because logically, they aren't in the view frustum either. However, if a parent box IS in the view frustum, in part or in whole, we can then check which of the child boxes are inside the view frustum. Then, we only render polygons that are inside boxes in the view frustum.

Occlusion Culling

Occlusion Culling checks which objects are in front of others and draws them in the correct order. An object which is in front of another, and therefore blocking part or all of it from sight is said to "occlude" that object. BSP (Binary Space Partition) trees (used in Doom) are an example of occlusion culling. There are several forms of occlusion culling, but the one I know best is Z-Buffering. In the Z-Buffer, the z values for each pixel are stored. When plotting a pixel in a polygon filler, for example, we check to see if the value for that pixel is closer to the camera than the pixel we are plotting. A good way to find this out is through linear interpolation. If the current value is closer to the camera, then we don't plot the pixel we wanted, but otherwise, pixel plotting goes ahead as normal. This is one of the most accurate ways to properly order your drawing, so things appear in the right order, but also very time consuming. Not only do we have to run a check for any pixel we want to plot, but after we're done, we have to reset the buffer, so we can perform the check again. There are however optimizations for this method, to cut down some of the time, but seeing as I'm still learning this method, I can't tell you how things like "1/z" work exactly. A primitive metod is to get the overall depth of the polygons (by average of the defining points), sort them, then drawing in the reverse order (deeper first, closer last).

Contribution Culling

Basically Contribution Culling checks projection values and if they are too small, or off-screen, you don't draw the polygon/primitive.