Introduction and Problem Definition

Our goal in backface culling is to quickly determine which polygons face away from the viewer and remove them from the rendering pipeline. If the objects in the model are closed and opaque, removing the backfacing polygons will not affect the visibility solution. To be more specific, we wish to quickly determine if a face is front-facing or back-facing (visible or invisible) by checking the angle between the polygon's normal and the viewing direction (from the eye to some point on the polygon). If this angle is less than 90 degrees then the polygon is visible; if greater than 90 then it is invisible (the edge-on case of 0 degrees can go either way; so we will consider it backfacing). This method culls the polygons in object space without requiring any modeling or viewing matrix transformations. However, in practice most methods, including hardware implementations, perform this test in viewing or eye coordinate space after a viewing transformation is applied. This approach has the advantage that it only requires a sign test; if the Z component of the polygon's normal is negative (in a right-handed coordinate system), then it is backfacing. Do you see why? We believe that the transformation step is too expensive for such a potentially trivial operation; however, current object-space methods would require at least a dot-product between the viewing direction and the polygon's normal (even more calculations required for the perspective case because the viewing direction does not remain fixed per polygon).

Our Solution : a much faster alternative

In this paper we propose a method that will completely avoid the per polygon test entirely and cull groups of polygons with a single test. We do this by allowing ourselves to be a little "conservative", meaning that we may not find the all of the polygons that are backfacing, but we will definitely find all those that are front-facing. In other words, our determination of the front-facing polygons will be an overestimation so the resulting visibility will be correct after hidden-surface removal. This brings up an important distinction between conservative visibility testing and hidden-surface removal: visibility testing determines the parts of the scene that can potentially be seen in the final rendered image and hidden-surface removal is the exact determination of the visible portions in the final image. View-frustum, occlusion or shadow, and backface culling are all examples of the first, while Z-buffering and the Painter's algorithm are examples of the latter. In fact, we can easily send the remaining polygons to the existing backface culling system with a greatly reduced workload after our conservative visibility test! This can be accomplished simply by reorganizing the list of polygons in a static "walkthru" scene in such a way as to facilitate a very fast culling system.

Often the rendering order of the polygons is not important, so we can group the polygons into partitions of the subdivided space of possible normal directions. For example, we partition the space of normal directions into many tiny frusta emanating from a central point through the uniformly subdivided grid cells on the sides of a surrounding cube (similar to the hemicube approach of calculating form factors in a radiosity solution). Now if we classify each polygon by its normal into one of these "normal clusters" as a preprocessing step, for each new view we need only find the front-facing clusters and render the polygons classified with them directly without any per polygon testing; in fact, the back-facing polygons are never even visited!

Problems: putting it into perspective

At a first glance this test may seem only slightly conservative dependent only on the granularity of the normal-space subdivision scheme, but actually the problem is slightly more complicated. In the case of an orthographic or parallel projection, the previous assumption holds very well since a single viewing direction regardless of the position of the polygons is sufficient in accurately backface testing, but in the perspective case we must allow ourselves to be even more conservative in order to correctly determine front-facing polygons regardless of their position in viewer's field-of-view (FOV). As Hansong Zhang (from the University of North Carolina at Chapel Hill) points out, in the parallel projection we can always cull the backfacing 180 degrees way since there is only one viewing direction, however, for the perspective case we must think of this projection as a union of parallel projections at arbitary orientations distributed about field-of-view (or FOV/2 around the central viewing direction). Zhang shows that the amount we can cull is a function of the size of the field-of-view and that we can only cull 180-FOV degrees away (vs. the full 180 in the parallel case). This means that for a 60 degree FOV, we can only cull two-thirds of the maximum range of polygon normals!

Nevertheless, we can easily reduce this by grouping the objects into bounding volumes that have a much lower field-of-view than the entire field-of-view. Each group can be culled using the same method, with the penalty of having to perform the cluster front-facing tests for each bounding-volume.

In more detail: a possible implementation

Each cube frusta-shaped cell will have an associated ID numbered linearly from 0 to n-1. As a preprocessing step, we can classify each polygon's normal in object space into one of the frusta cells; so each polygon will have an integer ID associated with it that represents the frusta its normal belongs to. Now, during runtime, for each new viewing direction we must determine the set of cells that are "front-facing" and draw only those polygons whose normal IDs belong in this set. This is still rather slow because it involves searching for polygons associated with a particular frustum cell ID. To do this efficiently, we can sort the polygon list by their IDs; this will result in a list of polygons that are grouped into frustum cells. In addition, we can create another array with an element for every frustum shaped cell that contains a pointer to the first polygon in an ID group and the number of polygons in the group. It shouldn't be necessary to store anything for the actual cube partitioning except for the number of grid cells on each side. All of these structures are created and initialized in preprocessing. Given this framework, for each viewing direction, we need only find the front-facing cells and directly render the polygons in the corresponding array entry. This doesn't require ANY run-time operations for backface culling except the search for front-facing cells. Let's look at the process in more detail:

• Given a set of polygons: 
  A,B,C,D,E

• We can create a list of polygons with an integer ID:
  Polygons: [A ID]--[B ID]--[C ID]--[D ID]--[E ID]

• Now we can classify each polygon by its normal into one of the cube frustum cells (the ID represents which cell):
  Polygons: [A 1]--[B 2]--[C 0]--[D 2]--[E 1]

• Now we sort the polygon list by IDs:
  Polygons: [C 0]--[A 1]--[E 1]--[B 2]--[D 2]

• We'll partition the space of normal directions into only six frusta (corresponding to the six faces of the cube - one grid cell per side). So, we must create the associated array (one element for each frustum); each element holds a ptr to the first polygon associated with it and the number of polygons in the group:
  Polygons: [C 0]--[A 1]--[E 1]--[B 2]--[D 2]
  FrustaGroups: [&C 1]--[&A 2]--[&B 2]--[NULL 0]--[NULL 0]--[NULL 0]

• Now for the current viewing direction we'll find all of the front-facing cells and render the corresponding polygons in the FrustaGroups array. So for example, if frustum #1 is determined to be front-facing, we would directly render polygons A and E (from FrustaGroups[1] starting at polygon A with 2 polygons in the group).

Of course, this method is still conservative and we must still find the front-facing cells. The main advantages of this method are that we do not have to traverse all of the polygons, there are no backfacing tests, and groups of polygons can be culled away together.