Rasterization of nonparametric curves

ABSTRACT

We examine a class of algorithms for rasterizing algebraic curves based on an implicit form that can be evaluated cheaply in integer arithmetic using finite differences. These algorithms run fast and produce “optimal” digital output, where previously known algorithms have had serious limitations. We extend previous work on conic sections to the cubic and higher order curves, and we solve an important undersampling problem.

REFERENCES

• 1: BOROFSK~, S. Elementary Theory of Equations. Macmillan, New York, 1950.
• 2: FREEMAN, H. On the encoding of arbitrary geometric configurations. IRE Trans. Electron. Comput. EC-IO, 2 (June 1961), 260-268.
• 3: FREEMAN, H. On the quantization of line-drawing data. IEEE Trans. Syst. ScL Cybern. 5, 1 (Jan. 1969), 70-79.
• 4: John Douglas Hobby, Digitized brush trajectories (raster, algorithms), 1985
• 5: HOBBY, J.D. Non-parametric digitization algorithms. Comput. Sci. Tech. Rep. 125, AT&T Bell Laboratories, Murray Hill, N.J., 1986.
• 6: John D. Hobby, Rasterizing curves of constant width, Journal of the ACM (JACM), v.36 n.2, p.209-229, April 1989 [doi>10.1145/62044.62045]
• 7: John D. Hobby, Numerically stable implicitization of cubic curves, ACM Transactions on Graphics (TOG), v.10 n.3, p.255-296, July 1991 [doi>10.1145/108541.108546]
• 8: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 9: KNUTH, D.E. Computers and Typesetting. Vol. D, Metafont: The Program, Addison-Wesley, Reading, Mass., 1986.
• 10: Richard R. Patterson, Parametric cubics as algebraic curves, Computer Aided Geometric Design, v.5 n.2, p.139-160, July 1988 [doi>10.1016/0167-8396(88)90028-3]
• 11: PITTEWAY, M. L.V. Algorithm for drawing ellipses or hyperbolae with a digital plotter. Comput. J. 10, 3 (Nov. 1967), 282-289.
• 12: Vaughan Pratt, Techniques for conic splines, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.151-160, Jul. 1985
• 13: Thomas Warren Sederberg, Implicit and parametric curves and surfaces for computer aided geometric design, 1983
• 14: SEDERBERG, W. W., ANDERSON, D. C., AND GOLDMAN, R.N. Implicitization, inversion and intersection of planar rational cubic curves. Comput. Vision Graph. Image Process. 31, 1 (July 1985), 89-102.
• 15: Jerry Van Aken , Mark Novak, Curve-drawing algorithms for Raster displays, ACM Transactions on Graphics (TOG), v.4 n.2, p.147-169, April 1985 [doi>10.1145/282918.282943]

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: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Theory