1112. C2-interpolating curves2ReadingOptional Bartels, Beatty, and Barsky. An Introduction to Splines for use in Computer Graphics and Geometric Modeling, 1987. (See course reader.)23Parametric curve review4Parametric curvesWe use parametric curves, Q(u)=(x(u),y(u)),where x(u) and y(u) are cubic polynomials:Advantages: easy (and efficient) to compute “well behaved” infinitely differentiableWe also assume that u varies from 0 to 1:HGuFuEuuyDCuBuAuux+++=+++=2323)()())0(),0(( yx))1(),1(( yx35Various ways to set A,B,C,D0) Directly – non-intuitive; not very useful. 1) Set positions and derivatives of endpoints:“Hermite Curve”2) Use “control points” that indirectly influencethe curve:“Bezier curve”:- interpolatesendpoints- does notinterpolatemiddlecontrol points“B-spline”- does notinterpolateANYcontrol pointsDCuBuAuux +++=23)(6Splines = join cubic curvesConsiderationsWhat kind of continuity at join points (“knots”)?C0 = valueC1 = first derivativeC2 = second derivativeHow do control points work?B-spline47Spline summaryJoined Hermite curves:C1 continuityInterpolates control pointsB-splines:C2 continuityDoes not interpolate control pointsCan we get…C2 continuityInterpolates control pointsThat’s what we’ll talk about towardsthe end of this lecture.But first, some other useful tips.8Useful tips for Bézier curves59Displaying Bézier curvesHow could we draw one of these things?It would be nice if we had an adaptive algorithm, that would take into account flatness.DisplayBezier( V0, V1, V2, V3 ) beginif ( FlatEnough( V0, V1, V2, V3 ) )Line( V0, V3 );elsesomething;end;10Subdivide and conquerDisplayBezier( V0, V1, V2, V3 ) beginif ( FlatEnough( V0, V1, V2, V3 ) )Line( V0, V3 );elseSubdivide(V[]) ⇒ L[], R[]DisplayBezier( L0, L1, L2, L3 );DisplayBezier( R0, R1, R2, R3 );end;611Testing for flatnessCompare total length of control polygon to length of line connecting endpoints:01 12 23031VV VV VVVVε−+− + −<+−12Simple splinesJoin several Bezier curves:- Make derivatives match (Hermite curve)- You still have ability to pick what thatmatched derivative is.713Catmull-Rom splinesIf we set each derivative to be one half of the vector between the previous and next controls, we get a Catmull-Rom spline.This leads to:==+==0111 2022 31321616(-)-(-)VPVP PPVP PPVP14We can give more control by exposing the derivative scale factor as a parameter:The parameter τcontrols the tension. Catmull-Rom uses τ= 1/2. Here’s an example with τ=3/2.Tension controlττ==+==0111 2022 313233(-)-( -)VPVP PPVP PPVP815Tips for B-splinesB-spline:- C2 continuity- does not interpolate any ctrl points16Endpoints of B-splinesWe can see that B-splines don’t interpolate thecontrol points.It would be nice if we could at least control the endpoints of the splines explicitly.There’s a trick to make the spline begin and end at control points by repeating them.In the example below, let’s force interpolation of the last endpoint: (use endpoint 3 times)012345BBBBBB917Tips for animator project18What if we want a closed curve, i.e., a loop?With Catmull-Rom and B-spline curves, this is easy:Closing the loop1019C2 interpolating curves20C2interpolating splinesHow can we keep the C2continuity we get with B-splines but get interpolation, too?Let’s start with connected cubic curves.We’ll think of each cubic segment as a Hermitecurve, for which we get to set the position and derivative of the endpoints.That leaves us with a spline that’s C0 and C1:But interestingly, we still get to choose the values of the (shared) first derivatives at the join points.Is there a way to set those derivatives to get other useful properties?1121Find second derivativesSo far, we have:C0, C1 continuityDerivatives are still free, as ‘D0…D4’Compute second derivatives at both sidesof every join point:For P1:For P2:…''0(1)Q =''1(0)Q=''1(1)Q =''2(0)Q=22Match the second derivativesNow, symbolically set the second derivatives tobe equal.For P1…blah(D1, D2, …) = blah2(D1, D2, …)For P2blah(D1, D2, …) = blah2(D1, D2, …)…1223Matching the derivatives, cont.How many equations is this? m-1How many unknowns are we solving for? m+124Not quite done yetWe have two additional degrees of freedom, which we can nail down by imposing more conditions on the curve.There are various ways to do this. We’ll use the variant called natural C2interpolating splines, which requires the second derivative to be zero at the endpoints.This condition gives us the two additional equations we need. At the P0endpoint, it is:At the Pmendpoint, we have:''0(0) 0Q=''1(1) 0mQ−=1325Solving for the derivativesLet’s collect our m+1 equations into a single linear system:It’s easier to solve than it looks.See the notes from Bartels, Beatty, and Barsky for details.010120231121213( )1413( )14 13( ) 1413( )123( )TTTTTTTTmmmTTmmmDPPDPPDPPDPPDPP−−−⎡⎤⎡ ⎤−⎡⎤⎢⎥⎢ ⎥⎢⎥−⎢⎥⎢ ⎥⎢⎥⎢⎥⎢ ⎥⎢⎥−=⎢⎥⎢ ⎥⎢⎥⎢⎥⎢ ⎥⎢⎥⎢⎥⎢ ⎥⎢⎥−⎢⎥⎢ ⎥⎢⎥−⎢⎥⎢⎥⎢ ⎥⎣⎦⎣⎦⎣ ⎦OMM26C2interpolating splineOnce we’ve solved for the real Dis, we can plug them in to find our Bézier control points and draw the final spline:Have we lost anything?=> Yes, local control.1427Next time: Subdivision curvesBasic idea:Represent a curve as an iterativealgorithm, rather than as an explicitfunction.Reading:• Stollnitz, DeRose, and Salesin. Wavelets forComputer Graphics: Theory and Applications,1996, section 6.1-6.3, A.5.[Course reader pp. 248-259 and pp.
View Full Document
Unlocking...