“Rendering CSG models with a ZZ-buffer” by Salesin and Stolfi

  • ©David Salesin and Jorge Stolfi

Conference:


Type:


Title:

    Rendering CSG models with a ZZ-buffer

Session/Category Title: Rendering

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    The ZZ-buffer is a simple acceleration scheme for ray tracing that can be applied to a wide variety of scenes, including those with small features, textured and transparent surfaces, shadows and penumbrae, and depth-of-field effects. In this paper, we describe how the ZZ-buffer algorithm can be adapted to the rendering of scenes defined by constructive solid geometry operations.

References:


    1. Amanatides, J., “Ray Tracing with Cones,” Computer Graphics (SIGGRAPH “84) vol. 18 no. 3 (July 1984), 129-135.
    2. Arvo, J. and Kirk, D., “Fast Ray Tracing by Ray Classification,” Computer Graphics (SIGGRAPH ’87) vol. 21 no. 4 (July 1987), 55-64.
    3. Atherton, P. R., “A Scanline Hidden Surface Removal Procedure for Constructive Solid Geometry,” Computer Graphics (SIGGRAPH ’83) vol. 17 no. 3 (July 1983), 73-82.
    4. Barr, A, H., “Superquadrics and Angle Preserving Transformations,” IEEE Computer Graphics and Applications, vol. 1 no. 1 (1981), 11-23.
    5. Blinn, J. E, “A Generalization of Algebraic Surface Drawing,” ACM Transactions on Graphics, vol. 1 no. 3 (July 1982), 236- 256.
    6. Carpenter, L., “The A-buffer, an Antialiased Hidden Surface Method,” Computer Graphics (SIGGRAPH ’84) vol. 18, 3 (July 1984), 103-108.
    7. Catmull, E., “A Subdivision Algorithm for Computer Display of Curved Surfaces,” Ph.D. Thesis, University of Utah, Salt Lake City, December 1974.
    8. Chazelle, B. and Guibas L. J., “Fractional Cascading,” Algorithmica, vol. 1, no. 2 (1986), 133-191. Also DEC Systems Research Center report # 12 (June 1986).
    9. Cook, R. L., “Stochastic Sampling in Computer Graphics,” ACM Transactions on Graphics vol. 5, no. 1 (January 1986), 51-72.
    10. Cook, R. L., Porter, T., and Carpenter, L., “Distributed Ray Tracing,” Computer Graphics (SIGGRAPH ’84) vol. 18 no. 3 (July 1984), 137-145.
    11. Dipp6, M. A. Z., and Wold, E. H., “Antialiasing through Stochastic Sampling,” Computer Graphics (SIGGRAPH ’85) vol. 19 no. 3 (July 1985), 69-78.
    12. Foley, J., van Dam, A., Feiner, S., and Hughes, J. Computer Graphics: Principles and Practice, 2nd Ed., Addison-Wesley, Reading, MA (1990).
    13. Fournier, A. and Fussell, D., “On the Power of the Frame Buffer,” ACM Transactions on Graphics voI. 7 no. 2 (April 1988), 103-128.
    14. Glassner, A. S., “Space Subdivision for Fast Ray Tracing,” IEEE Computer Graphics and Applications, vol. 4 no. 10 (October 1984), 15-22.
    15. Goldfeather, J., Huitquist, J. P. M., and Fuchs, H., “Fast Constructive Solid Geometry Display in the Pixel-Powers Graphics System,” Computer Graphics (SIGGRAPH ’86) vol. 20 no. 4 (August 1986), 107-116.
    16. Guibas L. J. and Stolfi J., “Ruler, Compass, and Computer: The Design and Analysis of Geometric Algorithms,” in Theoretical Foundations of Computer Graphics and CAD, R. A. Earnshaw, ed., NATO ASI Series F, vol. 40, Springer-Verlag (1988), 111-165. Also DEC Systems Research Center report # 37 (February 1989).
    17. Haines, E. A. and Greenberg, D. P., “The Light Buffer: A Ray Tracer Shadow Testing Accelerator,” IEEE Computer Graphics and Applications, vol. 6 no. 9 (September 1986), 6-15.
    18. Hanrahan, P., “Ray Tracing Algebraic Surfaces,” Computer Graphics (SIGGRAPH ’83) vol. 17 no. 3 (July t983), 83-90.
    19. Heckbert, P. S. and Hanrahan, P., “Beam Tracing Polygonal Objects,” Computer Graphics (SIGGRAPH ’84) vol. 18 no. 3 (July 1984), 119-127.
    20. Kay, D. S., “A Transparency Refraction and Ray Tracing Model for Computer Synthesized Images,” Master’s thesis, Comell University, Ithaca, New York, 1979.
    21. Kay, D. S., and Greenberg, D. P., “Transparency for Computer Synthesized Images,” Computer Graphics (SIGGRAPH ’79) vol. 13 no. 2 (August 1979), 158-164.
    22. Kay, T. L. and Kajiya, J., “Ray Tracing Complex Scenes,” Computer Graphics (SIGGRAPH ’86) vol. 20 no. 4 (August 1986), 269-278.
    23. Lee, M. E., Redner, R. A., and Uselton, S. P., “Statistically Optimized Sampting for Distributed Ray Tracing,” Computer Graphics (SIGGRAPH ’85) vol. 19 no. 3 (July 1985), 61-67.
    24. Mitchell, D. P., “Generating Antialiased Images at Low Sampiing Densities,” Computer Graphics (SIGGRAPH ’87) vol. 21 no. 4 (July 1987), 65-72.
    25. Mitchell, D. P., and Netravali, A. N., “Reconstruction Filters in Computer Graphics,” Computer Graphics (SIGGRAPH ’88) vol. 22 no. 4 (August 1988), 221-228.
    26. Moore, R. E., Interval Analysis, Prentice-Hall, Englewood Cliffs, N. j. (1966).
    27. Porter, T. and Duff, T., “Compositing Digital Images,” Computer Graphics (SIGGRAPH ’84) vol. 18 no. 3 (July 1984), 253-259.
    28. Painter, J. and Sloan, K., “Antialiased Ray Tracing by Adaptive Progressive Refinement,” Computer Graphics (SIG- GRAPH ’89) vol. 23, no. 3 (July 1989), 281-288.
    29. Pratt, W. K., Digital Image Processing, Wiley and Sons, New York (1978).
    30. Okino, N., Kakazu, Y., and Morimoto, M., “Extended Depth- Buffer Algorithms for Hidden-Surface Visualization,” IEEE Computer Graphics and Applications vol. 4, no. 5 (May 1984), 79-88.
    31. Reeves, W. T., Salesin, D. H., and Cook, R. L., “Rendering Antialiased Shadows with Depth Maps,” Computer Graphics (SIGGRAPH ’87) vol. 21 no. 4 (July 1987), 283-291.
    32. Rossignac, J. R. and Requicha, A. A. G., “Depth Buffering Display Techniques for Constructive Solid Geometry,” IEEE Computer Graphics and Applications vol. 6, no. 9 (September 1986), 29-39.
    33. Rossignac, J. R. and Voelcker, H. B., “Active Zones in CSG for Accelerating Boundary Evaluation, Redundancy Elimination, Interference Detection, and Shading Algorithms,” ACM Transactions on Graphics vol. 8, no. 1 (January 1989), 51-87.
    34. Roth, S. D., “Ray Casting for Modeling Solids,” Computer Graphics and Image Processing vol. t8 (1982), 109-144.
    35. Salesin, D., “The Fuzzy Buffer: A Stochastic Antialiased Hidden Surface Algorithm,” Ph. D. Programming Project Report, Stanford University (1986).
    36. Salesin, D. and Stolfi, J., “The ZZ-Buffer: A Simple and Efficient Rendering Algorithm with Reliable Antialiasing,” Proceedings of the PIXIM ’89 Conference (Hermes Editions, Paris, September 1989), 451-466.
    37. S6quin, C. G., Smyrl, E. K., “Parameterized Ray Tracing,” Computer Graphics (SIGGRAPH ’89) vol. 23 no. 3 (July 1989), 307-314.
    38. Thacker, C. P., Stewart, L. C., and Satterthwaite, E. H. Jr., “Firefly: A Multiprocessor Workstation,” DEC Systems Research Center, Research Report 23 (December 1987).
    39. Wamock, J. E., “A Hidden-Surface Algorithm for Computer- Generated Halftone Pictures,” Computer Science Department, University of Utah, TR 4-15 (June 1969).
    40. Weghorst, H., Hooper, G., and Greenberg, D. E, “Improved Computational Methods for Ray Tracing,” ACM Transactions on Graphics, vot. 3, no. 1 (January 1984), 52-69.
    41. Williams, L., “Casting Curved Shadows on Curved Surfaces,” Computer Graphics (SIGGRAPH ’78) volt 12 no. 3 (August 1978), 270-274.

ACM Digital Library Publication:


Overview Page: