JavaScript EditorFree JavaScript Editor     Ajax Editor 

Main Page
  Previous Section Next Section

Occluder-Based Algorithms

Occlusion testing is not an easy task. Generally speaking, it is a O(number of triangles^2) problem, because we need to test each triangle in the view frustum against each other to see whether they are occluding themselves. Clearly, some clever approaches are required to compute this at interactive frame rates. The first approach we will explore works by reducing the number of potential occluders to a small set of very promising candidates. Because closer triangles will statistically cover more area on the screen than distant ones, we only need to test for occlusions between very close geometry (which we will call occluders) and distant objects (occluded objects). This can decrease our initial cost to almost O (number of triangles). If you couple this with the fact that we know an upper bound to the view distance, we can further decrease the cost by assuming any triangle located away from this bound is effectively occluded, without really testing it. Here you can see the pseudocode of this raw occlusion algorithm:

from the current viewpoint
select a set of potential occluders (close, large triangles)
for each triangle in the scene
   if it is closer than the viewing distance
      test for occlusion with any of the occluders
      if passes the test -> paint it
      end if
   end if
end for

This algorithm can also take advantage of the clipping and culling steps. Obviously, an occluder must be visible and thus not be clipped away, and must not be culled. Back-facing triangles will never cover geometry, because they are not even painted.

The implementation details for such an algorithm are relatively straightforward. For each frame, perform software clipping and culling. Then, sort the remaining triangles by Z distance and take the first N entries of the list. Because the sorting process is relatively expensive, we can just perform it every few frames. If you think about it, the results will not change if the viewer did not move between two successive frames. Thus, we store the player's position and orientation, and only recompute the solution if the change in position or orientation exceeds a fixed threshold. This philosophy, called frame-coherence, can yield significant improvements, especially in costly routines. The overall structure of a frame-coherent loop would be

if  orientation or position changed more than X
   recompute solution
   store new position
   store new orientation
end if

Then, in the painting phase, we take triangles and test for inclusion inside the pyramid formed by the viewpoint and the occluder. The problem with such an approach is that a per triangle test is costly, and thus we will probably end up with a CPU-bound application. The CPU is the bottleneck here, sorting and testing for inclusion. Better methods need to be employed: methods in which we do not need to perform the full occlusion detection test at runtime, because part of the solution is precomputed beforehand. These are the methods used in most commercial games.

      Previous Section Next Section

    JavaScript EditorAjax Editor     JavaScript Editor