Contents |
|
The HOM Algorithm
The hierarchical occlusion map (HOM) algorithmis another way of enabling hierarchical image-space culling (such as the hierarchical Z-buffering algorithm). However, the HOM algorithm can be used on systems that have graphics hardware but not a hardware Z-pyramid, and it can also handle dynamic scenes. The HOM algorithm is described in detail in Zhang's Ph.D. thesis.
We start by describing how the function isOccluded works. This function, used in the pseudocode in Figure 2, is a key part of the algorithm. This occlusion test takes place after the view transform, so the viewer is located at the origin looking down the negative z-axis, with the x-axis going to the right, and the y-axis going upwards. The test is then divided into two parts: a one-dimensional depth test in the z-direction and a two-dimensional overlap test in the xy plane, i.e., whereby the image gets projected. The overlap test supports approximate visibility culling, where objects that "shine through" small holes in the occluders can be culled away using an opacity threshold parameter.
For both tests, a set of potentially good occluders is identified before the scene is rendered, and the occlusion representation is built from these. This step is followed by the rendering of the scene, where the occluders are rendered without an occlusion test. Then the rest of the scene is processed by having each object tested against the occlusion representation. If the object occluded by the occluder representation, it is not rendered.
For the
two-dimensional overlap test, the occluders are first rendered into the
color buffer with a white color on a black background. Therefore,
texturing, lighting, and Z-buffering can be turned off. An advantage of
this operation is that a number of small occluders can be combined into a
large occluder. The
rendered image, which is called an occlusion
map, is read back into the main memory of the computer. For
simplicity, we assume that this image has the resolution of 2^n
x 2^n pixels. It is used as the base for the occlusion
representation. Then a hierarchy of occlusion maps (HOM), i.e., an
image pyramid of occlusion maps, is created by averaging over 2^n-1
x 2^n-1 pixel blocks to form an image of 2^n-1 x
2^n-1 pixels. This is done recursively until a minimum size is
reached (for example 4x4 pixels). The highest-resolution level of the HOM
is numbered 0, with increasing numbers having decreasing resolution. The
gray-scale values in the HOM are said to be the opacity of the
pixels. A high opacity value (near white) for a pixel at a level above 0
means that most of the pixels it represents are covered by the
HOM.
The creation of the HOM can be implemented either on the CPU or by texture mapping, with bilinear interpolation used as a minification filter. For large image sizes, the texture filtering approach was found to be faster, and for small image sizes, the CPU was faster. Of course, this varies with CPUs and graphics hardware. For a 1024x1024 image, Zhang et al.used a 256x256 image as the base for the HOM. An example of a HOM is shown in Figure 7.
![]() |
Figure 7. On the left is an image of 956x956 pixels. Since this covers many pixels on the screen and is rather close to the viewer, it is a good candidate for an occluder. Its HOM is created by rendering this object in white against a black background in 256x256 pixels, an image which is called occlusion map 0. This image is subsampled into 128x128 pixels by averaging over 2x2 pixels. This is done recursively down to 8 x 8 pixels. (Model is reused courtesy of Nya Perspektiv Design AB.) |
The overlap test against the HOM starts by projecting the bounding volume of the object to be tested onto the screen (Zhang et al.used oriented bounding boxes). This projection is then bounded by a rectangle, which then covers more pixels than the object enclosed in the bounding volume. So this test is a conservative test, meaning that even if the test results show that the object is not occluded, it may still be so. This rectangle is then compared against the HOM for overlap. The overlap test starts at the level in which the size of the pixel in the HOM is approximately the size of the rectangle. If all pixels in the rectangle are opaque (which means fully white for non-approximate culling), then the rectangle is occluded in the xy plane and the object is said to pass the test. On the other hand, if a pixel is not opaque, then the test for that pixel continues recursively to the subpixels in the HOM which are covered by the rectangle, meaning that the resolution of the occlusion maps increases with each test.
For approximate visibility culling, the pixels in the HOM are not compared to full opacity, i.e., white, but rather against an opacity threshold value, a gray-scale value. The lower the threshold value, the more approximate the culling. The advantage here is that if a pixel is not fully opaque (white) but still higher than the threshold, then the overlap test can terminate earlier. The penalty is that some object may be omitted from rendering even though it is (partially) visible. The opacity values are not constant from one level to another in the HOM, as shown in the following example.
Example: Computation of opacity threshold values
Assume the rendered image is 1024x1024 pixels and that the lowest level in the HOM (i.e., the one with the largest resolution) has a resolution of 128x128 pixels. A pixel in this level-zero occlusion map corresponds to an 8x8-pixel region in the rendered image. Also assume that a 2x2 region of black pixels in an 8x8 region can pass as a negligible hole. This would give an opacity value O=1-2^2/8^8=0.9375. The next level in the HOM would then have a 64x64 resolution, and a pixel at this level would correspond to 16x16 pixels in the rendered image. So the opacity threshold at this level would be O=1-2^2/16^2 which is approximately 0.984.
We will now derive a recursive formula for computing the opacity values of the different levels in the HOM. The opacity of the level with the highest resolution in the HOM is O0=1-n/m, where n is equal to the number of black pixels that can be considered a negligible hole, and m is the number of pixels in the rendered image represented by one pixel in this occlusion map (m=8x8 in the example above). The next level in the HOM has a threshold of O1=1-n/(4m)=1-(1-O0)/4=(3+O0)/4. This reasoning can be generalized to the formula in below for the kth level in the HOM.
Ok+1=(3+Ok)/4
For more details on this topic, consult Zhang's Ph.D. thesis.
For the one-dimensional z-depth test, we must be able to determine whether an object is behind the selected occluders. Zhangdescribes a number of methods, and we choose to describe the depth estimation buffer, which provides reasonable estimation and does not require a Z-buffer. It is implemented as a software Z-buffer that divides the screen into a number of rectangular regions that are rather large in relation to the pixel size. The selected occluders are inserted into this buffer. For each region the farthest z-value is stored. This is in contrast to a normal Z-buffer, which stores the nearest z-value at each pixel. An estimation is used to obtain a far value for an occluder quickly. The z-value of the farthest vertex of the bounding box is used to estimate the farthest z-value of an occluder. An example of a depth estimation buffer is shown in Figure 8.
![]() |
Figure 8.
Illustration of the depth estimation buffer. Illustration after
Zhang. |
The depth estimation buffer is built for each frame. During rendering, to test whether an object passes the depth test (i.e., whether it is behind the occluders) the z-value of the nearest vertex of its bounding box is computed. This value is compared against the z-values of all regions in the depth estimation buffer that the bounding box rectangle covers in screen space. If the near value of the bounding box is larger than the stored z-depth in all regions, then the object passes the depth test, and is thus occluded in the depth direction. A resolution of 64x64 regions in the depth estimation buffer was used by Zhang et al..
For an object to be occluded, it must thus first pass the overlap test; i.e., the rectangle of the projected bounding volume of the object must pass the HOM test. Then it must pass the depth test, i.e., it must be behind the occluders. If an object passes both tests, the object is occluded and is not rendered.
Before the algorithm starts, an occluder database is built, where a few criteria are used to exclude certain objects. First, small objects do not work well in the occluder database, since they usually cover a small portion of the image unless the viewer is very close to them. Second, objects with a high polygon count are also avoided, as these may negatively affect the performance of the rendering of the occlusion map. Third, objects with large or ill-shaped bounding boxes (e.g., a bounding box for a skinny polygon) should be avoided, as they may cause the depth estimation buffer to be too conservative. Finally, redundant objects are avoided: for example, a clock on a wall does not contribute as much to occlusion as the wall itself.
At runtime, occluders are selected from the database. To avoid allowing the creation of the HOM to become a bottleneck, there is a limit to the number of occluders that can be selected. These are selected with respect to their distance from the viewer and to their size. Only objects inside the view frustum are selected. A case when this does not work well is shown in Figure 9.
![]() |
Figure 9. Scenario
where the occluder selection for the HOM algorithm may be
unsuccessful. The algorithm may select the dark gray objects as
occluders, but when the light gray objects (which also are good
occluders) are considered, the occluder count budget may have
already been reached. |
The number of occluders can vary during runtime using an adaptive scheme. If the portion of the scene that is culled away is low, then this number may be increased. On the other hand, if a high portion is culled away but the frame rate is low, then this number may be decreased. Another technique that can be used here is to render simplified versions of the occluders. This works well as long as the occluders cover approximately the same pixels as they did before.
For extremely dense scenes, i.e., those with high depth complexity, the HOM algorithm was able to cull away between about 50% and 95% of the scene, with a speed-up of up to six times in some cases.