Contents

Occlusion Culling Techniques

Hierarchical Z-Buffering and the Hierarchical Visibility Algorithm

The HOM algorithm

VISUALIZE: fx's Hardware Implementation

VISUALIZE: fx's Hardware Implementation

Hewlett-Packard has implemented occlusion culling in the VISUALIZE fx graphics hardware. The algorithm works as follows. When an object is about to be rendered, each pixel covered by its bounding box is scan-converted and tested against the contents of the Z-buffer using special-purpose hardware. If all of these pixels are further away from the viewer than the contents already in the frame buffer, then the object is guaranteed to be obscured, and it is thus not necessary to process the model inside the bounding box. Otherwise, the model is processed and rendered into the frame buffer.

This means that if a complex object is obscured, then instead of drawing the whole object, only a bounding box (consisting of at most three quadrilaterals) is scan-converted (but not drawn into the frame buffer). In this case, we gain performance by avoiding sending the complex object through the rendering pipeline. Otherwise, the bounding box is scan-converted and the object is drawn, and we actually lose a bit of performance.

Note also, that as for most occlusion culling algorithms, the performance is dependent on the order in which objects are drawn. As an example, consider a car with a motor inside it. If the hood of the car is drawn first, then the motor will (probably) be culled away. On the other hand, if the motor is drawn first, then the hood of the car will not be culled. Therefore, performance can be improved by techniques such as rough front-to-back sorting of the objects by their approximate distance from the viewer and rendering in this order.

With such techniques, performance has been reported to be between 25% and 100% faster than rendering that does not use any occlusion culling .

Shadow Culling

Here we describe briefly the work by Coorg and Tellerand Hudson et al.. These algorithms are quite similar, and the main idea is to select a small set of large occluders and discard the objects behind the occluders, i.e., objects that are shadowed by an occluder with respect to a certain viewpoint. This is done with some geometric calculations. The basic tests are shown in Figure 10, where the objects are represented by bounding boxes.

Figure 10. The left figure shows how Coorg and Teller's algorithm detects whether an object (the box) is occluded by a large polygon. If the viewer is in the region marked "occluded," then the object is occluded. The right figure shows how Hudson et al. detect occlusion - objects fully in shadow are occluded.

Coorg and Tellermake use of separating planes and. A separating plane is formed by an edge of an occluder polygon and a vertex of the bounding box (BB), and in such a way that the objects are on different sides of the plane. A supporting plane is constructed in a similar way except that the occluder and the BB should be located on the same side of the plane. An object is occluded if the viewer is inside all of the supporting planes, which means that the object is in shadow with respect to the viewer and the occluder. Coorg and Teller also describe a way of using several polygons that share edges as an aggregate occluder, and also an efficient way of computing the separating/supporting planes using preprocessing and runtime table look-ups.

Hudson et al.use an algorithm that culls away AABBs or OBBs in much the same way as we have done for a view-frustum algorithm, but the frustum does not have a far plane and may have more than four side planes, i.e., more than a left, right, bottom, and top plane. The near plane is the plane in which the occluder lies.

To select a good occluder, Coorg and Telleruse the following metric, which estimates the solid angle that a polygon subtends:

g= -a dot(n, v)/dot(d, d)

Here, a is the area of the polygon, n is the normal of the polygon, v is the view direction vector, and d is the vector from the viewpoint to the center of the polygon. Both v and n are assumed to be normalized. The geometry involved is shown in Figure 11.

Figure 11: The geometry involved in
the estimation of the solid angle.

The solid angle is the two-dimensional angle concept extended to three dimensions . In two dimensions, an angle of 2*pi radians covers the whole unit circle. If we extend this to three dimensions, the solid angle would cover the whole area of the unit sphere (4*pi steradians). The higher the value of g, the better the occluder is to use. The solid angle approximation estimates the "usefulness" of an occluder because: a) the larger the area, the larger the value; b) the value is inversely proportional to the distance to the occluder; and c) the maximum value is reached when the viewer looks at a polygon "head-on," and the value decreases with an increasing angle between the polygon normal and the view direction.

Hudson et al. use the same formula but also test with random sampling to determine whether a selected occluder is good in practice. They do this by choosing a number of random viewpoints and counting the number of objects occluded by the selected occluder. They also exploit coherence in that they assume that an occluder that was good (or bad) for one frame is probably good (or bad) the next frame too. The algorithm stores the objects that were culled by an occluder for each frame. Hudson et al. found that using about eight occluders was reasonable for their algorithm.

Both of these algorithms use a hierarchical data structure to represent the scene. Coorg and Teller use a k-d tree, and Hudson et al. use a bounding volume hierarchy of AABBs. At runtime the algorithms first perform view-frustum culling, and then identify good occluders. After that, the remaining objects are culled against the occluders.

Coorg and Teller'spreprocessing phase used very few seconds, and the speed-up was approximately 2 to 5 times, depending on the architecture. Hudson et al.note a speed-up of 55%, on average. Remember, though, that these tests were done on different platforms and for different scenes.


References

Coorg, S., and S. Teller, "Temporally Coherent Conservative Visibility", appeared in the Twelfth Annual ACM Symposium on Computational Geometry, May 1996.

Coorg, S., and S. Teller, "Real-Time Occlusion Culling for Models with Large Occluders", in Proceedings 1997 Symposium on Interactive 3D Graphics, pp. 83-90, April 1997.

Cripe, Brian and Thomas Gaskins, "The DirectModel Toolkit: Meeting the 3D Graphics Needs of Technical Applications", Hewlett-Packard Journal, pp. 19-27, May 1998. http://www.hp.com/hpj/98may/ma98a3.htm

Durand, Frédo, George Drettakis, and Claude Puech, "The Visibility Skeleton: A Powerful and Efficient Multi-Purpose Global Visibility Tool", Computer Graphics (SIGGRAPH 97 Proceedings), pp. 89-100, August 1997. http://w3imagis.imag.fr/Membres/Fredo.Durand/PUBLI/siggraph97/index.htm

Durand, Frédo, George Drettakis, and Claude Puech, "The 3D Visibility Complex: a unified data - structure for global visibility of scenes of polygons and smooth objects", in Canadian Conference on Computational Geometry, pp. 153-158, August 1997.

Glassner, Andrew S., Principles of Digital Image Synthesis, vol. 2, Morgan Kaufmann Publishers Inc., San Francisco, 1995.

Greene, Ned, Michael Kass, and Gavin Miller, "Hierarchical Z-Buffer Visibility", Computer Graphics (SIGGRAPH 93 Proceedings), pp. 231-238, August 1993.

Greene, Ned, and Michael Kass, "Error-Bounded Antialiased Rendering of Complex Environments", Computer Graphics (SIGGRAPH 94 Proceedings), pp. 59-66, July 1994.

Greene, Ned, Hierarchical Rendering of Complex Environments, Ph.D. Thesis, University of California at Santa Cruz, Report No. UCSC-CRL-95-27, June 1995.

Greene, Ned, "Hierarchical Polygon Tiling with Coverage Masks", Computer Graphics (SIGGRAPH 96 Proceedings), pp. 65-74, August 1996.

Hudson, T., D. Manocha, J. Cohen, M. Lin, K. Hoff and H. Zhang, "Accelerated Occlusion Culling using Shadow Frusta", Thirteenth ACM Symposium on Computational Geometry, Nice, France, June 1997.

Samet, Hanan, Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS, Addison-Wesley, Reading, Massachusetts, 1989.

Samet, Hanan, The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, Massachusetts, 1989.

Scott, N., D. Olsen, and E. Gannett, "An Overview of the VISUALIZE fx Graphics Accelerator Hardware", Hewlett-Packard Journal, pp. 28-34, May 1998. http://www.hp.com/hpj/98may/ma98a4.htm

Zhang, H., D. Manocha, T. Hudson, and K.E. Hoff III, "Visibility Culling using Hierarchical Occlusion Maps", Computer Graphics (SIGGRAPH 97 Proceedings), pp. 77-88, August 1997. http://www.cs.unc.edu/~zhangh/hom.html

Zhang, Hansong, Effective Occlusion Culling for the Interactive Display of Arbitrary Models, Ph.D. Thesis, Department of Computer Science, University of North Carolina at Chapel Hill, July 1998.

Tomas Möller has a MSc in Computer Science and Computer Engineering (1995) from Lund Institute of Technology, Sweden, and a PhD in Computer Graphics (1998) from Chalmers University of Technology, Sweden. He has worked in the graphics industry for five years, and is currently a project scientist at the Department of Computer Engineering, Chalmers University of Technology. During 2000, he will be a visiting scholar at the graphics group at the University of California at Berkeley.

Eric Haines has a B.S. in Computer Science from RPI (1980) and an M.S. in the area of Computer Graphics from Cornell University (1985). He has worked in the field of computer graphics for 16 years. During this time he has developed rendering software for Autodesk, Hewlett-Packard, Spatial, and 3D/EYE. He has contributed to a number of books on rendering, has taught courses at SIGGRAPH, and is an editor for the "journal of graphics tools," among other activities.

[Back to] Occlusion Culling Techniques