Curves and SplinesOutline•Hermite Splines•Catmull-Rom Splines•Bezier Curves•Higher Continuity: Natural and B-Splines•Drawing Splines3Modeling Complex Shapes• We want to build models of very complicated objects• An equation for a sphere is possible, but how about an equation for a telephone, or a face?• Complexity is achievedusing simple pieces– polygons, parametric curvesand surfaces, or implicit curves and surfaces– This lecture: parametriccurves4What Do We Need From Curvesin Computer Graphics?• Local control of shape (so that easy to build and modify)• Stability• Smoothness and continuity• Ability to evaluate derivatives• Ease of renderingDemoCurve Usage Demo5Curve Representations• Explicit: y = f(x)– Easy to generate points– Must be a function: big limitation—vertical lines?bmxy+=xy6Curve Representations• Explicit: y = f(x)– Easy to generate points– Must be a function: big limitation—vertical lines?bmxy+=xy•Implicit: f(x,y) = 0+Easy to test if on the curve–Hard to generate points0222=!+ ryxxy7Curve Representations• Explicit: y = f(x)+ Easy to generate points– Must be a function: big limitation—vertical lines?bmxy+=xy•Implicit: f(x,y) = 0+Easy to test if on the curve–Hard to generate points0222=!+ ryxxy•Parametric: (x,y) = ( f(u), g(u))+Easy to generate points)sin,(cos),( uuyx=u=0u=""""/2u= """"8Parameterization of a Curve• Parameterization of a curve: how a change in u moves you along a given curve in xyz space. • There are an infinite number of parameterizations of a given curve. Slow, fast, speed continuous or discontinuous, clockwise (CW) or CCW…9Polynomial Interpolation• An n-th degree polynomial fits a curve to n+1 points– called Lagrange Interpolation– result is a curve that is too wiggly, change to any control point affects entire curve (nonlocal) – this method is poor• We usually want the curve to be as smooth as possible– minimize the wiggles– high-degree polynomials are badLinear InterpolationChalkboardSpline InterpolationSpine Interpolation Demo10Splines: Piecewise Polynomials• A spline is a piecewise polynomial - many low degree polynomials are used to interpolate (pass through) the control points• Cubic piecewise polynomials are the most common:– piecewise definition gives local control11Piecewise Polynomials• Spline: lots of little polynomials pieced together• Want to make sure they fit together nicelyContinuous in positionContinuous in position and tangent vectorContinuous in position, tangent, and curvature12Splines• Types of splines:– Hermite Splines– Catmull-Rom Splines– Bezier Splines– Natural Cubic Splines– B-Splines– NURBS7Hermite Curves• Cubic Hermite SplinesThat is, we want a way to specify the end points and theslope at the end points!PoP1P213Splineschalkboard14The Cubic Hermite Spline Equationcontrol matrix(what the user gets to pick)basispoint thatgets drawn• Using some algebra, we obtain:[ ]!!!!"#$$$$%&!!!!!!"#$$$$%&""""=21212300010100123311221)(ppppuuuup• This form typical for splines– basis matrix and meaning of control matrix change with the spline type15The Cubic Hermite Spline Equationcontrol matrix(what the user gets to pick)basispoint thatgets drawn• Using some algebra, we obtain:[ ]!!!!"#$$$$%&!!!!!!"#$$$$%&""""=21212300010100123311221)(ppppuuuup!!!!"#$$$$%&!!!!!!!"#$$$$$%&"+"+"+"=212123232323232132)(ppppuuuuuuuuuup4 Basis FunctionsT16Every cubic Hermite spline is a linear combination (blend)of these 4 functions!!!!"#$$$$%&!!!!!!!"#$$$$$%&"+"+"+"=212123232323232132)(ppppuuuuuuuuuup4 Basis FunctionsFour Basis Functions for Hermite splinesTu17Piecing together Hermite Curves• It's easy to make a multi-segment Hermite spline– each piece is specified by a cubic Hermite curve– just specify the position and tangent at each “joint”– the pieces fit together with matched positions and first derivatives– gives C1 continuity• The points that the curve has to pass through are called knots or knot pointsOutline•Hermite Splines•Catmull-Rom Splines•Bezier Curves•Higher Continuity: Natural and B-Splines•Drawing SplinesProblem with Hermite Splines?•Must explicitly specify derivatives at each endpoint!•How can we solve this?8Catmull-Rom Splines• Use for the roller-coaster assignment• With Hermite splines, the designer must specify all the tangent vectors• Catmull-Rom: an interpolating cubic spline with built-in C1continuity.PoP1P2tangent at pi = s(pi+1 - pi-1)18Catmull-Rom Splines• Use for the roller-coaster (next programming assignment)• With Hermite splines, the designer must arrange for consecutive tangents to be collinear, to get C1continuity. This gets tedious.• Catmull-Rom: an interpolating cubic spline with built-in C1continuity.chalkboard19Catmull-Rom Spline Matrixcontrol vectorCR basisspline coefficients[ ]!!!!"#$$$$%&!!!!"#$$$$%&!!!!!!!=4321230010002332221)(ppppssssssssssuuuup• Derived similarly to Hermite• Parameter s is typically set to s=1/2.20Catmull-Rom Spline Matrix[ ][ ]!!!!"#$$$$%&!!!!"#$$$$%&!!!!!!!=444333222111230010002332221zyxzyxzyxzyxssssssssssuuuzyxcontrol vectorCR basisspline coefficients9Catmull-Rom Splines• Use for the roller-coaster assignment• With Hermite splines, the designer must specify all the tangent vectors• Catmull-Rom: an interpolating cubic spline with built-in C1continuity.10Catmull-Rom Spline Matrixcontrol vectorCR basis[ ]!!!!"#$$$$%&!!!!"#$$$$%&!!!!!!!=4321230010002332221)(ppppssssssssssuuuup• Derived similarly to Hermite• Parameter s is typically set to s=1/2.11Cubic Curves in 3D• Three cubic polynomials, one for each coordinate– x(u) = axu3+bxu2+cxu+dx– y(u) = ayu3+byu2+cyu+dy– z(u) = azu3+bzu2+czu+dz• In matrix notation[ ][ ]!!!!"#$$$$%&=zyxzyxzyxzyxdddcccbbbaaauuuuzuyux 1)()()(2312Catmull-Rom Spline Matrix in 3D[ ][ ]!!!!"#$$$$%&!!!!"#$$$$%&!!!!!!!=444333222111230010002332221)()()(zyxzyxzyxzyxssssssssssuuuuzuyuxcontrol vectorCR basisOutline•Hermite Splines•Catmull-Rom Splines•Bezier Curves•Higher Continuity: Natural and B-Splines•Drawing SplinesProblem withCatmull-Rom Splines?•No control of derivatives at endpoints!•How can we solve this?•We want something intuitive.13Bezier Curves*• Another variant of the same game• Instead of endpoints and tangents, four control points– points P0 and P3 are on the curve: P(u=0) = P0, P(u=1) = P3 – points P1 and P2 are off the curve– P'(u=0) = 3(P1-P0),
View Full Document
Unlocking...