#8: Curves and Curved SurfacesCSE167: Computer GraphicsInstructor: Ronen BarzelUCSD, Winter 20061Outline for todaySummary of Bézier curves Piecewise-cubic curves, B-splines Surface Patches2Curves: Summary Use a few control points to describe a curve in space Construct a function x(t) moves a point from start to end of curve as t goes from 0 to 1 tangent to the curve is given by derivative x’(t) We looked at: Linear -- trivial case, just to get oriented Bézier curves -- in particular, cubicp0p1p0p1p2p0p1p2p3Linear Quadratic Cubic3Linear Interpolation: Summary Given two points p0 and p1 “Curve” is line segment between themp0p1t=1..0<t<1t=0 • Three ways of writing expression:!!!!!!!!!x(t) = (1 ! t)p0+ (t)p1…Weighted average of the control pointsx(t) = (p1! p0)t + p0…Polynomial in tx(t) = p0p1[ ]!1 11 0"#$%&'t1"#$%&'…Matrix form4Cubic Bézier Curve: Summary Given four points p0, p1, p2, p3 curve interpolates the endpoints intermediate points adjust shape: “tangent handles” Recursive geometric construction de Casteljau algorithm Three ways to express curve Weighted average of the control points: Bernstein polynomials Polynomial in t Matrix formx•p0p1p2p35 Notice: Weights always add to 1 B0 and B3 go to 1 -- interpolating the endpoints!!!!!!!!!!!!!!!!!!!!x(t) = B0t( )p0+ B1t( )p1+ B2t( )p2+ B3t( )p3The cubic Bernstein polynomials :!!!!!!!!!!!!!!!!!!!! B0t( )= !t3+ 3t2! 3t + 1!!!!!!!!!!!!!!!!!!!! B1t( )= 3t3! 6t2+ 3t!!!!!!!!!!!!!!!!!!!! B2t( )= !3t3+ 3t2!!!!!!!!!!!!!!!!!!!! B3t( )= t3!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Bi(t) = 1"B0(t ) B1(t ) B2(t ) B3(t )Cubic Bézier: Bernstein Polynomials6Cubic Bézier: Polynomial, Matrix, Notation • Polynomial in t :!!!!!!!!x(t ) =!at3+!bt2+!ct + d!a = !p0+ 3p1! 3p2+ p3( )!b = 3p0! 6p1+ 3p2( )!c = !3p0+ 3p1( )d = p0( )•!Matrix form:!!!!!!!!x(t ) = p0p1p2p3[ ]GBez" #$$$ %$$$!1 3 !3 13 !6 3 0!3 3 0 01 0 0 0"#$$$$%&''''BBez" #$$$ %$$$t3t2t1"#$$$$%&''''T&•!(New)!Notation:!!!!!!!!Bez(t,p0,p1,p2,p3) = x (t ) for the given control points7Tangent to Cubic Bézier • Polynomial in t :!!!!!!!!!x (t ) = 3!at2+ 2!bt +!c!a = "p0+ 3p1" 3p2+ p3( )!b = 3p0" 6p1+ 3p2( )!c = "3p0+ 3p1( )d = p0( ) # d!not used in tangent•!Matrix form:!!!!!!!!!x (t ) = p0p1p2p3[ ]GBez" #$$$ %$$$"1 3 "3 13 "6 3 0"3 3 0 01 0 0 0$%&&&&'())))BBez" #$$$ %$$$3t22t10$%&&&&'())))!T&•!Notation:!!!!!!!! Be!z (t,p0,p1,p2,p3) =!x (t ) for the given control points8nth-order Bézier curvex t( )= Bint( )pii = 0n!Bint( )=ni"#$%&'1 ( t( )n (it( )B01t( )= (t + 1 !!!!! B02t( )= t2( 2t + 1!!!!! B03t( )= (t3+ 3t2( 3t + 1B11t( )= t B12t( )= (2t2+ 2t B13t( )= 3t3( 6t2+ 3tB22t( )= t2B23t( )= (3t3+ 3t2B33t( )= t39Evaluate/draw curves by: Sampling uniformly in t Adaptive/Recursive Subdivisionx(0.0)x(0.25)x(0.5)x(0.75)x(t)x(t)x(1.0)10Outline for today Summary of Bézier curvesPiecewise-cubic curves, B-splines Surface Patches11More control points Cubic Bézier curve limited to 4 control points Cubic curve can only have one inflection Need more control points for more complex curves With k points, could define a k-1 order Bézier But it’s hard to control and hard to work with The intermediate points don’t have obvious effect on shape Changing any control point can change the whole curve• Want local support: each control point only influences nearby portion of curve12Piecewise Curves With a large number of points… Construct a curve that is a sequence of simple (low-order) curves end-to-end Known as a piecewise polynomial curve E.g., a sequence of line segments: a piecewise linear curve E.g., a sequence of cubic curve segments: a piecewise cubic curve In this case, piecewise Bézier13Continuity For the whole curve to look smooth, we need to consider continuity: C0 continuity: no gaps. The segments must match at the endpoints C1 continuity: no corners. The tangents must match at the endpoints C2 continuity: tangents vary smoothly. (makes smoother curves.) Note also: G1, G2, etc. continuity• Looks at geometric continuity without considering parametric continuity• Roughly, means that the tangent directions must match, but not the magnitudes• Gets around “bad” parametrizations• Often it’s what we really want, but it’s harder to compute14Constructing a single curve from many Given N curve segments: x0(t), x1(t), …, xN-1(t) Each is parameterized for t from 0 to 1 Define a new curve, with u from 0 to N: Alternate: u also goes from 0 to 1 x(u) =x0(u), 0 ! u ! 1x1(u " 1), 1 ! u ! 2! !xN "1(u " N " 1( )), !!! N " 1 ! u ! N#$%%&%%x(u) = xi(u " i),!!where i = u'()*!! (and x(N ) = xN "1(1))x(u) = xi(Nu ! i),!!where i = Nu"#$%15 Given N+1 points p0, p1, …, pN Define curve: N+1 points define N linear segments x(i)=pi C0 continuous by construction G1 at pi when pi-1, pi, pi+1 are collinear C1 at pi when pi-pi-1 = pi+1-piPiecewise-Linear curvex(u) = Lerp(u ! i,pi,pi +1),!!!!!!!!!!!i " u " i + 1= (1 ! u + i)pi+ (u ! i)pi+1,!!!i = u#$%&p0p1p2p3p4p5p6x(1.5)x(5.25)x(2.9)16Piecewise Bézier curve: segments • Given 3N + 1 points p0,p1,…,p3N• Define N Bézier segments:x0(t ) = B0(t )p0+ B1(t )p1+ B2(t )p2+ B3(t )p3x1(t ) = B0(t )p3+ B1(t )p4+ B2(t )p5+ B3(t )p6!!!!!!!!!!!!xN !1(t ) = B0(t )p3N ! 3+ B1(t )p3N ! 2+ B2(t )p3N !1+ B3(t )p3Nx0(t)x1(t)x2(t)x3(t)p0p1p2p3p4p5p6p7p8p9p10p11p1217Piecewise Bézier curve !!!!!!!!!!!x(u) =x0(13u), 0 ! u ! 3x1(13u " 1), 3 ! u ! 6! !xN "1(13u " (N " 1)), 3N " 3 ! u ! 3N#$%%&%%!!!!!!!!!!!x(u) = xi13u " i( ),!where i =13u'()*x0(t)x1(t)x2(t)x3(t)x(3.5)x(8.75)18Piecewise Bézier curve 3N+1 points define N Bézier segments x(i)=p3i C0 continuous by construction G1 continuous at p3i when p3i-1, p3i, p3i+1 are collinear C1 continuous at p3i when p3i-p3i-1 = p3i+1-p3i C2 is harder to getp0p0p1p2P3P3p2p1p4p5p6p6p5p4C1 continuousC1 discontinuous19Piecewise Bézier curves Used often in 2D drawing programs Inconveniences: Must have 4 or 7 or 10 or 13 or … (1 plus a multiple of 3) points Not all points are the same• UI inconvenience: Interpolate, approximate, approximate, interpolate, …• Math inconvenience: Different weight functions for each point UI solution: “Bézier Handles” Math solution: B-spline20UI for Bézier Curve Handles Bézier segment points: Interpolating points presented normally as curve
View Full Document