Drawing antialiased cubic spline curves

ABSTRACT

Cubic spline curves have many nice properties that make them desirable for use in comptuer graphics, and the advantages of antialiasing have been known for some years. Yet, only recently has there been any attempt at directly antialiasing spline curves. Parametric spline curves have resisted antialiasing in several ways: single segments may cross or become tangent to themselves. Cusps and small loops are easily missed entirely. Thus, short pieces of the curve cannot necessarily be rendered in isolation. Finding the distance from a pixel center to the curve accurately and efficiently—usually an essential part of antialiasing—is an unsolved problem. The method presented by Lien, Shantz, and Pratt [21] is a good start, although it considers pixel-length pieces of the curve in isolation and lacks robustness in the handling of certain curves. This paper provides an improved method that is more robust, and is able to handle intersections and tangency.

REFERENCES

• 1: Jose Barros , Henry Fuchs, Generating smooth 2-D monocolor line drawings on video displays, ACM SIGGRAPH Computer Graphics, v.13 n.2, p.260-269, August 1979
• 2: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to splines for use in computer graphics & geometric modeling, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 3: Loren Carpenter, The A -buffer, an antialiased hidden surface method, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.103-108, July 1984
• 4: Franklin C. Crow, The use of grayscale for improved raster display of vectors and characters, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.1-5, August 1978
• 5: DECASTELJAU, P. Courbes et surface i2 P61es. Citr6en, Paris, 1959.
• 6: Gerald Farin, Curves and surfaces for computer aided geometric design: a practical guide, Academic Press Professional, Inc., San Diego, CA, 1988
• 7: FIELD, D. Two algorithms for drawing anti-aliased lines. In Proceedings GI '84 {May 1984). Canadian Information Processing Society, 1984, 87-89.
• 8: 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
• 9: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 10: FORREST, A. R. Antialiasing in practice. In Fundamental Algorithms in Computer Graphics, R. A. Earnshaw, Ed., Springer-Verlag, Berlin, 1985, 113-134.
• 11: FUJIMOTO, A., AND IWATA, K. Jag-free images on raster displays. IEEE Comput. Gr. AppL 3 (Dec. 1983), 26-34.
• 12: GONCZAROWSKI, J. Fast generation of unfilled and filled outline characters. In Proceedings of RIDT '89 (Oct. 1989). Cambridge University Press, 1989, 97-110.
• 13: Satish Gupta , Robert F. Sproull, Filtering edges for gray-scale displays, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.1-5, August 1981
• 14: Gary Herron, Polynomial bases for quadratic and cubic polynomials which yield control points with small convex hulls, Computer Aided Geometric Design, v.6 n.1, p.1-9, February 1989 [doi>10.1016/0167-8396(89)90002-2]
• 15: R. Victor Klassen, Integer forward differencing of cubic polynomials: analysis and algorithms, ACM Transactions on Graphics (TOG), v.10 n.2, p.152-181, April 1991 [doi>10.1145/108360.108364]
• 16: KNUTH, D. E. METAFONT, a system for alphabet design. In TEX and Metafont: New Directions in Typography, American Mathematical Society and DIGITAL Press, 1979.
• 17: Donald E. Knuth, The Metafont book, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 18: Jeffrey M. Lane , Loren C. Carpenter , Turner Whitted , James F. Blinn, Scan line methods for displaying parametrically defined surfaces, Communications of the ACM, v.23 n.1, p.23-34, Jan. 1980 [doi>10.1145/358808.358815]
• 19: LANE, J., AND RIESENFELD, g. A theoretical development for the computer generation and display of piecewise polynomial surfaces. IEEE Trans. Pattern Anal. Mach. lnteU. PAMI-2, 1 (Jan. 1980), 35-46.
• 20: William J Leler, Human vision, anti-aliasing, and the cheap 4000 line display, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.308-313, July 1980
• 21: Sheue-Ling Lien , Michael Shantz , Vaughan Pratt, Adaptive forward differencing for rendering curves and surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.111-118, July 1987
• 22: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 23: NI, G., AND TANNER, P. The application of anti-aliased technique for displaying high quality Chinese characters. In Proceedings of the 1982 International Conference of the Chinese Language Computer Society (Sept. 1982), 37-45.
• 24: 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]
• 25: Michael Plass , Maureen Stone, Curve-fitting with piecewise parametric cubics, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.229-239, July 1983
• 26: Dino Schweitzer , Elizabeth S. Cobb, Scanline rendering of parametric surfaces, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.265-271, July 1982
• 27: K. Turkowski, Anti-Aliasing through the Use of Coordinate Transformations, ACM Transactions on Graphics (TOG), v.1 n.3, p.215-234, July 1982 [doi>10.1145/357306.357309]
• 28: Turner Whitted, A scan line algorithm for computer display of curved surfaces, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.26, August 1978
• 29: 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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

General Terms:
Algorithms, Design