“Hierarchical polygon tiling with coverage masks” by Greene

We present a novel polygon tiling algorithm in which recursive subdivision of image space is driven by coverage masks that classify a convex polygon as inside, outside, or intersecting cells in an image hierarchy. This approach permits Warnock-style subdivision with its logarithmic search properties to be driven very efficiently by bit-mask operations. The resulting hierarchical polygon tiling algorithm performs subdivision and visibility computations very rapidly while only visiting cells in the image hierarchy that are crossed by visible edges in the output image. Visible samples are never overwritten. At 512 512 resolution, the algorithm tiles as rapidly as traditional incremental scan conversion, and at high resolution (e.g. 4096 4096) it is much faster, making it well suited to antialiasing by oversampling and filtering. For densely occluded scenes, we combine hierarchical tiling with the hierarchical visibility algorithm to enable hierarchical object-space culling. When we tested this combination on a densely occluded model, it computed visibility on a 4096 4096 grid as rapidly as hierarchical z-buffering [Greene-Kass-Miller93] tiled a 512 512 grid, and it effectively antialiased scenes containing hundreds of thousands of visible polygons. The algorithm requires strict front-to-back traversal of polygons, so we represent a scene as a BSP tree or as an octree of BSP trees. When maintaining depth order of polygons is not convenient, we combine hierarchical tiling with hierarchical z-buffering, resorting to z-buffering only in regions of the screen where the closest object is not encountered first.

1. G. Abram, L. Westover, and T. Whitted, “Efficient Alias-Free Rendering using Bit-Masks and Look-Up Tables,” Proceedings of SIGGFtAPH ’85, July 1985, 53-59.
2. L. Carpenter, “The A-buffer, an Antialiased Hidden Surface Method,” Proceedings of SIGGFtAPH ‘8g, July 1984, 103-108.
3. E. Catmull, “A Subdivision Algorithm for Computer Display of Curved Surfaces,” Phi) Thesis, Report UTEC-CSc- 74-133, Computer Science Dept., University of Utah, Salt Lake City, Utah, Dec. 1974.
4. E. Catmull, “A Hidden-Surface Algorithm with Anti- Aliasing,” Proceedings of SIGGRAPH ’78, Aug. 1978, 6-11.
5. R. Cook, “Stochastic Sampling in Computer Graphics,” ACM Transactions on Graphics, Jan. 1986, 51-72.
6. M. A. Z. I)ipp6 and E. H. Wold, “Antialiasing through Stochastic Sampling,” Proceedings of SIGGRAPH ’85, July 1985, 69-78.
7. E. Fiume, A. Fournier, and L. Rudolph, “A Parallel Scan Conversion Algorithm with Anti-Aliasing for a General- Purpose Ultracomputer,” Proceedings of SIGGRAPH ’83, July 1983, 141-150.
8. E. Fiume, “Coverage Masks and Convolution Tables for Fast Area Sampling,” Graphical Models and Image Processing, 53(1), Jan. 1991, 25-30.
9. J. Foley, A. van Dam, S. Feiner, and J. Hughes, Computer Graphics, Principles and Practice, 2nd edition, Addison- Wesley, Reading, MA, 1990.
10. H. Fuchs, J. Kedem, and B. Naylor, “On Visible Surface Generation by a Priori Tree Structures,” Proceedings of SIGGRAPH ’80, June 1980, 124-133.
11. N. Greene, M. Kass, and G. Miller, “Hierarchical Z-Buffer Visibility,” Proceedings of SIGGRAPH ’93, July 1993, 231-238.
12. N. Greene and M. Kass, “Error-Bounded Antialiased Rendering of Complex Environments,” Proceedings of SIGGRAPH ’94, July 1994, 59-66.
13. N. Greene, “Hierarchical Rendering of Complex Environments,” Phi) Thesis, Univ. of California at Santa Cruz, Report No. UCSC-CRL-95-27, June 1995.
14. N. Greene, “Naked Empire,” ACM Siggraph Video Review Issue 115: The Siggraph ’96 Electronic Theater, August 1996.
15. P. Haeberli and K. Akeley, “The Accumulation Buffer: Hardware Support for High-Quality Rendering,” Proceedings of SIGGRAPH ’90, Aug. 1990, 309-318.
16. A. Kaufman, “3i) Scan Conversion Algorithms for Voxel-Based Graphics,” Proceedings of the 1986 Workshop on Interactive 3D Graphics, Oct. 1986, 45-75.
17. I). Meagher, “The Octree Encoding Method for Efficient Solid Modeling,” Phi) Thesis, Electrical Engineering Dept., Rensselaer Polytechnic Institute, Troy, New York, Aug. 1982.
18. B. Naylor, “Interactive Solid Geometry Via Partitioning Trees,” Proceedings of Graphics Interface ’92, May 1992, 11- 18.
19. B. Naylor, “Partitioning Tree Image Representation and Generation from 3i) Geometric Models,” Proceedings of Graphics Interface ’92, May 1992, 201-212.
20. I). Rogers, Procedural Elements for Computer Graphics, McGraw-Hill, New York, 1985.
21. P. Sabella and M. Wozny, “Toward Fast Color- Shaded Images of CAD/CAM Geometry,” IEEE Computer Graphics and Applications, 3(8), Nov. 1983, 60-71.
22. S. Teller, “Visibility Computations in Densely Occluded Polyhedral Environments,” Phi) Thesis, Univ. of California at Berkeley, Report No. UCB/CSI) 92/708, Oct. 1992.
23. J. Warnock, “A Hidden Surface Algorithm for Computer Generated Halftone Pictures,” Phi) Thesis, Computer Science Dept., University of Utah, TR 4-15, June 1969.