 Open Journal of Applied Sciences, 2013, 3, 263-269 doi:10.4236/ojapps.2013.33033 Published Online July 2013 (http://www.scirp.org/journal/ojapps) A Unified Interpolating Subdivision Scheme for Curves/Surfaces by Using Newton Interpolating Polynomial Faheem Khan*, Irem Mukhtar, Noreen Batool Department of Mathematics, University of Sargodha, Sargodha, Pakistan Email: *fahimscholar@gmail.com, irammukhtar1133@hotmail.com, noreen_batool@yahoo.com Received April 1, 2013; revised May 12, 2013; accepted May 20, 2013 Copyright © 2013 Faheem Khan et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. ABSTRACT This paper presents a general formula for (2m + 2)-point n-ary interpolating subdivision scheme for curves for any in- teger m ≥ 0 and n ≥ 2 by using Newton interpolating polynomial. As a consequence, the proposed work is extended for surface case, which is equivalent to the tensor product of above proposed curve case. These formulas merge several notorious curve/surface schemes. Furthermore, visual performance of the subdivision schemes is also presented. Keywords: Interpolating Subdivision Scheme; Tensor Product Scheme; Newton Interpolating Polynomial 1. Introduction Subdivision schemes have become important in recent years because of giving a specific and proficient way to describe smooth curve/surfaces. It is an algorithm method to generate smooth curve/surfaces as a sequence of suc- cessively refined polyhedral meshes. Their beauty lies in the elegant mathematical formulation and simple imple-mentation. The flexibility and simplicity of subdivision schemes become more appropriate in computer and in- dustrial applications. There are two general classes of subdivision scheme namely interpolating and approximating. If the limit curve/ surface approximates the initial control polygon and that subdivision, the newly generated control points are not in the limit curve/surface, the scheme is said to be ap- proximating. It is called interpolating if after subdivision, the control points are interpolated on the limit curve/ surface. Among interpolating subdivision scheme 4-point interpolating scheme  was one of the initial scheme. Nowadays spacious mixture of interpolating scheme [2-8] has been anticipated in the literature with different shape parameters. In 1978, Catmull-Clark  and Doo-Sabin  first introduced subdivision surface schemes, which genera- lised the tensor product of bicubic and biquadratic B- splines respectively. After that, Kobbelt  gave the tensor product of the curve case and he generalized the four-point interpolatory subdivision scheme for curve to the surface by using tensor product. The proposed work gives a new idea in finding subdi- vision rules for curves and surfaces using Newton inter- polating polynomial. The proposed method is simple and avoids complex computation when deriving subdivision rules. Since higher arity subdivision schemes have high approximation order and lower support than their coun- terpart of lower arity schemes. Therefore researchers are focusing in introducing higher arity schemes (i.e., ternary, quaternary, ..., n-ary). This paper presents a general for- mula for (2m + 2)-point n-ary interpolating rules for curves. Since the subdivision schemes for surface design have gained more popularity in computer animation in- dustries. So, a new approach for regular quad meshes using 2-dimensional Newton interpolating formula is also the part of this paper. In the following section, there is presented a brief in- troduction about the preliminary concepts used in this work. In Sections 3 and 4, new formula for interpolating subdivision schemes is given for curves and surfaces by using Newton interpolating polynomial. In Section 5, application of the subdivision schemes is also accessible. A few remarks and conclusions are given in Section 6. 2. Preliminaries Given a sequence of control points ,,1kNipiN, where the upper index 0k*Corresponding author. Copyright © 2013 SciRes. OJAppS F. KHAN ET AL. 264 indicates the subdivision level. An n-ary subdivision curve is defined by 1,0,0,1,..., 1,mkkniji jjpap nn (2.1) where m > 0 and ,01,0,1,..., 1.mjja  (2.2) The set of coefficients ,j 0,0,1,...,1 mjan is called subdivision mask. In the limit the proc- ess (2.1) defines an infinite set of points in The sequence of control points ,k.Nkip1 is connected, in a natural way, with the diadic mesh points The process then defines a scheme whereby and replaces the values and at the mesh points S and 1ni n i/,kkitini1knip1kip1knip.1kni npkipktkt respectively,  while is inserted at the new mesh points 111()kknii itntnkt for 1,2,...,1.n Labeling of old and new points is shown in Figure 1, which illustrates subdivision scheme (2.1). Let 21mbe the space of all polynomials of degree where m is non-negative integer. If 1,1m2mjjmxis fundamental Newton polynomial corre- sponding to the node point 1mjmj1is defined by  21mmjjmPx aNxj (2.3) In general, the coefficient of the Newton form of polynomial is called divided difference, the divided dif- ference 0n is a symmetric function, hence can be found by following method, [x,..., x],jay,,[,..., ],,mmjjijmj mjimimikyxxpapx xxxik j (2.4) and can originate by the subsequent way, Ν(x)j 11,,,jjkmkjNx ikkj (2.5) 3. Construction of the Subdivision Scheme for Univariate Case This section gives the construction of (2m + 2)-point bi- nary and ternary interpolating schemes. Then by induc- tion, a general formula for (2m + 2)-point n-ary interpo- lating subdivision scheme is formulated for curve case. 3.1. (2m + 2)-Point Binary Interpolating Scheme To construct the rules for binary 2-point interpolating scheme, consider 10jjx be the Fundamental Newton polynomial to the node points {0, 1}. The New-ton polynomial replicate linear polynomial P in the way that taking m = 0 in (2.3), we achieve  110,jjjPxaN x (3.1) where j is divided difference can be calculated by (2.4), and by setting in (2.5). This implies that aΝ(x)j 101010011 xPxpp pxCp C ,  (3.2) with following Gamma function  1.11xxCx   Now, to construct the desired 2-point ternary subdivi- sion scheme, let 1121 21110, .2iippip pi  Since we want to construct uniform and stationary scheme reproducing polynomials up to a fixed degree, it is sufficient to consider the case i = 0 with subdivision level k = 0. This implies that (a) (b) (c) Figure 1. Solid lines show coarse polygons whereas dotted lines are refined polygons. (a)-(c) represent binary, ternary and quaternary refinement of coarse polygon using (2.1) for n = 2, 3, 4 respectively. Copyright © 2013 SciRes. OJAppS F. KHAN ET AL. 265 10(0) ,pp 1011 1.22 2pp 1p Now as an affine combination of 2-point 111,,kkiipp we suppose that at (k + 1)th level, the point 12kip is attached to the parametric value 12,2ki so the desired binary 2-point interpolating subdivision scheme is given by 12121 1,11.22kkiikkiipppppki0,1 (3.3) In composite form (3.3) can be written as  1120011 ,kxiipCpC  (3.4) where  1,.11kxixpC xx2    Continuing in the same way for m = 1 in (2.3), where be the Newton polynomial to the node points {−1, 0, 1, 2} then we have the following compact form of 4-point binary subdivision scheme Ν(x)j 123110011 ,kixipCp C   0,1 (3.5) where  12,.21xxCxx2    Consequently, we can generate a general form of (2m + 2)-point binary interpolating scheme, which is of the following form  21120011mkxiiimpCp  ,Cm (3.6) where  1,0,11xm xmCxm  1 corresponding to ,2xm0 and subdivision level 0.k3.2. (2m + 2)-Point Ternary Interpolating Scheme To construct the rules for ternary 4-point interpolating scheme, consider 21jjx be the Newton polyno- mial to the node points {−1, 0, 1, 2}. The Newton poly-nomial reproduces cubic polynomial P in the way that taking m = 1 in (2.3), we achieve  231.jjjPxaN x (3.7) Now by using (2.4) and (2.5) in (3.5), we have  3101210132101311001122133611 xiPxpp pxpppxxppppxxCp C  .  (3.8) Now to construct the 4-point ternary subdivision scheme, take 11 133 313323120, ,.33ii ippip pippi     (3.9) From (3.7) and (3.8), we get 300,pp 310131011520 10422p,381 2727802410205p,381272780pppppp pp we attain the following iterative rules for ternary 4-point interpolating subdivision scheme, 1313111 213211 2,520104,8127 2780410205.8127 2780kkiikkkkiiiikkkkiiiipppppppppp kikipp 1,2 (3.10) In composite form, the above rules can be written as  311310011 ,0,kkxiipCpC (3.11) where 2,.21xxCxx3    Accordingly, general formula for (2m + 2)-point ter- nary interpolating scheme is given by  21130011mkxiimpCp,mC  (3.12) Copyright © 2013 SciRes. OJAppS F. KHAN ET AL. 266 where  1,0,1,11xm xmCxm   2 corresponding to ,3xm0,C and subdivision level 0.k3.3. (2m + 2)-Point n-Ary Interpolating Subdivision Sc h e me (Ge n er a l ization) Now there is presented a general formula for (2m + 2)- point n-ary (i.e. binary, ternary and so on) interpolating subdivision scheme by using Newton interpolating poly-nomial. This new formula will be helpful to drive inter-polating subdivision rule plainly and quickly. The gen-eral formula for (2m + 2)-point n-ary interpolating subdi-vision scheme has the following form  2110011mkxni impCp  m (3.13) where  1,0,1,..., 111xm xmCnxm    corresponding to ,xmn0 and indicates 0kthe subdivision level, where n stand for n-ary scheme. Remark 3.1. In the following, we see that some other well-known interpolating schemes come from our pro-posed Formula (3.13).  Setting the value of m = 1, and n = 2, in above result, which is the 4-point DD scheme , 1212111 2,1991.1616 1616kkiikkkkiiiipppppp  kip  By setting m = 2, and n = 2, in proposed result, we get 6-point DD scheme , 121212 112,32575256256 12875253 .128 256256kkiikkkkiiiikkiipppppppp 3kip  Taking m = 1, and n = 3 in (3.13), we get ternary 4-point interpolating scheme , 1213111 213211 2,520204,8127 27814202058127 2781kkiikkkkiiiikkkkiiiipppppppppp   By setting m = 2, and n = 3 in (3.13), we get ternary 6-point interpolating scheme , 1213111 213211 2,520204,8127278142020581272781kkiikkkkiiiikkkkiiiipppppppppp kikipp 2, 4. Tensor Product of (2m + 2)-Point n-Ary Interpolating Subdivision Scheme Given a sequence of control points , ,kNijp,,ij N where the upper index indicates the subdivision level. An n-ary subdivision surface scheme in the tensor product form is defined by 0k1,,,,00, ,0,1,...,1,mmkkninjrsir jsrspaap  n (4.1) where ,0mrra and ,s 0msa satisfy (2.2). Given ini- tial values 0,,, ,Nijpijp then in the limit the process (4.1) defines an infinite set of points in The sequence of values is related, in a natu- k.N,kijral way, with the diadic mesh points ,,,kkijijnn . The process then defines a scheme whereby 1,kni njp replaces the value at the mesh point /,/kinjnp//,kkinjnnn for ,(0,n), while the val-ues 1,kni njp are inserted at the new mesh points 1,knjnn1kni for ,0,1,...,n1. Labeling of old and new points is shown in Figure 2 which illustrates subdivision scheme (4.1). Here, we present a general formula for tensor product of (2m+2)-point n-ary interpolating scheme in the fol-lowing form,  12 1212 121212 12212 11,00 0011mmkninjp         121122121 2112 2,,xm xmimj mCC pCC   (4.2) where   11122211111 122222 21,111.11xmxmxmCxmxmCxm kikipp Copyright © 2013 SciRes. OJAppS F. KHAN ET AL. Copyright © 2013 SciRes. OJAppS 267ss (a) (b) (c) Figure 2. Solid lines show one face of coarse polygons whereas dotted lines are refined polygons. (a)-(c) can be obtained by subdividing one face into four, nine and sixteen new faces by using (4.1) for n = 2, 3, 4 respectively. Here, 13,3 1, 1,, 1,252010 4,8127 2781kkkki jijijijijpppp  10,1,..., 1n corresponding to 1n,xkp 20,1,..., 1n corresponding to 2,xn0, 0mk 13,32, 1,410205,81 27kkkkki jijijppppp , 1,227 81ij ijindicate the subdivision level and . k 4.1. In the foatsomhe bivariate interpes come from our pr).  For obtainingivision scheme, subin (4.2), we have 12,2nnRemar llowing, it is to be noted th e of tolating subdivision schem131,31, ,1,2,520104,8127 2781kkkkkijij ij ijijppppp  oposed formula (4.2 Kobbelt  subd- 1kp3 1,311,11,1,11,2, 1,,1 ,21,11,1, 11,225100 5065612187 21872010040065612187729200 8050729 21872187200 10040729 7292187206561kkkijijij ijkkki jijijkk kijiji jkk kij ijijppppppppppp p   stitute 12,2nn and 12,2mmthe following refinement rules,  12,2, ,kkij ijpp12,2 11,,1,2,11991,16 1616 16199kkkkkijij ij ij ijkkkpppppppp     21,2, 1,,1,2121,2 11,11,1, 11, 21,16 1616 16199256256 25619256 256kki jijijijijkkkki jijijijkij ipppppppp  ,1,,1 ,21,11,1, 11,22, 12,2, 12,28125681 99256 25625681 819256 25625619256 25691.256 256kkjijkk kijiji jkk kijijijkkij ijkkij ijpppppp ppppp     For obtaining tensor product of ternary 4-point inter- polating scheme, taking the values2, 12,2, 12,28021874016 ,2187 6561kkijijkkij ijpppp  13 1,321,11,1,11,2,1,,1 ,21,11,1, 11,2205010065612187 21872580 20065612187 729400 10040729 21872187100 20050729 7292187166561kkki jijijijkki jijijkk kijiji jkk kij ijijpppppppppp pkkpp2, 12,2, 12, 24021878020 ,2187 6561kkij ijkkijijpppp   12,3nn and in (4.2), we get the folloent 12,1mm rules, wing refinem132,31,,1,2,410205,8127 2781kkkkijijijiji jpppp  kp13,3,,kkij ijpp F. KHAN ET AL. 268 13 2,311,11,1,11,2,1,,1 ,21,11,1, 11,22080 4065612187 21871650 20065612187 729100 40100729 21872187400 20080729 7292187256561kkki jijijijkkijijijkk kijiji jkk kij ijijpppppppppp pp    kkpp2, 12,2, 12,210021875020 ,2187 6561kkijijkkij ijppp   13 2,321,11,1,11,2, 1,,1 ,21,11,1, 11,21640 8065612187 2187204010065612187 729200 5080729 21872187200 400100729 7292187206561kkki jijijijkki jijijkk kijiji jkk kijijijpppppppppp pp    kkpp2, 12,2, 12,250218710025 .2187 6561kkij ijkkijijppp   Lemma 4.1.  Given initial control polygon let the values be de- subdivision pgether with (2.2), then the schemes derived by tensor product naturally get four-sided support regions. Remark 4.2. It can be loosely say that the support is the tensor product of the supports of the two regions, just as one can loosely say that Kobbelt subdivision scheme for surface  is the generalization of the tensor prodct 4-point DD subdivision scheme . Lemma 4.2.  Given initial control polygon let the values be de- subdivision pgether with (2.2), then if a scheme is derived from a tensor product, then the level of continuity can be determined between pieces by reference to the underlying basis func- tiocontinuity as their cou0,,,ij ijpp fined recu,,ijrsively by,,1kijpkrocess (4.1) tou0,,,ij ijpp fined recu,,ijrsively by,,1kijpkrocess (4.1) tons, i.e., all the tensor product schemes have the same nterparts. 5. Application This section is devoted for the visual performance of curves/surfaces. It is illustrated by some examples, ob-tained from the proposed work (3.13) and (4.2). The stepwise subdivision effects are shown in Figures 3 and 4. (a) (b) (c) (d) (e) (f) Figure 3. Dotted line indicate initial polygon whereas continu-ous curve generated by terna- and 6-point interpolating subdivision schemes . (a) 4t: 1st level; (b) 2nd level; (c) 3rd level; (d) 6-point: 1st level; (e) 2nd level; (f) 3rd level. ry 4-poin (a) (b) (c) (d) Figure 4. Tensor product of 4-point binary approximating scheme: (a)-(d) show the initial polygon, 1st-, 2nd-subdivi- sion levels and limit surface respectively. Copyright © 2013 SciRes. OJAppS F. KHAN ET AL. Copyright © 2013 SciRes. OJAppS 2696. Conclusion This work gives a variety of subdivision schemes for the univariate and bivariate cases by using Newton’s inter-polating formula. The work presented here is a new ap-proach to the subdivision rules, which reduce the computational cost. Most of the well-known subdivisionschemes are the special cases of the proposed work (3.13)and (4.2). 7. Acknowledgements The authors are pleased to acknowledge the mysterious referees for their careful reading of the manuscript andprecious comments, which made this manuscript moreconstructive. First author pays special thanks to Dr. Sha-hid Mubeen for his assistance in research. Interpolating 4-Point2CTernary Stationary Subdivision Scheme,” Computer Aided Geometric Design, Vol. 19, No. 1, 2002, pp. 1-18. doi:10.1016/S0167-8396(01)00084-X  M. K. Jena, P. Shunmugaraj and P. C. Das, “A Non-Sta- tionary Subdivision Scheme for Curve Interpolation,” Anziam Journal, Vol. 44, 2003, pp. 216-235.  G. Mustafa and F. Khan, “Ternary Six-Point Interpolatig Subdivision Scheme,” Lobachevskii Journal of Mathe- - matics, Vol. 29, No. 3, 2008, pp. 153-163. doi:10.1134/S1995080208030062  A. Weissman, “A 6-Point Interpolatory Subdivision Scheme for Curve Design,” M.Sc. Thesis, Tel Aviv University, Tel Aviv, 1990.  E. Catmull and J. Clark, “Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes,” Computer Aided Design, Vol. 10, No. 6, 1978, pp. 350-355. doi:10.1016/0010-4485(78)90110-0  Doo and M. Sabin, “Bahaviour of Recursive Division Durfaces near Extraordinary Points,” Computer Aided Design, Vol. 10, No. 6, 1978, pp. 356-360. doi:10.1016/0010-4485(78)90111-2REFERENCES  N. Dyn, D. Levin and J. A. Gregory, “A 4-Point Interpo-latory Subdivision Scheme for Curve Design,” Computer Aided Geometric Design, Vol. 24, No. 4, 1987, pp. 257- 268. doi:10.1016/0167-8396(87)90001-X pp. 409-420.  L. Kobbelt, “Interpolatory Subdivision on Open Quadri- lateral Nets with Arbitrary Topology,” Computer Graph- ics Forum, Vol. 15, No. 3, 1996, asciola and L. Romani, “An interpolating C. Beccari, G. C doi:10.1111/1467-8659.1530409  G. Deslauries and S. Dubuc, “Symmetric Iterative Inter- polation Process,” Constructive Approximation, Vol.1, 1989, pp. 49-68. 4-Point 2C Ternary Non-Stationary Subdivision Scheme with Tension Control,” Computer Aided Geometric De- sign, Vol. 24, No. 4, 2007, pp. 210-219. doi:10.1016/j.cagd.2007.02.001  N. Dyn, “Interpolatory Subdivision Scheme and Analysis of Convergence and Smoothness by the Foralism of Laur- ent Polynomials,” In: A.Iske, E. Quak and M. S. Floater, Eds., Tling, Springer 5, No. 889598doi:10.1007/BF01utorials on Multiresolution in Geometric Model-, Berlin, 2002, pp. 51-68 (Chapter 2 and 3)odgson, “Ternary and Three- Schemes,” In: A. Cohen, J. .  M. F. Hassan and N. A. DPoint Univariate SubdivisionL. Marrien and L. L. Schumaker, Eds., Curve and Surface Fitting: Saint-Malo, 2002, Nashboro Press, Brentwood, 2003, pp. 199-208.  M. F. Hassan, I. P. Ivrissimitzis and N. A. Dodgson, “An ournal, Vol. eometric . 51-68 (Chapter 4). . 106-123.  J. A. Lian, “On A-Aray Subdivision for Curve Design: 4-Point and 6-Point Interpolatory Scheme,” Applications and Applied Mathematics: An International J3, No. 1, 2008, pp. 18-29.  M. Sabin, “Eigenanalysis and Artifacts of Subdivision Curves and Surfaces,” In: A. Iske, E. Quak and M. S. Floater, Eds., Tutorials on Multiresolution in GModelling, Springer, Berlin, 2002, pp N. A. Dodgson, U. H. Augsdorfer, T. J. Cashman and M. A. Sabin, “Deriving Box-Spline Subdivision Schemes,” Springer-Verlag, Berlin, LNCS-5654, 2009, pp