B-Splines (Uniform and Non-Uniform)

Lecture 6 B-splines (Uniform and Non-uniform) 6.1 Introduction The formulation of uniform B-splines can be generalized to accomplish certain objectives. These include • Non-uniform parameterization. • Greater general flexibility. • Change of one polygon vertex in a Bézier curve or of one data point in a cardinal (or interpolatory) spline curve changes entire curve (global schemes). • Remove necessity to increase degree of Bézier curves or construct composite Bézier curves using previous schemes in order to increase degrees of freedom. • Obtain a “local” approximation scheme. The development extends the Bézier curve formulation to a piecewise polynomial curve with easy continuity control. 2 6.2 Definition A parametric non-uniform B-spline curve is defined by P(u) = n X Pi Ni,k (u) (6.1) i=0 where, Pi are n + 1 control points; Ni,k (u) are piecewise polynomial B-spline basis functions of order k (or degree k − 1) with n ≥ k − 1. Therefore n, k are independent, unlike Bézier curves. The parameter u obeys the inequality to ≤ u ≤ tn+k 6.2.1 (6.2) Knot vector For open (non-periodic) curves, it is usual to define a set T of non-decreasing real numbers which is called the knot vector, as follows: T = {to = t1 = · · · = tk−1 < tk ≤ tk+1 ≤ · · · ≤ tn < tn+1 = · · · = tn+k } | {z k equal values } | {z n−k+1 internal knots } | {z k equal values (6.3) } At each knot value, the curve P(u) has some degree of discontinuity in its derivatives above a certain order as we will see later. The total number of knots is n + k + 1 which equals the number of control points in the curve plus the curve’s order. 6.2.2 1. Properties and definition of basis function Ni,k (u) Pn i=0 Ni,k (u) = 1 (partition of unity). 2. Ni,k (u) ≥ 0 (positivity). 3. Ni,k (u) = 0 if u 6∈ [ti , ti+k ] (local support). 4. Ni,k (u) is (k − 2) times continuously differentiable at simple knots. If a knot tj is of multiplicity ρ(≤ k), ie. if tj = tj+1 = · · · = tj+ρ−1 (6.4) then Ni,k (u) is (k − ρ − 1) times continuously differentiable, ie. it is of class C k−ρ−1 . 3 5. Recursive definition (Cox-de Boor algorithm) Ni,1 (u) = Ni,k (u) = (set 0 0 ( 1 u ∈ [ti , ti+1 ) 0 u∈ 6 [ti , ti+1 ) ti+k − u u − ti Ni,k−1 (u) + Ni+1,k−1 (u) ti+k−1 − ti ti+k − ti+1 (6.5) (6.6) = 0 above when it occurs) Properties 1-4 or property 5 by itself (given a known knot vector T) define the B-spline basis. 6.2.3 Example: 2nd order B-spline basis function (Piecewise linear case– see Figure 6.1) k = 2, C k−2 = C 2−2 = C 0 Ni,2 (u) ti−1 ti ti+1 ti+2 ti+3 Figure 6.1: Plot of 2nd order B-spline basis functions. Ni,2 (u) consists of two piecewise linear polynomials: Ni,2 (u) = ( u−ti ti+1 −ti ti+2 −u ti+2 −ti+1 4 ti ≤ u ≤ ti+1 ti+1 ≤ u ≤ ti+2 6.2.4 Example: 3rd order B-spline basis function (Piecewise quadratic case– See Figure 6.2) k = 3, C k−2 = C 3−2 = C 1 Ni,3 (ti ) consists of three piecewise quadratic polynomials y1 (u), y2 (u) and y3 (u). We want to find y1 (u), y2 (u) and y3 (u) such that Figure 6.2: Plot of 3rd order B-spline basis function. 0 Ni,3 (ti ) = Ni,3 (ti ) = 0. 0 Ni,3 (ti+3 ) = Ni,3 (ti+3 ) = 0. (6.7) Position continuity: u − ti y1 (u) = A ti+1 − ti !2 !2 ti+3 − u y3 (u) = B ti+3 − ti+2 y2 (u) = A(1 − s)2 + Bs2 + C2s(1 − s) u − ti+1 s = ti+2 − ti+1 Note that y1 (ti+1 ) = y2 (ti+1 ) = A y3 (ti+2 ) = y2 (ti+2 ) = B 5 (6.8) (6.9) (6.10) (6.11) at s = 0, s = 1(u = ti+1 , u = ti+2 ). First derivative continuity: 1 1 = 2A ti+2 − ti+1 ti+1 − ti 1 1 = −2B 2(B − C) ti+2 − ti+1 ti+3 − ti+2 2(C − A) (6.12) (6.13) hence, " # 1 1 1 A + =C ti+1 − ti ti+2 − ti+1 ti+2 − ti+1 # " 1 1 1 =C + B ti+2 − ti+1 ti+3 − ti+2 ti+2 − ti+1 (6.14) (6.15) where A, B = functions(C) Need one more condition (normalization): Z ti+k or +∞ ti or −∞ Ni,k (u)du = 1 (ti+k − ti ) k We obtain A(ti+2 − ti ) + B(ti+3 − ti+1 ) + C(ti+2 − ti+1 ) = ti+3 − ti (6.16) From Equation 6.14 to 6.16, we obtain A= ti+1 − ti , ti+2 − ti B= ti+3 − ti+2 , ti+3 − ti+1 C=1 (6.17) Finally, Ni,3 (u) = y1 (u)Ni,1 (u) + y2 (u)Ni+1,1 (u) + y3 (u)Ni+2,1 (u) u − ti ti+3 − u = Ni,2 (u) + Ni+1,2 (u) ti+2 − ti ti+3 − ti+1 6 (6.18) 6.2.5 Example: 4th order basis function (Cubic B-spline case– K = 4 see Figure 6.3) n = 6 → 7 control points n + k + 1 = 11 knots 1 N0,4 N1,4 to N6,4 N3,4 N2,4 t4 t1 t2 t3 N4,4 t5 N0,4 is C 2 N1,4 is C 2 N4,4 is C 2 t6 2 N1,4 is C N5,4 is C2 N1,4 is C N2,4 is C 1 t7 t8 t9 2 N2,4 is C N6,4 is C0 t10 N0,4 is C-1 0 N5,4 N3,4 N4,4 N5,4 N6,4 N3,4 is C2 is is is is 2 C 1 C 0 C C-1 Figure 6.3: Cubic B-spline functions. From property 1: Ṅ0,4 (t0 ) + Ṅ1,4 (t0 ) = 0 (6.19) Ṗ(t0 ) = (P1 − P0 )Ṅ1,4 (t0 ) (6.20) Ṗ(t10 ) = (P6 − P5 )Ṅ6,4 (t10 ) (6.21) Therefore, Similarly, 7 P2 P1 t4 P3 span 2 affected by P1,P 2,P 3,P 4 P0 t5 span 3 affected by P2,P 3,P 4,P 5 span 1 affected by P0,P 1,P 2,P 3 u=t0=t1=t2=t3 t6 span 4 affected by P4 P3,P4,P 5,P 6 u=t7=t8=t9=t10 P5 P6 Figure 6.4: Example of local convex hull property of B-spline curve 8 Properties: • Local support (eg. P6 affects span 4 only), see Figure 6.4 i.e. Pi affects [ti , ti+k ] (k spans) • Convex hull (stronger that Bézier) let u ∈ [ti , ti+1 ], then Nj,k (u) 6= 0 for j ∈ i − k + 1, · · · , i (k values) i X Nj,k (u) = 1, Nj,k (u) ≥ 0 j=i−k+1 • Each span is in the convex hull of the k vertices contributing to its definition • Consequence: k consecutive vertices are collinear → span is a straight line segment • Variation diminishing property as for Bézier curves • Exploit knot multiplicity to make complex curves 6.2.6 Special case n = k − 1 The B-spline curve is also a Bézier curve in this case. T = {to = t1 = · · · = tk−1 < tk = tk+1 = · · · = t2k−1 } | 6.3 {z k equal knots } | {z k equal knots } Derivatives P(u) = P0 (u) = n X i=0 n X Pi Ni,k (u) (6.22) di Ni,k−1 (u) (6.23) i=1 di = (k − 1) 9 Pi − Pi−1 ti+k−1 − ti (6.24) 6.4 Approaches to design with B-spline curves Design procedure A 1. Designer chooses knot vector and control points. 2. Designer displays curve and tweaks control points to improve curve. Design procedure B 1. Designer starts with data points on or near curve. 2. Construct an interpolating/approximating B-spline curve. 3. Display curve and tweak control points to improve curve. 10 6.5 Interpolation of data points with cubic B-splines Given N data points: Pi , i = 1, 2, · · · , N , and no other derivative data at the boundaries. The problem is to construct a cubic B-spline curve which interpolates (precisely matches) these data points. Construction of knot vector Let û1 = 0 ûi+1 = ûi + di+1 di+1 = |Pi+1 − Pi | d= N X di → ui = i=2 i = 1, 2, · · · , N − 1 ûi d i = 1, 2, · · · , N − 1 Remove two knot values u2 and uN −1 from knot vector to obtain proper number of degrees of freedom (instead of having to prescribe boundary conditions, which could be done if needed) T = {u1 = u1 = u1 = u1 < u3 ≤ u4 ≤ · · · ≤ uN −2 < uN = uN = uN = uN } | {z } 4 times | {z internal knots=N −4 } | knots = n + 4 + 1 = (N − 4) + 4 + 4 = N + 4 → n = N − 1 R(u) = n X Ri Bi,4 (u) {z 4 times 0≤u≤1 } (6.25) i=0 n=N −1 Require that R(uj ) = N −1 X Ri Bi,4 (uj ) = Pj j = 1, 2, · · · , N (6.26) i=0 Solve for Ri (system is banded). There are also other more sophisticated ways to choose knot vector and parameterization attempting to make u proportional to arc length. 11 6.6 6.6.1 Evaluation and subdivision of B-splines De Boor algorithm for B-spline curve evaluation P33 t−t3 t4 −t3 t4 −t t4 −t3 P32 P22 t−t2 t4 −t2 t−t3 t5 −t3 t4 −t t4 −t2 t5 −t t5 −t3 P11 P13 P12 t−t2 t5 −t2 t−t1 t4 −t1 t4 −t t4 −t1 t5 −t t5 −t2 P0 t−t3 t6 −t3 t6 −t t6 −t3 P1 P2 P3 Figure 6.5: Diagram of de Boor subdivision algorithm over a cubic spline segment, where t ∈ [t3 , t4 ]. Evaluation of B-spline curves can be performed as follows (de Boor’s algorithm): P(u) = n X Pi Ni,k (u) t0 ≤ u ≤ tn+k (6.27) i=0 Let u ∈ [tl , tl+1 ) be a particular span. Ni,k (u) 6= 0 for i = l − k + 1, · · · , l Let P0i = Pi (6.28) De Boor’s recursive formula: j−1 Pji = (1 − αij )Pi−1 + αij Pij−1 , 12 i≥l−k+2 (6.29) where, αij = u − ti ti+k−j − ti (6.30) k−1 ⇒ Pk−1 = P(t) This algorithm is shown graphically in Figure 6.5. An example of the evaluation of a point on an cubic (k = 4, l = 3) B-spline curve is shown in Figure 6.6. 0 P P01 P2 1 2 2 P3 3 P P3 2 2 1 P3 1 P1 P P03 0 0 t0=t1=t2=t3 t4 u t5 t6 Figure 6.6: Evaluation of a point on a B-spline curve with the de Boor algorithm. The algorithm shown in Figure 6.5 also permits the splitting of the segment into two smaller segments of the same order: left polygon: right polygon: 13 P00 P11 P22 P33 P33 P32 P31 P30 6.6.2 Knot insertion: Boehm’s algorithm n X Pi Ni,k (t) n+1 X = i=0 P̂i N̂i,k (t) (6.31) i=0 | {z ai =    } | over [ti ]=[t0 ,···,tl ,tl+1 ,···] {z } over [ti ]=[t0 ,···,tl ,t̂,tl+1 ,···] P̂i = ai Pi + (1 − ai )Pi−1   1 0 (6.32) i≤l−k+1 l+1≤i l−k+2≤i≤l t−ti ti+k−1 −ti P2 P̂2 P1 t̂ t4 P̂3 t3 t5 P̂1 t2 t3 ≤ t̂ < t4 P3 = P̂4 P0 = P̂0 Figure 6.7: Control polygon of B-spline curve before and after knot insertion in interval [t 3 , t4 ]. By repeatedly applying knot insertion algorithm, multiple knots within the knot vector can be created. t4−t t −t 1 4 P0 P3 P2 P1 t −t1 t −t 1 t −t2 t −t 2 t5−t t −t 2 4 5 5 t6−t t −t 3 6 P2 P1 t −t3 t −t 3 6 P3 Figure 6.8: Boehm’s algorithm diagram with added knot t in interval [t3 , t4 ]. 14 6.7 Tensor product piecewise polynomial surface patches Let R(u) = n X Ri Fi (u) A≤u≤B (6.33) i=0 be 3-D (or 2-D) curve expressed as linear combinations of basis functions Fi (u). Let this curve sweep a surface by moving and possibly deforming. This can be described by letting each Ri trace a curve Ri (v) = m X aik Gk (v) C≤v≤D (6.34) k=0 The resulting surface is a tensor product surface (see Figure 6.9). R(u, v) = n X m X aik Fi (u)Gk (v) (u, v) ∈ [A, B] × [C, D] i=0 k=0 v=D R(u,v) u=A v=C v Patch D (u,v) C u A B Figure 6.9: A tensor product patch. 15 u=B (6.35) Matrix (tensor) form: R(u, v) = [F0 (u) · · · Fn (u)][aik ][G0 (v) · · · Gm (v)]T The basis functions can be: • Monomials → Ferguson patch • Hermite → Hermite-Coons patch • Bernstein → Bézier patch • Lagrange → Lagrange patch • Uniform B-splines → Uniform B-spline patch • Non-uniform B-splines → Non-uniform B-spline patch. 16 (6.36) 6.7.1 Example: Bézier patch R(u, v) = n X m X Rij Bi,n (u)Bj,m (v) 0 ≤ u, v ≤ 1 (6.37) i=0 j=0 where Rij are the control points creating a control polyhedron (net), see Figure 6.10. R 33 v R 00 R 10 R 30 1 0 u 1 Figure 6.10: A Bézier patch. Properties: • Lines of v= v̄ = constant (isoparameter lines) are Bézier curves of degree n with control points Qi = m X Rij Bj,m (v̄). (6.38) j=0 • The boundary isoparameter lines have the same control points as the corresponding polyhedron points. • The relation between the patch and Bézier net is affinely invariant (translation, rotation, scaling). • Convex hull. • No known variation diminishing property. • The procedure to create piecewise continuous surfaces with Bézier patches is complex. 17 6.7.2 Example: B-Spline patch R(u, v) = n X m X Rij Ni,k (u)Qj,l (v) n ≥ k − 1 and m ≥ l − 1 i=0 j=0 U = {u0 = u1 = · · · = uk−1 < uk ≤ uk+1 ≤ · · · ≤ un < un+1 = · · · = un+k } | {z } {z } k equal knots | {z k equal knots } V = {v0 = v1 = · · · = vl−1 < vl ≤ vl+1 ≤ · · · ≤ vm < vm+1 = · · · = vm+l } Properties: | l equal knots | {z l equal knots } • Obeys same properties as a Bézier patch to which it reduces for n = k − 1 and m = l − 1 (isoparameter lines, boundaries, affine invariance, convex hull). • Easy construction of complex piecewise continuous geometries. • Local control: 1. Rij affects [ui , ui+k ] × [vj , vj+l ]; 2. Subpatch [ui , ui+1 ] × [vj , vj+1 ] affected by Rp,q where (p, q) ∈ [i − k + 1, · · · i] × [j − l + 1, · · · j]. • Strong convex hull – each subpatch lies in the convex hull of the vertices contributing to its definition. 18 6.7.3 Example: Composite Bézier patches R R (2) (u,v) (1) (u,v) 0 ≤ u,v ≤ 1 v u Figure 6.11: Composite Bézier patches. 1. Positional continuity R(1) (1, v) = R(2) (0, v) (2) (1) i = 0, 1, 2, 3 = R0i R3i (6.39) (6.40) 2. Tangent plane (or normal) continuity (2) (1) (1) R(2) u (0, v) × Rv (0, v) = λ(v)Ru (1, v) × Rv (1, v) (direction of surface normal continuous for λ(v) > 0) Since (1) R(2) v (0, v) = Rv (1, v), (6.41) (6.42) use (1) R(2) u (0, v) = λ(v) Ru (1, v) | {z cubic in v to show (2) } (2) | {z } | {z constant cubic in v (1) (1) R1i − R0i = λ(R3i − R2i ). Therefore, collinearity of above polyhedron edges is required 19 (6.43) } (6.44) 6.8 Generalization of B-splines to NURBS The acronym NURBS stands for non-uniform rational B-splines. These functions have the • Same properties as B-splines, and • Are capable of representing a wider class of geometries. 6.8.1 Curves and Surface Patches NURBS curves are defined by Pn wi Ri Ni,k (u) i=0 wi Ni,k (u) i=0 R(u) = P n (6.45) where weights wi > 0; if all wi = 1, the integral piecewise polynomial spline case is recovered. This formulation permits exact representation of conics, eq. circle, ellipse, hyperbola. NURBS surface patches are defined by R(u, v) = Pn Pm i=0 j=0 wij Rij Ni,k (u)Qj,l (v) Pn Pm i=0 j=0 wij Ni,k (u)Qj,l (v) (6.46) where weights wij ≥ 0. This formulation allows for exact representation of quadrics, tori, surfaces of revolution and very general free-form surfaces. If all wij = 1, the integral piecewise polynomial case is recovered. 6.8.2 Example: Representation of a quarter circle as a rational polynomial y R θ x Figure 6.12: Quarter circle. Consider a quarter circle (see Figure 6.12) described in terms of trigonometric functions by x = R cos(θ) y = R sin(θ) ) for 0 ≤ θ ≤ 20 π . 2 Setting t = tan( 2θ ) and using basic identities from trigonometry, we can express x and y as functions of t:  2  x(t) = R 1−t 2 1+t  for 0 ≤ t ≤ 1. (6.47)  2t  y(t) = R 1+t 2 For the conversion of Equation 6.47 to the Bézier representation, apply      b0 1 −2 1 c2      [t2 t 1]  c1  = [t2 t 1]  −2 2 0   b1  b2 1 0 0 c0 separately to numerators and denominators to obtain the Bézier form. 6.8.3 Trimmed patches • R(u, v) is an untrimmed patch in the parametric domain (u, v) ∈ [A, B] × [C, D]. • Describe external loop as a set of edges (ie. curves in parameter space ri (t) = [ui (ti )vi (ti )] – eg. external loop the Figure 6.13 if made up of {r1 , r2 , r3 , r4 , r5 }, while the internal loop is made up of curve {r6 }. r5 D r6 r1 r4 r3 r2 C A Trimming lines Figure 6.13: Trimmed surface patch. 21 B 6.9 Comparison of free-form curve/surface representation methods Single span/patch Ferguson (monomial or power basis) Hermite Bézier Lagrange Composite Bézier Cardinal or interpolatory spline B-spline Table 6.1: Classification of free-form curve/surface representation. Property Ferguson Easy geometric representation Convex hull Variation diminishing ∗ Easiness for creation Local control Approximation ease Interpolation ease Generality Popularity ∗∗ HermiteCoons Bézier low no med no high yes no no low Lagrange Composite Bézier Cardinal Spline B-Splines NURBS med no high yes Medium no high yes high yes yes no yes no yes yes med med inappr. high high high no no no no med yes but complex no yes yes med med high high medium high high med med low med med low med med med low high but inappr. med low med med med high med med high med high high high very high Table 6.2: Comparison of curve/surface representation methods. ∗ Variation diminishing property does not apply to surfaces. ∗∗ Popularity in industry and STEP/PDES standards. 22 Bibliography [1] G. Farin. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide. Academic Press, Boston, MA, 3rd edition, 1993. [2] I. D. Faux and M. J. Pratt. Computational Geometry for Design and Manufacture. Ellis Horwood, Chichester, England, 1981. [3] J. Hoschek and D. Lasser. Fundamentals of Computer Aided Geometric Design. A. K. Peters, Wellesley, MA, 1993. Translated by L. L. Schumaker. [4] J. Owen. STEP: An Introduction. Information Geometers, Winchester, UK, 1993. [5] L. A. Piegl and W. Tiller. The NURBS Book. Springer, New York, 1995. [6] F. Yamaguchi. Curves and Surfaces in Computer Aided Geometric Design. Springer-Verlag, NY, 1988. 23