Open Journal of Applied Sciences, 2013, 3, 106111 doi:10.4236/ojapps.2013.31B1022 Published Online April 2013 (http://www.scirp.org/journal/ojapps) The 4Point αAry Approximating Subdivision Scheme Abdul Ghaffar1, Ghulam Mustafa1, Kaihuai Qin2 1Department of Mathematics, The Islamia University of Bahawalpur, Bahawalpur, Pakistan 2Dept. of Computer Science & Technology, Tsinghua University, Beijing 100084, P. R. China Email: abdulghaffar.jaffar@gmail.com, ghulam.mustafa@iub.edu.pk, qkhdcs@tsinghua.edu.cn Received 2013 ABSTRACT A general formula for 4point Ary approximating subdivision scheme for curve designing is introduced for any ar ity 2 . The new scheme is extension of Bspline of degree 6. Laurent polynomial method is used to investigate the continuity of the scheme. The variety of effects can be achieved in correspondence for different values of parameter. The applications of the proposed scheme are illustrated in comparison with the established subdivision schemes. Keywords: Approximating Subdivision Scheme; Binary; Ternary; Ary; Continuity; Convergence and Shape Parameters 1. Introduction Subdivision modeling methods are effective algorithms to generate continuous curves and surfaces from a dis crete set of control points by subdividing them according to some refining rules, recursively. Repetition of this process produces a very good approximation to the curve or surface defined by the original set of control points. In recent years, the subject of subdivision gained popularity due to some new applications, such as in the 3D anima tion industry. The next venture is to introduce these methods to be more consistent and efficient to the world of geometric modeling in the industry. Approximating schemes were first developed by Rham and Chaikin [1,2]. Consequent to this, a lot of work has been done by different authors in the field of binary sub division schemes, but the research communities are in terested in introducing higher arity schemes (i.e. ternary, quaternary, ...nary) which give better result and less computational cost. In late 80,s with the help of wavelet theory, a relation ship between subdivision scheme and the “mask” of re finable function have been developed. Lian [3,4] has introduced 3, 4, 5 and 6point aary interpolating schemes. In these research papers, Lian used wavelets theory, a relatively new subject area that has been deeply studied for the last two decades or so, and found many successful applications. Lian [5] also offered 2m and (2m + 1) point interpolating aary schemes for curve design ing. In 2009, Mustafa and Khan [6] for the first time in troduced a new 4point quaternary approximating subdi vision scheme. Mustafa and Najma [7] presented same perspective for constructing (2b + 2) and (2b + 4) point nary interpolating and approximating schemes. Ghaffar et al. presented unified 3point ary approximation schemes and discussed various properties [8]. This moti vates us to present 4point ary approximating scheme with high smoothness and more degree of freedom for curve designing. One of the main objectives of current work is to extend “The BSpline of degree 6” to 4point ary approximating subdivision scheme. This paper is organized as follows: General form of 4point ary subdivision scheme is constructed in Sec tion 2. The family of 4point ary approximating scheme, basic properties and analysis are presented in Section 3. Comparison of 4point ary schemes is given in Section 4. Finally conclusion is given in Section 5. 2. Main Results In this section, we are introducing family of 4point ary approximating subdivision scheme for curve de signing for any arity 2 . This family is the extension of Bspline of degree six i.e. (4point approximating sub division scheme): 1 21 1 1 2111 2 735211 , 6464 6464 121357 . 6464 6464 kkkk iiii kkkk iiii 2 k i k i ffff ffff , (1) If there exist a unique −sequence that de scribes the “two scale equation” 2 l{} k P 2 k k Pxk (2) Copyright © 2013 SciRes. OJAppS
A. GHAFFAR ET AL. 107 of scaling function . Then corresponding to this  sequence, let us introduce the notation 2 l 1 () , 2 k k k PzP zPz (3) Due to the development of the wavelet theory, the schemes (1) can be easily rediscovered by the scaling functions 4 satisfying the twoscale equations 444 4 444 44 127 212122 64 352335242125 72627, ttt t tt tttR t (4) By taking the Fourier transforms of (4), we arrive at the following twoscale equations of 4 2 444 3 2 2 44 5 3 2 44 11 721 ˆˆˆ ˆ 64 222222 35 35 ˆˆ 2222 21 7 ˆˆ 2222 iw iw iw iw iw iw ww wee ww ee ww ee 4 w 7 2 4 1ˆ. 22 iw w e This implies 4 2 2 3 2 44 3 0 2 13 11 ˆˆ. 22 41 iw iw iw j e w we j e This normalization simplifies to the following Fourier transform formulation: 444 1 ˆˆ , 22 w wP z where 4 23 43 0 3 11 , 1 4 j z Pz z j z (5) and 2. iw ze By introducing the shape parameter in (5), we get j u 4 23 42 0 3 111. 14 4 j j z Pz uz j z (6) By taking and , we get 03 4uu w 12 4(1 )uu w 2 4 4 1(1 ) ()()(1 )(1 ). 16 (1) z Pzwwzwzwz z Now, if we allow the scaling factor, denoted by a, to be , and denote such a scaling function denoted by 2 a , then the Fourier transforms of twoscale equation of a becomes , iw aaa aw wP a e and . aaa w wP a z where and again, is its twoscale symbol and (/)iw a zeaP a is then equivalent to satisfies aP 42 43 1(1 ) ()()(1)(1 ). (1 ) (2) a az PZwwzwzwz z a 3 (7) 3. Family of 4Point aAry Schemes In this section, we discuss only three 4point schemes. For setting 2,3a and 4 in (7), we obtain three poly nomials a Pza 4 with following sets of coef ficients called the mask of the 4point binary, ternary and quaternary schemes, respectively. ,2,3,4 2 4 ,13 ,5,105 , 1, 105 ,5,13, 16 www w ww ww (8) 3 4 ,13,55,143,263, 1359 ,359,263,143,, 54 55,13, ww www wwww www (9) and 4 4 ,13 ,55 ,147 ,305 , 51,717,8413 ,8413, 1, 717 ,51,305,147 , 128 55,13, ww www wwww www w www (10) Order of continuities of the above schemes is given in Table 1. One can easily find the order of continuity over the parametric intervals by using the approach of [9]. 3.1. Support of Basic Limit Function The basic function of a subdivision scheme is the limit function of the proposed scheme for the following data 01, 0, 0, 0. i i fi (11) 2 3 The following theorem is related to the support of ba sic limit functions of the 4point aary scheme. Theorem 1. The basic limit functions of 4 pro posed 4point aary approximating schemes have support Φ a Copyright © 2013 SciRes. OJAppS
A. GHAFFAR ET AL. Copyright © 2013 SciRes. OJAppS 108 Table 1. The order of continuity of proposed 4point aary schemes for certain ranges of parameter. Scheme Parameter Cn Scheme Parameter Cn Binary 35 22 w C0 Quaternary 33 14 2 w C0 ... 35 22 w C1 ... 1319 22 w C1 ... 13 22 w C2 ... 35w C2 ... 13 22 w C3 ... 13w C3 01w C4 ... 1 4 w C5 Ternary 23 31 44 w C0 ... 71 22 w 1 C1 ... 24w C2 ... 13w C3 (a) (b) (c) Figure 1. (ac) represent the basic limit functions of the 4point binary, ternary and quaternary schemes, respectively. by 411 2 a a on both sides. Hence after k subdivision width 41 1 a sa , for which implies 2, 3,4,...,,am that it vanishes outside the interval 4141 , 2121 aa aa . steps the furthest nonzero vertex on the left will be at 2 1 0 41111 2 41 1 . k k j j a aaa a aa Proof. Since the basic function is the limit function of the scheme corresponding to (7) for the data (11), its support width “s” can be determine by computing how far the effect of the nonzero vertex 0 0 will propagate along by. As the mask of aary 4point scheme is 41a long sequence by centering it on that vertex; the dis tances to the last of its left and right nonzero coefficients So the total support width is 0 411 41 2. 1 j j aa aa a are equal to 41 2 a At the first subdivision step we see 3.2. Precision Set that the vertices on the both sides of 1 0 at 41 2 a are For approximating schemes, we do not expect new verti ces to be lie on the same curve as old ones, so it is nec essary to look to see whether all the vertices lie on a common curve. We can calculate the order of precision by using the technique as given in [10]. the furthest nonzero new vertices. At each refinement, the distances on both sides are reduced by the factor 1 a. At the next step of the scheme, this will propagate along
A. GHAFFAR ET AL. 109 Lemma 2. The scheme (3.1) has cubic precision. Proof. We carry out this result by taking our origin the middle of an original span with ordinate ,5,3,1,1,3,5, nnnnnn If n x, then we have 1234 4321 1111 4321 4321 ,531 1 5311, 3113, 3113, , 1135, nnn nnnn nnnn nnnn nn nn ya aa a aaaa aaaa aaaa aaaa , n where 1234 375 ,,, 1616 1616 aaaa 1 . If 1 x, then we have 2 531135 ,,,,,,, 2 22222 ,1,1,1,1,1, 0, y y y where represents the differences of the vertices. If 2 x, then we have 15 73 3 , 2,2,2,2 2 222 715 2,2, 22 y wwww ww , Taking further differences, we get . 30y If 3 x, then we have ,2515,9 9,22, 22,99,2515, yww ww w w by taking further differences, we get . 4 δy0t Thus the scheme has cubic precision. For this analysis we observe that the scheme (8) is de signed so that it has cubic precision for any value of . While the schemes (9) and (10) have cubic precision for w any value of w and with the special values 1 w3 and 1 w 2 , the schemes have quartic precision, respectively. 4. Comparison and Application In this section, we show that the popular existing schemes are special cases of our proposed family of schemes (8) (10). With the special values of parameter (w0 and 1 w4 ), the subdivision schemes generated by Bsplines of degree 4 and 6, respectively, are obtained from the schemes (8). Moreover, the proposed scheme (8) is a generalized scheme, as the mask of the proposed scheme coincides with the mask of schemes [9,1113] after setting 5 w, 8 1 w0,wω 6 and wu respectively. It may be noted that if we put 11 wω,w u 6162 1 3 and 35 w24 in (9), the proposed 4point scheme can also be consid ered as the general form of the stationary 4point ternary approximating schemes of [8,13,16], respectively. For substituting 21 w8 , the obtained mask of scheme (10) coincides with mask of the famous 4point quaternary scheme of Ko [17]. Here we compare our proposed schemes with the ex isting binary, ternary and quaternary schemes (see Table 2). It is observed that the continuity and approximation order of proposed schemes are better than the existing schemes. Moreover, Figure 2 is exposed to show the role of free parameters when the schemes (8)(10) applied on discrete data points. In Figure 2(a), black, red and blue lines show the visual smoothness of the binary scheme at the parametric values 1 0, 8 ww and 1 2 w , re spectively. In Figure 2(b), blue, green, black and red lines show the visual smoothness of the ternary scheme at the parametric values 1 1,, 0 2 ww w, and 1 2 w , respectively. In Figure 2(c), blue, green, black and red lines show the visual smoothness of the quaternary scheme at the parametric values 1,w 1, 2 ww 0 and 1 2 w , respectively. From Figure 2, we conclude that the behavior of the limiting curve acts as tightness/looseness when the values of free pa ameter vary. r Copyright © 2013 SciRes. OJAppS
A. GHAFFAR ET AL. Copyright © 2013 SciRes. OJAppS 110 Table 2. Comparison of 4point ternary schemes. Type Support Scheme Order Cn Binary 4point [18] Inteng rpolati6 4 1 Binary 4point [19] Interpolating 4 6 1 Binary 4point [12] Approximating 7 4 2 Interpolating Ternary 4point [20] 5 4 1 Interpolating 5 3 Ternary 4point [21, 3] 1 Interpolating Ternary 4point [22] 5 2 Interpolating 5 Ternary 4point [3] 3 1 Ternary 4point [16] Approximating 4 5.5 2 Approximating 5 4 Quaternary 4point [17] 2 Approximating 4 Quaternary 4point [6] 5 3 Approximating 7 3 Binary 4point proposed 5 Approximating 5 Ternary 4point proposed 5.5 3 Approximating 5 5 Quaternary 4point proposed 3 (a) (b) (c) Figure 2. ectively. . Conclusio oint aary approximating schemes for 027), the National Natural a (60973101) and HEC Paki G. de Rham, “Un Peude Mathematiques a Proposed Une Courbe Plane,” Revwede Mathematiques Elementry II, Oevred Comp (ac) show the role of shape parameter of the schemes (8), (9) and (10) resp 5ns 6. Acknowledgement The families of 4p curve design were established in general. The first family is binary, the second is ternary and the third family is quaternary approximating. The support of subdivision scheme influences the locality. One of the best ways to get a smaller support is to raise the arity. This is one of the advantages of the proposal of the scheme. We have also studied its continuity and determined its order of precision. It is observed that the order of precision set increases by increasing the arity of the schemes while the continuity decreases by increasing the arity of the scheme. Moreover, we have showed that several previ ously proposed schemes are members of this family. It has been shown that proposed schemes are better than existing schemes in the sense of smoothness and ap proximation order. This work is supported by the Beijing Municipal Natural Science Foundation (4102 Science Foundation of Chin stan. REFERENCES [1] letes, 1947, pp. 678689. [2] G. M. Chaikin, “An Algorithm for HighSpeed Curve Generation,” Computer Graphics and Image Processing, Vol. 3, No. 4, 1974, pp. 346349. doi:10.1016/0146664X(74)900288 [3] J. A. Lian, “On Aary Subdivision for Curve Design: I. 4point and 6point Interpolatory Schemes,” Applications
A. GHAFFAR ET AL. 111 and Applied Mathematics: An Inte 3, No. 1, 2008, pp.1829. rnational Journal, Vol. 7. p. 434444. [4] J. A. Lian, “On Aary Subdivision for Curve Design: II. 3point and 5point Interpolatory Schemes,” Applications and Applied Mathematics: An International Journal, Vol. 3, No. 2, 2008, pp. 17618 [5] J. A. Lian, “On aary Subdivision for Curve design: III. 2mpoint and (2m+1) point Interpolatory Schemes,” Ap plications and Applied Mathematics: An International Journal, Vol. 4, No. 2, 2009, p [6] G. Mustafa and F. Khan, “A New 4point Quaternary Approximating Subdivision Scheme,” Abstract and Ap plied Analysis, Vol. 2009, Article ID 301967, 14 pages. [7] G. Mustafa and A. R. Najma , “The Mask of (2b + 4)point nary Subdivision Scheme,” Computing, Vol. 90, No. 12, 2010, pp. 114. doi:10.1007/s006070100108x [8] A. Ghaffar, G. Mustafa and K. Qin, “Unification and Application of 3point Approximating Subdivision Schemes of Varying Arity,” Open Journal of Applied Sciences, Vol. 2, No. 4B, 2012, pp. 4852. doi:10.4236/ojapps.2012.24B012 [9] M. F. Hassan and N. A. Dodgson, “Ternary and Threepoint Univariate Subdivision Schemes,” In: A. Cohen, J. L. Marrien, L. L. Schumaker (Ed Surface Fitting: SantMalo2002, N s.), Curve and ashboro Press, Brent nger, 2002, pp. 5168. wood, 2003, pp. 199208. [10] N. Dyn, “Analysis of Convergence and Smoothness by the Formalism of Laurent Polynomials,” In: A.Iske, E. Quak, M. S Floater (Eds), Tutorials on Multiresolution in Geometric Modelling, Spri doi:10.1007/9783662043882_3 [11] G. Mustafa, F. Khan and A. Ghaffar, “The Point Ap proximating Subdivision Scheme,” Lobachevskii Journal of Mathematics, Vol. 30, No. 2, 2009, pp. 138145. doi:10.1134/S1995080209020061 [12] N. Dyn, M. S. Floater and K. Horman, “A FourPoint Subdivision Scheme with Fourth Order Accuracy and its Extension,” In Mathematical Methods for Curves and Surfaces: Tromso 2004, M. Daehlen, K. Morken, and L ring, 2009, pp. . L. Schumaker (eds.), 2005, pp. 145156. [13] H. Zheng, M. Hu and G. Peng, “Pary Subdivision Gen eralizing Bsplines,” Second International Conference: On Computer and Electrical Enginee 214218. doi:10.1109/ICCEE.2009.204 [14] A. Ghaffar and G. Mustafa, “A Family of EvenPoint ternary Approximating Schemes,” ISRN Applied Mathe matics, Vol. 2012, 2012, Article ID 197383, 14 pages. er [15] H. Zheng, M. Hu and G. Peng, “Ternary Even Symmetric 2npoint Subdivision,” International Conference on: Computational Intelligence and Software Engine ing,2009, pp. 14.doi:10.1109/CISE.2009.5363033 [16] K. P. Ko, B. G. Lee and G. Joon Yoon. “A Ternary 4point Approximating Subdivision Scheme,” Applied Mathematics and Computation, Vol. 190, 2007 [17] K. P. Ko, “A Quatnary Approximating 4point Subdivi sion Scheme,” J. KSIAM, Vol. 13, No. 4, 2009, PP. 307341. [18] C. Beccari, G. Casciola and L. Romani, “A Nonstationary Uniform Tension Controlled Interpolating 4point Scheme Reproducing Conics,” Computer Aided Geometric Design, Vol. 24, No. 1, 2007, pp. 19. [19] G. Casciola and L. Romani. “An Interpolating 4point Ternarynonstationary Subdivision Scheme with Tension Control,” Computer Aided Geometric Design, Vol. 24, . 1, 2009, pp. 916927. No. 2, 2007, pp. 210219. [20] G. Casciola and L. Romani, “Shape Controlled Interpola tory Ternary Subdivision,” Applied Mathematics and Computation, Vol. 215, No [21] G. Deslauriers and S. Dubic, “Symmetric Iterative Inter polation Process,” Constractive Approximation, Vol. 5, No. 1, 1989, pp. 4968. doi:10.1007/BF01889598 [22] M. F. Hassan, I. P. Ivrissimitzis, N. A. Dodgson and M. A. Sabin, “An Interpolating 4points C2 Ternary Stationary Subdivision Scheme,” Computer Aided Geometric Design, Vol. 19, 2002, pp. 118. Copyright © 2013 SciRes. OJAppS
