Hierarchical Occlusion Maps
You have seen how both BSP and portal implementations try to compute indoors environments by means of quickly computing the occlusion portion. Clipping and culling are usually added to the mix easily, but it's the occlusion part that causes most trouble. Let's now review another approach. Like portal rendering, this technique is designed to compute occlusions at runtime. The main advantage of this new technique, called hierarchical occlusions maps (HOM), is that no preprocessing is actually needed. Occlusions can be computed from geometry that comes directly from your modeling package of choice. Another advantage is that HOM can handle static and dynamic geometry seamlessly, making it a bit more powerful (but also more complex) than portal rendering.
HOM was introduced in 1998 by Zhang. It is based on a hierarchy of occlusion maps, each one half the size of the previous one. We start with a full-resolution black-and-white rendering of our scene and compute a series of mipmaps, blending every 2x2 pixel into one. Obviously, this makes the algorithm easier to code if you start with a power-of-two sized image. This series of bitmaps is the hierarchical occlusion map. The occlusion map does not represent the whole scene, only a set of good occluders chosen with a method similar to the one explained in the first section of this chapter: large, close objects that are aligned to the screen.
Then, at runtime, we paint object-by-object, probably assisted by some hierarchical representation such as an octree or quadtree. For each object or node, we need to compute the screen-aligned bounding rectangle. This rectangle will enclose the whole object and be used in the occlusion processing part. Then, we select the HOM level in which the pixel size is approximately the size of the rectangle. If the HOM pixels are all white, there's a full overlap, so the object is either in front of the occluders or behind them. If the HOM is pure black, the object must be painted because no occlusion took place. If the HOM is gray, it means the current resolution cannot determine clearly whether we are occluded or not, so we will need to examine higher-resolution HOMs to discover whether we are in a white area after all.
For those objects in white zones, we need to test for Z-values and thus discover whether they are in front or behind the occluders. This is achieved with a depth estimation buffer (DEB), which is just a software Z-buffer constructed from the occluders. The DEB takes the bounding box of each occluder and stores in the pixels covered by it the farthest Z-value. Notice that we use farthest, not closest as in a regular Z-buffer. Because the DEB has a lower resolution than a regular Z-buffer, each pixel must provide a conservative estimation of the Z-value for all objects contained within its boundaries. Selecting the farthest Z-value performs that task.
The overall algorithm for the HOM is as follows. During preprocessing, preselect a good database of occluders. Objects smaller than a certain threshold, narrow, or with high polygon counts are discarded. Redundant objects are rejected as well. Any decoration on top of a wall should be discarded, and so on. In the end, the best occluders are probably room walls and large pillars. An alternative is to not use real scene geometry, but instead use placeholder objects that are manually located to act as good occluders.
Then, at runtime, we select the N closest occluders from the database. Remember that occluders need to be visible, so performing a clipping test as well will be worthwhile. We then build the HOM based on these objects. The high-resolution version is created with render-to-texture capabilities. To create the low-resolution copies, we can compute them on software, or even better, using lower resolution textures and bilinear minification filters. As we traverse our scene graph, we test visible nodes against the HOM. If they lie in a black zone, we need to paint them. If they are in a white zone, we perform the Z-test with the DEB and decide whether we should discard them or not based on the results. Objects in gray areas require further refining in the HOM before moving on to the DEB phase. In the end, a well-built HOM can cull away between 40 and 60 percent of all incoming geometry.