Integer forward differencing of cubic polynomials: analysis and algorithms

ABSTRACT

Two incremental cubic interpolation algorithms are derived and analysed. Each is based on a known linear interpolation algorithm and modified for third order forward differencing. The tradeoff between overflow avoidance and loss of precision has made forward differencing a method which, although known to be fast, can be difficult to implement. It is shown that there is one particular family of curves which represents the worst case, in the sense that if a member of this family can be accurately drawn without overflow, then any curve which fits in the bounding box of that curve can be. From this the limitations in terms of step count and screen resolution are found for each of the two algorithms.

REFERENCES

• 1: 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
• 2: BOOTHROYD, J., AND HAMII.TON, P.A. Exactly reversible plotter paths. Australian Comput. J. 2, 1 (1970), 20-21.
• 3: BnV:SV:Nn^M, J. E. Algorithm for computer control of a digital plotter. IBM Syst. J. 4, 1 (1965), 25-30.
• 4: S.-L. Chang , M. S. R. Rocchetti, Rendering cubic curves and surfaces with integer adaptive forward differencing, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.157-166, July 1989
• 5: Dan Field, Incremental linear interpolation, ACM Transactions on Graphics (TOG), v.4 n.1, p.1-11, Jan. 1985 [doi>10.1145/3973.3976]
• 6: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 7: 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]
• 8: 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
• 9: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 10: Nv;w~aAx, W. M., AND SPR()ULL, R.F. Principles of Interactive Computer Graphics. 2nd ed, McGraw-Hill, New York, 1979.
• 11: David F. Rogers, Procedural elements for computer graphics, McGraw-Hill, Inc., New York, NY, 1984
• 12: Dino Schweitzer , Elizabeth S. Cobb, Scanline rendering of parametric surfaces, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.265-271, July 1982
• 13: Thomas W. Sederberg , Alan K. Zundel, Scan line display of algebraic surfaces, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.147-156, July 1989
• 14: 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
• 15: WANt;, G. The subdivision method for finding the intersection between two Bdzier curves or surfaces. Zhej'iang University Journal, Special Issue on Computational Geometry spline, 1984, (in Chinese).
• 16: Turner Whitted, A scan line algorithm for computer display of curved surfaces, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.26, August 1978

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations; Geometric algorithms, languages, and systems

General Terms:
Algorithms

Keywords:
Be´zier curves, parametric curve plotting