HUNGAR~JOURNAL OF INDUS1RIAL CHEMIS1RY VESZPREM Vol. 29. pp. 105-111 (2001) B-SPLINES CONTRA BEZIERSPLINES N.HERFMANN (Institute fiir Angewandte Mathematik, Universitat Hannover, Hannover, GERMANY) Received: April 9, 2001 P. E. Bezier, a mechanical and electrical engineer, developed his idea of interpolating given data during his work at Renault. Instead of using ordinary polynomials he introduced Bernstein polynomials in his algorithm. With the help of the Bernstein operator and a piecewise forgoing he invented a method to interpolate given data with a smooth spline curve. I. J. Schoenberg is often entitled as the father of B-Splines, although Laplace probably worked with some kind of B- Splines in 1820. They are introduced as basis for the spline functions, and this is the reason for their name. We present the basic properties of Bezier- and B-Splines including their shape preserving behaviour. In many examples we illustrate the main differences in their interpolating properties. Keywords: interpolation, algorithms of de Boor and de Casteljau, comonotone behaviour History (a) B-Splines 1820 P.S. Laplace worked with some kind of B- Splines 1850 N.I. Lobatschewski gave a short explanation 1946 I.J. Schoenberg started with the investigation of "basic spline curves" 1967 I.J. Schoenberg introduced the name "B-splines" 1972 M.Cox, C.de Boor, L.Mansfield invented the "recurrel}Ce relation" (b) Beziersplines 1959 P. de Casteljau worked the first time with these splines 1962 P. Bezier developed the same idea a second time 1970 R. Forrest found the connection to Bernstein polynomials B·Splines: Alternative defmitions We start proposing four different kinds of definitions for B-Splines. (a) Recursive definition Given a knot sequence of real numbers in R.: T = (Xo' XI' Xz , ••• , xn, Xn+l , ••• , Xn+l+l) Then we define Z=O: { 1 if N 0 .(x) = ,I 0 xi::;; x :s;;xi+l , i:::::O, ... ,n otherwise l >0: i=O, ... ,n (b) Definition by divided differences We use the well-known divided differences to define with { {r- x)1 if t ~ x (t-x)~ := 0 lu: ~ t and we can prove the following theorem: Theorem: Let Q..,. :={.x ... }~z,.A;, jlx,)u(x1+1• 1,oo) and Js(:c}dx=l. It is not very surprising that we can prove it easily that the four definitions lead exactly to the same functions. Theorem: All definitions above are equivalent. Dermition: We will call the functions developed in the four definitions B-Splines. Basic properties We summarize some of the important properties of B- splines in the following theorem: Theorem: 1. We have N1/x) = 0 if x\l (xi'xi+l+l), 2. We have Nz,;(X)E el-l if XE [xi'xi+l+d' 3. Wehave Nl,i(x)>O if xE (xi.xi+l+1), 4. We have the property of partition of unity: n-1 L N1,;(x) = 1 if XE [xi,xi+l+d i=-l Remarks: l. This means that the B-splines have a small support. Only in an interval with l + 2 knots we have a chance to find values unlike zero. 2. Here we are told, that the B-splines have a defect of 1, therefore the B-splines of degree l are l-1- times continuously differentiable. 3. The B-splines are positive functions. 4. We can conclude on the bound 1 for ali B~splines . SeeFig.J. T = (to, tt, t2, t:1, t4) = (0~ 1, 2~ a, 4) f(t) 1 t- 0.75 r .. 0.5 1- 0.2!) [- 0 0.5 1 1.5 2 2.5 3 3.5 4 lt- 0.7~ [ O.i:> ; Fig.2a 4 intervals /"~\ / '\ 0.25 I- / \""' ;M,....-/~"'----'-~..J....-...-!.1 -"'.;;;.~.;.,.,~---L--'-----'---· t 0 0.5 1 1.5 2 2.5 3 3.5 4 Fig.2b 3 intervals Fig.2 Support-Reduction of a B-Spline of order 3 from 4 intervals to 2 intervals, if 1 is a knot of multiplicity 3. Multiple knots Given a knot sequence Xo' x1, Xz' .•. 'xn 'xn+l' ... , xn+l+l , we did not demand that ail points should be different. What happens if some neighbor points fall together? Theorem: If xi = xi+ I = · · · = xi+l+I, then we have N 1,i (x;) = 0, i = O, ... ,n From this we conclude immediately that N 1,i = 0, which is not a very interesting result. So we ask for the case when less than l + 2 knots coincide. Theorem: If X; is a knot with multiplicity m ~ l , it follows The smoothness of a B-Spline decreases therefore with multiple knots. The decrease of the smoothness comes together with a decrease of the support of the B-spline: Theorem: If xi is a knot of multiplicity m ~ l , then the support of Nr.i(x) is reduced from l +!intervals to l + 1- (m- 1) intervals. We show this behaviour in Fig.2. 1 0.75 0.5 0.25 107 0 0.5 1 1.5 2 2.5 3 3.5 4 . Fig.2c 2 intervals Fig.3 Example of a B-Spline curve with knot sequence T=(O,O,O,O, 1,2,3,4,5,6,6,6,6). B-spline curves of degree 1 Now we come to curves built with B-splinet, At first the definition: Definition: Given l E IN and points - - - 2 3 d 0 ,d1' ... ,d 11 E IR or IR and a knot sequence then we call the following linear combination 1l B1(x) = Ld;N1,;(x), i=O a B~spline curve of degree l for the knot sequence T. d 0 ,d 1 p .. ,d 11 are the de Boor puints, they build the de Boor polygon. One of the most important properties for such a B- spline curve is its local behaviour. If one of the points Ji is changed, the curve will be changed in a small vicinity of Ji only. This is what designers whish. So the front of a car can be changed whereas the back remains unchanged. This is the content of the following theorem: 108 Theorem: Given a B-spline curve n B1(x) = Ld;N1,;(x), i=O with knot sequence T and x* E (xi,xi+l). The point on the curve belonging to x* is only influenced by the de Boor points di_1,. •• ,dr Hereby Ji acts in (xpxj+l+l) only. Figure 3 gives an example of a B-Spline curve. Bezier curves The main tool in constructing Bezier curves are the Berpstein polynomials. Defmition: B," (x)= (; }' (!-x)~1 , i = 0, ... , n, x E [0,1] We summarize some important properties of the Bernstein polynomials in the following theorem. Theorem: Bi11 (x) > 0 for xE (0,1) a ba {B; 11 h=0, ... ,n is a basis for the vector space of all polynomials of degree ~ n . If LB~ (x)= 1 for xE (0,1) i=O Definition: A Bezier curve is defined as follows: If X 11 (x):= l:b.B~(x),XE (OJ) i=O The points b; are called the controlpoints of the Bezier cun·e. There are some relations between B-Splines and Beziersplines. The next theorem shows that each spline curve can be expressed in terms of B-Splines. Theorem: Lets be a spline function of degree l in [ atb ]. Tltefl we hal'e a unique representation It ~- . - 3 s(x} = £..id;.Nu (x), d; E R ,xE [a,b] ; .. _, In a very special case we have a direct coincidence between B-Splines and Beziersplines. Theorem: The B-Splines NIJ (x) of degree I are exactly the Bemsteitz polynomials B:(x). if the knot sequence T contains 2( I+ 1) elements where both 0 and / are of multiplicity l+ I: T=(O, ...• O. ...__,_.._ dt-tlli.IIM'l l, ... ,l ) ............... tl+htws The algorithm of de Boor and de Casteljau The formula for a B-spline curve is not easy to handle. For polynomials we have the formula of Horner for a quick evaluation of single values. For B-spline curves this part is played by the algorithm of de Boor. Algorithm (de Boor) forB-Splines Given n+1 de Boor points d0 ,d1, ••• ,dn,n?:.l, and a knot sequence Find B(x*): 1. Find r with xr ~ x* < Xr+l * 2. Calculate a~ x -xi . 1 l 1 , z = r + - , ... ,r -z 1 - z- di =(1-a t) d;_1 +atdt 3. For j=2,3, ... ,l,i=r-l+j, ... ,r * a! x -xi l xi+t-u-n -xi J/ = (1-a!) Ji-li-1 +a! J/-t l I I l 4. Then we have B(x*) = J; The following table gives an impression how this algorithm works. On the horizontal lines we multiply by a/ and on the diagonal lines by 1-a/. The sum of both values gives the new de Boor point on the right: dr-1+1 -1 d r-1+1 dr-1+:!. -1 d r-1+2 -z d r-1+2 dr-1+3 -~ d r-1+3 -z d r-1+3 JI-I r-t ii, Jtr -z d r {jl-lr tPr =B(x*) The most important advantage of this algorithm is how fast it works. It is possible to evaluate thousands of points in less than a second. So this algorithm makes it possible to change a curve and in the same way a surface nearly in real time. A similar algorithm for the Bezier splines was developed by de Casteljau. It is based on the recurrence relation: b;(x) = (1- x)b;-1(x)+b 1 l!-l(x) Fig.4 13 given points which build a tunnel are interpolated with B-Splines. Algorithm (de Casteljau) for Beziersplines Given n + 1 Bezier points or control points E0 , ••• , En . Find X 11 (x*): 1. 2. 3. 4. · -o - -o ... -o .... Start wzth b0 := b0 ,b1 := bl' ... ,b11 := bn .... 1 -1 -1 Calculate b0 ,b1 , ... ,h11_ 1 using the recurrence relation above. Continue calculating b~ , ... ,bLi, i = 2, ... , n Thenwehave X 11 (x*)=b;(x*). This calculation cav be filled in a table quite similar to the table for the de Boor algorithm above. We have only to replace the de Boor points a by the Bezier points b and then to multiply in the horizontal line with x*, in the diagonal line with 1- x*, and afterwards to sum up. Interpolation using B-Splines Now we will try to compare both methods in their behaviour regarding interpolation problems. Consider the points Po, .f1, ... , Pq-l in IR 2 or IR 3 • We want to find an interpolating spline curve. For the use of B-splines we could try to take each point in the knot sequence (1+1)-times. Then the curve runs through each of the points, but it is really not a smoot!J curve. In each point there is perhaps a sharp cusp. This is therefore no answer to the problem. In order to combine the given points with the points in the knot sequence we should note, that in the interval [x0 , xz] less than l+ 1 B-splines are :1: 0 . So we try the following combination: This leads to the following linear system: It :LJi NI;(Xl+l,) = P.t, u =O,l, ... ,q-1 io::O 109 This is a system of q linear equations for the n+1unknown d0 ,dp ... ,Jn.For q=n-1+2 thereare n + 1- (n -l + 2) equations missing. For cubic splines (l=3) we have to find 2 equations more. A typical choice is to consider spline functions which are linear outside the interval [x0 , X11 ] • They are called natural and the following two equations are based on the fact that their second derivative is zero: dn_zN~:n-2 (xn+l) +dn-lN~:n- (xn+2) +dnN~:n (xn+3) = 0 Altogether we come to the following pentadiagonal system for natural cubic splines: 6 12 6 jr ~o l 11 -11 11 0 1 4 1 0 dl Po 0 J2 ~ 6 ~:T 0 0 1 4 h~ J pq-1 6 12 0 11 -11 In Fig.4 we have interpolated 13 points, which could be understood to build a tunnel, using B-Splines. But the oscilating behaviour of the curve is not acceptable. Interpolation using Beziersplines- Comonotone Interpoation After the bad result with our tunnel example using B-Splines we are interested to develop a better method for interpolating given data. One reason for the misbehaved shape can be seen in Fig.4. From the left hand side up to the midpoint the datas are monotone increasing, whereas the spline curve oscilates through the first four points. At first let us define what we want to understand by a comonotone interpolating procedure: Deimition: Consider the given data (x0,y0),(xpy1), ... ,(xn,yn) with x0 < x1 < ··· < Xn. Let sE C1[x0 ,xn] be a function which interpolates these data. Then we will calls comonotone with the data, iff s'(x)·m1 >0 if m; ¢0,xE (xi_1,xi) s"'(x} =0 if mi =0 This is easy to explain. The slope of the spline functions should always be the same sign as the slope of the straight line between two neighb< 'ur points. Then swill be monotone increasing or decrea~ing in the same intervals where the data are monotone mcreasing or decreasing. respectively. 110 !) ''"""-'"'"~"--·,-.. - ... ·-··--,---., i\ 4 ., I ~r j 1 ~ ·~ " .; (J ·u ·4 ..:l {I Fig.5 The same 13 given points as in Fig A are now interpolated with the comonotone algorithm using Bezier- Splines. The Bernstein operator and its shape preserving behaviour I The· main point in developing our new algorithm is to use the Bernstein operator. It works with the help of the Bernstein polynomials. Deimition: Let f be a vector valued continuous function on the interval [0,1]. Then the Bernstein operator is defined as In the following theorem we summarize some of the most important properties regarding the shape preserving of the Bernstein operator: Theorem: For the Bernstein operator we have: 1. f bounded ==> Bnf is bounded (with the same bounds) 2. f ;?:: 0 in [0,1] :::::? Bnf ~ 0 in [0,1] 3. Bn/(0) = /(0), Bnf(!) = /(1) 4. /monotone ==> Bnf monotone 5. f convex ==> Blff convex Now we are able to explain the algorithm: Comonotone algorithm: 1. Construct the subknots t 0 , t 1 , •••• t '1.N + 1 x. -x. 1 witlt r. = ' ~- hv t 3 • 2. Calculate the difference quotients: Y;- Yi-1 . 1 N nz; = , l = , ... , X; -xi-! 3. Determine a piecewise linear comonotone function l by l( X; ) := y i , r( X; ) := d; with d 0 :=2m1 -d1 ,dN :=2mN -dN-J andfor i=l, ... ,N-1 0 if mi ·m;+I =0 d ·- m; 3mi+I -mi if O lmi+ll m; 2 4. Calculate l(t1), l(t2i ), l(t2;+1), l(t2N) 5. Apply in each subinterval the Bernstein operator. This leads to the desired function: Remark: The formula in 3. is the heart of the algorithm. The derivative di at the knots xi is evaluated in a way that the resulting linear spline function is comonotone with the data. Because of the shape preserving behaviour of the Bernstein operator we get therefore the desired comonotone cubic spline function. In Fig.5 we show the tunnel data from above, but now comonotone interpolated. The result looks much better. Conclusion In this paper we compared B-Splines and Beziersplines. After a short introduction for both spline cancidates we explained some of the most important properties. The similar algorithms of de Boor and de Casteljau lead to very fast evaluation processes. Several figures show the different behaviour regarding the interpolation procedure. In contrast to the disadvantage of the monotony preserving of the B-Splines we propose a comonotone interpolation algorithm using Bezier splines. R SYMBOLS real numbers knots inR T = (x0 ~ .... xn+l+I) knot sequence N li B-Splines (t- x)~ +-function A =(X0 , ••• ,xn+l) given knots C 1 - 1 [a.b] (l-1)-times continuously differentiable functions IP 1 vector space of polynomials of degree less or equall S1(A) Q"" B1(x) do, ... ,dn Bt(x) xn(x) s(x) a/ Po, ... ,Pq l(x) vector space of spline functions infinite knot sequence B-Spline curve de Boor points Bernstein polynomials Bezier curve spline function coefficients in the de Boor algorithm interpolation points linear spline function difference quotients REFERENCES 1. COSTATINI, P., MORANDI, R.: Monotone and convex cubic spline interpolation, Calcolo, 1984, 21,281-294 111 2. COSTATINI, P., MORAt~DI, R.: An algrithm for computing shape-preserving cubic spline interpolation to data, Calcolo, 1984,21, 295-305 3. DEPPE, U.: Anwendung der BEM auf eine Integralgleichung 1. Art zur Bestimmung der Porenradienverteilung eines SLP-Katalysator- Pellets Diploma Thesis, Universitat Hannover, 1994 4. FARIN, G.: Curves and Surfaces for Computer Aided Geometric Design, Academic Press, Boston et al., 1990 5. GRONEWOLD, G.: Co-Monotone Spline- Interpolation in Chemical Engineering, Hung. J. Ind. Chern., 1997,25,59-62 6. HERRMANN, N.: Hohere Mathematik fUr Ingenieure I, II, Oldenbourg Verlag, Mtinchen, 1995 7. HERRMANN, N.: Spline-Funktionen und ihre Anwendung, Preprint Institut fiir Angewandte Mathematik, Uni. Hannover, 1996 8. HERRMANN, N.: Surface Fitting in CAGD via Finite Elements, Hung. J. Ind. Chern., 1997,25,63-69 9. I!OSCHEK, 1., LASSER, D.: Grundlagen der geometrischen Datenverarbeitung, B. G. Teubner, Stuttgart, 2. ed. 1992 Page 109 Page 110 Page 111 Page 112 Page 113 Page 114 Page 115