“Hierarchical Z-buffer visibility” by Greene, Kass and Miller

An ideal visibility algorithm should a) quickly reject most of the
hidden geometry in a model and b) exploit the spatial and perhaps
temporal coherence of the images being generated. Ray casting
with spatial subdivision does well on criterion (a), but poorly on
criterion (b). Traditional Z-buffer scan conversion does well on
criterion (b), but poorly on criterion (a). Here we present a hierarchical Z-buffer scan-conversion algorithm that does well on
both criteria. The method uses two hierarchical data structures, an
object-space octree and an image-space Z pyramid, to accelerate
scan conversion. The two hierarchical data structures make it possible to reject hidden geometry very rapidly while rendering visible
geometry with the speed of scan conversion. For animation, the
algorithm is also able to exploit temporal coherence. The method
is well suited to models with high depth complexity, achieving
orders of magnitude acceleration in some cases compared to ordinary Z-buffer scan conversion.

1. S.M. Rubin and T. Whitted. A 3-dimensional representation for fast rendering of complex scenes. Computer Graphics, 14(3):110-1 16, July 1980.
2. A. Glassner. Space subdivision for fast ray tracing. IEEE CG&A, 4(10):15-22, Oct. 1984.
3. D. Jevans and B. Wyvill. Adaptive voxel subdivision for ray tracing. Proc. Graphics Interface ’89, 164-172, June 1989.
4. T. Kay and J. Kajiya. Ray tracing complex surfaces. Computer Graphics, 20(4):269-278, Aug. 1986.
5. M. Kaplan. The use of spatial coherence in ray tracing. In Techniques for Computer Graphics, etc., D. Rogers and R. A. Earnshaw, Springer-Verlag, New York, 1987.
6. H. Hubschman and S. W. Zucker. Frame to frame coherence and the hidden surface computation: constraints for a convex world. ACM TOG, 1(2):129-162, April 1982.
7. D. Jevans. Object space temporal coherence for ray tracing. Proc. Graphics Interface ’92, Vancouver, B.C., 176- 183, May 11-15, 1992.
8. A. Glassner. Spacetime ray tracing for animation. IEEE CG&A, 8(3):60-70, March 1988.
9. J. Chapman, T. W. Calvert, and J. Dill. Spatio-temporal coherence in ray tracing. Proceedings of Graphics Interface ’90, 196-204, 1990.
10. S. Badt, Jr. Two algorithms for taking advantage of temporal coherence in ray tracing The Visual Computer, 4:123-132, 1988.
11. B. Gaflick, 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.
12. J. Airey. Increasing update rates in the building walkthrough system with automatic model-space subdivision. Technical Report TR90-027, The University of North Carolina at Chapel Hill, Department of Computer Science, 1990.
13. J. Airey, J. Rohlf, and F. Brooks. Towards image realism with interactive update rates in complex virtual building environments. ACM SIGGRAPH Special Issue on 1990 Symposium on Interactive 3D Graphics, 24(2):41-50, 1990.
14. S. Teller and C. Sequin. Visibility preprocessing for interactive walkthroughs. Computer Graphics, 25(4):61-69, 1991.
15. S. Teller and C. Sequin. Visibility computations in polyhedral three-dimensional environments. U.C. Berkeley Report No. UCB/CSD 92/680, April 1992.
16. D. Meagher. Efficient synthetic image generation of arbitrary 3-D objects. Proc. IEEE Conf. on Pattern Recognition and Image Processing, 473-478, June 1982.