# Unified Framework of Approximating and Interpolatory Subdivision Schemes for Construction of Class of Binary Subdivision Schemes

Authors: Pakeeza Ashraf; Ghulam Mustafa; Abdul Ghaffar; Rida Zahra; Kottakkaran Sooppy Nisar; Emad E. Mahmoud; Wedad R. Alharbi
Journal: Journal of Function Spaces
 (2020)

---

## Abstract

In this paper, a generalized algorithm to develop a class of approximating binary subdivision schemes is presented. The proposed algorithm is based on three-point approximating binary and four-point interpolating binary subdivision schemes. It contains a parameter which classifies members of the new class of subdivision schemes. A set of efficient properties, for instance, polynomial generation and reproduction, support, continuity, and Hölder continuity, is discussed. Moreover, applications of the proposed subdivision schemes are given in order to demonstrate their variety, flexibility, and visual performance.


---

## Body

## 1. Introduction

Subdivision is a competent way of producing smooth curves or surfaces in geometric modeling and computer graphics. It repeatedly refines the initial polygonal shape. After each split average step, we get closer to the limit curve, which is the limit of an infinite series. A nice property of subdivision schemes is that they are simple and local, which means that local change in initial data will only have a local effect in the resulting object. Subdivision schemes have become celebrated because of their simplicity and efficiency. There are generally two main categories of subdivision schemes: interpolatory and approximating. For interpolating subdivision schemes, limit curve always passes through initial control points while for approximating subdivision schemes it may or may not. Subdivision schemes play an integral role in computer graphics due to their wide range of applications in many fields such as engineering, medical science, space science, graphic visualization, and image processing. Differential equations are used for mathematical modeling of many phenomena. Different techniques are being used to solve boundary value problems [1] and nonlinear problems [2]. Nowadays, subdivision schemes are also becoming a popular tool to numerically solve boundary value problems [3]. Subdivision algorithms are also a major field in many multiscale techniques applied in data compression. In some applications, the given data need not be reproduced at each step of the subdivision process, which needs the applications of subdivision schemes. Several researchers in the area of continuous geometry have been established classical subdivision schemes for various kinds of initial control data. In geometric modeling and engineering, practical applications of subdivision curves are restricted due to their shortcomings, and to overcome these shortcomings, a lot of work has been carried out [4–17].Deslauriers and Dubuc [18] presented a family of interpolating binary subdivision schemes. They used Lagrange interpolating polynomial for construction of schemes. Horman and Sabin (HS) [19] proposed a family of binary subdivision schemes having cubic precision. Some members of the HS family are interpolating and some are approximating. Mustafa et al. [20] offered a family of binary subdivision schemes which has alternating primal and dual symbols. Ashraf et al. [21] discussed a family of binary subdivision schemes based on Lane-Riesenfeld algorithm. Members of the proposed family have quintic precision. Mustafa and Bari [22] developed a family of univariate subdivision schemes for curve generation and data fitting. Asghar and Mustafa [23] presented a unified framework of stationary and nonstationary subdivision schemes. Keeping in view this practice, we present a generalized algorithm to develop a new class of approximating binary subdivision schemes. Ghaffar et al. [24–29] constructed geometric continuity conditions for the construction of free-form generalized subdivision curves with single shape parameter. These free-form complex shape adjustable generalized curves can be obtained by using shape-adjustable generalized subdivision schemes. These newly proposed approaches not only take over the benefits of classical subdivision curve and surface schemes but also resolve the issue of shape adjustability of subdivision curves and surfaces with the help of tension control shape parameters. They modeled some complex curves and surfaces using higher continuity conditions. The proposed masks of the schemes provide an alternative approach to generate the complex curves using higher continuity conditions with simple and straightforward calculation for the proposed algorithm because they are blended with linear polynomials rather than trigonometric functions. In 2020, Ashraf et al. [17, 30, 31] proposed a new approach using the generalized hybrid subdivision curve with shape parameters to solve the problem in construction of some symmetric curves and surfaces. These curves are easily modified by the changing the values of shape parameters.In this paper, we offer a Lane-Riesenfeld-like algorithm to derive a class of binary approximating subdivision schemes. Our algorithm is based on the well-known four-point interpolating binary subdivision scheme [18], which is C1 continuous, and three-point approximating binary subdivision scheme [32], which has C3 continuity. Considering ϕ smoothing stages as in the Lane-Riesenfeld algorithm, our proposed algorithm allows us to derive a class of univariate subdivision schemes. In fact, each member of the proposed class is enumerated by ϕ, and higher values of ϕ give schemes with wider masks and support, higher continuity, higher Holder regularity, and higher degree of polynomial generation. The first member of the proposed class (corresponding to ϕ=0) coincides with the three-point approximating binary subdivision scheme [32]. The proposed class of schemes generates schemes of higher continuities and visually more smooth limit curves as compared to existing families of schemes. The content of the paper is structured as follows. In Section 2, fundamental definitions and concepts are given. Section 3 presents a generalized algorithm for construction of new class of subdivision schemes. Section 4 is devoted for properties of proposed schemes, such as continuity, Hölder continuity, and support of basic limit function. Geometrical analysis and some beautiful examples of limit curve are given in Section 5. Section 6 presents a summary of the paper.


## 2. Preliminaries

Let the initial data be given by a set of control pointsG0=gi0∈ℝ,i∈ℤ, and the set of control points at refinement level hh≥0,h∈ℕ is given by Gh=gih∈ℝ,i∈ℤ. Define Gh+1=gih+1∈ℝ,i∈ℤ recursively by the following binary refinement rules:
(1)gih+1=∑k∈ℤbi−2kgih,i∈ℤ,where the finite set B=bi,i∈ℤ is called mask. The recursive algorithm associated with the repeated application of (1) is called subdivision scheme and denoted by S. The Laurent polynomial or symbol of the scheme S is defined as
(2)Bz=∑l∈ℤblzl.Theorem 1 (see [33]).
If a binary schemeS is convergent, then the mask B=bi,i∈ℤ satisfies
(3)∑l∈ℤb2l=∑l∈ℤb2l+1=1.
The symbol of a convergent scheme can be also be written as(4)Bz=Bevenz2+zBoddz2,with Bevenz=∑l∈ℤb2lzl and Boddz=∑l∈ℤb2l+1zl.Theorem 2 (see [33]).
A binary schemeS associated with the symbol
(5)Bz=z+1m+12mLzis said to be Cm continuous if the subdivision scheme associated with the symbol Lz is contractive.Proposition 3 (see [34]).
A binary schemeS generates polynomials of degree m if and only if
(6)B1=2,B−1=0andBj−1=0,j=1,2,⋯,m.Proposition 4 (see [34]).
A binary schemeS reproduces polynomials of degree n with respect to parametrization ejh=j+τ/2hj∈ℤ with τ=Bj1/2, if and only if it generates polynomials of degree n and
(7)Bj1=2∏i=0j−1τ−i,j=1,2,⋯,n.


## 3. Algorithm for Construction of Schemes

The well-known four-point interpolating binary subdivision scheme [18] is given by
(8)g2ih+1=gih,g2i+1h+1=−116gi−1h+916gih+916gi+1h−116gi+2h.By considering (4), the symbol of the even part of scheme (8) is as follows:
(9)Pevenz=z+12−z2+10z−18.Now, consider the three-point approximating binary subdivision scheme [32]
(10)g2ih+1=116gi−1h+1016gih+516gi+1h,g2i+1h+1=516gi−1h+1016gih+116gi+1h.The symbol of scheme (10) is given by
(11)Tz=2z+125.Let us now present the class of subdivision schemes, namely,R=Rφ:φ≥0,φ∈ℕ. The symbol of the scheme Rφ is obtained by applying symbol of the even part of scheme (8) φ-times on symbol of scheme (10) and given by
(12)Rφz=PevenzφTz.So by (9), (11), and (12), we have
(13)Rφz=2z+12φ+5−z2+10z−18φ,where φ≥0,φ∈ℕ. The members of the class R of subdivision schemes can be categorized by varying φ=0,1,2,⋯, in (13). By taking φ=0 in (13), we get three-point approximating binary scheme [32]. Table 1 presents mask of some members of the proposed class.Table 1
Mask of theRφ schemes corresponding to different values of parameter φ.
φSchemeMask03-point1161,5,10,10,5,115-point1256−1,4,44,124,170,124,44,4,−126-point140961,−13,−17,309,1338,2478,2478,1338,309,−17,−13,138-point165536−1,22,−91,−580,1303,12362,31557,41928,31557,12362,1303,−580,−91,22,−1


## 4. Properties of the Proposed Schemes

In this section, we present some desirable properties of classR of subdivision schemes, comprising of polynomial generation and reproduction, support, continuity, and Hölder continuity.


### 4.1. Polynomial Generation and Reproduction

If a subdivision scheme generates polynomials of degree up todG, then the polynomial generation degree of the scheme is dG. Also, if the initial data G0=gi0,i∈ℤ is sampled from a polynomial P^ of degree dR and the scheme yields precisely the same polynomial in the limit, then the reproduction degree dR is the maximal degree of polynomials that can be reproduced by the scheme. Clearly, the reproduction degree is always less than or equal to the generation degree. Now, we establish few results about polynomial generation and polynomial reproduction of the proposed subdivision schemes.Proposition 5.
Rφ-scheme generates space of polynomials up to degree φ+4.Proof.
Since symbol ofRφ-scheme satisfies the conditions
(14)Rφ1=2,Rφ−1=0andRφj−1=0,j=1,2,⋯,φ+4,so by Proposition 3, Rφ-scheme has φ+4 polynomial generation degree.In the view of Conti and Hormann [35], the standard parametrization ejh=j/2h at level h∈ℕ is not appropriate to analyze a subdivision scheme to reproduce space of polynomials, and the relative shift τh=e0h−e0h+1/2h+1 between the parameterizations at iteration level h and h+1 is important for polynomial reproduction of degree dR≥1. By applying a more suitable parametrization ejh=j+τφ/2h with shift parameter τφ=Rφ11/2=3φ+5/2, we have the following result.Proposition 6.
Rφ-scheme reproduces linear polynomial with respect to parametrization ejh=j+τφ/2hj∈ℤ with shift τφ=3φ+5/2.Proof.
It can be easily verified that(15)Rφ11=2τφ=3φ+5,Rφj1=2∏i=0j−1τφ−j,j=0,1.
Thus, by Propositions4 and 5, Rφ-scheme reproduces polynomial of degree one.Table2 presents the degree of polynomial generation and reproduction of some of the proposed Rφ-schemes. It is observed that the degree of polynomial generation is increasing linearly with the value of parameter φ.Table 2
Support, degree of polynomial generation (dG), degree of polynomial reproduction (dR), continuity (C), and HC of Rφ-scheme for φ=0,1,2, and 3.
φSupportdGdRCHölder continuityLBUB0541344185144.6784.6782116155.2995.3323147155.8715.968


### 4.2. Support

The support of a subdivision scheme quantifies how much one vertex brought change in its neighboring vertices, and its measure represents local support of the limit curve. Basic limit function (BLF) of a convergent subdivision scheme is a limit function of the initial dataG0=gi0,i∈ℤ which is of the form
(16)gi0=1,i=0,0,i≠0.By following [36], we determine that support of BLF of Rφ-scheme is 3φ+5. BLF generated by the proposed R0 and R1 schemes are demonstrated in Figure 1.Figure 1
(a, b) Basic limit functions generated by the proposed schemesR0 and R1, respectively.
(a)(b)


### 4.3. Continuity Analysis

Continuity of a subdivision scheme is an essential parameter on which efficiency of a scheme depends. To investigate continuity of our proposed class, we follow the approach as given in [33] and use the symbol of Rφ-scheme.Theorem 7.
TheRφ-scheme has Cφ+3−vφ continuity, where φ=1,2,3,⋯, and vφ=φ−1/2 (floor function).Proof.
The symbol ofRφ-scheme (13) can be simplified as
(17)Rφz=z+1φ+4−vφ2φ+3−vφrφz,with
(18)rφz=z+121+vφ−z2+10z−18φ,φ=1,2,3,⋯,where vφ=φ−1/2.
LetSrφ be the subdivision scheme associated with the symbol rφz. The scheme Srφ is contractive provided that Srφ∞=max∑l∈ℤr2l,∑l∈ℤr2l+1<1. So, by Theorem 2, Rφ-scheme has Cφ+3−Vφ continuity.
In Theorem7, we discuss continuity of Rφ-scheme for φ=1,2,3,⋯. It is to be noted that R0-scheme has C3 continuity which is analyzed in [32].Corollary 8.
TheR1-scheme has C4 continuity.Proof.
By lettingφ=1, the symbol of R1-scheme from (17) and (18) is given by
(19)R1z=z+1524r1z,with
(20)r1z=116−z3+9z2+9z−1.
LetSr1 be the scheme corresponding to the symbol r1z. The scheme Sr1 is contractive, as Sr1∞=max10/16,10/16=10/16<1. So, by Theorem 7, R1-scheme has C4 continuity.Similarly, for different values of parameterφ, continuity of Rφ-scheme can be easily computed by using Theorem 7.


### 4.4. Hölder Continuity Analysis

Continuity of a subdivision scheme is related to the existence of derivative of subdivision curve. For example, subdivision curve is said to beCm continuous if the mth derivative of the curve exists and is continuous everywhere in the given interval. On the other hand, Hölder continuity (HC) of a subdivision scheme tells how continuous the highest continuous derivative is. Therefore, it is also important to find HC of subdivision schemes along with continuity. Lower bound (LB) on HC of the proposed class is calculated by using an interesting property of symbol of Rφ-scheme, i.e., odd coefficients in Rφz are nonnegative and even coefficients are nonpositive.Theorem 9.
LB on the HC ofRφ-scheme is φ+5−log23/2φ+1, where φ=0,1,2,⋯.Proof.
By (13), symbol of Rφ-scheme can be expressed as
(21)Rφz=z+12φ+5Uφz,where Uφz=azφbz, az=−z2+10z−1/8, and bz=2. So LB on HC of Rφ-scheme is given by φ+5−log2Uφ. As we know Uφ=maxu⋄,u⋄, where u⋄ is the sum of odd and u⋄ is the sum of even coefficients of Uφz. We can write coefficients of Uφz in the following manner:
(22)u⋄u⋄=a⋄a⋄a⋄a⋄φb⋄b⋄.Thus, we have
(23)u⋄u⋄=54−14−1454φ02.
By eigenvalue decomposition, we have(24)u⋄u⋄=12−111132001φ−111102,which implies that
(25)u⋄u⋄=−32φ+132φ+1φ.Thus, we have
(26)Uφ=32φ+1.
Consequently, LB on HC ofRφ-scheme is φ+5−log23/2φ+1, where φ=0,1,⋯.
Upper bound (UB) on HC ofRφ-scheme is as follows.Theorem 10.
UB on HC ofRφ-scheme is φ+5−log2ζφ, where φ=0,1,⋯, and ζφ be the joint spectral radius of the matrices Q0 and Q1 which are obtained by using symbol of Rφ-scheme.Proof.
By (13), symbol of Rφ-scheme can be expressed as
(27)Rφz=z+12φ+5Qφz,where Qφz=2−z2+10z−1/8φ. Let q0,q1,⋯,qd be the nonzero real coefficients of Qφz. Also, Q0 and Q1 are the matrices of order d×d defined by
(28)Q0mn=qd+m−2n,andQ1mn=qd+m−2n+1,where m,n=1,2,⋯,d.
Let us denote joint spectral radius of both matricesQ0 and Q1 by ζφ. Then, by Rioul [37] and Dyn [33], UB on HC of Rφ-scheme is given by φ+5−log2ζφ.For different values of parameterφ, upper and lower bounds on the HC of Rφ-schemes can be straightforwardly computed by using Theorems 9 and 10. Table 2 summarizes the continuity and HC of the proposed class of subdivision schemes. It clearly indicates that as we go up for higher values of parameter φ, continuity and HC of Rφ-schemes also increase. Moreover, newly generated Rφ-schemes have higher order of continuity and HC as compared to their parent subdivision schemes.


## 4.1. Polynomial Generation and Reproduction

If a subdivision scheme generates polynomials of degree up todG, then the polynomial generation degree of the scheme is dG. Also, if the initial data G0=gi0,i∈ℤ is sampled from a polynomial P^ of degree dR and the scheme yields precisely the same polynomial in the limit, then the reproduction degree dR is the maximal degree of polynomials that can be reproduced by the scheme. Clearly, the reproduction degree is always less than or equal to the generation degree. Now, we establish few results about polynomial generation and polynomial reproduction of the proposed subdivision schemes.Proposition 5.
Rφ-scheme generates space of polynomials up to degree φ+4.Proof.
Since symbol ofRφ-scheme satisfies the conditions
(14)Rφ1=2,Rφ−1=0andRφj−1=0,j=1,2,⋯,φ+4,so by Proposition 3, Rφ-scheme has φ+4 polynomial generation degree.In the view of Conti and Hormann [35], the standard parametrization ejh=j/2h at level h∈ℕ is not appropriate to analyze a subdivision scheme to reproduce space of polynomials, and the relative shift τh=e0h−e0h+1/2h+1 between the parameterizations at iteration level h and h+1 is important for polynomial reproduction of degree dR≥1. By applying a more suitable parametrization ejh=j+τφ/2h with shift parameter τφ=Rφ11/2=3φ+5/2, we have the following result.Proposition 6.
Rφ-scheme reproduces linear polynomial with respect to parametrization ejh=j+τφ/2hj∈ℤ with shift τφ=3φ+5/2.Proof.
It can be easily verified that(15)Rφ11=2τφ=3φ+5,Rφj1=2∏i=0j−1τφ−j,j=0,1.
Thus, by Propositions4 and 5, Rφ-scheme reproduces polynomial of degree one.Table2 presents the degree of polynomial generation and reproduction of some of the proposed Rφ-schemes. It is observed that the degree of polynomial generation is increasing linearly with the value of parameter φ.Table 2
Support, degree of polynomial generation (dG), degree of polynomial reproduction (dR), continuity (C), and HC of Rφ-scheme for φ=0,1,2, and 3.
φSupportdGdRCHölder continuityLBUB0541344185144.6784.6782116155.2995.3323147155.8715.968


## 4.2. Support

The support of a subdivision scheme quantifies how much one vertex brought change in its neighboring vertices, and its measure represents local support of the limit curve. Basic limit function (BLF) of a convergent subdivision scheme is a limit function of the initial dataG0=gi0,i∈ℤ which is of the form
(16)gi0=1,i=0,0,i≠0.By following [36], we determine that support of BLF of Rφ-scheme is 3φ+5. BLF generated by the proposed R0 and R1 schemes are demonstrated in Figure 1.Figure 1
(a, b) Basic limit functions generated by the proposed schemesR0 and R1, respectively.
(a)(b)


## 4.3. Continuity Analysis

Continuity of a subdivision scheme is an essential parameter on which efficiency of a scheme depends. To investigate continuity of our proposed class, we follow the approach as given in [33] and use the symbol of Rφ-scheme.Theorem 7.
TheRφ-scheme has Cφ+3−vφ continuity, where φ=1,2,3,⋯, and vφ=φ−1/2 (floor function).Proof.
The symbol ofRφ-scheme (13) can be simplified as
(17)Rφz=z+1φ+4−vφ2φ+3−vφrφz,with
(18)rφz=z+121+vφ−z2+10z−18φ,φ=1,2,3,⋯,where vφ=φ−1/2.
LetSrφ be the subdivision scheme associated with the symbol rφz. The scheme Srφ is contractive provided that Srφ∞=max∑l∈ℤr2l,∑l∈ℤr2l+1<1. So, by Theorem 2, Rφ-scheme has Cφ+3−Vφ continuity.
In Theorem7, we discuss continuity of Rφ-scheme for φ=1,2,3,⋯. It is to be noted that R0-scheme has C3 continuity which is analyzed in [32].Corollary 8.
TheR1-scheme has C4 continuity.Proof.
By lettingφ=1, the symbol of R1-scheme from (17) and (18) is given by
(19)R1z=z+1524r1z,with
(20)r1z=116−z3+9z2+9z−1.
LetSr1 be the scheme corresponding to the symbol r1z. The scheme Sr1 is contractive, as Sr1∞=max10/16,10/16=10/16<1. So, by Theorem 7, R1-scheme has C4 continuity.Similarly, for different values of parameterφ, continuity of Rφ-scheme can be easily computed by using Theorem 7.


## 4.4. Hölder Continuity Analysis

Continuity of a subdivision scheme is related to the existence of derivative of subdivision curve. For example, subdivision curve is said to beCm continuous if the mth derivative of the curve exists and is continuous everywhere in the given interval. On the other hand, Hölder continuity (HC) of a subdivision scheme tells how continuous the highest continuous derivative is. Therefore, it is also important to find HC of subdivision schemes along with continuity. Lower bound (LB) on HC of the proposed class is calculated by using an interesting property of symbol of Rφ-scheme, i.e., odd coefficients in Rφz are nonnegative and even coefficients are nonpositive.Theorem 9.
LB on the HC ofRφ-scheme is φ+5−log23/2φ+1, where φ=0,1,2,⋯.Proof.
By (13), symbol of Rφ-scheme can be expressed as
(21)Rφz=z+12φ+5Uφz,where Uφz=azφbz, az=−z2+10z−1/8, and bz=2. So LB on HC of Rφ-scheme is given by φ+5−log2Uφ. As we know Uφ=maxu⋄,u⋄, where u⋄ is the sum of odd and u⋄ is the sum of even coefficients of Uφz. We can write coefficients of Uφz in the following manner:
(22)u⋄u⋄=a⋄a⋄a⋄a⋄φb⋄b⋄.Thus, we have
(23)u⋄u⋄=54−14−1454φ02.
By eigenvalue decomposition, we have(24)u⋄u⋄=12−111132001φ−111102,which implies that
(25)u⋄u⋄=−32φ+132φ+1φ.Thus, we have
(26)Uφ=32φ+1.
Consequently, LB on HC ofRφ-scheme is φ+5−log23/2φ+1, where φ=0,1,⋯.
Upper bound (UB) on HC ofRφ-scheme is as follows.Theorem 10.
UB on HC ofRφ-scheme is φ+5−log2ζφ, where φ=0,1,⋯, and ζφ be the joint spectral radius of the matrices Q0 and Q1 which are obtained by using symbol of Rφ-scheme.Proof.
By (13), symbol of Rφ-scheme can be expressed as
(27)Rφz=z+12φ+5Qφz,where Qφz=2−z2+10z−1/8φ. Let q0,q1,⋯,qd be the nonzero real coefficients of Qφz. Also, Q0 and Q1 are the matrices of order d×d defined by
(28)Q0mn=qd+m−2n,andQ1mn=qd+m−2n+1,where m,n=1,2,⋯,d.
Let us denote joint spectral radius of both matricesQ0 and Q1 by ζφ. Then, by Rioul [37] and Dyn [33], UB on HC of Rφ-scheme is given by φ+5−log2ζφ.For different values of parameterφ, upper and lower bounds on the HC of Rφ-schemes can be straightforwardly computed by using Theorems 9 and 10. Table 2 summarizes the continuity and HC of the proposed class of subdivision schemes. It clearly indicates that as we go up for higher values of parameter φ, continuity and HC of Rφ-schemes also increase. Moreover, newly generated Rφ-schemes have higher order of continuity and HC as compared to their parent subdivision schemes.


## 5. Geometrical Analysis of Proposed Schemes

The shape of an object is generally controlled by a control polygon. The purpose of applying a subdivision scheme on the control polygon is to generate visually smooth curves. Figure2 presents the behavior of some of the proposed schemes. R0, R1, and R2 schemes are applied on the same initial polygon, and limit curves are obtained after three iterations. It is evident that the proposed class offers more choices to meet different designing needs.Figure 2
Behavior of the proposedR0, R1, and R2 schemes after three iterations.


### 5.1. Subdivision Rules for Endpoints

For closed curves, the subdivision rules ofR0, R1, R2, and R3 schemes can be defined by their corresponding Laurent polynomial from (13). The limit curves generated by these schemes are C3, C4, C5, and C5 continuous, respectively. In case of dealing with open polygons, these rules can be used to improve the interior of the curve, while it is quite troublesome to improve the first and last edges with the help of subdivision rules of the original proposed schemes. So to handle the endpoints of an open polygon, we need to supply additional points which are not usually required in case of a closed polygon. Let g0hg1h be the first edge of the open polygon Gh=gkh:k=0,⋯,2hm. Now, we define an additional control point g−1h, as an extrapolatory rule in the nonrefined polygon Gh, and then we can compute the point g1h+1 through the proposed schemes by applying subdivision to the subpolygon g−1h,g0h,g1h,g2h. We select the point as g−1h=2g0h−g1h. The first edge of an open control polygon Gh=gkh:k=0,1,⋯,2hm can be refined by using the following rules.
(i)
Refinement rules of the proposed three-point schemeR0 are given by
(29)g0h+1=54g0h−14g1h,g1h+1=34g0h+14g1h.(ii)
Refinement rules of the proposed five-point schemeR1 are given by
(30)g0h+1=380256g0h−120256g1h−4256g2h,g1h+1=255256g0h+2256g1h−1256g2h,g2h+1=132256g0h+120256g1h+4256g2h,g3h+1=42256g0h+171256g1h+44256g2h−1256g3h.(iii)
Refinement rules of the proposed six-point schemeR2 are given by
(31)g0h+1=30704096g0h+10294096g1h−44096g2h+14096g3h,g1h+1=13064096g0h+24954096g1h+3084096g2h−134096g3h,g2h+1=2834096g0h+24914096g1h+13384096g2h−174096g3h+14096g4h,g3h+1=−154096g0h+13374096g1h+24784096g2h+3094096g3h−134096g4h.(iv)
Refinement rules of the proposed eight-point schemeR3 are given by
(32)g0h+1=6506665536g0h+102865536g1h−58065536g2h+2265536g3h,g1h+1=3397665536g0h+3025465536g1h+139465536g2h−9065536g3h−165536g4h,g2h+1=1124665536g0h−4250865536g1h+1234065536g2h−58065536g3h+2265536g4h,g3h+1=111965536g0h+3164865536g1h+3155865536g2h+130365536g3h−9165536g4h−165536g5h,g4h+1=53665536g0h−1234065536g1h+4192865536g2h+1236265536g3h−58065536g4h+2265536g5h,g5h+1=−9365536g0h+130465536g1h+3155765536g2h+3155765536g3h+130365536g4h−9165536g5h−165536g6h.Similarly, we can refine the final edges of the open polygon.


### 5.2. Applications and Comparison

Geometrical performance ofR0, R1, R2, and R3 schemes is depicted through several examples. The proposed schemes have good continuity and present smooth limit curves. Figures 3(a) and 4(a) present initial control polygons of cap and elephant, respectively, while Figures 3(b) and 4(b) are the limit curves obtained by applying three iterations of R0-scheme on these initial polygons. Figures 5(a) and 6(a) present initial control polygons of flower and bird, respectively, while Figures 5(b) and 6(b) are the limit curves obtained by applying three iterations of R1-scheme on these initial polygons. Figures 7(a) and 8(a) present initial control polygons of face of girls, while Figures 7(b) and 8(b) are the limit curves obtained by applying three iterations of R2-scheme on these initial polygons, respectively.Figure 3
Application ofR0-scheme: (a) initial polygon and (b) the limit curve generated by R0-scheme at the third subdivision level.
(a)(b)Figure 4
Application ofR0-scheme: (a) initial polygon and (b) the limit curve generated by R0-scheme at the third subdivision level.
(a)(b)Figure 5
Application ofR1-scheme: (a) initial polygon and (b) the limit curve generated by R1-scheme at the third subdivision level.
(a)(b)Figure 6
Application ofR1-scheme: (a) initial polygon and (b) the limit curve generated by R1-scheme at the third subdivision level.
(a)(b)Figure 7
Application ofR2-scheme: (a) initial polygon and (b) the limit curve generated by R2-scheme at the third subdivision level.
(a)(b)Figure 8
Application ofR3-scheme: (a) initial polygon and (b) the limit curve generated by R3-scheme at the third subdivision level.
(a)(b)Figure9 represents the initial polygon along with sharp features of limit curve generated by R3-scheme at the third subdivision level. Figures 10 and 11 present comparison of some existing subdivision schemes (3-point scheme [38], 4-point scheme [18], and 5-point scheme [19]) with the proposed subdivision schemes (R0, R1, and R2 schemes). We have chosen two different initial polygons, and limit curves are generated after three subdivision levels. It is clear from the figures that the proposed schemes generate smooth limit curves.Figure 9
Application ofR3-scheme: (a, b) the initial polygon along with sharp features of limit curve generated by R3-scheme at the third subdivision level.
(a)(b)Figure 10
Comparison of the existing and proposed subdivision schemes at the third subdivision level.
(a)
3-point scheme [38](b)
4-point scheme [18](c)
5-point scheme [19](d)
R0-scheme(e)
R1-scheme(f)
R2-schemeFigure 11
Comparison of the existing and proposed subdivision schemes at the third subdivision level.
(a)
3-point scheme [38](b)
4-point scheme [18](c)
5-point scheme [19](d)
R0-scheme(e)
R1-scheme(f)
R2-scheme


## 5.1. Subdivision Rules for Endpoints

For closed curves, the subdivision rules ofR0, R1, R2, and R3 schemes can be defined by their corresponding Laurent polynomial from (13). The limit curves generated by these schemes are C3, C4, C5, and C5 continuous, respectively. In case of dealing with open polygons, these rules can be used to improve the interior of the curve, while it is quite troublesome to improve the first and last edges with the help of subdivision rules of the original proposed schemes. So to handle the endpoints of an open polygon, we need to supply additional points which are not usually required in case of a closed polygon. Let g0hg1h be the first edge of the open polygon Gh=gkh:k=0,⋯,2hm. Now, we define an additional control point g−1h, as an extrapolatory rule in the nonrefined polygon Gh, and then we can compute the point g1h+1 through the proposed schemes by applying subdivision to the subpolygon g−1h,g0h,g1h,g2h. We select the point as g−1h=2g0h−g1h. The first edge of an open control polygon Gh=gkh:k=0,1,⋯,2hm can be refined by using the following rules.
(i)
Refinement rules of the proposed three-point schemeR0 are given by
(29)g0h+1=54g0h−14g1h,g1h+1=34g0h+14g1h.(ii)
Refinement rules of the proposed five-point schemeR1 are given by
(30)g0h+1=380256g0h−120256g1h−4256g2h,g1h+1=255256g0h+2256g1h−1256g2h,g2h+1=132256g0h+120256g1h+4256g2h,g3h+1=42256g0h+171256g1h+44256g2h−1256g3h.(iii)
Refinement rules of the proposed six-point schemeR2 are given by
(31)g0h+1=30704096g0h+10294096g1h−44096g2h+14096g3h,g1h+1=13064096g0h+24954096g1h+3084096g2h−134096g3h,g2h+1=2834096g0h+24914096g1h+13384096g2h−174096g3h+14096g4h,g3h+1=−154096g0h+13374096g1h+24784096g2h+3094096g3h−134096g4h.(iv)
Refinement rules of the proposed eight-point schemeR3 are given by
(32)g0h+1=6506665536g0h+102865536g1h−58065536g2h+2265536g3h,g1h+1=3397665536g0h+3025465536g1h+139465536g2h−9065536g3h−165536g4h,g2h+1=1124665536g0h−4250865536g1h+1234065536g2h−58065536g3h+2265536g4h,g3h+1=111965536g0h+3164865536g1h+3155865536g2h+130365536g3h−9165536g4h−165536g5h,g4h+1=53665536g0h−1234065536g1h+4192865536g2h+1236265536g3h−58065536g4h+2265536g5h,g5h+1=−9365536g0h+130465536g1h+3155765536g2h+3155765536g3h+130365536g4h−9165536g5h−165536g6h.Similarly, we can refine the final edges of the open polygon.


## 5.2. Applications and Comparison

Geometrical performance ofR0, R1, R2, and R3 schemes is depicted through several examples. The proposed schemes have good continuity and present smooth limit curves. Figures 3(a) and 4(a) present initial control polygons of cap and elephant, respectively, while Figures 3(b) and 4(b) are the limit curves obtained by applying three iterations of R0-scheme on these initial polygons. Figures 5(a) and 6(a) present initial control polygons of flower and bird, respectively, while Figures 5(b) and 6(b) are the limit curves obtained by applying three iterations of R1-scheme on these initial polygons. Figures 7(a) and 8(a) present initial control polygons of face of girls, while Figures 7(b) and 8(b) are the limit curves obtained by applying three iterations of R2-scheme on these initial polygons, respectively.Figure 3
Application ofR0-scheme: (a) initial polygon and (b) the limit curve generated by R0-scheme at the third subdivision level.
(a)(b)Figure 4
Application ofR0-scheme: (a) initial polygon and (b) the limit curve generated by R0-scheme at the third subdivision level.
(a)(b)Figure 5
Application ofR1-scheme: (a) initial polygon and (b) the limit curve generated by R1-scheme at the third subdivision level.
(a)(b)Figure 6
Application ofR1-scheme: (a) initial polygon and (b) the limit curve generated by R1-scheme at the third subdivision level.
(a)(b)Figure 7
Application ofR2-scheme: (a) initial polygon and (b) the limit curve generated by R2-scheme at the third subdivision level.
(a)(b)Figure 8
Application ofR3-scheme: (a) initial polygon and (b) the limit curve generated by R3-scheme at the third subdivision level.
(a)(b)Figure9 represents the initial polygon along with sharp features of limit curve generated by R3-scheme at the third subdivision level. Figures 10 and 11 present comparison of some existing subdivision schemes (3-point scheme [38], 4-point scheme [18], and 5-point scheme [19]) with the proposed subdivision schemes (R0, R1, and R2 schemes). We have chosen two different initial polygons, and limit curves are generated after three subdivision levels. It is clear from the figures that the proposed schemes generate smooth limit curves.Figure 9
Application ofR3-scheme: (a, b) the initial polygon along with sharp features of limit curve generated by R3-scheme at the third subdivision level.
(a)(b)Figure 10
Comparison of the existing and proposed subdivision schemes at the third subdivision level.
(a)
3-point scheme [38](b)
4-point scheme [18](c)
5-point scheme [19](d)
R0-scheme(e)
R1-scheme(f)
R2-schemeFigure 11
Comparison of the existing and proposed subdivision schemes at the third subdivision level.
(a)
3-point scheme [38](b)
4-point scheme [18](c)
5-point scheme [19](d)
R0-scheme(e)
R1-scheme(f)
R2-scheme


## 6. Conclusion

Subdivision is an efficient way of constructing smooth curves or surfaces in geometric modeling and computer graphics. In this paper, we have presented an elegant way of constructing a class of approximating binary subdivision schemes by using two well-known binary subdivision schemes. Several examples are provided to illustrate that the proposed schemes give wide choice to geometric designers for generation of smooth geometric models as per their own needs. Comparison with some existing schemes is also given. Moreover, several important properties like polynomial reproduction and generation, support of BLF, continuity, and HC of the proposed scheme are discussed. Geometrical analysis of the limit curve is also carried out.



---

*Source: 6677778-2020-12-17.xml*