University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don FussellParametric CurvesUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 2Parametric Representations3 basic representation strategies:Explicit: y = mx + bImplicit: ax + by + c = 0Parametric: P = P0 + t (P1 - P0)Advantages of parametric formsMore degrees of freedomDirectly transformableDimension independentNo infinite slope problemsSeparates dependent and independent variablesInherently boundedEasy to express in vector and matrix formCommon form for many curves and surfacesUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 3Algebraic RepresentationAll of these curves are just parametric algebraic polynomials expressedin different basesParametric linear curve (in E3)Parametric cubic curve (in E3)Basis (monomial or power)! x = axu3+ bxu2+ cxu + dxy = ayu3+ byu2+ cyu + dyz = azu3+ bzu2+ czu + dz! x = axu + bxy = ayu + byz = azu + bz! p(u) = au + b! p(u) = au3+ bu2+ cu + d! u 1[ ]u3u2u 1[ ]University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 4Hermite Curves12 degrees of freedom (4 3-d vector constraints)Specify endpoints and tangent vectors at endpointsSolving for the coefficients:! p(0) = dp(1) = a + b + c + dpu(0) = cpu(1) = 3a + 2b + c! a = 2p(0) " 2p(1) + pu(0) + pu(1)b = "3p(0) + 3p(1) " 2pu(0) " pu(1)c = pu(0)d = p(0)! pu(u) "dpdu(u)••pu(0)u = 0u = 1p(0)p(1)pu(1)University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 5Hermite Curves - Hermite BasisSubstituting for the coefficients and collecting terms givesCallthe Hermite blending functions or basis functionsThen! p(u) = (2u3" 3u2+ 1)p(0) + ("2u3+ 3u2)p(1) + (u3" 2u2+ u)pu(0) + (u3" u2)pu(1)! H1(u) = (2u3" 3u2+ 1)H2(u) = ("2u3+ 3u2)H3(u) = (u3" 2u2+ u)H4(u) = (u3" u2)! p(u) = H1(u)p(0) + H2(u)p(1) + H3(u)pu(0) + H4(u)pu(1)H1H2H3H4nUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 6Hermite Curves - Matrix FormPutting this in matrix formMH is called the Hermite characteristic matrixCollecting the Hermite geometriccoefficients into a geometry vector B,we have a matrix formulation forthe Hermite curve p(u)! H = H1(u) H2(u) H3(u) H4(u)[ ]= u3u2u 1[ ]2 "2 1 1"3 3 "2 "10 0 1 01 0 0 0# $ % % % % & ' ( ( ( ( = UMH! B =p(0)p(1)pu(0)pu(1)" # $ $ $ $ % & ' ' ' ' p(u) = UMHBUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 7Hermite and Algebraic FormsMH transforms geometric coefficients(“coordinates”) from the Hermite basis to thealgebraic coefficients of the monomial basis! A =abcd" # $ $ $ $ % & ' ' ' ' p(u) = UA = UMHBA = MHBB = MH(1A! MH"1=0 0 0 11 1 1 10 0 1 03 2 1 0# $ % % % % & ' ( ( ( (University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 8Cubic Bézier CurvesSpecifying tangent vectors at endpoints isn’t always convenient forgeometric modelingWe may prefer making all the geometric coefficients points, let’s callthem control points, and label them p0, p1, p2, and p3For cubic curves, we can proceed by letting the tangents at theendpoints for the Hermite curve be defined by a vector between a pairof control points, so that:! p(0) = p0p(1) = p3pu(0) = k1(p1" p0)pu(1) = k2(p3" p2)p0p1p2•p3p(u)k2k1University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 9Cubic Bézier CurvesSubstituting this into the Hermite curve expressionand rearranging, we getIn matrix form, this is! p(u) = 2 " k1( )u3+ 2k1" 3( )u2" k1u + 1[ ]p0+ k1u3" 2k1u2+ k1u[ ]p1+ "k2u3+ k2u2[ ]p2+ k2" 2( )u3+ 3 " k2( )u2[ ]p3! p(u) = UMBP! MB=2 " k1k1"k2k2" 22k1" 3 "2k1k23 " k2"k1k10 01 0 0 0# $ % % % % & ' ( ( ( ( ! P =p0p1p2p3" # $ $ $ $ % & ' ' ' 'University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 10Cubic Bézier CurvesWhat values should we choose for k1 and k2?If we let the control points be evenly spaced in parameterspace, then p0 is at u = 0, p1 at u = 1/3, p2 at u = 2/3 and p3at u = 1. Then and k1 = k2 = 3, giving a nice symmetric characteristicmatrix:So! MB="1 3 "3 13 "6 3 0"3 3 0 01 0 0 0# $ % % % % & ' ( ( ( ( ! p(u) = "u3+ 3u2" 3u + 1( )p0+ 3u3" 6u2+ 3u( )p1+ "3u3+ 3u2( )p2+ u3p3! pu(0) = (p1" p0) (1/3 " 0) = 3(p1" p0)pu(1) = (p3" p2) (1" 2 /3) = 3(p3" p2)University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 11General Bézier CurvesThis can be rewritten asNote that the binomial expansion of(u + (1 - u))n is This suggests a general formula for Bézier curvesof arbitrary degree! p(u) = (1" u)3p0+ 3u(1" u)2p1+ 3u2(1" u)p2+ u3p3=3i# $ % & ' ( ui1" u( )3"ipii= 03)! ni" # $ % & ' ui1( u( )n(ii= 0n)! p(u) =ni" # $ % & ' ui1( u( )n(ipii= 0n)University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 12General Bézier CurvesThe binomial expansion gives the Bernstein basis (or Bézier blendingfunctions) Bi,n for arbitrary degree Bézier curvesOf particular interest to us (in addition to cubic curves):Linear: p(u) = (1 - u)p0 + up1Quadratic: p(u) = (1 - u)2p0 + 2u(1 - u)p1 + u2p2! p(u) =ni" # $ % & ' ui1( u( )n(ipii= 0n)Bi,n(u) =ni" # $ % & ' ui1( u( )n(ip(u) = Bi,n(u) pii= 0n)Cubic BézierBlending FunctionsB0,3B1,3B2,3B3,3nUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 13Bézier Curve PropertiesInterpolates end control points, not middle onesStays inside convex hull of control pointsImportant for many algorithmsBecause it’s a convexcombination of points,i.e. affine with positive weightsVariation diminishingDoesn’t “wiggle” more than control polygonp0p1p2p3University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 14Rendering Bézier CurvesWe can obtain a point on a Bézier curve by just evaluatingthe function for a given value of uFastest way, precompute A=MBP once control points areknown, then evaluate p(ui)=[ui3 ui2 ui 1]A, i = 0,1,2,…,nfor n fixed increments of uFor better numerical stability, take e.g. a quadratic curve(for simplicity) and rewriteThis is just a linear interpolation of two points, each ofwhich was obtained by interpolating a pair of adjacentcontrol points! p(u) = (1" u)2p0+ 2u(1" u)p1+ u2p2= (1" u)[(1" u)p0+ up1] + u[(1" u)p1+ up2]University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 15de
View Full Document
Unlocking...