Adaptive forward differencing for rendering curves and surfaces

ABSTRACT

An adaptive forward differencing algorithm is presented for rapid rendering of cubic curves and bicubic surfaces. This method adjusts the forward difference step size so that approximately one pixel is generated along an ordinary or rational cubic curve for each forward difference step. The adjustment involves a simple linear transformation on the coefficients of the curve which can be accomplished with shifts and adds. This technique combines the advantages of traditional forward differencing and adaptive subdivision. A hardware implementation approach is described including the adaptive control of a forward difference engine. Surfaces are rendered by drawing many curves spaced closely enough together so that no pixels are left unpainted. A simple curve anti-aliasing algorithm is also presented in this paper. Anti-aliasing cubic curves is supported via tangent vector output at each forward difference step. The adaptive forward differencing algorithm is also suitable for software implementation.

REFERENCES

• 1: 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]
• 2: Edwin Earl Catmull, A subdivision algorithm for computer display of curved surfaces., 1974
• 3: George M. Chaikin, "An Algorithm for High Speed Curve Generation," Computer Graphics and linage Processing, vol. 3, pp. 346-349, 1974.
• 4: S. A. Coons, SURFACES FOR COMPUTER-AIDED DESIGN OF SPACE FORMS, Massachusetts Institute of Technology, Cambridge, MA, 1967
• 5: 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]
• 6: Jeffrey M. Lane and Richard F. Riesenfeld, "A Theoretical Development for the Computer Generation of Piecewise Polynomial Surfaces," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-2, no. 1, pp. 35-46, January 1980.
• 7: M.L.V. Pitteway, "Algorithm for drawing ellipses or hyperbolae with a digital plotter," Computer Journal, vol. 10, no. 3, pp. 282-289, Nov. 1967.
• 8: Vaughan Pratt, Techniques for conic splines, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.151-160, Jul. 1985
• 9: Michael Shantz , Sheue-Ling Lien, Shading bicubic patches, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.189-196, July 1987

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

General Terms:
Algorithms, Design, Theory