贝塞尔曲线算法

Bezier Subdivision and De Casteljau’s Algorithm Ron Goldman Department of Computer Science Rice University De Casteljau’s Algorithm 0 1 2 B(t) b − t b − t b − t ∇ ∇ ∇ t − a t − a t − a P0 P1 P2 P3 t − a b − t t − a b − t t − a b − t ♦ ♦ B(t) = Bezier Curve a ≤ t ≤ b P0 ,K, Pn = Control Points De Casteljau’s Algorithm 0 1 2 B(t) 1− t ∇ ∇ ∇ P0 P1 P2 P3 ♦ ♦ 1− t 1− t 1− t 1− t1− tt t t t tt B(t) = Bezier Curve 0 ≤ t ≤1 P0 ,K, Pn = Control Points Bezier Curve ∇ ♦ • • b – t P0 P1 P2 P3 B(r) • • •• • Bezier Subdivision ∇ ♦ • • t–a P0 = Q0 P1 P2 P3 = R3 Q3 = R0 Q1 Q2 R1 R2 • • • • • • • •• Q(t) R(t) Problem: Given P0 ,K, Pn, find Q0 ,K,Qn and R0 ,K, Rn . De Casteljau’s Subdivision Algorithm 0 1 2 1− r Q1 ∇ Q0 = P0 P1 P2 R3 = P3 1− r 1− r 1− r 1− r1− rr r r r rr Q2 Q3 = R0 R1 R2 B(t) = Bezier Curve 0 ≤ t ≤1 P0 ,K, Pn = Original Control Points Algorithms for Bezier Curves Rendering 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 Answers Question: When can a Bezier curve be approximated by a straight line? Answer: When all the control points are within tolerance of the straight line because 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 L Question: 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) • v L v dist(P, L)| P −Q | P • dist2 (P, L) =| P −Q |2 − (P −Q) • v( )2 Intersection Between Two Line Segments Given Line #1: L1(s) = (1− s)P0 + sP1 = P0 + s(P1 − P0 ) 0 ≤ s ≤ 1 Line #2: L2 (t) = (1− t)Q0 + tQ1 = Q0 + t(Q1 −Q0 ) 0 ≤ t ≤1 To Find Intersection L1(s) = L2 (t) P0 + s(P1 − P0 ) = Q0 + t(Q1 −Q0 ) s(P1 − P0 ) − t(Q1 −Q0 ) = (Q0 − P0 ) Apply Dot Products s (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 Subdivision P 0 1 P0 P00 P01 P001P000 P010 P011 2 P1 P11 P111 P10 P100 P101 P110 M Control 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 Algorithm 0 1 2 1/ 2 Q1 ∇ Q0 = P0 P1 P2 R3 = P3 1/ 2 Q2 Q3 = R0 R1 R2 1/ 2 1/ 2 1/ 2 1/ 21/ 2 1/ 21/ 2 1/ 2 1/ 2 1/ 2 One Level of the de Casteljau Algorithm ∇ ♦ • • t–a P0 P1 P2 P3• • • • • • • ≤ d 2 ≤ d ≤ d Q1 ∇ R2 ≤ d 2 ≤ d 2 ≤ d 2 ≤ d 2 ≤ d 2 Variation Diminishing Property Theorem: 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. C L Variation Diminishing Curves Definition A 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 . Examples P0 P1 P2 P3 L C P0 P1 P2 P3 D L Variation Diminishing Not Variation Diminishing Corner Cutting Q0 = P0 Q1 Q2 Q4 = P3 P1 € Q3 = P2 • • • • • • L L #intersection of L and Q ≤ #intersection of L and P De Casteljau’s Subdivision Algorithm 0 1 2 1− r Q1 ∇ Q0 = P0 P1 P2 R3 = P3 1− r 1− r 1− r 1− r1− rr r r r rr Q2 Q3 = R0 R1 R2 de Casteljau Subdivision and Corner Cutting ∇ ♦ • • t–a P0 P1 P2 P3• • • • • • • Q1 ∇ R2 ∇ ♦ • • t–a P0 P1 P2 P3• • • • • • • Q1 ∇ R2 •Q2 R1 Q3 = R0 First step Second step Corollary: 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 Cutting Q0 = P0 Q1 Q2 Q4 = P3 P1 € Q3 = P2 • • • • • • Corner Cutting Reduces Length Recursive Subdivision for Tensor Product Bezier Surfaces * * * * * * * * P00 P01 P02 P10 P11 P12 P20 P21 P22 B(s, t) 1 − s s ss1 − s 1 − s P0(t ) P1(t ) P2(t) 1− t 1 − t 1 − t t tt 1 − t 1 − t 1 − t tt t 1− t 1− t 1 − t t tt Subdivide each of the rail curves Pk (t ) using the de Casteljau subdivision algorithm for Bezier curves. Recursive Subdivision for Tensor Product Bezier Surfaces * * * * * * * * P00 € P10 € P20 € P01 P11 € P21 € P02 € P12 P22 B(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 € s Subdivide each of the rail curves € Pk *(s) using the de Casteljau subdivision algorithm for Bezier curves. Algorithms for Bezier Surfaces Rendering Algorithm • If the Bezier surface can be approximated to within tolerance by two triangles joining three of its four corner points, then draw the two triangles determined by the four corner points. • Otherwise subdivide the surface (at t = 1/ 2) and render the segments recursively. Intersection Algorithm • If the convex hulls of the control points of two Bezier surfaces fail to intersect, then the surfaces themselves do not intersect. • Otherwise if each Bezier surface can be approximated by two triangles joining three of its four corner points, then intersect the corresponding triangles. • Otherwise subdivide the two surfaces and intersect the segments recursively. Questions and Answers Question: When can a Bezier surface be approximated by two planes? Answer: When all the control points are within tolerance of the two planes because a Bezier surface lies in the convex hull of its control points. Question: What is the distance from a point P to a plane L? Answer: dist(P,Plane) =| (P −Q) • N | • Q = point on plane • N = unit vector normal to plane Question: 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 planes? Answer: Use vector techniques (see below). Distance from a Point to a Plane . • Q plane L dist(P, L) P −Q P • N θ θ dist(P, L) =| P −Q | cosθ = (P −Q)• N Intersection Between Two Planes Given Plane #1: N1 • (P −Q1 ) = 0 Plane #2: N2 • (P −Q2 ) = 0 To Find Intersection Line Direction Vector = N1 × N2 Point on Line • Solve 2 Equations in 3 Unknowns {P = (x,y,z)} N1 • (P −Q1 ) = 0 N2 • (P −Q2 ) = 0 • Solve 3 Equations in 3 Unknowns {P = (x,y,z)} N1 • (P −Q1 ) = 0 N2 • (P −Q2 ) = 0 (N1 × N2 )• (P −Q3 ) = 0 Observations Theorem: The control polyhedra generated by recursive subdivision converge to the original tensor product Bezier surface provided that the subdivision is done in both the s and t directions. Remark: There is No Known Variation Diminishing Property for Tensor Product Bezier Surfaces. Smooth Piecewise Bezier Curves ∇ ♦ • • b – t P0 P1 P2 B(t) ∇ ♦ • • b – t P3 = Q0 Q1 ? Q2 ? Q3 ?• • • • C(t ) • •• De Casteljau’s Evaluation Algorithm 0 1 2 B(t) 1− t ∇ ∇ ∇ P0 P1 P2 P3 ♦ ♦ 1− t 1− t 1− t 1− t1− tt t t t tt B(t) = Bezier Curve 0 ≤ t ≤1 P0 ,K, Pn = Control Points Differentiating de Casteljau’s Algorithm -- First Derivative 0 1 2 ′ B (t) = 3× _ −1 ∇ ∇ ∇ P0 P1 P2 P3 ♦ ♦ 1− t 1− t 1− t 1 t t t 11−1 −1 B(t) = Bezier Curve 0 ≤ t ≤1 P0 ,K, Pn = Control Points Differentiating de Casteljau’s Algorithm -- Second Derivative 0 1 2 ′ ′ B (t) = 6 × _ −1 ∇ ∇ ∇ P0 P1 P2 P3 ♦ ♦ 1− t 1 1 t 1 11−1 −1 −1 −1 B(t) = Bezier Curve 0 ≤ t ≤1 P0 ,K, Pn = Control Points Differentiating Bezier Curves Observations • To differentiate the de Casteljau algorithm k times, differentiate any k levels and multiply the result by n! (n − k)! . • The kth derivative at either end point (t = 0,1) depends only on the adjacent k control points. Continuity Conditions for Adjacent Bezier Curves Derivatives at End Points • B(0) = P0 B(1) = Pn • ′ B (0) = n(P1 − P0 ) ′ B (1) = n(Pn − Pn−1) • ′ ′ B (0) = n(n −1)(P2 − 2P1 + P0 ) ′ ′ B (1) = n(n −1)(Pn − 2Pn−1 + Pn−2 ) Continuity Conditions -- Matching k Derivatives k = 0: Q0 = Pn k = 1: Q1 −Q0 = Pn − Pn−1 ⇒ Q1 = Pn + (Pn − Pn−1) k = 2 : Q2 − 2Q1 + Q0 = Pn − 2Pn−1 + Pn−2 ⇒ Q2 = Pn−2 + 4(Pn − Pn−1) Subdivision and Differentiation 1 2P0 P1 P2 P3 = Q0 Q1 Q2 Q3 2−1 −1 −1 −1−1 −1 * 2 2 2 2 2 * * Subdivision at r = 2 Subdivision and Differentiation Observations 1. The two curves • B(t) = B[P0,K, Pn ](t) 0 ≤ t ≤1 • B(t) = B[P0,K, Pn ](t) 1≤ t ≤ 2 meet smoothly, since they are the same polynomial. 2. The kth derivative at either end point (t = 0,1) depends only on the adjacent k control points. 3. Therefore subdividing a Bezier curve at r = 2 generates the locations of the control points {Qk} for arbitrary smooth piecewise Bezier curves. Subdivision Key Ideas • de Casteljau’s Evaluation Algorithm is also a Subdivision Procedure • Subdivision = Divide and Conquer • Subdivision is the Basic Tool for Analyzing Bezier Curves and Surfaces • Rendering • Intersection • Joining Curves Smoothly • Variation Diminishing Property