Generating antialiased images at low sampling densities

ABSTRACT

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.

REFERENCES

• ABR85: Greg Abram , Lee Westover, Efficient alias-free rendering using bit-masks and look-up tables, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.53-59, Jul. 1985
• AMA84: John Amanatides, Ray tracing with cones, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.129-135, July 1984
• BRO69: Brown, Earl F., "Television: The Subjective Effects of Filter Ringing Transients", Journal of the SMPTE, Vol. 78, No 4, April t969, pp. 249-255.
• CAEgl: Caelli, Terry~ Visual Perception: Theory and Practice, Pergamon Press, Oxford (1981).
• COO84: Robert L. Cook , Thomas Porter , Loren Carpenter, Distributed ray tracing, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.137-145, July 1984
• COO86: Robert L. Cook, Stochastic sampling in computer graphics, ACM Transactions on Graphics (TOG), v.5 n.1, p.51-72, Jan. 1986 [doi>10.1145/7529.8927]
• CRO77: Franklin C. Crow, The aliasing problem in computer-generated shaded images, Communications of the ACM, v.20 n.11, p.799-805, Nov. 1977 [doi>10.1145/359863.359869]
• DIP85: Mark A. Z. Dippé , Erling Henry Wold, Antialiasing through stochastic sampling, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.69-78, Jul. 1985
• FLO75: Floyd, R. and L. Steinberg, "An Adaptive Algorithm for Spatial Grey Scale", SID Digest. 1975, 36-37.
• FRA82: Franke, Richard, "Scattered Data Interpolation: Tests of Some Methods", Mathematics of Computation, Vol. 38, No. 157, January 1982.
• KAJ84: Kajiya, James T., Engineering and Science, Vol 48, No. 2, California Institute of Technology: November 1984.
• KAJ86: James T. Kajiya, The rendering equation, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.143-150, Aug. 1986
• LEES5: Mark E. Lee , Richard A. Redner , Samuel P. Uselton, Statistically optimized sampling for distributed ray tracing, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.61-68, Jul. 1985
• LIM69: Limb, J. O., "Design of Dither Waveforms for Quantized Visual Signals", Bell System Tech. J., Vol 48, pp. 2555- 2582, 1969.
• LIM77: Limb, John O., "Digital Coding of Color Video Signals-- A Review", IEEE Trans. Comm., Vol. COMM-25, No. 11, November 1977, pp. 1349-1382.
• MIT85: Mitchell, Don P., "Antialiased Ray Tracing By Nonuniform Sampling", unpublished Bell Labs report, April 1985.
• NET86: Netravali, Arun, Personal Communication.
• PET62: 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.
• RIP77: Ripley, B. D., "Modeling Spatial Patterns", J. Roy. Statist. Soc. B, Vol. 39, 1977, pp. 172-212.
• ROT82: Roth, S. D., "Ray Casting for Modeling Solids", Computer Graphics and Image Processing, Vol. 18, 1982, pp. 109-144.
• SAK77: 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.
• SHA49: Shannon, C.E., "Communication in the presence of noise.", Proc. IRE Vol. 37, 1949, pp. 10-21.
• SHA60: Shapiro, Harold S. and Richard A. Silverman, "Alias- Free Sampling of Random Noise", J. SLAM, Vol. 8, No. 2, June 1960, pp. 225-248.
• wHIg0: Turner Whitted, An improved illumination model for shaded display, Communications of the ACM, v.23 n.6, p.343-349, June 1980 [doi>10.1145/358876.358882]
• YEL83: Yellott, John I. Jr., "Spectral Consequences of Photoreceptor Sampling in the Rhesus Retina", Science, Vol. 221, 1983, pp. 382-385.
• YEN56: Yen, J. L., "On Nonuniform Sampling of Bandwidth- Limited Signals", IRE Trans. Circuit Theory, Vol. 3, Dec. 1 1956, pp. 251-257.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Design, Theory