New version page

Rice COMP 360 - Bezier Approximation and De Casteljaus Algorithm

Documents in this Course

19 pages

15 pages

10 pages

16 pages

30 pages

37 pages

34 pages

10 pages

9 pages

25 pages

31 pages

21 pages

29 pages

10 pages

34 pages

69 pages

8 pages

42 pages

16 pages

18 pages

21 pages

13 pages

10 pages

22 pages

14 pages

30 pages

Unformatted text preview:

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