Bezier Approximation and De Casteljau’s AlgorithmRon GoldmanDepartment of Computer ScienceRice UniversityInterpolation and Approximation Data Interpolation of Data Approximation of ShapeNeville’s AlgorithmP0123(t)t3− tt2− tt2− tt3− tt3− tt − t1t − t1t − t2P12(t)P23(t)P1P2P3t1− tt − t0t − t0t − t0P012(t)P01(t)P123(t)P0 P0123(tk) = PkLinear InterpolationP1b − tt − aP(t)P1b − tb − at − ab − aP(t)P0P0 Normalized UnnormalizedP(t) =b − tb − aP0+t − ab − aP1P(a) = P0 P(b) = P1De Casteljau’s Algorithm012B(t)b − tb − tb − t∇∇∇t − at − at − aP0P1P2P3t − ab − tt − ab − tt − ab − t♦♦B(t) = Bezier Curve a ≤ t ≤ b P0,K, Pn = Control PointsDe Casteljau’s Algorithm012B(t)1− t∇∇∇P0P1P2P3♦♦1− t1− t1− t1− t1− tttttttB(t) = Bezier Curve 0 ≤ t ≤1 P0,K, Pn = Control PointsCubic Bezier CurveDe Casteljau’s Algorithm -- Geometric Interpretation∇♦•••b–tt–aP0P1P2P3t − ab − tt − at − ab − tb − t∇∇∇♦♦b − tt − ab − tb − tt − at − aB(t)••••Elementary Properties of Bezier Curves1. Polynomial2. Translation Invariant -- Affine Invariant3. Lie in Convex Hull of their Control Points4. Symmetry5. Interpolation of End PointsTranslation InvarianceLinear Interpolation€ L(t) =b −tb − a P0+t − ab− a P1€ L(t) + v =b −tb − a P0+ v( )+t − ab− a P1+v( )Bezier Curves B P0,K, Pn[ ](t) + v = B P0+ v,K, Pn+ v[ ](t)Consequences• Bezier Curves Depend Only on their Control Points• Bezier Curves are Independent of the Choice of the Origin of the Coordinate System -- Also True for Lagrange InterpolationTranslation Invariance012B(t) + vb − tb − tb − t∇ + v∇ + v∇ + vt − at − at − aP0+ vP1+ vP2+ vP3+ vt − ab − tt − ab − tt − ab − t♦+v♦+vAffine Invariance012€ B(t),1( )∗ Mb − tb − tb − t€ (∇,1)∗ Mt − at − at − a€ (P0,1) ∗ Mt − ab − tt − ab − tt − ab − t€ (♦,1)∗ M€ (P1,1) ∗ M€ (P2,1) ∗ M€ (P3,1) ∗ M€ (∇,1)∗ M€ (∇,1)∗ M€ (♦,1)∗ M€ L(t) =b −tb − a P0+t − ab− a P1€ (L(t),1)∗ M =b −tb − a P0,1( )∗ M +t − ab− a P1,1( )∗ MConvexityPQP••••Q (a) Convex Set (b) Non-Convex SetDefinition A set is convex if and only if for every two points in the set the line segment joining the two points lies entirely inside the set.Convex Hull PropertyDefinitionConvex Hull P0,K, Pn{ } = Smallest Convex Set Containing P0,K, PnTheoremBezier Curves Lie in the Convex Hull of their Control Points.ProofFrom the de Casteljau Algorithm by Induction on Degree.Consequence• If the Control Points are Visible, the Entire Bezier Curve is Visible.• Not True for Lagrange Interpolation.De Casteljau’s Algorithm012B(t)b − tb − tb − t∇∇∇t − at − at − aP0P1P2P3t − ab − tt − ab − tt − ab − t♦♦B(t) = Bezier Curve a ≤ t ≤ bSymmetry∇♦••b–tP0P1P2P3B(t)•••• B Pn,K, P0[ ](t) = B P0,K, Pn[ ](a + b − t)Reversing the order of the control points, reverses the orientation of the Bezier curve.Symmetry012B(t)b − tb − tb − t∇∇∇t − at − at − aP3P2P1P0t − ab − tt − ab − tt − ab − t♦♦ B Pn,K, P0[ ](t) = B P0,K, Pn[ ](a + b − t)Symmetry012B(t)b − tb − tb − t∇∇∇t − at − at − aP3P2P1P0t − ab − tt − ab − tt − ab − t♦♦012B(a + b − t)t − a∇∇∇b − tP0P1P2P3♦♦=t − at − at − at − at − ab − tb − tb − tb − tb − t B Pn,K, P0[ ](t) = B P0,K, Pn[ ](a + b − t)Consequence• Reversing the order of the control points, reverses the orientation of the Bezier curve.Interpolation of End PointsTheoremBezier Curves Interpolate their First and Last Control Points.In particular, B(a) = P0 and B(b) = PnProofExamine the De Casteljau Diagram.ConsequenceEasy to String Together Bezier Curves in a Continuous Manner.Interpolation of End Points012B(t)b − tb − tb − t∇∇∇t − at − at − aP0P1P2P3t − ab − tt − ab − tt − ab − t♦♦B(a) = P0 and B(b) = P3Piecewise Bezier Curve∇♦••b–tP0P1P2B(t)∇♦••b–tP3= Q0Q1Q2Q3••••C(t)•••Advantages of de Casteljau’s Algorithm1. Numerically Stable• Uses the Control Points Directly• Computes Only Convex Combinations2. Fast• Dynamic Programming•O(n2) vs. O(2n)3. Simple Structure• All Computations are Identical4. Basic Properties of Bezier Curves• Polynomial• Translation Invariant• Lie in Convex Hull of their Control Points• Symmetric• Interpolate First and Last Control PointsTensor Product Bezier SurfacesSetups = cs = dt = at = bP00P10P20P30P01P11P21P31P02P12P22P32P03P13P23P33 Domain -- Rectangle Range -- Rectangular Array of PointsProblemFind a smooth surface B(s,t) that approximates the shape defined by the control points.Tensor Product Bezier Surface••••••P03P02P01P00P0(t)P13P12P11P10P3(t )P23P33P22P21P20P30P31P32B(s,t)•••P1(t )•P2(t)Tensor Product Bezier Surface••••••P03P02P01P00P13P11P10P23P33P22P21P20P30P31P32€ P12••€ P0*(s)€ P1*(s)€ P2*(s)••€ P3*(s)€ B(s,t)Tensor Product Bezier SurfaceDe Casteljau’s Algorithm for Tensor Product Bezier Surfaces********P00P01P02P10P11P12P20P21P22B(s,t)1 − ssss1 − s1 − sP0(t)P1(t )P2(t)1 − t1 − t1 − tttt1 − t1 − t1 − tttt1 − t1 − t1 − ttttDe Casteljau’s Algorithm for Tensor Product Bezier Surfaces********P00€ P10€ P20€ P01P11€ P21€ P02€ P12P22B(s,t)€ 1− t€ t€ t€ t€ 1− t€ 1− t€ P0*(s)€ P1*(s)€ P2*(s)€ 1− s€ 1− s€ 1− s€ s€ s€ s€ 1− s€ 1− s€ 1− s€ s€ s€ s€ 1− s€ 1− s€ 1− s€ s€ s€ sElementary Properties of Tensor Product Bezier Surfaces1. Polynomial2. Translation Invariant3. Lie in Convex Hull of their Control Points4. Symmetry5. Interpolation of Boundary Bezier Curves Defined by Boundary Control PointsSummaryKey Ideas• de Casteljau’s Algorithm• Basic Properties of Bezier Curves• Extension to Tensor Product Bezier
View Full Document
Unlocking...