An efficient antialiasing technique

ABSTRACT

An intuitive concept of antialiasing is developed into very efficient antialiased line and circle generators that require even less amount of integer arithmetic than Bresenham's line and circle algorithms. Unlike its predecessors, the new antialiasing technique is derived in spatial domain (raster plane) under a subjectively meaningful error measure to preserve the dynamics of curve and object boundaries. A formal analysis of the new antialiasing technique in frequency domain is also conducted. It is shown that our antialiasing technique computes the same antialiased images as Fujimoto-Iwata's algorithm but at a fraction of the latter's computational cost. The simplicities of the new antialiased line and circle generators also mean their easy hardware implementations.

REFERENCES

• 1: Anthony C. Barkans, High speed high quality antialiased vector generation, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.319-326, Aug. 1990
• 2: J. E. Bresenham, "Algorithm for computer control of digital plotter," IBM Syst. J., vol. 4, no. 1, 1965, p. 25-30.
• 3: Jack Bresenham, A linear algorithm for incremental digital display of circular arcs, Communications of the ACM, v.20 n.2, p.100-106, Feb. 1977 [doi>10.1145/359423.359432]
• 4: 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]
• 5: Dan Field, Algorithms for drawing anti-aliased circles and ellipses, Computer Vision, Graphics, and Image Processing, v.33 n.1, p.1-15, Jan. 1986 [doi>10.1016/0734-189X(86)90218-5]
• 6: A. Fujimoto and K. Iwata, "Jay-free images on " IEEE CG~A, vol. 3, no. 9, p 26- raster displays, 34, Dec. 1983.
• 7: Satish Gupta , Robert F. Sproull, Filtering edges for gray-scale displays, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.1-5, August 1981
• 8: M. L. V. Pitteway , D. J. Watkinson, Bresenham's algorithm with Grey scale, Communications of the ACM, v.23 n.11, p.625-626, Nov. 1980 [doi>10.1145/359024.359027]
• 9: Xiaolin Wu , Jon G. Rokne, Double-step incremental generation of lines and circles, Computer Vision, Graphics, and Image Processing, v.37 n.3, p.331-344, March 1987 [doi>10.1016/0734-189X(87)90041-7]
• 10: X. Wu , J. Rokne, On Properties of Discretized Convex Curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.217-223, February 1989 [doi>10.1109/34.16719]
• 11: Xiaolin Wu , Jon G. Rokne, Double-Step Generation of Ellipses, IEEE Computer Graphics and Applications, v.9 n.3, p.56-69, May 1989 [doi>10.1109/38.28111]
• 12: X. Wu and J. Rokne, "Dynamic error measure for curve scan-conversion," Proc. Graph. ics//lnterface'89, London, Ontario, p. 183-190, June 1989.
• 13: J. G. Rokne , Brian Wyvill , Xiaolin Wu, Fast line scan-conversion, ACM Transactions on Graphics (TOG), v.9 n.4, p.376-388, Oct. 1990 [doi>10.1145/88560.88572]
• 14: X. Wu, "A frame buffer architecture for parallel vector generation," Proc. Graphics//Interface'91, Calgary, June 1991.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Digitizing and scanning; Antialiasing**
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms

Keywords:
antialiasing, convolution, curve digitization, digital geometry