B-Splines and the de Boor AlgorithmRon GoldmanDepartment of Computer ScienceRice UniversityPrimary Properties of the Blossomi. Symmetry p(u1,K,un) = p(uσ(1),K, uσ(n)) for any permutation σ of {1,K,n}.ii. Multiaffine p(u1,K,(1−α)uk+αwk,K, un) = (1 −α)p(u1,K,uk,K, un) +αp(u1,K, wk,K, un)iii. Diagonal P(t) = p(t,K,tn1 2 3 )iv. Differentiation P(k)(t) =n!(n − k)!p(t,K, tn−k1 2 3 ,δ,K,δk1 2 3 )v. Dual Functional Pk= p(a,K, an −k1 2 3 ,b,K,bk1 2 3 )The Multiaffine Property€ aabb − tt − a€ aatb − tb − at − ab − a€ p(a, a,t)€ p(a, a,a)€ aaa€ p(a, a,b) Normalized Unnormalized€ t =b − tb − aa +t − ab − ab€ p(a, a,t) = p a,a,b − tb − aa +t − ab − ab      =b − tb − ap a, a,a( )+t − ab − ap a, a,b( )€ aat =b −tb − aaaa +t − ab − aaabde Casteljau’s Algorithmb–tb–tb–tb–tb–tt–at–at–at–at–at–atttb − tb − tb − tb − tb − tb − tt − at − at − at − at − at − aaaaaababbbbbaatabtbbtattbtt aLai1 2 3 bLbj1 2 3 tLtk{= p(a,K,ai1 2 3 ,b,K,bj1 2 3 ,t,K, tk1 2 3 )t =b − tb − aa +t − ab − abMultiaffine Propertyt1t2t3t2t3t4t2t3tt4− tt − t1€ t =t4−tt4− t1t1+t − t1t4−t1t4€ p(t2,t3,t) =t4− tt4−t1p(t1,t2,t3) +t − t1t4−t1p(t2,t3,t4)€ t2t3t =t4− tt4−t1t1t2t3+t − t1t4−t1t2t3t4De Boor Algorithmtttt − t3t − t3t − t2t2t3tt3t4tt4t5tt3ttt4ttt1t2t3t2t3t4t3t4t5t4t5t6t4− tt4− tt4− tt − t1t − t3t5− tt5− tt6− tt − t2One Polynomial Segment: t3≤ t ≤ t4Knots: t1≤ t2≤ t3< t4≤ t ≤ t5≤ t6B-Spline Curve•t1t2t3t2t3t4t3t4t5t4t5t6t2t3tt3t4tt4t5ttttt3ttt4tt••••••••••One Polynomial Segment: t3≤ t ≤ t4De Boor Algorithmtttt − t3t − t3t − t2t2t3tt3t4tt4t5tt3ttt4ttt1t2t3t2t3t4t3t4t5t4t5t6t4− tt4− tt4− tt − t1t − t3t5− tt5− tt6− tt − t2One Polynomial Segment: t3≤ t ≤ t4Knots: t1≤ t2≤ t3< t4≤ t ≤ t5≤ t6De Boor Algorithmtttt − t4t − t4t − t3t3t4tt4t5tt5t6tt4ttt5ttt2t3t4t3t4t5t4t5t6t5t6t7t5− tt5− tt5− tt − t2t − t4t6− tt6− tt7− tt − t3One Polynomial Segment: t4≤ t ≤ t5Knots: t2≤ t3≤ t4< t5≤ t ≤ t6≤ t7De Boor Algorithmtttt − t4t − t4t − t3t3t4tt4t5tt5t6tt4ttt5ttt2t3t4t3t4t5t4t5t6t5t6t7t5− tt5− tt5− tt − t2t − t4t6− tt6− tt7− tt − t3tttt3ttt2t3tt − t2t − t3t − t1t1t2t3t4− tt4− tt4− tTwo Polynomial Segments: t3≤ t ≤ t4 and t4≤ t ≤ t5Knots: t1≤ t2≤ t3< t4< t5≤ t ≤ t6≤ t7Dual Functional PropertyB-Spline Curves• T = {t0,K,tL} = knot vector•S(t) = B-spline curve• s(tk +1,K, tk +n) = Pk= kth B-Spline Control PointBezier Curves• T = {a,K, an1 2 3 ,b,K,bn1 2 3 } = knot vector•P(t) = Bezier curve• p(a,K, an −k1 2 3 ,b,K,bk1 2 3 ) = Pk= kth Bezier Control PointDe Boor Algorithmt − t4t − t4t − t3t3t4tt4t5tt5t6tt4ttt5ttP1P2P3P4t5− tt5− tt5− tt − t2t − t4t6− tt6− tt7− tt − t3S3(t)t3ttt2t3tt − t2t − t3t − t1P0t4− tt4− tt4− tS4(t)Two Polynomial Segments: t3≤ t ≤ t4 and t4≤ t ≤ t5Knots: t1≤ t2≤ t3< t4< t5≤ t6≤ t7Advantages of the de Boor Algorithm1. Numerically Stable• Uses the Given Data Directly• Computes Only Convex Combinations2. Flexible• Automatic Smoothness Between Polynomial Segments• No Special Positioning of the Control Points3. Simple Structure• In-Out Property• Basic Step of the de Boor Algorithm Pkt − tktk+n +1− tDe Boor Algorithm -- Evaluationtttt − t4t − t4t − t3t3t4tt4t5tt5t6tt4ttt5ttt2t3t4t3t4t5t4t5t6t5t6t7t5− tt5− tt5− tt − t2t − t4t6− tt6− tt7− tt − t3tttt3ttt2t3tt − t2t − t3t − t1t1t2t3t4− tt4− tt4− tC0 Continuity ttt = t4tt at t = t4De Boor Algorithm -- First Derivativet − t4t − t4t − t3t3t4δt4t5δt5t6δt4tδt5tδt2t3t4t3t4t5t4t5t6t5t6t7−1t5− tt5− t11t6− t−1−11ttδt3tδt2t3δt − t2t − t31t1t2t3t4− tt4− t−1ttδC1 Continuity ttδ= t4tδ at t = t4De Boor Algorithm -- Second Derivativet − t4t3t4δt4t5δt5t6δt4δδt5δδt2t3t4t3t4t5t4t5t6t5t6t7−1t5− t11−1−11tδδt3δδt2t3δt − t31t1t2t3t4− t−1tδδ−1−1−1111C2 Continuity tδδ= t4δδ at t = t4Elementary Properties of B-Spline Curves1. Piecewise polynomial2. Continuity of order Cn −µ at knots of multiplicity µ on curves of degree n3. Translation invariance4. Local convex hull property5. Interpolation at knots where the multiplicity µ is equal to the degree n6. Local controlTranslation Invariancet − t4t − t4t − t3t3t4t + vt4t5t + vt5t6t + vt4tt + vt5tt + vP2+ vP3+ vP4+ vP5+ vt5− tt5− tt5− tt − t2t − t4t6− tt6− tt7− tt − t3S3(t) + vt3tt + vt2t3t + vt − t2t − t3t − t1P1+ vt4− tt4− tt4− tS4(t) + vInterpolationS(t)t − t3t − t3t − t2t2t3tt3t4tt4t5tt3ttt4ttt1t2t3t2t3t4t3t4t5t4t5t6t4− tt4− tt4− tt − t1t − t3t5− tt5− tt6− tt − t2 Interpolation at knots of multiplicity n = 3 t1= t2= t3⇒ S(t3) = t3t3t3= t1t2t3Local ControlBasic Step of the de Boor Algorithm Pkt − tktk+n +1− tkth Segment of a Degree n B-spline Curve• lies over the parameter interval [tk,tk +1]• has n +1 control points -- Pk −n,..., Pk• depends on 2n knots -- tk −n+1,..., tk +nLocal Control•Pk influences only the n +1 curve segments over the interval [tk,tk + n+1]•tk influences solely the 2n curve segments over the interval [tk −n,tk +n]Knot Insertion•t1t2t3t2t3t4t3t4t5t4t5t6t2t3ut3t4ut4t5u••••••••••S(t3)S(t4)S(u)Inserting the knot u between the knots t3 and t4,changes the control polygon, but does not alter the curve.Knot InsertionAlgorithms• Boehm’s Algorithm• Oslo Algorithm• Lane Riesenfeld AlgorithmApplications• Conversion to Piecewise Bezier Form• Rendering• Intersection• Variation Diminishing PropertyBoehm’s Knot Insertion AlgorithmInsert One Knot at a TimeReplace K,tk −1,tk,tk +1,tk +2,K with K,tk −1,tk,u,tk +1,tk +2,KOld Control Pointsp(tk −2,tk −1,tk), p(tk −1,tk,tk +1), p(tk,tk +1,tk + 2), p(tk +1,tk +2,tk +3) New Control Points p(tk −2,tk −1,tk), p(tk −1,tk,u), p(tk,u,tk +1), p(u,tk +1,tk +2), p(tk +1,tk +2,tk +3)t2t3ut3t4ut4t5ut1t2t3t2t3t4t3t4t5t4t5t6t4− uu − t1u − t3t5− ut6− uu − t2New Control PointsOriginal Control PointsOslo Knot Insertion Algorithm -- Blossoming the de Boor AlgorithmInserts Many Knots SimultaneouslyReplace K,tk −1,tk,tk +1,tk +2,K