Bezier Subdivision and De Casteljau’s AlgorithmRon GoldmanDepartment of Computer ScienceRice UniversityDe 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 PointsBezier Curve∇♦••b–tP0P1P2P3B(r)•••••Bezier Subdivision∇♦••t–aP0= Q0P1P2P3= R3Q3= R0Q1Q2R1R2•••••••••Q(t)R(t) Problem: Given P0,K, Pn, find Q0,K, Qn and R0,K, Rn.De Casteljau’s Subdivision Algorithm0121− rQ1∇Q0= P0P1P2R3= P31− r1− r1− r1− r1− rrrrrrrQ2Q3= R0R1R2B(t) = Bezier Curve 0 ≤ t ≤ 1 P0,K, Pn = Original Control PointsAlgorithms for Bezier CurvesRendering Algorithm• If the Bezier curve can be approximated to within tolerance by the straight line joining its first and last control points, then draw either this line segment or the control polygon.• Otherwise subdivide the curve (at r = 1/ 2) and render the segments recursively.Intersection Algorithm• If the convex hulls of the control points of two Bezier curves fail to intersect, then the curves themselves do not intersect.• Otherwise if each Bezier curve can be approximated by the straight line joining its first and last control points, then intersect these line segments.• Otherwise subdivide the two curves and intersect the segments recursively.Questions and AnswersQuestion: When can a Bezier curve be approximated by a straight line?Answer: When all the control points are within tolerance of the straight linebecause a Bezier curve lies in the convex hull of its control points.Question: What is the distance from a point P to a line L?Answer:dist2(P, L) =| P − Q |2− (P − Q) • v( )2• Q = point on L• v = unit vector parallel to LQuestion: How can we compute the convex hull of the control points?Answer: Replace the convex hull by a bounding box.Question: How do we compute the intersection of two line segments?Answer: Use vector techniques (see below).Distance from a Point to a Line .•Q(P − Q) • vLvdist(P, L)| P − Q |P•dist2(P, L) =| P − Q |2− (P − Q) • v( )2Intersection Between Two Line SegmentsGivenLine #1: L1(s) = (1− s)P0+ sP1= P0+ s(P1− P0) 0 ≤ s ≤ 1Line #2: L2(t) = (1− t)Q0+ tQ1= Q0+ t(Q1− Q0)0 ≤ t ≤ 1To Find IntersectionL1(s) = L2(t) P0+ s(P1− P0) = Q0+ t(Q1− Q0)s(P1− P0) − t(Q1− Q0) = (Q0− P0)Apply Dot Productss (P1− P0) •(P1− P0){ }− t (Q1− Q0)•( P1− P0){ }= (Q0− P0)• (P1− P0)s (P1− P0) •(Q1− Q0){ }− t (Q1− Q0)•(Q1− Q0){ }= (Q0− P0)• (Q1− Q0)Solve Two Linear Equations in Two Unknowns {s,t}.Test 0 ≤ s,t ≤ 1 to Determine whether the Intersection Lies on the Line Segments.Substitute Back into L1(s) or L2(t) to Find the Intersection Point.Recursive SubdivisionP01P0P00P01P001P000P010P0112P1P11P111P10P100P101P110 MControl Polygons Generated by Recursive Subdivision .b1Lbn→ b ⇒ Pb1Lbn→ B(b)Theorem: The control polygons generated by recursive subdivision converge to the original Bezier curve.Proof: Let d = the maximum distance between any two adjacent control points.The points on any level of the de Casteljau algorithm for t = 1/ 2 lie at the midpoints of the edges of the polygons generated by the previous level. Therefore, by induction, adjacent points on any level of the de Casteljau diagram for t = 1/ 2 are no further than d apart. By the same midpoint argument, as we proceed up the diagram, adjacent points along the left (right) lateral edge of the triangle can be no further than d / 2 apart. Hence, as we apply recursive subdivision, the distance between the control points of any single control polygon must converge to zero.Since the first and last control points of a Bezier control polygon always lie on the curve, these control polygons must converge to points along the original curve.De Casteljau’s Subdivision Algorithm0121/ 2Q1∇Q0= P0P1P2R3= P31/ 2Q2Q3= R0R1R21/ 21/ 21/ 21/ 21/ 21/ 21/ 21/ 21/ 21/ 2One Level of the de Casteljau Algorithm∇♦••t–aP0P1P2P3•••••••≤d2≤ d≤ dQ1∇R2≤d2≤d2≤d2≤d2≤d2Variation Diminishing PropertyTheorem: Bezier curves never oscillate more than their control points.Remark: Lagrange interpolating curves often oscillate more than the data points.Question: How do we measure oscillations?Answer: Compute intersections with a straight line.CLVariation Diminishing CurvesDefinitionA curve scheme B(t) is said to be variation diminishing if for every line L# intersections of B(t) and L ≤ # intersections of the control polygon and L .ExamplesP0P1P2P3LCP0P1P2P3DL Variation Diminishing Not Variation DiminishingCorner CuttingQ0= P0Q1Q2Q4= P3P1€ Q3= P2••••••LL #intersection of L and Q ≤ #intersection of L and PDe Casteljau’s Subdivision Algorithm0121− rQ1∇Q0= P0P1P2R3= P31− r1− r1− r1− r1− rrrrrrrQ2Q3= R0R1R2de Casteljau Subdivision and Corner Cutting∇♦••t–aP0P1P2P3•••••••Q1∇R2∇♦••t–aP0P1P2P3•••••••Q1∇R2•Q2R1Q3= R0First step Second stepCorollary: Bezier curves are variation diminishing.Proof: Since recursive subdivision is a corner cutting procedure, the limit curve must be variation diminishing with respect to the original control polygon. But we have proved that the Bezier curve is the limit curve of recursive subdivision.Hence Bezier curves are variation diminishing.Corollary: The arc length of a Bezier curve is always less than or equal to the length of its control polygon.Proof: Corner cutting reduces length.Since recursive subdivision is a corner cutting procedure, the arc length of the limit curve must be must be less than or equal to the length of the control polygon. But we have proved that the Bezier curve is the limit curve of recursive subdivision.Hence the arc length of a Bezier curve is always less than or equal to the length of its control polygon.Corner CuttingQ0= P0Q1Q2Q4= P3P1€ Q3= P2••••••Corner Cutting Reduces LengthRecursive Subdivision 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 − ttttSubdivide each of the rail curves Pk(t) using the de Casteljau