# Recursive Process for Constructing the Refinement Rules of New Combined Subdivision Schemes and Its Extended Form

Authors: Rabia Hameed; Ghulam Mustafa; Jiansong Deng; Shafqat Ali
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this article, we present a new method to construct a family of2N+2-point binary subdivision schemes with one tension parameter. The construction of the family of schemes is based on repeated local translation of points by certain displacement vectors. Therefore, refinement rules of the 2N+2-point schemes are recursively obtained from refinement rules of the 2N-point schemes. Thus, we get a new subdivision scheme at each iteration. Moreover, the complexity, polynomial reproduction, and polynomial generation of the schemes are increased by two at each iteration. Furthermore, a family of interproximate subdivision schemes with tension parameters is also introduced which is the extended form of the proposed family of schemes. This family of schemes allows a different tension value for each edge and vertex of the initial control polygon. These schemes generate curves and surfaces such that some initial control points are interpolated and others are approximated.


---

## Body

## 1. Introduction

Subdivision schemes are efficient tools for generating smooth curves/surfaces as the limit of an iterative process based on simple refinement rules starting from certain control points defining a control polygon/mesh. In recent years, subdivision schemes have been an important research area. These schemes provide an efficient way to describe curves, surfaces, and related geometric objects. Generally, subdivision schemes are classified as interpolatory or approximating, depending on whether the limit curve passes through all the given initial control points or not. Although approximating schemes yield smoother curves with higher order continuity, interpolating schemes are more useful for engineering applications as they preserve the shape of the coarse mesh. The special family of interpolatory schemes consists of the schemes with refinement rules that preserve the points associated with the coarse mesh and only generate new points related to the additional vertices of the refined mesh. An important family of interpolatory schemes was introduced by Deslauriers and Dubuc [1], and latest tools for its analysis were introduced by Amat et al. [2] whereas an important family of approximating subdivision schemes that is the dual counterparts of the schemes of Deslauriers and Dubuc [1] was proposed by Dyn et al. [3]. In 2017, Hameed and Mustafa [4] introduced an oscillation-free family of a-point b-ary subdivision schemes which can produce approximating curves with high continuity and less complexity.However, there also exist the parametric subdivision schemes, which can produce family of smooth approximating curves for special choices of the tension parameters. The families of such schemes were introduced in [5–8]. Furthermore, a parametric subdivision scheme can be converted to the nonuniform subdivision scheme by defining the local tension parameter. Mustafa and Hameed [6, 7] converted their families of univariate and bivariate subdivision schemes to nonuniform approximating subdivision schemes by defining local tension parameters. A parametric subdivision scheme which can produce both interpolatory and approximating curves is called the combined subdivision scheme. If a combined subdivision scheme is capable to convert in the nonuniform form such that it can interpolate only certain initial control points and approximate all the other initial control points, then such a scheme will be interproximate scheme. Pan et al. [9] and Novara and Romani [10] presented the combined ternary subdivision schemes to fit interpolatory and approximating curves. However, they did not present the nonuniform form of their combined subdivision schemes.Li and Zheng [11] combined the 4-point scheme of Dyn et al. [12] and the cubic B-spline binary refinement scheme to construct an interproximate subdivision scheme. Tan et al. [13] combined the 4-point scheme of Dyn et al. [12] and a 2-point corner cutting scheme to construct another interproximate subdivision scheme. However, these schemes give interproximate behavior but are not easy to implement and analyze. Nowadays, surface modeling is also modifying to fulfill the previous gaps. Pan et al. [14] presented a surface formulation method of multipatches based on rational splines. Nguyen-Thanh et al. [15] gave a subdivision approach for the minimal surface models on planar domains.In this paper, we present a recursive method to construct the2N+2-point combined subdivision schemes with one tension parameter to control the given points of the initial polygon. The construction of combined subdivision schemes by a recursive method is a new trend in CAGD. We also present an extended form of this family of combined schemes by defining another tension parameter to control the insertion of new point between the given points in order to smooth the given polygon. Thus, the involvement of two tension parameters increases the flexibility in curves and surfaces fitting. Furthermore, we analyze the behavior of these combined subdivision schemes mathematically and show that these schemes not only give optimal smoothness but also give a desired reproduction degree. The results are then verified geometrically. Furthermore, we convert our schemes to interproximate schemes that generate smooth and oscillation-free curves and surfaces such that some initial control points are interpolated and others are approximated.This article is organized as follows. Section2 deals with some basic definitions and results. In Section 3, we construct three families of primal subdivision schemes. Section 4 deals with some important properties of the proposed families of schemes. In Section 5, numerical examples and comparisons are presented. A family of interproximate subdivision schemes and associated numerical examples are presented in Section 6. Conclusions are given in Section 7.


## 2. Preliminaries

A general compact form of linear, uniform, and stationary binary univariate subdivision schemeSa which maps a polygon fk=fik,i∈ℤ to a refined polygon fk+1=fik+1,i∈ℤ is defined as(1)fik+1=∑j∈ℤai−2jfjk,i∈ℤ.Since the subdivision scheme (1) is a binary scheme, the two rules for defining the new control points are as follows:(2)f2ik+1=∑j∈ℤa2i−2jfjk=∑γ∈ℤa2γfi−γk,i∈ℤ,f2i+1k+1=∑j∈ℤa2i+1−2jfjk=∑γ∈ℤa2γ+1fi−γk,i∈ℤ.The symbol of the above subdivision scheme is given by the Laurent polynomial:(3)az=∑i∈ℤaizi,z∈ℂ∖0,where a=ai,i∈ℤ is called the mask of the subdivision scheme. Detailed information about refinement rules, Laurent polynomials, and convergence of a subdivision scheme can be found in [16–18]. The necessary condition for the convergence of the subdivision scheme (2) is that ∑γ∈ℤa2γ=∑γ∈ℤa2γ+1=1. The continuity of the subdivision schemes can be analyzed by the following theorems.Theorem 1 (see [17]).
A convergent subdivision schemeSa corresponding to the symbol(4)az=1+z2znbz,is Cn-continuous iff the subdivision scheme Sb corresponding to the symbol bz is convergent.Theorem 2 (see [17]).
The schemeSb corresponding to the symbol bz is convergent iff its difference scheme Sc corresponding to the symbol cz is contractive, where bz=1+zcz. The scheme Sc is contractive if(5)cl∞=max∑icj−2lil:0≤j<2l<1,l∈ℕ,where cil are the coefficients of the scheme Scl with symbol(6)clz=czcz2,…,cz2l−1.In a geometric context, subdivision schemes are further categorized into primal and dual subdivision schemes. The primal binary subdivision schemes are the schemes that leave or modify the old vertex points and create one new point at each old edge. Primal schemes can be interpolatory, approximating, or combined. Dual binary subdivision schemes on the other hand are the schemes that create two new points at the old edges and discard the old points. Most of the dual schemes are approximating subdivision schemes; however, recently Romani [19, 20] introduced interpolatory subdivision schemes that are dual in nature. Detailed information about the primal and dual subdivision schemes can be found in [16]. Furthermore, if one refinement rule of an approximating binary subdivision scheme (2) uses the affine combination of ξ=ξ1>2:ξ1∈ℤ control points at level k to get a new control point at level k+1 whereas the other refinement rule of (2) uses the affine combination of control points less than ξ at level k to get a new point at level k+1, then that binary scheme is called the primal binary scheme. Moreover, every primal binary scheme is the relaxed subdivision scheme. Mathematical definition of primal and dual subdivision schemes is presented as follows.Definition 1.
Let the symbol of the symmetric subdivision scheme (2) defined in (3) can particularly be written as az=⋯+a−3z−3+a−2z−2+a−1z−1+a0z0+a1z1+a2z2+a3z3+⋯. If the symbol az defined in (3) corresponding to the scheme Sa satisfies the following condition:(7)az=az−1,then Sa is said to be a primal subdivision scheme. On the other hand, if it satisfies following condition:(8)zaz=az−1,then Sa is said to be a dual subdivision scheme.
The combined subdivision schemes are the schemes which depend on one or more tension parameters. Moreover, at the specific values of these parameters, these schemes can be regarded either as an approximating subdivision scheme or an interpolatory one. Interproximate subdivision schemes (see [11]) are the schemes which generate the limit curves that interpolate some of the vertices of the given control polygons, while approximate the other vertices of the given control polygons.
Generation and reproduction degrees are used to check the behaviors of a subdivision scheme when the original data points lie on the graph of a polynomial. Suppose that the original data points are taken from a polynomial of degreed. If the control points of the limit curve lie on graph of the polynomial having same degree (i.e., d), then we say that the subdivision scheme generates polynomials of degree d. If the control points of the limit curve lie on graph of the same polynomial, then we say that the subdivision scheme reproduces polynomials of degree d. Mathematically, let Πd denote the space of polynomials of degree d and g, h∈Πd; an operator O generates polynomials of degree d if Og=h∀g,h∈Πd, whereas O reproduces polynomials of degree d if Og=g∀g∈Πd. Furthermore, the generation degree of a subdivision scheme is the maximum degree of polynomials that can theoretically be generated by the scheme, provided that the initial data are taken correctly. Evidently, it is not less than the reproduction degree. For exact definitions of polynomial generation and reproduction, the readers can consult [16, 21]. The following theorem is used to check the generation and reproduction degrees of the subdivision schemes in this paper.Theorem 3 (see [21]).
A univariate convergent binary subdivision schemeSa performs the following functions:(i)
Generates polynomials up to degreed if and only if(9)a1=2,a−1=0,Dmaz|z=−1=0,m=1,2,…,d,whereDmaz|z=−1 denotes the m-th derivative of az with respect to z evaluated at a point z=−1.(ii)
Reproduces polynomials up to degreed with respect to the parametrization tik=i+τ/2ki∈ℤ with τ=1/2D1z|z=1 if and only if it generates polynomials of degree d and(10)Dmaz|z=1=2∏h=0m−1τ−h,m=1,2,…,d.The support of a basic limit function and a subdivision scheme is the area of the limit curve that will be affected by the displacement of a single control point from its initial place. The part which is dependent on that given control point is called the support width of the given subdivision scheme. By following the approach of [22], we give following theorem to calculate the support width of a relaxed binary combined scheme or an interpolatory binary scheme.Theorem 4.
The support width of aξ-point binary relaxed subdivision scheme Sa is 2ξ where ξ=ξ1>2:ξ1∈ℤ, which implies that it vanishes outside the interval −ξ,ξ. The support width of a ξ-point interpolatory binary scheme Sa is 2ξ−2, which implies that it vanishes outside the interval −ξ+1,ξ−1.


## 3. Construction of the Families of Subdivision Schemes

In this section, we present a family of2N+2-point relaxed combined subdivision schemes that is based on repeated local translation of points by using certain displacement vectors. Thus, the refinement rules of a member of the proposed family is recursively obtained by the refinement rules of one other member of this family, i.e., the refinement rules of a 2N+2-point scheme for N=M are recursively obtained from the refinement rules of the 2N+2-point scheme for N=M−1. We propose a new family of 2N+3-point relaxed combined schemes with two tension parameters by extending the points of the family of 2N+2-point relaxed combined schemes. Then, we modify the family of 2N+3-point relaxed schemes to a family of 2N+4-point interpolatory schemes by removing one of its tension parameters. Construction process for the family of 2N+2-point relaxed combined schemes with one tension parameter is given as follows.


### 3.1. Framework for the Construction of a Family of2N+2-Point Relaxed Schemes

The family of2N+2-point combined subdivision schemes Sa2N+2 which maps the polygon fN+1k=fi,N+1k:i∈ℤ to the refined polygon fN+1k+1=fi,N+1k+1:i∈ℤ is defined by the set of following refinement rules:(11)f2i,N+1k+1=∑j=−N−1N+1a2j,N+1fi+j,N+1k,f2i+1,N+1k+1=∑j=−N−1Na2j+1,N+1fi+j+1,N+1k,where N∈ℕ0=ℕ∪0 is used to calculate the complexity (number of control points at k-th subdivision level used in the insertion of a new point at k+1-th subdivision level is called the complexity) of the subdivision schemes and k∈ℕ denotes the number of times subdivision is applied on the original data points. Hence, for each N, the set fi,N+1k+1:i∈ℤ represents the k+1-th level subdivided points obtained by applying k+1-times the 2N+2-point relaxed subdivision scheme (11) on the initial data points fi0=fi,N+10:i∈ℤ, and a=aj,N+1:j=−2N+1,…,2N+1 is mask of the scheme (11) which is same at each level of refinement for a fix value of N. The schematic sketches of both rules defined in (11) are presented in Figures 1(a) and 1(b).Figure 1
Graphical sketches of the rules of2N+2-point primal schemes in (a-b) and of 2N+3-point primal schemes in (c-d), respectively. (a) Vertex rule. (b) Edge rule. (c) Vertex rule. (d) Edge rule.
(a)(b)(c)(d)The construction process of these rules is given as follows.IfN=0, the two refinement rules of the 2-point relaxed scheme are obtained from (12). Hence, fi,11:i∈ℤ are the control points at first subdivision level obtained by the 2-point relaxed subdivision scheme on the initial control points fi0=fi,10:i∈ℤ. These two refinement rules are the initial refinement rules used to calculate the other refinement rules of proposed family of schemes for each successive value of N. The initial refinement rules are defined as(12)f2i,11=fi,10+α0fi−1,10−2fi,10+fi+1,10,f2i+1,11=12fi,10+12fi+1,10,where α0∈−1,1.Now, we calculate pointsf2i+ℓ,N+11:ℓ=0,1i∈ℤ of the HTML translation failed-point relaxed subdivision scheme for N⩾1. Hence, for a fix value of N, the points f2i+ℓ,N+11:ℓ=0,1i∈ℤ of the 2N+2-point relaxed subdivision scheme are obtained by moving the points f2i+ℓ,N1:ℓ=0,1i∈ℤ to the new position according to the displacement vectors αℓC⟶2i+ℓ,N+1:ℓ=0,1i∈ℤ, where αℓ is the tension parameter with α1=1 and α0=α.Mathematically, forN≥1, the two refinement rules of the family of 2N+2-point relaxed subdivision schemes at first level of subdivision are obtained by the following recurrence relation:(13)f2i+ℓ,N+11=f2i+ℓ,N1+αℓC⟶2i+ℓ,N+1,ℓ=0,1,where the vectors C⟶2i+ℓ,N+1:ℓ=0,1 are calculated by the following recurrence relation:(14)C⟶2i,N+1=C⟶2i,N−C⟶2i+1,N+C⟶2i,N−C⟶2i−1,N,C⟶2i+1,N+1=1NN4−18C⟶2i+1,N−C⟶2i+1+1,N+C⟶2i+1,N−C⟶2i−1+1,N,and initial values for relation (14) are(15)C⟶2i,1=fi−1,10−fi,10+fi+1,10,C⟶2i+1,1=12fi,10+fi+1,10.Here,fi0 = fi,10 = fi,20=fi,30=⋯=fi,N+10 are the initial control points.While the pointsfi,11, fi,21, fi,31, and fi,41 are the initial points of the 4-point, 6-point, and 8-point relaxed subdivision schemes obtained by substituting the values of N equal to 1, 2, and 3, respectively, in (13) and (14). Since the proposed subdivision schemes are stationary, the refinement rules are same at each level of subdivision. Therefore, for other subdivision levels, we apply (11) while the coefficients of points fi,N+1k remain same as the coefficients of points fi,N+10=fi0 obtained from (13). Also, fi,1k+1, fi,2k+1, fi,3k+1, and fi,4k+1 are the control points at k+1-th subdivision level obtained by applying the 2-point, 4-point, 6-point, and 8-point relaxed subdivision schemes on the k-th level points fi,1k, fi,2k, fi,3k, and fi,4k, respectively. Moreover, the points other than the initial control points hold the relation fi,Nk≠fi,N+1k∀N∈ℕ.At each iteration, i.e., by substitutingN=1,2,3,… in (11), (13), and (14), we get a new binary primal 2N+2-point subdivision scheme. The masks of these 2N+2-point schemes by defining α0=α are tabulated in Table 1.Table 1
Mask of the2N+2-point schemes Sa2N+2.
NMask01/22α,1,2−4α,1,2α11/16−16α,−1,64α,9,16−96α,9,64α,−1,−16α21/256−256α,3,−1536α,−25,3840α,150,256−5120α,150,3840α,25,−1536α,3,256α31/2048−2048α,−5,16384α,49,−57344α,−245,114688α,1225,2048−143360α,1225,114688α,−245,−57344α,49,16384α,−5,−2048α41/6553665536α,35,−655360α,−405,2949120α,2268,−7864320α−8820,13762560α,39690,65536−16515072α,39690,13762560α,−8820,−7864320α,2268,2949120α,−405,−655360α,35,65536α51/524288−524288α,−63,6291456α,847,−34603008α,−5445,115343360α,22869,−259522560α,−76230,415236096α,320166,524288,−484442112α,320166,415236096α,−76230,−259522560α,22869,115343360α,−5445,−34603008α,847,6291456α,−63,−524288αRemark 1.
Ifα=0, the family of scheme (11) reduces to the family of 2N+2-point interpolatory schemes with symbol(16)az=1+∑j=−N−1Na2j+1,N+1z2j+1,which is proposed by Deslauriers and Dubuc [1]. The continuity of 2N+2-point interpolatory schemes is CN for 0≤N≤4 and C≈83/200N+1 for N≥5.


### 3.2. Interpretation of Framework 3.1 forN=1

The refinement rules of the initial subdivision scheme defined in (12) are(17)f2i,11=αfi−10+1−2αfi0+αfi+10,f2i+1,11=12fi0+12fi+10.Moreover, the initial valuesC⟶2i+ℓ,1:ℓ=0,1 which will be used to calculate the vectors C⟶2i+ℓ,N+1:ℓ=0,1N∈ℕ defined in (15) are(18)C⟶2i,1=fi−10−fi0+fi+10,C⟶2i+1,1=12fi0+12fi+10.Now, we use initial relations (17) and (18) to calculate the refinement rules of 4-point relaxed scheme which will be obtained by putting N=1 in (13) and (14). Hence, for N=1, we get(19)f2i,21=f2i,11+α0C⟶2i,2,f2i+1,21=f2i+1,11+α1C⟶2i+1,2,where(20)C⟶2i,2=C⟶2i,1−C⟶2i+1,1+C⟶2i,1−C⟶2i−1,1,C⟶2i+1,2=18C⟶2i+1,1−C⟶2i+1+1,1+C⟶2i+1,1−C⟶2i−1+1,1.By using (18) in (20), we get(21)C⟶2i,2=−fi−20+3fi−10−4fi0+3fi+10−fi+20,C⟶2i+1,2=116−fi−10+fi0+fi+10−fi+20.Now, firstly we putα0=α and α1=1 in (19) and then we use (17) and (21) in (19). Hence, we get the following 4-point relaxed subdivision scheme:(22)f2i,21=−αfi−20+4αfi−10+1−6αfi0+4αfi+10−αfi+20,f2i+1,21=116−fi−10+9fi0+9fi+10−fi+20.By using (22) in (11), we get(23)f2i,2k+1=−αfi−2k+4αfi−1k+1−6αfik+4αfi+1k−αfi+2k,f2i+1,2k+1=116−fi−1k+9fik+9fi+1k−fi+2k.Step by step geometrical representations of the above procedure are shown in Figures2 and 3. The description of Figure 2 is as follows. In Figure 2(a), the implementation of the initial subdivision scheme defined in (17) is given. In Figure 2(b), blue bullets show the points obtained by the relations defined in (18). Here, C⟶2i−2,1=fi−20−fi−10+fi0, C⟶2i−1,1=1/2fi−10+fi0, C⟶2i,1=fi−10−fi0+fi+10, C⟶2i+1,1=1/2fi0+fi+10, C⟶2i+2,1=fi0−fi+10+fi+20, and C⟶2i+3,1=1/2fi+10+fi+20. In Figure 2(c), C⟶2i,2 is the resultant vector of two vectors C⟶2i,1−C⟶2i+1,1 and C⟶2i,1−C⟶2i−1,1. Similarly, CC⟶2i+1,2 is the resultant vector of C⟶2i+1,1−C⟶2i+1+1,1 and C⟶2i+1,1−C⟶2i−1+1,1. The resultant vectors are obtained by adding two vectors using head to tail rule. The resultant vectors are denoted by blue solid lines while the other vectors are denoted by blue dashed lines. Moreover, the description of Figure 3 is as follows, In Figure 3(a), the geometrical representation of the vectors defined in (20) is given. Here, C⟶2i+1,2=1/8CC⟶2i+1,2; In Figure 3(b), the translation of the points f2i,11 and f2i+1,11 is shown by using vectors αC⟶2i,2 and C⟶2i+1,2 to obtain the points f2i,21 and f2i+1,21 denoted by green bullets; In Figure 3(c), green bullets show the points of the subdivision scheme (21) constructed by the proposed framework.Figure 2
Geometrical interpretation of the proposed framework. Red bullets and red lines represent initial points and initial polygons, respectively. Black bullets and black lines represent the points and the polygons obtained by the subdivision scheme (17).
(a)(b)(c)Figure 3
Geometrical interpretation of the proposed framework. Red bullets and red lines represent initial points and initial polygons, respectively. Black bullets and black lines represent the points and the polygons obtained by the subdivision scheme (17). Green bullets and green lines represent the points and the polygons obtained by the subdivision scheme (22).
(a)(b)(c)


### 3.3. Extended Form of Framework 3.1 for Constructing a Family of2N+3-Point Relaxed Schemes

Whenℓ=1, we add these weights(24)∑j=−N−1N−1j+N+12j+1N−j+12N+2N+j+2β1−αfi+j+1,N+10+β1−αfi−N−1,N+10+fi+N+2,N+10,in (13), where −1<α<1&−1<β<1. Hence, we get the family of 2N+3-point combined relaxed schemes Sa2N+3 associated with the following refinement rules:(25)f2i,N+1k+1=∑j=−N−1N+1b2jfi+j,N+1k,f2i+1,N+1k+1=∑j=−N−2N+1b2j+1fi+j+1,N+1k,where(26)b2j=a2j,N+1forj=−N+1,−N,…,N+1,b2j+1=a2j+1,N+1+−1j+N+12j+1N−j+12N+2N+j+2β1−αforj=−N+1,−N,…,Nandb2j+1=β1−αforj=−N+2N+1.The schematic sketches of these rules are given in Figures1(c) and 1(d), and mask of the first three members of this family of schemes is given as follows:(i)
WhenN=0, (25) gives the primal 3-point relaxed scheme with mask(27)β1−α,α,12−β1−α,1−2α,12−β1−α,α,β1−α.(i)i
WhenN=1, (25) gives the primal 5-point relaxed scheme with mask(28)β1−α,−α,−116−3β1−α,4α,916+2β1−α,1−6α,916+2β1−α,4α,−116−3β1−α,−α,β1−α.(iii)
WhenN=2, (25) gives the primal 7-point relaxed scheme with mask(29)β1−α,α,3256−5β1−α,−6α,−25256+9β1−α,15α,150256−5β1−α,1−20α,150256−5β1−α,15α,−25256+9β1−α,−6α,3256−5β1−α,α,β1−α.


### 3.4. Interpretation of Extended Form 3.3 forN=1

WhenN=1, (24) gives(30)∑j=−21−1j+22j+12−j43+jβ1−αfi+j+1,20+β1−αfi−2,20+fi+3,20=β1−αfi−2,20−3fi−1,20+2fi,20+2fi+1,20−3fi+2,20+fi+3,20.Adding weights which are defined in (30) in the edge rule of (22), we get(31)f2i,21=−αfi−20+4αfi−10+1−6αfi0+4αfi+10−αfi+20,f2i+1,21=β1−αfi−20−116+3β1−αfi−10+916+2β1−αfi0+916+2β1−αfi+10−116+3β1−αfi+20+β1−αfi+30.Since the above scheme is stationary, the refinement rules of proposed 5-point relaxed scheme with two tension parameters are(32)f2i,2k+1=−αfi−2k+4αfi−1k+1−6αfik+4αfi+1k−αfi+2k,f2i+1,2k+1=β1−αfi−2k−116+3β1−αfi−1k+916+2β1−αfik+916+2β1−αfi+1k−116+3β1−αfi+2k+β1−αfi+3k.Remark 2.
(i)
The schemes of [5] are the special cases of the proposed family of 2N+3-point schemes.(ii)
The family of2N+4-point interpolatory schemes Sa2N+4I with one tension parameter is obtained by putting α=0 in (25). The refinement rules of these schemes are given as follows:(33)f2i,N+1k+1=fi,N+1k,f2i+1,N+1k+1=∑j=−N−2N+1b2j+1fi+j+1,N+1k,where b2j+1 is defined in (26).


## 3.1. Framework for the Construction of a Family of2N+2-Point Relaxed Schemes

The family of2N+2-point combined subdivision schemes Sa2N+2 which maps the polygon fN+1k=fi,N+1k:i∈ℤ to the refined polygon fN+1k+1=fi,N+1k+1:i∈ℤ is defined by the set of following refinement rules:(11)f2i,N+1k+1=∑j=−N−1N+1a2j,N+1fi+j,N+1k,f2i+1,N+1k+1=∑j=−N−1Na2j+1,N+1fi+j+1,N+1k,where N∈ℕ0=ℕ∪0 is used to calculate the complexity (number of control points at k-th subdivision level used in the insertion of a new point at k+1-th subdivision level is called the complexity) of the subdivision schemes and k∈ℕ denotes the number of times subdivision is applied on the original data points. Hence, for each N, the set fi,N+1k+1:i∈ℤ represents the k+1-th level subdivided points obtained by applying k+1-times the 2N+2-point relaxed subdivision scheme (11) on the initial data points fi0=fi,N+10:i∈ℤ, and a=aj,N+1:j=−2N+1,…,2N+1 is mask of the scheme (11) which is same at each level of refinement for a fix value of N. The schematic sketches of both rules defined in (11) are presented in Figures 1(a) and 1(b).Figure 1
Graphical sketches of the rules of2N+2-point primal schemes in (a-b) and of 2N+3-point primal schemes in (c-d), respectively. (a) Vertex rule. (b) Edge rule. (c) Vertex rule. (d) Edge rule.
(a)(b)(c)(d)The construction process of these rules is given as follows.IfN=0, the two refinement rules of the 2-point relaxed scheme are obtained from (12). Hence, fi,11:i∈ℤ are the control points at first subdivision level obtained by the 2-point relaxed subdivision scheme on the initial control points fi0=fi,10:i∈ℤ. These two refinement rules are the initial refinement rules used to calculate the other refinement rules of proposed family of schemes for each successive value of N. The initial refinement rules are defined as(12)f2i,11=fi,10+α0fi−1,10−2fi,10+fi+1,10,f2i+1,11=12fi,10+12fi+1,10,where α0∈−1,1.Now, we calculate pointsf2i+ℓ,N+11:ℓ=0,1i∈ℤ of the HTML translation failed-point relaxed subdivision scheme for N⩾1. Hence, for a fix value of N, the points f2i+ℓ,N+11:ℓ=0,1i∈ℤ of the 2N+2-point relaxed subdivision scheme are obtained by moving the points f2i+ℓ,N1:ℓ=0,1i∈ℤ to the new position according to the displacement vectors αℓC⟶2i+ℓ,N+1:ℓ=0,1i∈ℤ, where αℓ is the tension parameter with α1=1 and α0=α.Mathematically, forN≥1, the two refinement rules of the family of 2N+2-point relaxed subdivision schemes at first level of subdivision are obtained by the following recurrence relation:(13)f2i+ℓ,N+11=f2i+ℓ,N1+αℓC⟶2i+ℓ,N+1,ℓ=0,1,where the vectors C⟶2i+ℓ,N+1:ℓ=0,1 are calculated by the following recurrence relation:(14)C⟶2i,N+1=C⟶2i,N−C⟶2i+1,N+C⟶2i,N−C⟶2i−1,N,C⟶2i+1,N+1=1NN4−18C⟶2i+1,N−C⟶2i+1+1,N+C⟶2i+1,N−C⟶2i−1+1,N,and initial values for relation (14) are(15)C⟶2i,1=fi−1,10−fi,10+fi+1,10,C⟶2i+1,1=12fi,10+fi+1,10.Here,fi0 = fi,10 = fi,20=fi,30=⋯=fi,N+10 are the initial control points.While the pointsfi,11, fi,21, fi,31, and fi,41 are the initial points of the 4-point, 6-point, and 8-point relaxed subdivision schemes obtained by substituting the values of N equal to 1, 2, and 3, respectively, in (13) and (14). Since the proposed subdivision schemes are stationary, the refinement rules are same at each level of subdivision. Therefore, for other subdivision levels, we apply (11) while the coefficients of points fi,N+1k remain same as the coefficients of points fi,N+10=fi0 obtained from (13). Also, fi,1k+1, fi,2k+1, fi,3k+1, and fi,4k+1 are the control points at k+1-th subdivision level obtained by applying the 2-point, 4-point, 6-point, and 8-point relaxed subdivision schemes on the k-th level points fi,1k, fi,2k, fi,3k, and fi,4k, respectively. Moreover, the points other than the initial control points hold the relation fi,Nk≠fi,N+1k∀N∈ℕ.At each iteration, i.e., by substitutingN=1,2,3,… in (11), (13), and (14), we get a new binary primal 2N+2-point subdivision scheme. The masks of these 2N+2-point schemes by defining α0=α are tabulated in Table 1.Table 1
Mask of the2N+2-point schemes Sa2N+2.
NMask01/22α,1,2−4α,1,2α11/16−16α,−1,64α,9,16−96α,9,64α,−1,−16α21/256−256α,3,−1536α,−25,3840α,150,256−5120α,150,3840α,25,−1536α,3,256α31/2048−2048α,−5,16384α,49,−57344α,−245,114688α,1225,2048−143360α,1225,114688α,−245,−57344α,49,16384α,−5,−2048α41/6553665536α,35,−655360α,−405,2949120α,2268,−7864320α−8820,13762560α,39690,65536−16515072α,39690,13762560α,−8820,−7864320α,2268,2949120α,−405,−655360α,35,65536α51/524288−524288α,−63,6291456α,847,−34603008α,−5445,115343360α,22869,−259522560α,−76230,415236096α,320166,524288,−484442112α,320166,415236096α,−76230,−259522560α,22869,115343360α,−5445,−34603008α,847,6291456α,−63,−524288αRemark 1.
Ifα=0, the family of scheme (11) reduces to the family of 2N+2-point interpolatory schemes with symbol(16)az=1+∑j=−N−1Na2j+1,N+1z2j+1,which is proposed by Deslauriers and Dubuc [1]. The continuity of 2N+2-point interpolatory schemes is CN for 0≤N≤4 and C≈83/200N+1 for N≥5.


## 3.2. Interpretation of Framework 3.1 forN=1

The refinement rules of the initial subdivision scheme defined in (12) are(17)f2i,11=αfi−10+1−2αfi0+αfi+10,f2i+1,11=12fi0+12fi+10.Moreover, the initial valuesC⟶2i+ℓ,1:ℓ=0,1 which will be used to calculate the vectors C⟶2i+ℓ,N+1:ℓ=0,1N∈ℕ defined in (15) are(18)C⟶2i,1=fi−10−fi0+fi+10,C⟶2i+1,1=12fi0+12fi+10.Now, we use initial relations (17) and (18) to calculate the refinement rules of 4-point relaxed scheme which will be obtained by putting N=1 in (13) and (14). Hence, for N=1, we get(19)f2i,21=f2i,11+α0C⟶2i,2,f2i+1,21=f2i+1,11+α1C⟶2i+1,2,where(20)C⟶2i,2=C⟶2i,1−C⟶2i+1,1+C⟶2i,1−C⟶2i−1,1,C⟶2i+1,2=18C⟶2i+1,1−C⟶2i+1+1,1+C⟶2i+1,1−C⟶2i−1+1,1.By using (18) in (20), we get(21)C⟶2i,2=−fi−20+3fi−10−4fi0+3fi+10−fi+20,C⟶2i+1,2=116−fi−10+fi0+fi+10−fi+20.Now, firstly we putα0=α and α1=1 in (19) and then we use (17) and (21) in (19). Hence, we get the following 4-point relaxed subdivision scheme:(22)f2i,21=−αfi−20+4αfi−10+1−6αfi0+4αfi+10−αfi+20,f2i+1,21=116−fi−10+9fi0+9fi+10−fi+20.By using (22) in (11), we get(23)f2i,2k+1=−αfi−2k+4αfi−1k+1−6αfik+4αfi+1k−αfi+2k,f2i+1,2k+1=116−fi−1k+9fik+9fi+1k−fi+2k.Step by step geometrical representations of the above procedure are shown in Figures2 and 3. The description of Figure 2 is as follows. In Figure 2(a), the implementation of the initial subdivision scheme defined in (17) is given. In Figure 2(b), blue bullets show the points obtained by the relations defined in (18). Here, C⟶2i−2,1=fi−20−fi−10+fi0, C⟶2i−1,1=1/2fi−10+fi0, C⟶2i,1=fi−10−fi0+fi+10, C⟶2i+1,1=1/2fi0+fi+10, C⟶2i+2,1=fi0−fi+10+fi+20, and C⟶2i+3,1=1/2fi+10+fi+20. In Figure 2(c), C⟶2i,2 is the resultant vector of two vectors C⟶2i,1−C⟶2i+1,1 and C⟶2i,1−C⟶2i−1,1. Similarly, CC⟶2i+1,2 is the resultant vector of C⟶2i+1,1−C⟶2i+1+1,1 and C⟶2i+1,1−C⟶2i−1+1,1. The resultant vectors are obtained by adding two vectors using head to tail rule. The resultant vectors are denoted by blue solid lines while the other vectors are denoted by blue dashed lines. Moreover, the description of Figure 3 is as follows, In Figure 3(a), the geometrical representation of the vectors defined in (20) is given. Here, C⟶2i+1,2=1/8CC⟶2i+1,2; In Figure 3(b), the translation of the points f2i,11 and f2i+1,11 is shown by using vectors αC⟶2i,2 and C⟶2i+1,2 to obtain the points f2i,21 and f2i+1,21 denoted by green bullets; In Figure 3(c), green bullets show the points of the subdivision scheme (21) constructed by the proposed framework.Figure 2
Geometrical interpretation of the proposed framework. Red bullets and red lines represent initial points and initial polygons, respectively. Black bullets and black lines represent the points and the polygons obtained by the subdivision scheme (17).
(a)(b)(c)Figure 3
Geometrical interpretation of the proposed framework. Red bullets and red lines represent initial points and initial polygons, respectively. Black bullets and black lines represent the points and the polygons obtained by the subdivision scheme (17). Green bullets and green lines represent the points and the polygons obtained by the subdivision scheme (22).
(a)(b)(c)


## 3.3. Extended Form of Framework 3.1 for Constructing a Family of2N+3-Point Relaxed Schemes

Whenℓ=1, we add these weights(24)∑j=−N−1N−1j+N+12j+1N−j+12N+2N+j+2β1−αfi+j+1,N+10+β1−αfi−N−1,N+10+fi+N+2,N+10,in (13), where −1<α<1&−1<β<1. Hence, we get the family of 2N+3-point combined relaxed schemes Sa2N+3 associated with the following refinement rules:(25)f2i,N+1k+1=∑j=−N−1N+1b2jfi+j,N+1k,f2i+1,N+1k+1=∑j=−N−2N+1b2j+1fi+j+1,N+1k,where(26)b2j=a2j,N+1forj=−N+1,−N,…,N+1,b2j+1=a2j+1,N+1+−1j+N+12j+1N−j+12N+2N+j+2β1−αforj=−N+1,−N,…,Nandb2j+1=β1−αforj=−N+2N+1.The schematic sketches of these rules are given in Figures1(c) and 1(d), and mask of the first three members of this family of schemes is given as follows:(i)
WhenN=0, (25) gives the primal 3-point relaxed scheme with mask(27)β1−α,α,12−β1−α,1−2α,12−β1−α,α,β1−α.(i)i
WhenN=1, (25) gives the primal 5-point relaxed scheme with mask(28)β1−α,−α,−116−3β1−α,4α,916+2β1−α,1−6α,916+2β1−α,4α,−116−3β1−α,−α,β1−α.(iii)
WhenN=2, (25) gives the primal 7-point relaxed scheme with mask(29)β1−α,α,3256−5β1−α,−6α,−25256+9β1−α,15α,150256−5β1−α,1−20α,150256−5β1−α,15α,−25256+9β1−α,−6α,3256−5β1−α,α,β1−α.


## 3.4. Interpretation of Extended Form 3.3 forN=1

WhenN=1, (24) gives(30)∑j=−21−1j+22j+12−j43+jβ1−αfi+j+1,20+β1−αfi−2,20+fi+3,20=β1−αfi−2,20−3fi−1,20+2fi,20+2fi+1,20−3fi+2,20+fi+3,20.Adding weights which are defined in (30) in the edge rule of (22), we get(31)f2i,21=−αfi−20+4αfi−10+1−6αfi0+4αfi+10−αfi+20,f2i+1,21=β1−αfi−20−116+3β1−αfi−10+916+2β1−αfi0+916+2β1−αfi+10−116+3β1−αfi+20+β1−αfi+30.Since the above scheme is stationary, the refinement rules of proposed 5-point relaxed scheme with two tension parameters are(32)f2i,2k+1=−αfi−2k+4αfi−1k+1−6αfik+4αfi+1k−αfi+2k,f2i+1,2k+1=β1−αfi−2k−116+3β1−αfi−1k+916+2β1−αfik+916+2β1−αfi+1k−116+3β1−αfi+2k+β1−αfi+3k.Remark 2.
(i)
The schemes of [5] are the special cases of the proposed family of 2N+3-point schemes.(ii)
The family of2N+4-point interpolatory schemes Sa2N+4I with one tension parameter is obtained by putting α=0 in (25). The refinement rules of these schemes are given as follows:(33)f2i,N+1k+1=fi,N+1k,f2i+1,N+1k+1=∑j=−N−2N+1b2j+1fi+j+1,N+1k,where b2j+1 is defined in (26).


## 4. Analysis of the Families of Schemes

In this section, we present properties of the proposed families of schemes. In Table2, we present “ranges of tension parameter α” for which the first six members of “the family of 2N+2-point relaxed schemes” are Cn-continuous. The continuity of the proposed schemes is analyzed with a computer algebra system like Mathematica/Maple by using Theorems 1 and 2. Similarly, continuity of the first three members of 2N+3-point relaxed schemes and 2N+4-point interpolatory schemes is presented in Tables 3 and 4, respectively, for specific ranges of tension parameters.Table 2
MC: the maximum continuity of the proposed schemesSa2N2.
NMCC0C1C2C3C4C501−1/4<α<3/40<α<1/4α=1/812−3/25<α<6/25−1/35<α<27/2000<α<1/1623−1/21<α<1/14−1/64<α<1/25−1/80<α<1/4833/5000<α<19/125034−1/256<α<1/116−1/151<α<1/80−1/384<α<1/160−1/21000<α<1/24629/50000<α<41/5000045−1/70<α<1/129−1/416<α<1/255−1/838<α<1/501−1/3560<α<1/828−1/200000<α<1/13541/4099<α<1/171755−1/509<α<1/400−1/1208<α<1/804−1/2212<α<1/1556−1/7440<α<1/2716−1/26106<α<1/44461/10160<α<1/7240Table 3
MC: the maximum continuity of the proposed schemeSa2N3.
Nα/βMCC0C1C2C3C40α=1/816β+1/2β+14−3/20<β<5/4−1/16<β<3/8−1/16<β<3/80<β<1/12β=1/26β=−1/168α−1/α−1−1/4<α<3/40<α<1/20<α<1/21/8<α<1/4α=3/161α=1/128256β−3/2β−14−21/208<β<11/272−13/224<β<3/256−13/224<β<3/256−2/121<β<−1/248−2/121<β<−1/248β=1/256128α−3/α−1−1/16<α<3/160<α<1/80<α<1/81/32<α<7/1281/32<α<7/1282α=1/10242048β+5/2β+14−21/2080<β<113/5888−5/2048<β<11/997−5/2048<β<11/9973/2032<β<8/30413/2032<β<8/3041β=−1/20481024α−5/α−1−1/64<α<1/240<α<27/10240<α<27/10241/128<α<31/30721/128<α<31/3072Tabe 4
GD and RD represent the degree of polynomial generation and degree of polynomial reproduction of the proposed schemesSa2N4I.
N012C0−1/8<β<0−5/48<β<1/16−39/2560<β<89/2560C12−6/8<β<1−3/815−273/96<β<−5+337/224219−661133/31232<β<−171+56713/6144C20<β<1/3616−286/96<β<−675+637161/31744C3−157/20000<β<−43/20000GD1∀β3∀β5∀β3 forβ=−1/165 forβ=3/2567 forβ=−5/2048RD1∀β3∀β5∀β3 forβ=−1/165 forβ=3/2567 forβ=−5/2048In Tables4–6, we tabulate the support widths, degrees of polynomial generation, and degrees of polynomial reproduction of the proposed families of 2N+2-point relaxed, 2N+3-point relaxed, and 2N+4-point interpolatory schemes, respectively. The generation and reproduction degrees of the proposed schemes are analyzed by using Theorem 3, while the support widths of the proposed schemes are calculated by using Theorem 4. Properties of some special members of the family of schemes (11) are presented in Table 7.Table 5
Properties of schemesSa2N+2 for ∀α.
N012345Support4812162024Generation1357911Reproduction1357911Table 6
Properties of schemesSa2N+3.
N012Sp61014GD1∀α and β3∀α&β5∀α&β3∀α where β=−1/168α−1/α−15∀α where β=1/256128α−3/α−17∀α where β=−1/20481024α−5/α−13∀β where α=1/816β+1/2β+15∀β where α=1/128256β−3/2β−17∀β where α=1/10242048β+5/2β+15 forα=3/16&β=−1/168α−1/α−17 forα=5/128&β=1/256128α−3/α−19 forα=35/4096&β=−1/20481024α−5/α−15 forβ=1/26 where α=1/816β+1/2β+17 forβ=−1/123 where α=1/128256β−3/2β−19 forβ=15/8122 where α=1/10242048β+5/2β+1RD1∀α&β3∀α&β5∀α&β3 forα=0&β=−1/165 forα=0&β=3/2567 forα=0&β=−5/20483 forα=−1/8&β=05 forα=−3/128&β=07 forα=−5/1024&β=0Sp, GD, and RD represent support width, generation degree, and reproduction degree, respectively.Table 7
Properties of schemesSa2N+2 for specific values of α.
N012345α1/83/1285/102435/3276863/262144231/4194304ContinuityC2C2C2C3C5C3Generation35791113Reproduction1357911Leta2N+2z, a2N+3z, and a2N+4Iz denote the symbols of schemes (11), (25), and (33), respectively. By Definition 1, the following theorem can be easily proved.Theorem 5.
The families of subdivision schemes (11), (25), and (33) are the families of primal schemes.Proof.
Since the symbols associated with schemes (11), (25), and (33) satisfy the relations a2N+2z=a2N+2z−1, a2N+3z=a2N+3z−1, and a2N+4Iz=a2N+4Iz−1, respectively, for all N∈ℕ0, then by Definition 1, these schemes are primal. This completes the proof.
Now, we check the property of polynomial generation and reproduction of the families of schemesSa2N+2, Sa2N+3, and Sa2N+4I by using Theorem 3. We prove the following theorems for this purpose.Theorem 6.
The families of subdivision schemes (11), (25), and (33) generate polynomials up to degree 2N+1 for all α and β and for all N∈ℕ0.Proof.
It is to be noted that for allα and β, the results a2N+21=a2N+31=a2N+4I1=2 and a2N+2−1=a2N+3−1=a2N+4I−1=0 are trivial for all N∈ℕ0. Furthermore, Dma2N+2z|z=−1=Dma2N+3z|z=−1=Dma2N+4Iz|z=−1=0 for m=0,1,…,2N+1 and N∈ℕ0. Therefore, by Theorem 3, the result proved.Theorem 7.
The families of subdivision schemes (11), (25), and (33) reproduce polynomials up to degree 2N+1 for all α and β and N∈ℕ0.Proof.
Since by Theorem5, the families of schemes (11), (25), and (33) are primal; hence, the parameter τ=0 for all α and β and N∈ℕ0. Moreover, Dma2N+2z|z=1=Dma2N+3z|z=1=Dma2N+4Iz|z=1=2∏h=0m−1τ−h for m=0,1,…,2N+1 and N∈ℕ0. Now, by combining these conditions with Theorem 6 and then by using Theorem 3, we get the required result.Remark 3.
Theorems6 and 7 show that the schemes defined in (11), (25), and (33) generate and reproduce polynomials up to degree 2N+1 for all α and β. However, by choosing specific values of α and β, the polynomial generation and polynomial reproduction of these schemes can be increased. Tables 4, 6, and 7 summarize the generation and reproduction degrees of proposed schemes for specials choices of tension parameters.
In the coming theorem, we give the support width of the proposed families of schemes.Theorem 8.
The support width of the family of scheme (11) is 4N+4 where N∈ℕ0. The support width of each family of subdivision schemes defined in (25) and (33) is 4N+6.Proof.
By Theorem4, the result is trivial.
We prove the following theorem by using Theorems1 and 2.Theorem 9.
The subdivision schemesSa3, Sa5, and Sa7 are C1, C3, and C5, respectively, for some special conditions.Proof.
The conditions forC1, v, and C5 continuities of the schemes Sa3, Sa5, and Sa7, respectively, are given as follows:
The subdivision schemeSa3 is C1 if(34)maxγ1,γ2+γ3<1,where γ1=22α−4β1−α, γ2=22β1−α, and γ3=1+4β1−α−4α.
The schemeSa5 is C3 if(35)maxη1+η2,η3+η4<1,where η1=16β1−α, η2=2−56β1−α−32α+1/2, η3=2−32β1−α−8α, and η4=−48α−64β1−α+2.
Similarly, the subdivision schemeSa7 is C5 if(36)maxχ1+χ2+χ3,χ4+χ5<1,where χ1=64β1−α, χ2=2−512β1−α+192α−3/8, χ3=−19/4−960β1−α+640α, χ4=2−192β1−α+32α, and χ5=2480α−9/4−832β1−α.Remark 4.
Throughout the article, red bullets and red lines represent initial points and initial polygons/meshes, respectively.


## 5. Numerical Examples and Comparisons

This section deals with the numerical examples of the proposed families of subdivision schemes. We also give some numerical and mathematical companions of the proposed schemes with the existing schemes. Numerical performance of 2-point, 3-point, 4-point, 5-point, 6-point, and 7-point relaxed subdivision schemes is shown in Figures4(a), 4(b), 4(d), 4(e), 4(g), and 4(h), respectively. From these figures, it is easy to see that the tension parameters which are involved in the proposed schemes allow us to draw different models from same initial points. Similarly, geometrical behaviors of interpolatory 4-point, 6-point, and 8-point schemes for different values of tension parameters are shown in Figures 4(c), 4(f), and 4(i), respectively. An interesting geometrical behavior of 3-point, 5-point, and 7-point schemes is shown in Figures 5(a)‒5(h) and 6(a)‒6(d), respectively.Figure 4
Black curves are the limit curves obtained by the subdivision schemes: (a)Sa2; (b) Sa3; (c) Sa4I; (d) Sa4; (e) Sa5; (f) Sa6I; (g) Sa6; (h) Sa7; (i) Sa8I, respectively.
(a)(b)(c)(d)(e)(f)(g)(h)(i)Figure 5
Black curves are the limit curves obtained by subdivision schemeSa3 in (a–d) and by subdivision scheme Sa5 in (e–h), respectively: (a) α=1/2048,β=255/4096; (b) α=1/16,β=−1/30; (c) α=1/8,β=0; (d) α=1/4,β=1/4; (e) α=1/32,β=−3/62; (f) α=1/16,β=−1/48; (g) α=1/10,β=−49/1152; (h) α=1/8,β=−11/128.
(a)(b)(c)(d)(e)(f)(g)(h)We apply these schemes to two different initial models with same values of the tension parameters. From these figures, we observe that the artifacts in the limit curve can be removed either by changing values of the tension parameters or by changing the initial polygons. While schemes proposed by Deslauriers and Dubuc [1], which are also the special cases of the proposed schemes for specific values of tension parameters α and β, do not have this characteristic (see Figures 6(e)–6(h)). Figures 7–9 show that the surfaces produced by the tensor product schemes of proposed primal schemes also give better numerical results than those of the tensor product schemes of primal schemes [1]. Table 8 gives comparisons between proposed families of primal schemes and the family of primal interpolatroy schemes of Deslauriers and Dubuc [1]. The parameters used in our families of subdivision schemes not only increase the choices of drawing different shapes but also increase the polynomial reproduction, polynomial generation, and smoothness of the proposed schemes. Moreover, we can draw interpolatory and approximating curves by using a single member of the family. Table 9 gives the comparisons of the proposed primal schemes with the primal approximating schemes of [6, 7]. Since approximating subdivision schemes give more smoothness in limits curves as comparative to the interpolating and combined schemes, some of the proposed schemes give lower level of continuity than that of the schemes of [6, 7]. However, the degrees of polynomial reproduction of the proposed schemes are higher than those of these approximating primal schemes.Figure 6
Black curves are the limit curves obtained by subdivision schemeSa7 in (a–d) and by subdivision schemes of Deslauriers and Dubuc [1] in (e–h), respectively: (a) α=1/2048,β=1/512; (b) α=1/100,β=−1/128; (c) α=1/128,β=1/512; (d) α=1/80,β=1/80; (e) 2-point scheme; (f) 4-point scheme; (g) 6-point scheme; (h) 8-point scheme.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 7
(a–c, g–i) The surfaces generated by the tensor product of schemeSa3. (d–f) The mirror images of the parts inside the blue rectangles of (a–c), respectively. (j–l) The 2-dimensional images in xy-planes of (g–i), respectively.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Figure 8
(a–c, g–i) The surfaces generated by the tensor product of schemeSa5. (d–f) The mirror images of the parts inside the blue rectangles of (a–c), respectively. (j–l) The 2-dimensional images in xy-planes of (g–i), respectively.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Figure 9
(a–c, g–i) The surfaces generated by the tensor product schemes of Deslauriers and Dubuc [1]. (d–f) The mirror images of the parts inside the blue rectangles of (a–c), respectively. (j–l) The 2-dimensional images in xy-planes of (g–i), respectively.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Table 8
NTP, RD, GD, MC, Pr, In, Cm, Re, and DD-schemes represent the number of tension parameter(s), degree of polynomial reproduction, degree of polynomial generation, maximum continuity, primal, interpolatory, combined, relaxed, and schemes of Deslauriers and Dubuc [1], respectively, where N∈ℕ0 with N<5.
Family of schemesTypeNTPRDGDMC2N+2-point DD-schemesPr/In02N+12N+1CN2N+2-point schemesPr/Cm/Re12N+1∀′2N+3∀′At leastCN+12N+3-point schemesPr/Cm/Re22N+3∀′2N+5∀′At leastC42N+4-point schemesPr/In12N+3∀′2N+3∀′CN+1Here,∀ and ∀′ stand for “for all value(s) of parameter(s)” and “not for all value(s) of parameter(s) (at specific values of parameter(s)),” respectively.Table 9
Comparison of the proposed schemes with existing primal relaxed schemes having the same support width.
SchemesSWNTPTypeGDGD1RDRD1ContinuitySchemeSa362Combined1513C4Scheme [7]61Approximating1511C1SchemeSa481Combined3533C2Scheme [7]81Approximating3711C3Scheme [6]81Approximating1311C1SchemeSa5102Combined3735C4Scheme [7]101Approximating5911C5SchemeSa6121Combined5755C3Scheme [7]121Approximating71111C7SchemeSa7142Combined5957C4Scheme [6]141Approximating3513C3SW, NTP, GD, GD1, RD, and RD1 represent the support width, number of tension parameter(s), degree of polynomial generation at all value(s) of tension parameter(s), degree of polynomial generation at specific value(s) of tension parameter(s), degree of polynomial reproduction for all value(s) of tension parameter(s), and degree of polynomial reproduction at specific value(s) of tension parameter(s).


## 6. Interproximate Subdivision Schemes

In this section, we present a new family of subdivision schemes, that is, the family of interproximate subdivision schemes, for generating curves that interpolate certain given initial control points and approximate the other initial control points. By the interproximate subdivision scheme, only the initial control points specified to be interpolated are fixed and the other points are updated at each refinement step. The interproximate subdivision schemes can be defined by replacingαi and βi as the substitution of α and β in (25) and (26). In this interproximate subdivision process, the parameters αi control the interpolating property of the subdivision schemes and parameters βi control the approximating property of the subdivision schemes. Figures 10(a)–10(c) show the initial polygon and limit curves generated by the subdivision scheme Sa3 using initial control points 1,5,1,2,13,3.4,14,2.5,14,4.5,13,3.6, and 1,5. Figures 10(d)–10(f) demonstrate that this scheme interpolates the control points in a local manner and uses a different value of tension parameter for each edge of the control polygon. Values of the tension parameters at first subdivision levels are shown in these figures. Whereas at the other subdivision levels, we use same interpolating values for the control points which are interpolated at the first subdivision levels and use the approximating values of the tension parameters for the modified and new inserted points. Figures 10(g)–10(l) show the limit curves generated by subdivision scheme Sa5 using initial control points 0,0, 4,0, 5,5, 4,10, 0,10, 0,8, 1,8, 2,5, 1,2, and 0,2. In this figure, (i)
(g) represents the initial polygon with indexed initial control points.(ii)
(h) shows the limit curve that interpolates all the control points withα,β=0,−0.001.(iii)
(i) represents the limit curve that approximates all the initial control points withα,β=1/16,−1/48.(iv)
(j) shows the interproximate limit curve withαi,βi = 1/10−49/1152, 1/10−49/1152, 1/10−49/1152, 1/10−49/1152, 1/10−49/1152, 1/10−49/1152, 0,1/64, 0,1/64, 0,1/64, 1/10−49/1152 at first subdivision level. Whereas at other subdivision levels, we use αi,βi=0,1/64 for the points 1,8, 2,5, and1,2 and αi,βi=1/10,−49/1152 for all the other points.(v)
(k) shows the interproximate limit curve withαi,βi = [1/14−43/1664, 0,−2/125, 0,−2/125, 0,−2/125, 1/14−43/1664, 1/14−43/1664, 1/14−43/1664, 1/14−43/1664, 1/14−43/1664, 1/14−43/1664 at first subdivision level. Whereas at other subdivision levels, we use αi,βi=0,−2/125 for the points 4,0, 5,5, and4,10 and αi,βi=1/14,−43/1664 for all the other points.(vi)
(l) shows the interproximate limit curve withαi,βi = [0,1/30,0,1/30, 1/11,−1/30, 0,1/30, 0,1/30, 1/11,−1/30, 1/11,−1/30, 1/11,−1/30, 1/11,−1/30, 1/11−1/30 at first subdivision level. Whereas at other subdivision levels, we use αi,βi=0,1/30 for the points 0,0, 4,0, 4,10, and0,10 and αi,βi=1/11,−1/30 for all the other points.Figure 10
The effect of local interpolation by our combined subdivision schemeSa3 with different αi and βi is shown in (a–f) and by our combined subdivision scheme Sa5 with different αi and βi is shown in (g–l), respectively.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)These figures show that proposed schemes can interpolate the initial control points which are chosen by the programmers to be interpolated.Figure11 shows the limit surfaces generated by tensor product subdivision scheme of scheme Sa3 using initial control points 0,2,0, 5,0,0, 10,2,0, 5,15,0, 0,2,0, 0,2,2, 5,0,2, 10,2,2, 5,15,2, 0,2,2, (0,2, 4), 5,0,4, 10,2,4, 5,15,4, (0,2, 4), 0,2,6, 5,0,6, 10,2,6, 5,15,6, and 0,2,6, where Figure 11(a) shows the limit surface that interpolates all the initial control points with α,β=0,−1/40 , Figure 11(b) shows the limit surface that approximates all the initial control points with α,β=1/8,0, and Figure 11(c) shows the limit surface that interpolates only the control points 5,15,0, 5,15,2, 5,15,4, and 5,15,6 at each level of subdivision with αi,βi=0,−1/40 and approximates all the other control points at each level of subdivision with αi,βi=1/8,0. Similarly, a programmer can choose other control points of his choice to be interpolated by using the tensor product schemes of the proposed schemes. Moreover, the extension of these schemes to the more general schemes which can produce surfaces with arbitrary topology is a direction for future study.Figure 11
The effect of local interpolation by tensor product of our combined subdivision schemeSa3 with different αi and βi.
(a)(b)(c)


## 7. Conclusion

In this article, we have proposed a recursive method to generate the refinement rules of combined subdivision schemes. On the basis of that recursive refinement rules, we have presented the family of2N+2-point relaxed primal combined schemes, the family of 2N+3-point relaxed combined schemes, and the family of 2N+4-point interpolatory subdivision schemes with reproduction degrees 2N+1, 2N+3, and 2N+3, respectively, at certain values of the tension parameters. In fact, when value of N is increased by one, polynomial reproductions of the proposed families of schemes are increased by two. Similarly, polynomial generations of the proposed families of schemes are 2N+3, 2N+5, and 2N+3, respectively. N is also directly proportional to the polynomial generations of the schemes. The continuity of the proposed families may be increased by increasing N. Our families of schemes not only give the flexibility in fitting limit curves/surfaces because of the involvement of tension parameters but also give the optimal polynomial reproduction, polynomial generation, and continuity than the existing primal schemes. Moreover, we converted the proposed family of 2N+3-point combined subdivision schemes to the family of interproximate subdivision schemes by defining local parameters. One of these parameters is defined to control the interpolating property of the subdivision schemes and other one is defined to control the approximating property of the subdivision schemes. The interproximate subdivision schemes have applications in situations where some of the initial data points cannot be measured exactly. Future work is to do a theoretical study that how to choose values of tension parameters in an interproximate algorithm automatically.



---

*Source: 6639706-2021-04-16.xml*