R(t) point to be faired Figure 8.3: Kjellander's fairing method (e) Determine new curve Rnew(t) R(t) if tE[tJ-1, tj+1 Q(t) (8.18) (f)Compute Rnew(tJ). Notice that Rnew(t) is infinitely differentiable there (g) Construct a spline curve on P1,……,PJ-1,Rnen(t),PJ+1,…,PN (h)The resulting curve is usually fairer at tJ Disadvantages ● Global scheme Repeated interpolation 2. Farin's Method 4 Recall boehm's knot insertion method PN4t)=∑PN4() (8. tu, t, tu 20 and the control points are a2P+(1-a)P 21 0<i<l-3 0 l+1<i<n+1 Hence P;=P20≤i<1-3 P1=P-1l+1<i<n+1 P=aP+(1-a)P-1l-2≤i≤l
� � � � � Pj−1 Pj Pj+1 R(t) point to be faired Rnew(tj) Figure 8.3: Kjellander’s fairing method (e) Determine new curve ⎟ R(t) if t ⇒� [tJ−1, tJ+1] Rnew(t) = (8.18) Q(t) if t � [tJ−1, tJ+1] (f) Compute Rnew(tJ ). Notice that Rnew(t) is infinitely differentiable there. (g) Construct a spline curve on P1, · · ·, PJ−1, Rnew(tJ ), PJ+1, · · ·, PN . (h) The resulting curve is usually fairer at tJ . Disadvantages • Global scheme. • Repeated interpolation. 2. Farin’s Method [4] Recall Boehm’s knot insertion method n n+1 P ˆ ˆ iNi,4(t) = PiNi,4(t) (8.19) i=0 i=0 [t ˆ 0, t1, · · ·] ≤ t0, · · · , tl, t, tl+1, · · · (8.20) and the control points are Pˆi = τiPi + (1 − τi)Pi−1 (8.21) where � ⎧⎧ 1 0 � i � l − 3 τi = 0 l + 1 � i � n + 1 (8.22) ⎧⎧⎠ t ˆ−ti l − 2 � i � l ti+3−ti Hence Pˆi = Pi 0 � i � l − 3 Pˆi = Pi−1 l + 1 � i � n + 1 Pˆi = τiPi + (1 − τi)Pi−1 l − 2 � i � l (8.23) 6
. Idea of farin's method (a) remove a knot first to make curve infinitely differentiable at that location such that the curve is fairer now in that area (b) Insert the removed knot back so as to have the same knot vector(if needed; not usually necessary) ● Knot removal Knot removal is an inverse process of knot insertion. From Equations(8.23), we have P;,i=0.1.….l a2P+(1-a)P P -2,l-1 P=Px+1,t=l,l+1,……,n (8.24 Here we have n+2 equations and n+ l unknowns, therefore, an approximate solution can be obtained by the least squares method A sample solution using Farin's method P P 0,1,…,1-3 P l,1+1 825 and from the least squares method, we have the following equations for Pl-2, Pl-1 0 P P-2-(1-a1-2)P 1-al-1 P 26 P PI-agPl+ or in the matrix form which yields P=(AAAf This should be followed by knot insertion to complete the fairing process(if necessary) . Knot insertion T={to,…,t,t,t+1,…]=[1,…,T,T+1,T+2, 29 where the removed knot t is inserted as the knot Ti+1. Hence the control points of the aired curve can be determined by the knot insertion method( Equation 8.23), where t-t Ti+1-Th t1+3-tt Ti+4-T1 t1+2-t1-1T4+3-T7 t-tr (8.30)
• Idea of Farin’s method (a) Remove a knot first to make curve infinitely differentiable at that location such that the curve is fairer now in that area. (b) Insert the removed knot back so as to have the same knot vector (if needed; not usually necessary). • Knot removal Knot removal is an inverse process of knot insertion. From Equations (8.23), we have P ˆ i = Pi, i = 0, 1, · · ·, l − 3 τ ˆ iPi + (1 − τi)Pi−1 = Pi, i = l − 2, l − 1, l P ˆ i = Pi+1, i = l, l + 1, · · · , n (8.24) Here we have n + 2 equations and n + 1 unknowns, therefore, an approximate solution can be obtained by the least squares method. A sample solution using Farin’s method: P ˆ i = Pi, i = 0, 1, · · ·, l − 3 P ˆ i = Pi+1, i = l, l + 1, · · · , n (8.25) and from the least squares method, we have the following equations for Pl−2, Pl−1 ⎨ ⎛ ⎨ ⎛ τl−2 0 ˆ Pl−3 ⎝ ⎞ Pl−2 − (1 − τl−2)ˆ ⎩ ⎩ ⎜ τl−1 ⎜ Pl−2 ⎪ 1 − τ = ⎩ ˆ l−1 � ⎪ P ⎜ (8.26) l−1 � 0 1 − τl Pl−1 Pˆ ˆ l − τlPl+1 or in the matrix form A · p = f ≤ ATAp = AT f (8.27) which yields p = (ATA) −1 AT f (8.28) This should be followed by knot insertion to complete the fairing process (if necessary). • Knot insertion T = [t ˆ 0, · · · , tl, t, tl+1, · · ·] = [T0, · · ·, Tl, Tl+1, Tl+2, · · ·] (8.29) where the removed knot t ˆ is inserted as the knot Tl+1. Hence the control points of the faired curve can be determined by the knot insertion method ( Equation 8.23), where t ˆ− tl Tl+1 − Tl t τl = = l+3 − tl Tl+4 − Tl t ˆ− tl−1 Tl+1 − Tl−1 t τl−1 = = l+2 − tl−1 Tl+3 − Tl−1 t ˆ− tl−2 Tl+1 − Tl−2 t τl−2 = = (8.30) l+1 − tl−2 Tl+2 − Tl−2
If we remove all or many of the knots as in Figure 8.5, the other constraints( such as deviation) will dominate the problem Let the curve obtained by either interpolation or approximation be R()=∑RN4(t) and the curve after knot removal be Ro(t)=∑QN4(1) where m< n. Then, (n-m) knots removed before are inserted to make Ro(t) have the same knot vector as R(t), such that Ro(t)=∑QN4(t) where Q ,0<is n, are new control points determined by knot insertion, and Ni. 4 (t) are B-spline basis function over the same knot vector as that of r(t) The deviation of two B-spline curves R(t)-Ro(t)l=I2(R-Q:)Ni,4(t) max Imax R -Q remove all the knots Figure 8.5: Deviation of fair curve
� � � If we remove all or many of the knots as in Figure 8.5, the other constraints (such as deviation) will dominate the problem. Let the curve obtained by either interpolation or approximation be n R(t) = RiNi,4(t) (8.31) i=0 and the curve after knot removal be m R ˜ ˜ 0(t) = QiNi,4(t) (8.32) i=0 where m < n. Then, (n − m) knots removed before are inserted to make R0(t) have the same knot vector as R(t), such that n R0(t) = QiNi,4(t) (8.33) i=0 where Qi, 0 � i � n, are new control points determined by knot insertion, and Ni,4(t) are B-spline basis function over the same knot vector as that of R(t). The deviation of two B-spline curves �n |R(t) − R0(t)| = | (Ri − Qi)Ni,4(t)| (8.34) i=0 �n � max i |Ri − Qi| i=0 Ni,4(t) (8.35) = max i |Ri − Qi| (8.36) remove all the knots Figure 8.5: Deviation of fair curve