Lecture 21: Tuesday, 19 November 2002Today:(Warman Group)Parametric Curves & SurfacesHermite curvesBezier splinesB-splinesSpline bases and change of basisSubdivision Curves and SurfacesMIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 1Curved Primitives (FvDFHP §9.2)Motivation:Necessary to model organic/machined surfacesNeeded to “blend” differently-oriented primitivesDesigners tire of linear (polyhedral) primitivesModel plane and space curves first, then surfacesApplications beyond shape modeling:Smooth variation of position, pose, camera parameters, etc.MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 2Plane and space curvesWant a curve primitive that has:Explicit representation (for rendering)Controllable start/end pointsControllable start/end derivativesTry: implicit curves Ax2+ By2+ ....F = 0How to model “less” than the whole curve?How to fit to given position, derivative ?Try: functions y = f(x)How to model double-valued or vertical curves?How to rotate the curve?MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 3Parametric CurvesExpress (simple) lerp in (complicated) new way(1 − t) P0 + t P1P1P0t = 0t = 1P1 − P0B1B011tQ(t) =Qx(t)Qy(t)Qz(t)=(P0) (P1)−1 11 0t1What is the derivative Q0(t) w.r.t. t?Q0(t) =ddtQ(t) =x0(t)y0(t)z0(t)=(P0) (P1)−1 11 010= P1− P0Note that Q(t), Q0(t) can be written as:Q(t) = Geometry G · Spline Basis B · Power Basis T(t)Q(t) = GBT(t) Q0(t) = GBT0(t)MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 4Hermite CurvesWant to specify position, derivative at start, endpointP4P1t = 0t = 1R4R1What do we know?Linear, quadratic aren’t sufficient. Why?MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 5Hermite CurvesPosition and derivative at start, endpointP4P1t = 0t = 1R4R1Knowns:G =P1P4R1R4T(t) =t3t2t1; T0(t) =3t22t10Q(0) = P1Q(1) = P4Q0(0) = R1Q0(1) = R4MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 6Hermite CurvesGiven:Q(t) = GBT (t), Q0(t) = GBT0(t);P4P1t = 0t = 1R4R1Solve for B:GBT (0) = P1GBT (1) = P4GBT0(0) = R1GBT0(1) = R4MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 7Hermite Matrix Formulation(P1) (P4) (R1) (R4)B0001= P1(P1) (P4) (R1) (R4)B1111= P4(P1) (P4) (R1) (R4)B0010= R1(P1) (P4) (R1) (R4)B3210= R4Or, in matrix form as:G = GB(T (0))(T (1))(T0(0))(T0(1))so B =2 −3 0 1−2 3 0 01 −2 1 01 −1 0 0Q(t) = GBT (t) =Qx(t)Qy(t)Qz(t)MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 8Hermite CurvesQ(t) = GBT =Qx(t)Qy(t)Qz(t); B =2 −3 0 1−2 3 0 01 −2 1 01 −1 0 0Write out Q(t), Q0(t):Q(t) = (2t3− 3t2+ 1)P1+ (−2t3+ 3t2)P4+ (t3− 2t2+ t)R1+ (t3− t2)R4Q0(t) = (6t2− 6t + 0)P1+ (−6t2+ 6t)P4+ (3t2− 4t + 1)R1+ (3t2− 2t)R4Check Q(0), Q(1), Q0(0), Q0(1)Call polynomials in t the Hermite basisGraph them with respect to t:P111P4R1R4tNote how control point “weights” vary over intervalMIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 9Cubic B´ezier CurveGiven four control points P1.. P4P4P1t = 0t = 1P2P3Q(t) = (1 − t)3P1+ 3t(1 − t)2P2+ 3t2(1 − t)P3+ t3P4B´ezier “basis functions” weight control point contributionsB111tB2B3B4MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 10B´ezier CurveQ(t) = (1 − t)3P1+ 3t(1 − t)2P2+ 3t2(1 − t)P3+ t3P4Q0(t) = −3(1 − t)2P1+ (9t2− 12t + 3)P2+ (−9t2+ 6t)P3+ 3t2P4P4P1t = 0t = 1P2P3Q(0) = P1Q(1) = P4Q0(0) = 3(P2− P1)Q0(1) = 3(P4− P3)Properties:Endpoint interpolationEndpoint tangentsMIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 11B´ezier Curve PropertiesConvex hull property:P4P1t = 0t = 1P2P3P4P1t = 0t = 1P2P3P4P1t = 0t = 1P2P3Is the curve planar ? Why or why not ?MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 12B´ezier Basis FunctionsB´ezier “basis functions” weight control point contributionsB111tB2B3B4B1(t) = (1 − t)3; B2(t) = 3t(1 − t)2; B3(t) = 3t2(1 − t); B4(t) = t3P4P1t = 0t = 1P2P3P4P1t = 0t = 1P2P3P4P1t = 0t = 1P2P3MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 13Tangent MatchingCan use control points to match tangents:P1t = 0t = 1P2P3P4t = 0t = 1P2P3P4P1What are the design degrees of freedom?MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 14Variation DiminishingCurve crosses line (plane) at most the numberof times control polygon crosses line (plane)P4P1t = 0t = 1P2P3P4P1t = 0t = 1P2P3P4P1t = 0t = 1P2P3Affine InvarianceAffine transformation, B´ezier generation commute!P4P1t = 0t = 1P2P3P4P1t = 0t = 1P2P3Note: does not commute with perspective!For that, we must use rational curvesMIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 15Defined for any degreeUse “Bernstein polynomials,” one per control pointBni(t) =n!i!(n − i)!ti(1 − t)n−i, 0 ≤ i ≤ nLinear, Cubic, we’ve seenWhat about quadratic?MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 16Stability of EvaluationHigh degree power basis is numerically unstableBut... beautiful property of B´ezier curves:Evaluation via nested interpolation!P4P1t = 0t = 1P2P3t = 0.8Works for any degree! (de Casteljau evaluation)How long does it take?MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 17Quality of EvaluationStill, discretization artifacts can ariseP4P1t = 0t = 1P3P2t = 0.1How can this problem be avoided?MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 18Subdivision:Split curve segment Q into two segments L, RP4P1t = 0t = 1P2P3t = t*LWhy? How?MIT 6.837 Computer Graphics Tuesday, 19 November 2002 (L21) Page 19B-Splines (FvDFHP §9.2.4)(Sometimes) Undesirable properties of Hermite,
View Full Document