“Visibility culling using hierarchical occlusion maps” by Zhang, Manocha, Hudson and Hoff

We present hierarchical occlusion maps (HOM) for visibility culling on complex models with high depth complexity. The culling algorithm uses an object space bounding volume hierarchy and a hierarchy of image space occlusion maps. Occlusion maps represent the aggregate of projections of the occluders onto the image plane. For each frame, the algorithm selects a small set of objects from the modelas occludersand renders them to form an initial occlusion map, from which a hierarchy of occlusion maps is built. The occlusion maps are used to cull away a portion of the model not visible from the current viewpoint. The algorithm is applicable to all models and makes no assumptions about the size, shape, or type of occluders. It supports approximate culling in which small holes in or among occluders can be ignored. The algorithm has been implemented on current graphics systems and has been applied to large models composed of hundreds of thousands of polygons. In practice, it achieves significant speedup in interactive walkthroughs of models with high depth complexity.

1. J. Airey, J. Rohlf, and F. Brooks. Towardsimage realism with interactive update rates in complex virtual building environments. In Symposium on Interactive 3D Graphics, pages 41-50, 1990.
2. D. Blythe and T. McReynolds. Programming with Opengl: Advanced course. Siggraph’ 96 Course Notes, 1996.
3. M. Bunker and R. Economy. Evolution of GE CIG Systems, SCSD document, General Electric Company, Daytona Beach, FL, 1989
4. L. Carpenter. The A-buffer, an antialiased hidden surface method. Proc. of ACM Siggraph, pages 103-108,1984.
5. E. Catmull. A subdivision algorithm for computer display of curved surfaces. PhD thesis, University of Utah, 1974.
6. J.C. Chauvin (Sogitec). An advanced Z-buffer technology. IMAGE VII, pages 76-85,1994.
7. J.H. Clark. Hierarchical geometric models for visible surface algorithms. Communications of the ACM, 19(10):547-554,1976.
8. S. Coorg and S. Teller. A spatially and temproally coherent object space visibility algorithm. Technical Report TM 546, Laboratory for Computer Science, Massachusetts Institute of Technology, 1996.
9. S. Coorg and S. Teller. Temporally coherent conservative visibility. In Proc. of l2th ACM Symposium on Computational Geometry, 1996.
10. S.E. Dorward. A survey of object-space hidden surface removal. Internat. J. Comput. Geom. Appl., 4:325-362,1994.
11. J. Foley, A. Van Dam, J. Hughes, and S. Feiner. Computer Graphics: Principles and Practice. Addison Wesley, Reading, Mass., 1990.
12. H. Fuchs, Z. Kedem, and B. Naylor. On visible surface generation by a priori tree structures. P~vc. ofACM Siggraph, 14(3): 124-133,1980.
13. R. Coifman G. Beylkin and V. Rokhlin. Fast wavelet transforms and numerical algorithms: I. Communications of Pure and Applied Mathematics, 44(2):141-183,1991.
14. B. Garlick, D. Baum, and J. Winget. Interactive viewing of large geometric databases using multiprocessor graphics workstations. Siggraph’ 90 course notes: Parallel Algorithms and Architectures for 3D Image Generation, 1990.
15. Z. Gigus, J. Canny, and R. Seidel. Efficiently computing and representing aspect graphs of polyhedral objects. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13 (6):542-551,1991.
16. N. Greene and M. Kass. Error-bounded antialiased rendering of complex environments. In Proc. ofACM Siggraph, pages 59-66,1994.
17. N. Greene, M. Kass, and G. Miller. Hierarchical Z-buffer visibility. In Proc. of ACM Siggraph,pages 231-238,1993.
18. C. Georges. Obscuration culling on parallel graphics architectures. Technical Report TR95-017, Department of Computer Science, University of North Carolina, Chapel Hill, 1995.
19. N. Greene. Hieralrhical rendering of complex envilvnments. PhD thesis, University of California at Santa Cruz, 1995.
20. N. Greene. Hierarchical polygon tiling with coverage masks. In P1vc. of ACM Siggraph, pages 65-74,1996.
21. T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff and H. Zhang. Accelerated occlusion culling using shadow frusta. Technical Report TR96-052, Department of Computer Science, University of North Carolina, 1996. To appear in Proc. of ACM Symposium on Computational Geometry, 1997.
22. R. Latham (CGSD). Advanced image generator architectures. Course reference material, 1994.
23. D. Luebke and C. Georges. Portals and mirrors: Simple, fast evaluation of potentially visible sets. In ACMInteractive 3D Graphics Conference, Monterey, CA, 1995.
24. Loral ADS. GT200T Level II image generator product overview, Bellevue, WA.
25. M. McKenna. Worst-case optimal hidden-surfaceremoval.ACM Trans. Graph., 6:19-28,1987.
26. S. Molnar, J. Eyles and J. Poulton. PixelFlow: High speed rendering image composition. Proc. ofACM Siggraph, pp. 231-248,1992.
27. C. Mueller. Architectures of image generators for flight simulators. Technical Report TR95-015, Department of Computer Science, University of North Carolina, Chapel Hill, 1995.
28. K. Mulmuley. An efficient algorithm for hidden surface removal. Computer Graphics, 23(3):379-388,1989.
29. B. Naylor. Partitioning tree imge representation and generation from 3d geometric models. In Proc. of Graphics Intelface, pages 201-12, 1992.
30. R. Brechner et al. Interactive walkthroughof large geometric databases. Siggraph’ 96 course notes, 1996.
31. J. Rohlf and J. Helman. Iris performer: A high performance multiprocessor toolkit for realtime 3d graphics. In P~vc. ofACM Siggraph, pages 381-394,1994.
32. B. Schneider, R Borrel, J. Menon, J. Mittleman, and J. Rossignac. Brush as a walkthroughsystem for architectural models. InFifth Eulvgraphics Workshop on Rendering, pages 389-399, July 1994.
33. O. Sudarsky and C. Gotsman. Output sensitive visibility algorithms for dynamic scenes with applications to virtual reality. Computer Graphics Forum, 15(3):249-58,1996. Proc. of Eurographics’96.
34. J. Torborg and J. Kajiya. Talisman: Commodity Realtime 3D Graphics for the PC. Proc. ofACM Siggraph, pp. 353-363,1996.
35. S. Tanimoto and T. Pavlidis. A hierarchical data structure for picture processing. Computer Graphics and Image Processing, 4(2): 104-119, 1975.
36. S. Teller and C.H. Sequin. Visibility preprocessing for interactive walkthroughs. In Proc. ofACM Siggraph, pages 61-69,1991.
37. J. Warnock. A hidden-surface algorithm for computer generated halftone pictures. Technical Report TR 4-15, NTIS AD-753 671, Department of Computer Science, University of Utah, 1969.
38. L. Williams. Pyramidal parametrics. ACM Computer Graphics, pages 1-11, 1983.
39. R. Yagel and W. Ray. Visibility computations for efficient walkthrough of complex environments. Presence, 5 ( 1 ): 1-16,1996.