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

  • ©Ned Greene, Michael Kass, and Gavin S. P. Miller




    Hierarchical Z-buffer visibility



    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.

ACM Digital Library Publication:

Overview Page: