Rendering cubic curves and surfaces with integer adaptive forward differencing

ABSTRACT

For most compute environments, adaptive forward differencing is much more efficient when performed using integer arithmetic than when using floating point. Previously low precision integer methods suffered from serious precision problems due to the error accumulation inherent to forward differencing techniques. This paper proposes several different techniques for implementing adaptive forward differencing using integer arithmetic, and provides an error analysis of forward differencing which is useful as a guide for integer AFD implementation. The proposed technique using 32 bit integer values is capable of rendering curves having more than 4K forward steps with an accumulated error of less than one pixel and no overflow problems. A hybrid algorithm employing integer AFD is proposed for rendering antialiased, texture-mapped bicubic surfaces.

REFERENCES

• 1: Salim Abi-Ezzi, '~The Graphical Processing of NURB Surfaces," Industrial Associate Review Summary, November 1988. Rensselaer Design Research Center, Rensselaer Polytechnic Institute
• 2: 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]
• 3: 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
• 4: Edwin Earl Catmull, A subdivision algorithm for computer display of curved surfaces., 1974
• 5: George M. Chaikin, "An Algorithm for High Speed Curve Generation," Computer Graphics and Image Processing, vol. 3, pp. 346-349, 1974.
• 6: Robert Cook, Patch Work, Tech. Memo 118, Computer Div., Lucasfilm Ltd., June 1985.
• 7: Robert L. Cook , Loren Carpenter , Edwin Catmull, The Reyes image rendering architecture, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.95-102, July 1987
• 8: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 9: R. Victor Klassen, Drawing antialiased cubic spline curves, ACM Transactions on Graphics (TOG), v.10 n.1, p.92-108, Jan. 1991 [doi>10.1145/99902.99906]
• 10: 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]
• 11: 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, pp. 35-46, 1980.
• 12: 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
• 13: 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.
• 14: Vaughan Pratt, Techniques for conic splines, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.151-160, Jul. 1985
• 15: Alyn P. Rockwood, Generalized scanning technique for display of parametrically defined surfaces, IEEE Computer Graphics and Applications, v.7 n.9, p.15-26, Aug. 1987
• 16: Michael Shantz , Sheue-Ling Lien, Shading bicubic patches, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.189-196, July 1987
• 17: Micheal Shantz , Sheue-Ling Chang, Rendering trimmed NURBS with adaptive forward differencing, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.189-198, Aug. 1988

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

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: Curve, surface, solid, and object representations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture; Visible line/surface algorithms

General Terms:
Algorithms, Design