Efficient alias-free rendering using bit-masks and look-up tables

ABSTRACT

We demonstrate an efficient method of rendering alias-free synthetic images using precomputed convolution integrals. The method is based on the observation that a visible polygon fragment's contribution to an image is solely a function of its position and shape, and that within a reasonable level of accuracy, a limited number of shapes represent the majority of cases encountered in images commonly rendered.The convolution integral is precomputed for all pixels affected by the polygon fragment and is stored in a table. Completely visible fragments which are either triangular or trapezoidal produce two indices into the table. Most other fragments which are represented as differences of simple fragments. The remaining cases are characterized by a bit-mask for which each bit has a corresponding set of look up tables.The basic technique has been applied to several fundamentally different rendering algorithms. In addition, we illustrate a version of the newly introduced nonuniform sampling technique implemented in the same program, but with different table values.

REFERENCES

• 1: Abram, G.D., forthcoming PhD dissertation.
• 2: Loren Carpenter, The A -buffer, an antialiased hidden surface method, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.103-108, July 1984
• 3: Edwin Catmull, A hidden-surface algorithm with anti-aliasing, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.6-11, August 1978
• 4: Edwin Catmull, An analytic visible surface algorithm for independent pixel processing, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.109-115, July 1984
• 5: Robert L. Cook , Thomas Porter , Loren Carpenter, Distributed ray tracing, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.137-145, July 1984
• 6: 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]
• 7: Crow, F.C., "A Comparison of Antialiasing Techniques," IEEE Computer Graphics and Applications, 1, 1, Jan. 1981.
• 8: Eliot A. Feibush , Marc Levoy , Robert L. Cook, Synthetic texturing using digital filters, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.294-301, July 1980
• 9: Eugene Fiume , Alain Fournier , Larry Rudolph, A parallel scan conversion algorithm with anti-aliasing for a general-purpose ultracomputer, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.141-150, July 1983
• 10: Fuchs, Henry, John Poulton, AI Paeth, and Alan Bell, "Developing Pixel Planes, a Smart Memory- Based Raster Graphics System", Proceedings of the 1982 MIT Conference on Advanced Research in VLSI.
• 11: Henry Fuchs , J. Goldfeather , J. P. Hultquist , S. Spach , John Austin , Frederick P. Brooks, Jr. , John Eyles , John Poulton, Fast Spheres, Shadows, Textures, Transparencies, and Image Enhancements in Pixel-Planes, Advances in Computer Graphics I (Tutorials from Eurographics'84 and Eurographics'85 Conf.), p.169-187, January 1986
• 12: Mitchell, Don P., "Antialiased Ray Tracing By Nonuniform Sampling," AT&T Bell Labs., unpublished report, Dec. 1984.
• 13: Jerri, A.J., "The Shannon Sampling Theorem- Its Various Extensions and Applications: A Tutorial Review," Proc. IEEE, 66, 11, Nov. 1977.
• 14: Robinson, John, tutorial notes for State of the Art in Imase Synthesis Seminar, SIGGRAPH '81.
• 15: Shapiro, H.S., and R.A. Silverman, "Alias Free Samplin~ of Random Noise," J. SIAM, 8, Jun. 1960.
• 16: Kevin Weiler , Peter Atherton, Hidden surface removal using polygon area sorting, Proceedings of the 4th annual conference on Computer graphics and interactive techniques, p.214-222, July 20-22, 1977, San Jose, California
• 17: T. Whitted , D. M. Weimer, A Software Testbed for the Development of 3D Raster Graphics Systems, ACM Transactions on Graphics (TOG), v.1 n.1, p.43-58, Jan. 1982 [doi>10.1145/357290.357295]
• 18: Turner Whitted, Anti-aliased line drawing using brush extrusion, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.151-156, July 1983

INDEX TERMS

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

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
anti-aliasing, image synthesis