Spline Curves - Clemson University

1 Chapter 14 Spline CurvesAspline curveis a mathematical representation for which it is easy to buildan interface that will allow a user to design and control the shape of complexcurves and surfaces. The general approach is that the user enters a sequenceof points, and a curve is constructed whose shape closely follows this points are calledcontrol points. A curve that actually passes through eachcontrol point is called aninterpolating curve; a curve that passes near to thecontrol points but not necessarily through them is called anapproximating curveapproximating curvethe points are calledcontrol pointsOnce we establish this interface, then to change the shape of the curve we justmove the control easiest example to help us to understand how thisworks is to examine a curve that is like the graph of afunction, likey=x2.

2 This is a special case of a polyno-mial 14. Spline Polynomial curvesPolynomials have the general form:y=a+bx+cx2+dx3+..Thedegreeof a polynomial corresponds with the highest coefficient that is non-zero. For example ifcis non-zero but coefficientsdand higher are all zero,the polynomial is of degree 2. The shapes that polynomials can make are asfollows:degree 0:Constant, onlyais :y= constant, uniquely defined by one 1:Linear,bis highest non-zero :y= 1 + line, uniquely defined by two 2:Quadratic,cis highest non-zero :y= 1 2x+ parabola, uniquely defined by three 3:Cubic,dis highest non-zero.

3 Y= 1 7/2x+ 3 cubic curve (which can have an inflection, atx= 0 in this example),uniquely defined by four degree three polynomial known as acubic polynomial is the one thatis most typically chosen for constructing smooth Curves in computer is used because1. it is the lowest degree polynomial that can support an inflection so wecan make interesting Curves , and2. it is very well behaved numerically that means that the Curves willusually be smooth like this:and not jumpy like this:. POLYNOMIAL CURVES89So, now we can write a program that constructs cubic Curves .

4 The user entersfour control points, and the program solves for the four coefficientsa,b,canddwhich cause the polynomial to pass through the four control points. Below, wework through a specific the interface would allow the user to entercontrol points by clicking them in with the example, say the user has entered control points( 1,2),(0,0),(1, 2),(2,0) as indicated by the dots inthe figure to the , the computer solves for the coefficientsa,b,c,dand might draw the curveshown going through the control points, using a loop something like this:glBegin(GLLINESTRIP);for(x = -3; x <= 3; x += )glVertex2f(x,a+b* x +c* x * x +d* x * x * x);glEnd().

5 Note that the computer is not really drawing the curve. Actually, all it is doingis drawing straight line segments through a sampling of points that lie on thecurve. If the sampling is fine enough, the curve will appear to the user as acontinuous smooth solution fora,b,c,dis obtained by simultaneously solving the 4 linearequations below, that are obtained by the constraint that the curve must passthrough the 4 points:general form:a+bx+cx2+dx3=ypoint( 1,2):a b+c d= 2point(0,0):a= 0point(1, 2):a+b+c+d= 2point(2,0):a+ 2b+ 4c= 8d= 0 This can be written in matrix formMa=y,90 CHAPTER 14.

6 Spline CURVESor (one row for each equation) 1 1 1 1100011111248 abcd = 20 20 The solution isa=M 1y,which is hard to do on paper but easy to do on the computer using matrix andvector example, using the code I have provided, you could write:Vector a(4), y(4);Matrix M(4, 4);y[0] = 2; y[1] = 0; y[2] = -2; y[3] = 0;// fill in all rows of MM[0][0] = 1; M[0][1] = -1; M[0][2] = 1; M[0][3] = -1;// etc. to fill all 4 rowsa = () * y;After this computation,a[0]contains the value ofa,a[1]ofb,a[2]ofcanda[3]ofd. For this example the correct values area= 0,b= 223,c= 0, andd= Piecewise polynomial curvesIn the previous section, we saw how four control points can define a cubicpolynomial curve, allowing the solution of four linear equations for the fourcoefficients of the curve.

7 Here we will see how more complex Curves can bemade using two new ideas:1. construction of piecewise polynomial Curves ,2. parameterization of the we wanted to make the curve shown to the know that a single cubic curve can only have one in-flection point, but this curve has three, marked withO s. We could make this curve by entering extra controlpoints and using a 5th degree polynomial, with six coef-ficients, but polynomials with degree higher than threetend to be very sensitive to the positions of the controlpoints and thus do not always make smooth PIECEWISE POLYNOMIAL CURVES91 The usual solution to this problem in computer graphics and computer aideddesign is to construct a complex curve, with a high number of inflection points,by piecing together several cubic Curves :+Here is one way that this can be done.

8 Let each pair of control points representone segment of the curve. Each curve segment is a cubic polynomial with itsown coefficients:x0x9x8x7x6x5x4x3x2x1f0(x)f8 (x)f1(x)(x5,y5)(x6,y6)yxIn this example, the ten control points have ascending values for thexcoordi-nate, and are numbered with indices 0 through 9. Between each control pointpair is a function, which is numbered identically to the index of its leftmostpoint. In general,fi(x) =ai+bix+cix2+dix3is the function representing thecurve between control pointsiandi+ each curve segment is represented by a cubic polynomial function, wehave to solve for four coefficients for each segment.

9 In this example we have4 9 = 36 coefficients to solve for. How shall we do this?92 CHAPTER 14. Spline CURVESHere is one way:1. We require that each curve segment pass through its control points. Thus,fi(xi) =yi, andfi(xi+1) =yi+ enforcesC0continuity that is,where the Curves join they meet each that for each curve segment this gives us two linear equations:ai+bixi+cix2i+dix3i=yi, andai+bixi+1+cix2i+1+dix3i+1=yi+1. But tosolve for all four coefficients we need two more equations for each We require that the curve segments have the same slope where they jointogether.

10 Thus,f i(xi+1) =f i+1(xi+1).This enforcesC1continuity that is that slopes match where the Curves that:fi(x) =ai+bix+cix2+dix3, so thatf i(x) =bi+ 2cix+ gives us one more linear equation for each segmentbi+ 2cixi+1+ 3dix2i+1=bi+1+ 2ci+1xi+1+ 3di+1x2i+1orbi+ 2cixi+1+3dix2i+1 bi+1 2ci+1xi+1 3di+1x2i+1= To get the fourth equation we require that the curve segments have thesame curvature where they join together. Thus,f i(xi+1) =f i+1(xi+1).This enforcesC2continuity that curvatures match at the :f i(x) = 2ci+ 6dixAndC2continuity gives us the additional linear equation that we need2ci+ 6dixi+1= 2ci+1+ 6di+1xi+1or 2ci+ 6dixi+1 2ci+1 6di+1xi+1= 04.