Piecewise Polynomial Interpolation

  The full text may be freely downloaded.
...
NEW Material. (as of Feb 21 2014)  See below .
...
   This is both a study of the fundamentals described in simple terms as well as a reference showing many types of Polynomial Interpolation - including many common types and some developed by the author.  It also shows some techniques not seen elsewhere. 
Linear interpolation is looked at carefully and shown is as the basis for all more advanced types using only Algebra.  Only after understanding how adding squared and cubed terms cause smooth curves, are the more advanced curves examined such as Bezier, Catmul-Rom, and b-spline.  More advanced mathematical concepts and notations are kept to a minimum.  Some additional techniques that are suggested by the mathematics and that the author has not seen elsewhere are examined.   A reference is also included with all the most common curve drawing methods and includes drawings to allow comparison with other types.
Why I wrote it (.txt)  Click Here.  
Overview  (.txt)  Click Here. 
  
Interpolation and Curves for Graphics Text.
A Study of Piecewise Polynomial Interpolation Fundamentals And Curve Reference.
   Full Text last revision 2 April 2011
 Full Text (PDF) - Click Here
 Appendix (PDF)  - Click Here

Supplemental information that I didn't get added to the book. 
   The following documents have information on things I have not incorporated in the book, but provide here in the form in which I investigated them. The spreadsheets actually implement the techniques and show the behaviors in graphs.  While they may not be highly significant methods, they were interesting and I include them as possible solutions to some particular problem, or as a seed for another algorithm.  If there is no "formulas" document, the interested reader must extract the formulas from the Excel spreadsheets.
.
   Approximating the SINE function with a method based on the Coons "linear quintic function", Coons (1977), brought to my attention by Faux & Pratt (1979).  This quintic function has zero first and second derivatives at the ends to add a tension-like parameter to an existing curve.  It is a generalized extension of the concept of the Hermite h3 and h4 functions.
Coons SINE formulas and demo spreadsheet CLICK HERE 
.
.
   These next two came to my attention from postings on c.g.a. and subsequent email exchanges with the respective authors. 
.
.   If you want to draw a 'smooth curve' through some points and only have a cubic Bezier curve routine, this is another way to do it. This was from an exchange I had with Maxin on c.g.s. in 2003.
Maxim Shemanarev's method of drawing a curve through a series of points using cubic Bezier curves.  While a transformation of control points described in the book  (Ch 14 & A3)  may be a preferred technique, this uses a unique method of calculating the two inner control points of a cubic Bezier from the other control points to yield a curve through all the given control points. While similar to the Catmul-Rom, the curve bows outward more for close spaced points and less for widely spaced points.  This curve actually approaches a limit for adjacent points that move out to infinity, where the Catmul-Rom curve also approaches infinity. It is essentially a general form of the K-B with a different tangent parameter at each end.   It also degrades to Simple Cubic when Smoothness = 0.  I only made algebraic simplification to the equations that Maxim provided. I regret that I, only now, Feb 2014, found out that Maxim passed away in November 2013 and am unable to tell him I wanted to include this in my book and now provide it here.
  Maxim formulas CLICK HERE.
  Maxim demo spreadsheet CLICK HERE.  
 .
   Dylan Miller's method approximates an arbitrary circular arc with a cubic Bezier segment.  The start and end points on the arc are specified along with the axis crossings for the complete circle or ellipse it approximates.
  Dylan formulas CLICK HERE.
. Dylan demo spreadsheet CLICK HERE.
.
References. 
.
- Bartels R.H., Beatty J.C., Barsky B.A., (1987), ' An Introduction to Splines for use in Computer Graphics and Geometric Modeling', Morgan Kaufmann.
.
- Coons S.A. (1977), 'Modification of the Shape of Piecewise Curves', Computer Aided Design, 9, 3, 178-180.
.
- Faren G., (1992), 'Curves and Surfaces for Computer Aided Geometric Design', 3rd, Academic Press.
.
- Faux I.D.  and Pratt M.J. (1979), 'Computational Geometry for Design and Manufacture', Wiley, pg. 196.
.
- Foley J.D., van Dam A., Feiner S.K., Hughs J.F. (1990),' Computer Graphics Principles and Practice', 2nd.
.
- Kochanek D. and Bartels R.H., (1984), 'Interpolating Splines With Local Tension, Continuity and Bias Controls', Computer Graphics Vol. 18 Number 2, May 1984 Quarterly report, ACM SIGGRAPH
.
- Mortenson M.E., (1995), 'Geometric Transformations', Industrial Press.

 

 The addition of the Coons, Shemanarev and Miller algorithms is most likely  the last information for my book.  While there are a few curve sample Figures that have not been added to the Appendix, all the information needed was provided to produce them as well as comments on behavior.

NOTE:   While comments are appreciated, because of the time laps since I did this study I won't be able to engage in deep discussions on much of this, but welcome questions that I will do my best to answer.

......... This page last updated February 21 2014 .....................

 
Steve N.