“Generating antialiased images at low sampling densities” by Mitchell

  • ©Don Mitchell




    Generating antialiased images at low sampling densities



    Ray tracing produces point samples of an image from a 3-D model. Constructing an antialiased digital picture from point samples is difficult without resorting to extremely high sampling densities. This paper describes a program that focuses on that problem. While it is impossible to eliminate aliasing totally, it has been shown that nonuniform sampling yields aliasing that is less conspicuous to the observer. An algorithm is presented for fast generation of nonuniform sampling patterns that are optimal in some sense. Some regions of an image may require extra sampling to avoid strong aliasing. Deciding where to do extra sampling can be guided by knowledge of how the eye perceives noise as a function of contrast and color. Finally, to generate the digital picture, the image must be reconstructed from the samples and resampled at the display pixel rate. The nonuniformity of the samples complicates this process, and a new nonuniform reconstruction filter is presented which solves this problem efficiently.


    1. Abram, Greg, Lee Westover, Turner Whitted, “Efficient Alias-free Rendering using Bit-masks and Look-up Tables”, Computer Graphics, Vol. 19, No. 3, July 1985, p. 57.
    2. Amanatides, John, “Ray Tracing with Cones”, Computer Graphics, Vol. 18, No. 3, July 1984, pp. 129-135.
    3. Brown, Earl F., “Television: The Subjective Effects of Filter Ringing Transients”, Journal of the SMPTE, Vol. 78, No 4, April t969, pp. 249-255.
    4. Caelli, Terry~ Visual Perception: Theory and Practice, Pergamon Press, Oxford (1981).
    5. Cook, Robert L, Thomas Porter, Loren Carpenter, “Distributed Ray Tracing”, Computer Graphics, Vol. 18, No. 3, July 1984, pp. 137-145.
    6. Cook, Robert L, “Stochastic Sampling in Computer Graphics”, ACM Trans. Graphics, Vol. 5, No. 1, January 1986.
    7. Crow, Franklin C., “The Aliasing Problem in Computer- Generated Shaded Images”, Comm. ACM, Vol. 20, No. 11, November 1977, pp 799-805.
    8. Dippe, Mark A. Z. and Erling Henry Wold, “Antialiasing Through Stochastic Sampling”, Computer Graphics, Vol. 19, No. 3, July 1985, pp. 69-78.
    9. Floyd, R. and L. Steinberg, “An Adaptive Algorithm for Spatial Grey Scale”, SID Digest. 1975, 36-37.
    10. Franke, Richard, “Scattered Data Interpolation: Tests of Some Methods”, Mathematics of Computation, Vol. 38, No. 157, January 1982.
    11. Kajiya, James T., Engineering and Science, Vol 48, No. 2, California Institute of Technology: November 1984.
    12. Kajiya, James T., “The Rendering Equation”, Computer Graphics, Vol. 20, No. 4, July 1986, pp. 143-150.
    13. Lee, Mark, Richard A. Redner, Samuel P. Uselton, “Statistically Optimized Sampling for Distributed Ray Tracing”, Computer Graphics, Vol. 19, No. 3, July 1985, pp. 61-67.
    14. Limb, J. O., “Design of Dither Waveforms for Quantized Visual Signals”, Bell System Tech. J., Vol 48, pp. 2555- 2582, 1969.
    15. Limb, John O., “Digital Coding of Color Video Signals– A Review”, IEEE Trans. Comm., Vol. COMM-25, No. 11, November 1977, pp. 1349-1382.
    16. Mitchell, Don P., “Antialiased Ray Tracing By Nonuniform Sampling”, unpublished Bell Labs report, April 1985.
    17. Netravali, Arun, Personal Communication.
    18. Petersen, Daniel P., David Middleton, “Sampling and Reconstruction of Wave-Number-Limited Funetions in N-Dimensional Euclidean Spaces”, Information and Control, Vol. 5, t962, pp. 279-323.
    19. Ripley, B. D., “Modeling Spatial Patterns”, J. Roy. Statist. Soc. B, Vol. 39, 1977, pp. 172-212.
    20. Roth, S. D., “Ray Casting for Modeling Solids”, Computer Graphics and Image Processing, Vol. 18, 1982, pp. 109-144.
    21. Sakrison, David J., “On the Role of the Observer and a Distortion Measure in Image Transmission.”, IEEE Trans. Comm., Vol. COM-25, No. 11, November 1977, pp 1251-1267.
    22. Shannon, C.E., “Communication in the presence of noise.”, Proc. IRE Vol. 37, 1949, pp. 10-21.
    23. Shapiro, Harold S. and Richard A. Silverman, “Alias- Free Sampling of Random Noise”, J. SLAM, Vol. 8, No. 2, June 1960, pp. 225-248.
    24. Whitted, Turner, “An Improved Illumination Model for Shaded Display”, Comm. ACM, Vol. 23, No. 6, June 1980, pp. 343-349.
    25. Yellott, John I. Jr., “Spectral Consequences of Photoreceptor Sampling in the Rhesus Retina”, Science, Vol. 221, 1983, pp. 382-385.
    26. Yen, J. L., “On Nonuniform Sampling of Bandwidth- Limited Signals”, IRE Trans. Circuit Theory, Vol. 3, Dec. 1 1956, pp. 251-257.

ACM Digital Library Publication: