Antialiased ray tracing by adaptive progressive refinement

ABSTRACT

We describe an antialiasing system for ray tracing based on adaptive progressive refinement. The goals of the system are to produce high quality antialiased images at a modest average sample rate, and to refine the image progressively so that the image is available in a usable form early and is refined gradually toward the final result.The method proceeds by adaptive stochastic sampling of the image plane, evaluation of the samples by ray tracing, and image reconstruction from the samples. Adaptive control of the sample generation process is driven by three basic goals: coverage of the image, location of features, and confidence in the values at a distinguished "pixel level" of resolution.A three-stage process of interpolation, filtering, and resampling is used to reconstruct a regular grid of display pixels. This reconstruction can be either batch or incremental.

REFERENCES

• 1: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• 2: Larry Bergman , Henry Fuchs , Eric Grant , Susan Spach, Image rendering by adaptive refinement, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.29-37, Aug. 1986
• 3: Blanford, Ronald P., Painter, James S. and Sloan, Kenneth R. Adaptive Sampling, Transmission, and Rendering of Images. SPIE Proceedings 1077 (Jan., 1989), SPIE Conference on Human Vision, Visual Processing, and Digital Display.
• 4: IEEE Computer Graphics and Applications Staff, Return of the Jaggy, IEEE Computer Graphics and Applications, v.9 n.2, p.82-89, March 1989 [doi>10.1109/38.19054]
• 5: Burr, Irving W. Applied Statistical Methods. Academic Press, New York, NY, 1974.
• 6: Cendes, Zoltan J. and Wong, Steven H. C~ Quadratic Interpolation Over Arbitrary Point Sets. IEEE Computer Graphics and Applications 7, 11 (Nov., 1987), 8-16.
• 7: Michael F. Cohen , Shenchang Eric Chen , John R. Wallace , Donald P. Greenberg, A progressive refinement approach to fast radiosity image generation, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.75-84, June 1988
• 8: 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]
• 9: Robert L. Cook , Thomas Porter , Loren Carpenter, Distributed ray tracing, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.137-145, January 1984
• 10: Franklin C. Crow, Summed-area tables for texture mapping, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.207-212, January 1984
• 11: Mark A. Z. Dippé , Erling Henry Wold, Antialiasing through stochastic sampling, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.69-78, Jul. 1985
• 12: James T. Kajiya, The rendering equation, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.143-150, Aug. 1986
• 13: 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
• 14: Lounsbery, J. Michael The Renaissance Modeling System. Dept. of Computer Science, Univ. of Washington, Tech. Rep. #89-01-05, Jan., 1989.
• 15: Don P. Mitchell, Generating antialiased images at low sampling densities, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.65-72, July 1987
• 16: Avi Naiman , Alain Fournier, Rectangular convolution for fast filtering of characters, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.233-242, July 1987
• 17: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 18: 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]
• 19: Yellott, James I. Jr. Spectral Consequences of Photoreceptor Sampling in the Rhesus Retina. Science 221 (July, 1983), 392- 385.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  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, Theory