《Computational Geometry》lecnotes 6 N.M. Patrikalakis

13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lecture 6 N.M. Patrikalakis Massachusetts Institute of Technology Cambridge MA 02139-4307 USA Copyright 2003 Massachusetts Institute of Technology Contents 6 B-splines (Uniform and Non-uniform) 6.1 Introduction 6.2 Definition 6.2.1 Knot vector 6.2.2 Properties and definition of basis function Ni k(u) 6.2. Example: 2nd order B-spline basis function 6.2.4 Example: 3 order B-spline 6.2.5 Example: 4th order basis function 6.2.6 Special case n= k 6.3 Derivatives 6.4 Approaches to design with B-spline curves 6.5 Interpolation of data points with cubic B-splines 6.6 Evaluation and subdivision of B-splines 6.6.1 De Boor algorithm for B-spline curve evaluation 6.6.2 Knot insertion: Boehm's algorithm 6.7 Tensor product piecewise polynomial surface patches 6.7.1 Example: Bezier patch 6.7.2 Example: B-Spline patch 6.7.3 Example: Composite Bezier patches 8 Generalization of B-splines to NURBS 6.8.1 Curves and Surface Patches 6.8.2 Example: Representation of a quarter circle as a rational polynomial 6.8.3 Trimmed patches 6.9 Comparison of free-form curve/surface representation method Reading in the Textbook · Chapter1,pp.6-33

13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lecture 6 N. M. Patrikalakis Massachusetts Institute of Technology Cambridge, MA 02139-4307, USA Copyright c 2003 Massachusetts Institute of Technology Contents 6 B-splines (Uniform and Non-uniform) 2 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 6.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6.2.1 Knot vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6.2.2 Properties and definition of basis function Ni,k(u) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6.2.3 Example: 2 nd order B-spline basis function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 6.2.4 Example: 3 rd order B-spline basis function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6.2.5 Example: 4 th order basis function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6.2.6 Special case n = k − 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.3 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.4 Approaches to design with B-spline curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6.5 Interpolation of data points with cubic B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.6 Evaluation and subdivision of B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.6.1 De Boor algorithm for B-spline curve evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.6.2 Knot insertion: Boehm’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6.7 Tensor product piecewise polynomial surface patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.7.1 Example: B´ezier patch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6.7.2 Example: B-Spline patch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 6.7.3 Example: Composite B´ezier patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6.8 Generalization of B-splines to NURBS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6.8.1 Curves and Surface Patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6.8.2 Example: Representation of a quarter circle as a rational polynomial . . . . . . . . . . . . . . . . . . . . . . 20 6.8.3 Trimmed patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.9 Comparison of free-form curve/surface representation methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Bibliography 23 Reading in the Textbook • Chapter 1, pp. 6 - 33 1

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 Bezier curve or of one data point in a cardinal(or interpolatory) spline curve changes entire curve(global schemes) Remove necessity to increase degree of Bezier curves or construct composite Bezier curves using previous schemes in order to increase degrees of freedom Obtain a"local "approximation scheme The development extends the Bezier curve formulation to a piecewise polynomial curve with easy continuity control

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´ezier 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´ezier curves or construct composite B´ezier curves using previous schemes in order to increase degrees of freedom. • Obtain a “local” approximation scheme. The development extends the B´ezier 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)=∑PMk(u) where, Pi are n+ 1 control points; Nik(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 Bezier curves. The parameter u obeys the inequality u .2 6.2.1 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=化=三“<女≤…≤<如+1元:=t 3 k equal values 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+ l which equals the number of control points in the curve plus the curve's order 6.2.2 Properties and definition of basis function Nik(u) 1. 2i_o Ni k(u)=l(partition of unity 3. Nik(u)=0 if u ti, ti+k(local 4. Ni k(a)is(k-2) times continuously differentiable at simple knots If a knot t, is of multiplicity p(< k), ie. if then Nik(u) is(k-p-1)times continuously differentiable, ie. it is of class CK-p-

6.2 Definition A parametric non-uniform B-spline curve is defined by P(u) = Xn i=0 PiNi,k(u) (6.1) 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´ezier curves. The parameter u obeys the inequality to ≤ u ≤ tn+k (6.2) 6.2.1 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 | {z } k equal values < tk ≤ tk+1 ≤ · · · ≤ tn | {z } n−k+1 internal knots < tn+1 = · · · = tn+k | {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 Properties and definition of basis function Ni,k(u) 1. 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 u∈[t2,t+1) 0ugt1,t+1) a-t (6.6) 0 above when it occur Properties 1-4 or property 5 by itself(given a known knot vector T) define the B-spline 6.2.3 Eacample: 2 order B-spline basis function Piecewise linear case- see Figure 6.1) k=2,C t-1t;t+1t2+2t2+3 Figure 6. 1: Plot of 2nd order B-spline basis functions Ni,2() consists of two piecewise linear polynomials t;≤u≤t N2(u) t+1≤u≤t

5. Recursive definition (Cox-de Boor algorithm) Ni,1(u) = ( 1 u ∈ [ti ,ti+1) 0 u 6∈ [ti ,ti+1) (6.5) Ni,k(u) = u − ti ti+k−1 − ti Ni,k−1(u) + ti+k − u ti+k − ti+1 Ni+1,k−1(u) (6.6) (set 0 0 = 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: 2 nd order B-spline basis function (Piecewise linear case– see Figure 6.1) k = 2, C k−2 = C 2−2 = C 0 ti−1 ti ti+1 ti+2 ti+3 Ni,2(u) Figure 6.1: Plot of 2 nd order B-spline basis functions. Ni,2(u) consists of two piecewise linear polynomials: Ni,2(u) = ( u−ti ti+1−ti ti ≤ u ≤ ti+1 ti+2−u ti+2−ti+1 ti+1 ≤ u ≤ ti+2 4

6.2. 4 Example: 3a order B-spline basis functio (Piecewise quadratic case- See Figure 6.2) k=3,Ck-2=C3-2=C1 Ni.3(ti) consists of three piecewise quadratic polynomials y1(u), y2( u) and y3(a). We want to find y(a), y2(u) and y3(a) such that Y,(u. t Figure 6.2: Plot of 3a order B-spline basis function N2.3(t) 3(t)=0 Ni. 3(t: (6.7) Position continuity (6.8 t+1-t )=B(4+3-a)2 (6.9) ti+ v2(u)=A(1-s)2+Bs2+C2s(1-s) (6.11) Note that n(t+1)=y(1+1) y9(t+2)=y(t+2)=B

6.2.4 Example: 3 rd 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 3 rd order B-spline basis function. Ni,3(ti) = N 0 i,3 (ti) = 0. Ni,3(ti+3) = N 0 i,3 (ti+3) = 0. (6.7) Position continuity: y1(u) = A u − ti ti+1 − ti !2 (6.8) y3(u) = B ti+3 − u ti+3 − ti+2 !2 (6.9) y2(u) = A(1 − s) 2 + Bs 2 + C2s(1 − s) (6.10) s = u − ti+1 ti+2 − ti+1 (6.11) Note that y1(ti+1) = y2(ti+1) = A y3(ti+2) = y2(ti+2) = B 5

1(=t1 First derivative continuity: 2(C-A (6.12) t+2-t 2(B-C 2B (6.13 t+2-t hence, t2+1-t;t+2-t+1 2-t1+1 (6.14 1 4+2-1+ (6.15) t2+3-t where A, B= functions(C) Need one more condition(normalization) Nik(a)d We obtain A(t1+2-t)+B(t+3-t+1)+C(t+2-t+1)=t+3-t (6.16 From Equation 6.14 to 6.16, we obtain 4B1 t+1-t +3-1+2 t2+3-t1+1 Finall N23(u)=v1(u)N21()+y()M+11(x)+y()N+2(u) t t2+3 (6.18)

at s = 0, s = 1(u = ti+1, u = ti+2). First derivative continuity: 2(C − A) 1 ti+2 − ti+1 = 2A 1 ti+1 − ti (6.12) 2(B − C) 1 ti+2 − ti+1 = −2B 1 ti+3 − ti+2 (6.13) hence, A " 1 ti+1 − ti + 1 ti+2 − ti+1 # = C 1 ti+2 − ti+1 (6.14) B " 1 ti+2 − ti+1 + 1 ti+3 − ti+2 # = C 1 ti+2 − ti+1 (6.15) where A, B = functions(C) Need one more condition (normalization): Z ti+k or +∞ ti or −∞ Ni,k(u)du = 1 k (ti+k − ti) 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+2 − ti Ni,2(u) + ti+3 − u ti+3 − ti+1 Ni+1,2(u) (6.18) 6

6.2.5 Example: 4 order basis function (Cubic B-spline case-K= 4 see Figure 6.3 n=6→7 control points m+k+l=ll knots 2,4 七 s,4 Figure 6.3: Cubic B-spline functions From property 1 N04(to)+N1,4(to)=0 (6.19) erefore P(to)=(P1-Po)N.(to) Similarly P(t10)=(P6-P5)N64(to) (6.21)

6.2.5 Example: 4 th order basis function (Cubic B-spline case– K = 4 see Figure 6.3) n = 6 → 7 control points n + k + 1 = 11 knots t 1 o t1 t2 t3 t4 t7 t8 t9 t10 t5 t6 N0,4 N1,4 N2,4 N3,4 N4,4 N5,4 N6,4 N0,4 is C -1 N0,4 is C 2 N1,4 is C 2 N5,4 is C 2 N2,4 is C 2 N6,4 is C 0 N1,4 is C 2 N4,4 is C 2 N1,4 is C 0 N2,4 is C 1 N3,4 is C 2 N3,4 is C 2 N4,4 is C 1 N5,4 is C 0 N6,4 is C -1 Figure 6.3: Cubic B-spline functions. From property 1: N˙ 0,4(t0) + N˙ 1,4(t0) = 0 (6.19) Therefore, P˙ (t0) = (P1 − P0)N˙ 1,4(t0) (6.20) Similarly, P˙ (t10) = (P6 − P5)N˙ 6,4(t10) (6.21) 7

P span 2 affected b span 3 af ●--- ar i affected by t span 4 affected by u=t,=t。=t。=t igure 6.4: Example of local convex hull property of B-spline curve

u=t0=t1=t2=t3 t4 t5 t6 P0 P1 P2 P3 P4 P5 u=t7=t8=t9=t10 P6 span 1 affected by P0,P1,P2,P3 span 2 affected by span 3 affected by span 4 affected by P1,P2,P3,P4 P2,P3,P4,P5 P3,P4,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 ti, ti+k](k Convex hull (stronger that Bezier) let u E ti, ti+1l, then Nik(u)+0 for j Ei-k+1 ∑Nk(n)=1,NJk(n)≥ 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 Bezier curves Exploit knot multiplicity to make complex curves 6.2.6 Special case n=k-1 The B-spline curve is also a Bezier curve in this case tk-1<tk=t k equal knots k equal knots 6.3 Derivatives P(u)=∑PNk(a) P′ (6.23 P-P (6.24) t

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´ezier) let u ∈ [ti ,ti+1], then Nj,k(u) 6= 0 for j ∈ i − k + 1, · · · , i (k values) X i j=i−k+1 Nj,k(u) = 1, Nj,k(u) ≥ 0 • 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´ezier curves • Exploit knot multiplicity to make complex curves 6.2.6 Special case n = k − 1 The B-spline curve is also a B´ezier curve in this case. T = {to = t1 = · · · = tk−1 | {z } k equal knots < tk = tk+1 = · · · = t2k−1 | {z } k equal knots } 6.3 Derivatives P(u) = Xn i=0 PiNi,k(u) (6.22) P 0 (u) = Xn i=1 diNi,k−1(u) (6.23) di = (k − 1) Pi − Pi−1 ti+k−1 − ti (6.24) 9

6.4 Approaches to design with B-spline curves Design procedure A 1. Designer chooses knot vector and control point 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

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