Cubic CurvesCSE167: Computer GraphicsInstructor: Steve RotenbergUCSD, Fall 2005Project 3Render a smooth, cubic surface by tessellating it into a set of trianglesDue November 17Polynomial FunctionsLinear:Quadratic:Cubic:( )( )( )dctbtattfcbtattfbattf+++=++=+=232Vector Polynomials (Curves)Linear:Quadratic:Cubic:We usually define the curve for 0 ≤ t ≤ 1( )( )( )dcbafcbafbaf+++=++=+=ttttttttt232Linear InterpolationLinear interpolation (Lerp) is a common technique for generating a new value that is somewhere in between two other valuesA ‘value’ could be a number, vector, color, or even something more complex like an entire 3D object…Consider interpolating between two points a and b by some parameter t( ) ( )baba tttL erp +−= 1,,abt=1..0<t<1t=0Bezier CurvesBezier curves can be thought of as a higher order extension of linear interpolationp0p1p0p1p2p0p1p2p3Linear Quadratic CubicBezier Curve FormulationThere are lots of ways to formulate Bezier curves mathematically. Some of these include:de Castlejau (recursive linear interpolations)Bernstein polynomials (functions that define the influence of each control point as a function of t)Cubic equations (general cubic equation of t)Matrix formWe will briefly examine each of theseBezier Curvep0p1p2p3Find the point x on the curve as a function of parameter t:x(t)•de Casteljau AlgorithmThe de Casteljau algorithm describes the curve as a recursive series of linear interpolationsThis form is useful for providing an intuitive understanding of the geometry involved, but it is not the most efficient formde Casteljau Algorithmp0p1p2p3We start with our original set of pointsIn the case of a cubic Bezier curve, we start with four pointsde Casteljau Algorithmp0q0p1p2p3q2q1( )( )( )322211100,,,,,,ppqppqppqtLer ptLerptLerp===de Casteljau Algorithmq0q2q1r1r0( )( )211100,,,,qqrqqrtLerptLerp==de Casteljau Algorithmr1xr0•( )10,, rrx tLerp=Bezier Curvex•p0p1p2p3Recursive Linear Interpolation( )( )( )322211100,,,,,,ppqppqppqtLerptLerptLer p===( )( )211100,,,,qqrqqrtLerptLerp==( )10,, rrx tLerp=3210pppp210qqq10rrx3210ppppExpanding the Lerps( ) ( )( ) ( )( ) ( )( ) ( ) ( )( ) ( )( )( ) ( ) ( )( ) ( )( )( ) ( ) ( ) ( )( ) ( )( )( )( ) ( )( ) ( )( )( )3221211010322121121101003232221211101001111111,,111,,111,,1,,1,,1,,pppppppprrxppppqqrppppqqrppppqppppqppppqtttttttttttttttLerptttttttLerptttttttLerptttLerptttLerptttLerp+−++−−++−++−−−==+−++−−==+−++−−==+−==+−==+−==Bernstein Polynomial Form( ) ( ) ( )( ) ( )( )( )( ) ( )( ) ( )( )( )( ) ( ) ( )( ) ( )( ) ( )33223123023332212033221211033363133131311111111ppppxppppxppppppppxttttttttttttttttttttttttttttt++−++−++−+−=+−+−+−=+−++−−++−++−−−=Cubic Bernstein Polynomials( ) ( )( ) ( )( ) ( ) ( ) ( )( )( )( )( )333233223312330333232131030332231230233336313333363133ttBtttBttttBttttBtBtBtBtBttttttttt=+−=+−=+−+−=+++=++−++−++−+−=ppppxppppxBernstein PolynomialsB33B03B13B23Bernstein Polynomials( )( )( )( )( )( )( )( )( )( ) ( ) ( )( )( )1!!!112212333631331110222221220333233223312330=−=−==+−==+−=+−==+−=+−=+−+−=∑−tBinininttintBttBttBttBtttBtttBttBtttBttttBttttBniiinniBernstein Polynomials( ) ( ) ( )( ) ( )∑=−=−=niiniiinnitBtttintB01pxBernstein polynomial form of a Bezier curve:Bernstein PolynomialsWe start with the de Casteljau algorithm, expand out the math, and group it into polynomial functions of t multiplied by points in the control meshThe generalization of this gives us the Bernstein form of the Bezier curveThis gives us further understanding of what is happening in the curve:We can see the influence of each point in the control mesh as a function of tWe see that the basis functions add up to 1, indicating that the Bezier curve is a convex average of the control pointsCubic Equation Form( ) ( )( ) ( )( ) ( )( ) ( )133363333336313301022103321033223123023ppppppppppxppppx++−++−++−+−=++−++−++−+−=ttttttttttttCubic Equation Form( ) ( )( ) ( )( )( )( )( )010210321023010221033210333633313336333pdppcpppbppppadcbaxppppppppppx=+−=+−=+−+−=+++=++−++−++−+−=ttttttCubic Equation FormIf we regroup the equation by terms of exponents of t, we get it in the standard cubic formThis form is very good for fast evaluation, as all of the constant terms (a,b,c,d) can be precomputedThe cubic equation form obscures the input geometry, but there is a one-to-one mapping between the two and so the geometry can always be extracted out of the cubic coefficientsCubic Matrix Form( )( )( )( )0102103210233336333pdppcpppbppppadcbax=+−=+−=+−+−=+++= ttt[ ]⋅−−−−=⋅=32102300010033036313311ppppdcbadcbax tttCubic Matrix Form[ ][ ]⋅−−−−⋅=⋅−−−−⋅=zyxzyxzyxzyxpppppppppppptttttt333222111000233210230001003303631331100010033036313311xppppxMatrix Form[ ]CtxGBtxx⋅=⋅⋅=⋅−−−−⋅=BezBezzyxzyxzyxzyxppppppppppppttt3332221110002300010033036313311Matrix FormWe can rewrite the equations in matrix formThis gives us a compact notation and shows how different forms of cubic curves can be relatedIt also is a very efficient form as it can take advantage of existing 4x4 matrix hardware support…DerivativesFinding the derivative (tangent) of a curve is easy:cbaxdcbax ++=+++= ttdtdttt 23223[ ] [ ]⋅=⋅=dcbaxdcbax
View Full Document
Unlocking...