A recursive evaluation algorithm for a class of Catmull-Rom splines

ABSTRACT

It is known that certain Catmull-Rom splines [7] interpolate their control vertices and share many properties such as affine invariance, global smoothness, and local control with B-spline curves; they are therefore of possible interest to computer aided design. It is shown here that another property a class of Catmull-Rom splines shares with B-spline curves is that both schemes possess a simple recursive evaluation algorithm. The Catmull-Rom evaluation algorithm is constructed by combining the de Boor algorithm for evaluating B-spline curves with Neville's algorithm for evaluating Lagrange polynomials. The recursive evaluation algorithm for Catmull-Rom curves allows rapid evaluation of these curves by pipelining with specially designed hardware. Furthermore it facilitates the development of new, related curve schemes which may have useful shape parameters for altering the shape of the curve without moving the control vertices. It may also be used for constructing transformations to Bézier and B-spline form.

REFERENCES

• 1: Phillip Jerome Barry, Urn models, recursive curve schemes, and computer aided geometric design, 1987
• 2: Barry, Phillip J. and Goldman, Ronald N,, Piecewise polynomial recursive curve schemes and computer aided geometric design, in prepexation.
• 3: Brian Andrew Barsky, The beta-spline: a local representation based on shape parameters and fundamental geometric measures, 1981
• 4: de Boor, Carl, On calculating with B-splines, Journal of Approzimation Theory 6, (1972), 50-62.
• 5: de Boor, Carl, A Pyaetical Guide to Splines, Springer-Verlag, New York, 1978.
• 6: Burden, Richard L., Faires, J.Douglas, and Reynolds, Albert C., Numerical Analysis, Prrindle, Weber, and Schmidt, Boston, 1978.
• 7: Catmull, Edwin and Rom, Raphael, A class of local interpolating splines, in R.E. Barnhill and R.F. Riesenfe}d (eds.) Computer Aided Geometric Design, Academic Press, New York, 1974, 317-326.
• 8: Cox, M.G., The numerical evaluation of B-splines, J. Inst. Maths. Applies. 10, (1972), 134-149.
• 9: DeRose, Anthony D. and Barsky, Brian A., Geometric continuity and shape parameters for Catmull-Rom splines, submitted for publication.
• 10: DeRose, Anthony D. and Holman, Thomas J., The triangle: a multiprocessor architecture for fast curve and surface generation, submitted for publication.
• 11: Overhauser, A.H., Analytic definition of curves and surfaces by parabolic blending, Scientific Research Staff Publication, Ford Motor Co., Detroit, Michigan, 1968.
• 12: Ramshaw, Lyle, Blossoming: A Connect-the-Dots Approach to Splines, Digital Systems Research Center, Palo Alto, California, 1987.
• 13: Richard Franklin Riesenfeld, Applications of b-spline approximation to geometric problems of computer-aided design., 1973

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      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: Splines; Curve, surface, solid, and object representations

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
B-spline, Catmull-Rom spline, Lagrange polynomial, Neville's algorithm, de Boor algorithm, recursive evaluation algorithm