723
Views
1
CrossRef citations to date
0
Altmetric
Original Article

Modeling of curves by a design-control approximating refinement scheme

ORCID Icon, ORCID Icon, , ORCID Icon & ORCID Icon
Pages 164-178 | Received 22 Apr 2022, Accepted 19 Mar 2023, Published online: 28 Mar 2023

Abstract

This paper introduces a modified method for construction of a new design-control 6-point approximating refinement scheme. The construction of the new scheme is based on translation of the points of 4-point approximating refinement scheme to the new position according to the linear combination of certain displacement vectors. The initial and terminal points of these vectors are the refinement points of two 4-point approximating binary schemes. The new scheme contains three design-control parameters. These parameters increase the efficiency and flexibility of the new scheme. The mathematical and graphical analysis of the refinement scheme show that this scheme is good choice for curve modeling.

1. Introduction

Computer aided geometric design (CAGD) is considered as an emerging research field of computational mathematics hat has been rapidly growing since the past two decades due to a wide range of applications (Garg, Citation2020). In CAGD different mathematical algorithms and refinement rules are used to obtain better shapes of the objects. The CAGD field works on the same principle that was used by Archimedes to approximate a circle by increasing the number of vertices of a regular polygon. This field concerns with modeling and designing different complex objects with the help of elegant mathematical algorithms. Therefore, CAGD is the field which is mostly used by designers for shaping or fitting curves and surfaces with non-uniform shapes or discrete set of control points.

Refinement schemes have been a well-liked techniques in CAGD to produce curves and surfaces. Refinement schemes have various applications in graphics, image processing, engineering etc and thus have become an important area of study (Livesu, Citation2021; Livesu, Pitzalis, & Cherchi, Citation2021; Meng et al., Citation2020; Ning et al., Citation2020; Zhang et al., Citation2020). These schemes succeeded to get a great attention due to their high efficiency and clarity. A subdivision process refines the initial polygon recursively to a set of refined polygons which converge to a smooth limiting curve. Also, the refinement schemes were designed mainly for getting the desirable shapes. In addition, by different refinement schemes we can create smooth curves and surfaces by using a sequence of successive refinements. It starts by choosing a rough shape, and then converges finally to a smooth shape (Mahalingam & Koneru, Citation2020).

The most important classes of refinement schemes are interpolatory and approximating refinement schemes which interpolate and approximate the given data respectively. Both are considered as a non-parametric binary approximating refinement schemes. The construction and analysis of the non-parametric binary approximating refinement schemes are discussed in (Hameed & Mustafa, Citation2017; Mustafa & Rehman, Citation2010; Siddiqi & Younis, Citation2013). Also, the parametric binary approximating schemes and their inspections are presented in (Asghar & Mustafa, Citation2019; Daniel & Shunmugaraj, Citation2010; Rehan & Siddiqi, Citation2015; Siddiqi & Rehan, Citation2010; Citation2011).

In this paper, we present a novel method which merges two non-parametric binary refinement schemes to get a new parametric binary approximating refinement schemes called the design-control binary approximating refinement scheme. The schemes which are used in the construction process have equal complexity, but have different geometric behavior. Hence, the new scheme gives the geometric flexibility. Moreover, it contains the geometric behavior of both parent schemes as those are the special cases of the new design-control scheme.

The remainder of this research is organized as follows. In Section 2, we present some basic notations and results. In Section 3, the framework for the construction of the design-control binary refinement scheme is presented. In Section 4, we study the local control property of the design-control refinement scheme. We discuss the smoothness analysis of new refinement scheme in Section 5. And then, we give the Gibbs phenomena analysis of our refinement scheme in Section 6. Finally, summary and conclusions are given in Section 7.

2. Basic notation and results

A uni-variate linear binary refinement scheme Sa is based on repeated (successive) application of the refinement rules. Which are used to map a polygon Pk={Pik}iZl(Z) to a refined polygon Pk+1={Pik+1}iZl(Z). The general compact form of these refinement rules is defined as: (2.1) P2i+ξk+1=jZa2j+ξPi+jk, ξ=0,1,(2.1) where l(Z) denotes the space of scaler-valued sequences. The sequence a={aj}jZ is called the refinement mask. Therefore, the polynomial which uses this mask as coefficients is called the Laurent polynomial. In addition, the Laurent polynomial corresponding to refinement scheme Equation(2.1) is: a(z)=jZa2jz2j+jZa2j+1z2j+1.

The necessary condition for the convergence of a binary refinement scheme are: (2.2) jZa2j=1,jZa2j+1=1.(2.2)

Which is equivalent to the following relations; (2.3) a(1)=2 and a(1)=0.(2.3)

Definition 2.1.

A linear refinement scheme is called approximating refinement scheme if it can be written as: P2ik+1=iZa2jPijk,P2i+1k+1=iZa2j+1Pijk.

This type of refinement schemes generates the limiting curves in which the control points Pjk of k-th polygon level are not included in the points of the (k+1)-th polygon level.

Definition 2.2.

Convergence analysis by Eigenvalues method

We seek the complete demonstration about the necessary and sufficient conditions for uniform convergence of the refinement scheme. This analysis was firstly introduced by Doo and Sabin (Doo & Sabin, Citation1978), and then developed through the years (see for example (Xumin, Xiaojun, Xianpeng, & Cailing, Citation2013; Thorne, Citation2021)). As a matter of fact, the matrix formalism is the technique for derive the necessary conditions for a scheme to be Ck, it based mainly on the eigenvalues of the subdivision matrix.

Let the eigenvalues of the n×n subdivision matrix be {λi:i=0,1,2,n1}, where λ0=1 and |λi||λi+1|,iN. And we have the necessary conditions for the following properties:

  • 1: |λ1|=|λ2| shows kink, i.e. not C1.

  • 2: λ12<λ2 shows unbounded curvature.

  • 3: λ12=|λ2|=|λ3| shows mildly diverging curvature.

  • 4: λ12=|λ2|>|λ3| shows curvature bounded.

  • 5: λ12>|λ2| shows curvature to zero.

Theorem 2.1.

Let the matrix formalism to derive the necessary conditions for a scheme to be Ck based on the eigenvalues of the subdivision matrix. If the limiting curve is C2 continuity, the eigenvalues {λi} satisfy (Hassan, Ivrissimitzis, Dodgson, & Sabin, Citation2002): λ0=1,|λi|>|λi+1|,iN, and λ12=|λ2|>|λ3|.

And a scheme will be uniformly convergent if and only if there is an integer L1 such that 12SamL <1.

Theorem 2.2.

Let the refinement scheme Sa with mask a={ai} where iZ satisfying the condition (Dyn & Levin, Citation2002) (2.4) iZa2i=iZa2i+1=1.(2.4)

If there exist an integer L1, such that (12Sam)L1, then the refinement scheme Sa is Cn-continuous, where (12Sam)L=max{jZ|bi2Lj[m,L]|:0i2L1}, and Laurent polynomial b[m,L](z)=b(z)b(z2)b(z2L1), so, b(z)=12am(z). When L=1, (12Sam)=12max{iZa2i,iZa2i+1}.

Let am(z)=(2z1+z)ma(z) with Sb is contractive. Then Sa is also convergent with Cn-continuous.

Theorem 2.3.

Given 0ψh, let g be a function defined by (Amat, Ruiz, & Trillo, Citation2018) g(x)=g(x),gCn(],ψ]),xψ,g(x)=g(x),g+Cn(]ψ,+]),xψ, with n2 and g(ψ)>g+(ψ). Let Sa be a uni-variate stationary refinement scheme with condition: ζl(i)[k]={τia2[k]τ+li<0,0,i=0,τia2[k]τ+li>0, where a[k] define as: aj[k]=iZai[k1]aj2i, and 0l<2k. Then, if ζl(i)0,i,k; and if h is sufficiently small, we have the following two conditions:

P 1. If |x|max{|M12|,|M+N2+1|}h, then |g(x)(Sagh)(x)|=O(hn), with n2.

P 2. If |x|max{|M12|,|M+N2+1|}h, there exists βh=O(h) such that: g1,hβhg+(h)βh(Sagh)(x)g(0)+βh=g0,h+βh.

3. Construction structure of the new 6-point design-control refinement scheme

In this section, we describe the construction process of the new design-control binary approximating refinement scheme. The new scheme contains three design-control parameters which control the behavior of the limit curves. Therefore, the step by step procedure of the construction is given below:

3.1. Step 1

In this step, we take two already published binary approximating refinement schemes.

Firstly, the 4-point approximating refinement scheme which was presented by (Deslauriers & Dubuc, Citation1989; Mustafa & Rehman, Citation2010) is (3.1) {Q2ik+1=7128Pi1k+105128Pik+35128Pi+1k5128Pi+2k,Q2i+1k+1=5128Pi1k+35128Pik+105128Pi+1k7128Pi+2k,(3.1) where {Qjk+1:j=0,1,,2n+1} are the refined points of the subdivided polygon by scheme Equation(3.1) if {Pjk:j=0,1,,n} are the given points of the given polygon.

Secondly, the 4-point approximating B-spline refinement scheme which is constructed by B-spline basis function of degree-6 is (3.2) {R2ik+1=764Pi1k+3564Pik+2164Pi+1k+164Pi+2k,R2i+1k+1=164Pi1k+2164Pik+3564Pi+1k+764Pi+2k,(3.2) where {Rjk+1:j=0,1,,2n+1} are the refined points of the subdivided polygon by scheme Equation(3.2) if {Pjk:j=0,1,,n} are the given points of the given polygon.

3.2. Step 2

In this step, firstly we define two displacement vectors. The first displacement vector is denoted by D2ik+1 and is shown in . We get this vector by subtracting refinement point R2ik+1 defined in Equation(3.2) from the refinement point Q2ik+1 defined in Equation(3.1). That is D2ik+1=Q2ik+1R2ik+1.

Figure 1. Vectors D2ik+1 and D2i+1k+1.

Figure 1. Vectors D2ik+1 and D2i+1k+1.

Similarly, we get the second displacement vector D2i+1k+1 which is shown in by subtracting refitment point R2i+1k+1 defined in Equation(3.2) from the refinement point Q2i+1k+1 defined in Equation(3.1) D2i+1k+1=Q2i+1k+1R2i+1k+1.

Hence the displacement vectors can be expressed in the linear combination of the given control points {Pjk:j=0,1,,n}. That is (3.3) {D2ik+1=21128Pi1k+35128Pik7128Pi+1k7128Pi+2k,D2i+1k+1=7128Pi1k7128Pik+35128Pi+1k21128Pi+2k.(3.3)

If we increase/decrease the indices of refinement equations defined in Equation(3.1)–(3.2) and define four more displacement vectors in same manner, we get (3.4) {D2i2k+1=21128Pi2k+35128Pi1k7128Pik7128Pi+1k,D2i1k+1=7128Pi2k7128Pi1k+35128Pik21128Pi+1k,D2i+2k+1=21128Pik+35128Pi+1k7128Pi+2k7128Pi+3k,D2i+3k+1=7128Pik7128Pi+1k+35128Pi+2k21128Pi+3k.(3.4)

3.3. Step 3

In this step, we use the properties of “vector addition” and “scalar multiplication” to get the resultant vectors. We use the six vectors defined in Equation(3.3)–(3.4) along with three scalars μ ν and ω R. Hence we get two resultant vectors denote by: DE and DO and they defined below: (3.5) {QE=μD2i2k+1+νD2ik+1+ωD2i+2k+1,DO=ωD2i1k+1+νD2i+1k+1+μD2i+3k+1.(3.5)

3.4. Step 4

In this step, we calculate refinement rules of the new 6-point approximating refinement scheme by translating the refinement points of scheme Equation(3.1). For the translation of these points we use the resultant vectors DE and DO which are defined in Equation(3.5). Hence the first refinement rule is: P2ik+1=Q2ik+1QE.

Similarly, the second refinement rule is: P2i+1k+1=Q2i+1k+1QO.

Thus, the new design-control approximating scheme is: (3.6) {P2ik+1=a5Pi2k+a3Pi1k+a1Pik+a1Pi+1k+a3Pi+2k+a5Pi+3k,P2i+1k+1=a6Pi2k+a4Pi1k+a2Pik+a0Pi+1k+a2Pi+2k+a4Pi+3k,(3.6) where, a5=a4=21128μ, a3=a2=712835128μ+21128ν,a1=a0=105128+7128μ35128ν+21128ω,a1=a2=35128+7128μ+7128ν35128ω,a3=a4=5128+7128ν+7128ω, a5=a6=7128ω.

Here, P2ik+1 and P2i+1k+1 are points at (k+1)-th refinement level, whereas μ, ν and ω are the scalars used as design-control parameters. Thus the sequence {,0,0,a6,a5,a4,a3,a2, a1,a0,a1,a2,a3,a4,0,0,} is the mask of the scheme Equation(3.6). The new 6-point approximating refinement scheme is denoted by Sa,μ,ν,ω.

If we put i=2,1,0,1,2 in the pair of refinement Equationequation (3.6), then we get a system of refinement equations. Which can be written in a matrix form as: (P4k+1P3k+1P2k+1P1k+1P0k+1P1k+1P2k+1P3k+1P4k+1P5k+1) =(a5a3a1a1a3a50000a6a4a2a0a2a400000a5a3a1a1a3a50000a6a4a2a0a2a400000a5a3a1a1a3a50000a6a4a2a0a2a400000a5a3a2a1a3a50000a6a4a2a0a2a400000a5a3a1a1a3a50000a6a4a2a0a2a4)(P4kP3kP2kP1kP0kP1kP2kP3kP4kP5k).

Then, the mask of refinement scheme Sa,μ,ν,ω defined in Equation(3.6) is a={,0,0,7128ω,21128μ,5128+7128ν+7128ω,712835128μ+21128ν,35128+7128μ+7128ν35128ω,105128+7128μ35128ν+21128ω,105128+7128μ35128ν+21128ω,35128+7128μ+7128ν35128ω,712835128μ+21128ν,5128+7128ν+7128ω,21128μ,7128ω,0,0,}.

Remark 3.1.

In this article, we use the “sub-scheme” word for the refinement scheme which is the special case of our refinement scheme Sa,μ,ν,ω defined in Equation(3.6).

3.5. Sub-scheme St,ν of the refinement scheme Sa,μ,ν,ω

In this section, we present the sub-scheme, with design-control parameter ν, of scheme Sa,μ,ν,ω that is defined in Equation(3.6). We set μ=ω=0 in Equation(3.6) to get the following sub-scheme of scheme Sa,μ,ν,ω (3.7) {P2ik+1=t3Pi1k+t1Pik+t1Pi+1k+t3Pi+2k,P2i+1k+1=t4Pi1k+t2Pik+t0Pi+1k+t2Pi+2k,(3.7) where t3=t2=7128+21128ν, t1=t0=10512835128ν,t1=t2=35128+7128ν, t3=t4=5128+7128ν.

Where, the mask of above scheme is {,0,0,t4,t3,t2,t1,t0,t1,t2,t3,0,0,}. Hence, the mask of corresponding refinement scheme St,ν is, t={,0,0,5128+7128ν,7128+21128ν,35128+7128ν,10512835128ν,10512835128ν,35128+7128ν,7128+21128ν,5128+7128ν,0,0,}.

Remark 3.2.

For the scheme St,ν, the vectors defined in Equation(3.5) reduce to QE=νD2ik+1 and DO=νD2i+1k+1.

3.6. Sub-scheme Sℓ,μ of the refinement scheme Sa,μ,ν,ω

In this section, we give the sub-scheme with design-control parameter μ of scheme Sa,μ,ν,ω defined in Equation(3.6). We set μ=ω and ν=2μ+1 in Equation(3.6) then, to get the following scheme denotes by S,μ (3.8) {P2ik+1=5Pi2k+3Pi1k+1Pik+1Pi+1k+3Pi+2k+5Pi+3k,P2i+1k+1=6Pi2k+4Pi1k+2Pik+0Pi+1k+2Pi+2k+4Pi+3k,(3.8) where, 5=4=21128μ, 3=2=76477128μ, 1=0=3564+4964μ,1=2=21642164μ, 3=4=1647128μ, 5=6=7128μ, with {,0,0,6,5,4,3,2,1,0,1,2,3,4,5,0,0,} is the mask of this refinement scheme. Thus, the mask of corresponding refinement scheme S,μ is, ={,0,0,7128μ,21128μ,1647128μ,76477128μ,21642164μ,3564+4964μ,3564+4964μ,21642164μ,76477128μ,1647128μ,21128μ,7128μ,0,0,}.

Remark 3.3.

For the scheme S,μ, the vectors which are defined in Equation(3.5) take the following form: QE=D2ik+1+μ[(D2i2k+1D2ik+1)+(D2i+2k+1D2ik+1)],DO=D2i+1k+1+μ[(D2i1k+1D2i+1k+1)+(D2i+3k+1D2i+1k+1)].

3.7. Refinement rules for boundary points when the given polygon is open

Here, we discuss the refinement rules for the open polygon of our new approximating refinement scheme Sa,μ,ν,ω. Whenever, we have to smooth an open polygon, we use a specific relations which replace the unknowns point with known points to get the refinement rules for boundary points of our refinement scheme.

Let the indices of the given points be Pjk: j=0,1,,n as shown in . Hence, the point Pjk: j<0 and Pjk: j>n are unknowns. So, first we use the following relation to find out the unknown points Pjk: j<0. (3.9) Pmk=2P0kPmk, where  m=1,2.(3.9)

Figure 2. Sketch of open polygon.

Figure 2. Sketch of open polygon.

Then, we use the following relation to replace the unknown points Pjk: j>n with the known points Pjk: j=0,1,,n. And then, (3.10) Pn+mk=2PnkPnmk,  where m=1,2,3.(3.10)

Hence, the boundary refinement points for the open polygons are: P0k+1=1128[(21μ+7ν+21ω+91)P0k+(42+42μ14ν35ω)P1k+(21μ+7ν+7ω5)P2k+7ωP3k], P1k+1=1128[(7μ+21ν7ω+25)P0k+(7μ42ν+14ω+110)P1k+(35μ+21ν7ω7)P2k+21μP3k], P2k+1=1128[(7μ+21ν7)P0k+(14μ35ν+21ω+105)P1k+(7μ+7ν35ω+35)P2k+(7ν+7ω5)P3k+7ωP4k], P3k+1=1128[(7ν+21ω5)P0k+(7μ+7ν42ω+35)P1k+(7μ35ν+21ω+105)P2k+(35μ+21ν7)P3k+21μP4k], P2n4k+1=1128[21μPn4k+(35μ+21ν7)Pn3k+(7μ35ν+21ω+105)Pn2k+(7μ+7ν42ω+35)Pn1k+(7ν+7ω5)Pnk], P2n3k+1=1128[7ωPn4k+(7ν+7ω5)Pn3k+(7μ+7ν35ω+35)×Pn2k+(14μ35ν+21ω+105)Pn1k+(7μ+21ν7)Pnk], P2n2k+1=1128[21μPn3k+(35μ+21ν7ω7)Pn2k+(7μ42ν+14ω+110)Pn1k+(7μ+21ν7ω+25)Pnk], P2n1k+1=1128[7ωPn3k+(21μ+7ν+7ω5)Pn2k+(42μ+14ν35ω+14)Pn1k+(21μ+7ν+21ω+91)Pnk], P2nk+1=1128[7μPn3k+(21μ7ν7ω+5)Pn2k+(42μ42ν+35ω42)Pn1k+(21μ7ν21ω+165)Pnk], P2n+1k+1=1128[21μPn3k+(35μ21ν+7ω+7)Pn2k+(7μ+42ν14ω110)Pn1k+(7μ21ν+7ω+231)Pnk].

4. Support of design-control refinement scheme

In this section, we analyze the support of our design-control refinement scheme. The support of our refinement scheme shows that how better it locally controls the limiting curves. The support of our refinement scheme is small, hence our scheme has better local control on shapes. We calculate the support of our refinement scheme Sa,μ,ν,ω and its sub-schemes St,ν and S,μ which are defined in Equation(3.6), Equation(3.7) and Equation(3.8) respectively. The support of these schemes is analyzed theoretically and graphically as follows.

Lemma 4.1.

If we use refinement scheme Sa,μ,ν,ω on initial data (4.1) Pi0={1i=0,0i0.(4.1)

Then, after first subdivision step the non-zero points are P61, P51, , P41, P51.

Proof.

If we use i=4 and k=0 in Equation(3.6), we get P81=a5P60+a3P50+a1P40+a1P30+a3P20+a5P10,=a5(0)+a3(0)+a1(0)+a1(0)+a3(0)+a5(0)=0, and P71=a6P60+a4P50+a2P40+a0P30+a2P20+a4P10,=a6(0)+a4(0)+a2(0)+a0(0)+a2(0)+a4(0)=0.

If we put i=3 and k=0 in Equation(3.6), we get P61=a5P50+a3P40+a1P30+a1P20+a3P10+a5P00,=a5(0)+a3(0)+a1(0)+a1(0)+a3(0)+a5(1)=a5,=7128ω, and P51=a6P50+a4P40+a2P30+a0P20+a2P10+a4P00,=a6(0)+a4(0)+a2(0)+a0(0)+a2(0)+a4(1)=a4,=21128μ.

If we substitute Equation(3.6) by i=2 and k=0, we get P41=a5P40+a3P30+a1P20+a1P10+a3P00+a5P10,=a5(0)+a3(0)+a1(0)+a1(0)+a3(1)+a5(0)=a3,=5128+7128ν+7128ω, and P31=a6P40+a4P30+a2P20+a0P10+a2P00+a4P10,=a6(0)+a4(0)+a2(0)+a0(0)+a2(1)+a4(0)=a2,=712835128μ+21128ν.

For i=1 and k=0 in Equation(3.6), we get P21=a5P30+a3P20+a1P10+a1P00+a3P10+a5P20,=a5(0)+a3(0)+a1(0)+a1(1)+a3(0)+a5(0)=a1,=35128+7128μ+7128ν35128ω, and P11=a6P30+a4P20+a2P10+a0P00+a2P10+a4P20,=a6(0)+a4(0)+a2(0)+a0(1)+a2(0)+a4(0)=a0,=105128+7128μ35128ν+21128ω.

If we put i=0 and k=0 in Equation(3.6), we get P01=a5P20+a3P10+a1P00+a1P10+a3P20+a5P30,=a5(0)+a3(0)+a1(1)+a1(0)+a3(0)+a5(0)=a1,=105128+7128μ35128ν+21128ω, and P11=a6P20+a4P10+a2P00+a0P10+a2P20+a4P30,=a6(0)+a4(0)+a2(1)+a0(0)+a2(0)+a4(0)=a2,=35128+7128μ+7128ν35128ω.

If we put i=1 and k=0 in Equation(3.6), we get P21=a5P10+a3P00+a1P10+a1P20+a3P30+a5P40,=a5(0)+a3(1)+a1(0)+a1(0)+a3(0)+a5(0)=a3,=712835128μ+21128ν, and P31=a6P10+a4P00+a2P10+a0P20+a2P30+a4P40,=a6(0)+a4(1)+a2(0)+a0(0)+a2(0)+a4(0)=a4,=5128+7128ν+7128ω.

If we use i=2 and k=0 in Equation(3.6), we get P41=a5P00+a3P10+a1P20+a1P30+a3P40+a5P50,=a5(1)+a3(0)+a1(0)+a1(0)+a3(0)+a5(0)=a5,=21128μ, and P51=a6P00+a4P10+a2P20+a0P30+a2P40+a4P50,=a6(1)+a4(0)+a2(0)+a0(0)+a2(0)+a4(0)=a6,=7128ω.

If we use i=3 and k=0 in Equation(3.6), we get P61=a5P10+a3P20+a1P30+a1P40+a3P50+a5P60,=a5(0)+a3(0)+a1(0)+a1(0)+a3(0)+a5(0)=0, and P71=a6P10+a4P20+a2P30+a0P40+a2P50+a4P60,=a6(0)+a4(0)+a2(0)+a0(0)+a2(0)+a4(0)=0.

Hence, if we use the design-control refinement scheme Sa,μ,ν,ω defined in Equation(3.6) on the given initial data Equation(4.1), then after first subdivision step the non-zero points are P61, P51, …, P41 and P51.

Lemma 4.2.

If we use refinement scheme Sa,μ,ν,ω on initial data Pi0={1i=0,0i0.

Then, after second subdivision step, the non-zero points are P182, P172, , P142, P152.

Lemma 4.3.

If we use refinement scheme Sa,μ,ν,ω on initial data Pi0={1i=0,0i0.

Then, after third subdivision step, the non-zero points are P423, P413, , P343, P353.

Theorem 4.4.

The support width of our binary refinement scheme Sa,μ,ν,ω defined in Equation(3.6) is 11. So, it vanishes outside the closed interval [−5.5,5.5].

Proof.

In order to prove the above result, we use the results of Lemmas 4.1, 4.2 and 4.3. Let us define a set Fk={j2k:  jZ}, such that ϕ(j2k)=Pjk  jZ.

By Lemma 4.1, we get that: if we use one subdivision step on initial data by our design-control refinement scheme, the leftmost non-zero point is P61=ϕ(62), and the rightmost non-zero point is P51=ϕ(52).

By Lemma 4.2, we get that: if we use two subdivision steps on initial data by refinement scheme Sa,μ,ν,ω, the leftmost non-zero point is P182=P6(1+2)3=ϕ(6(1+2)22), and the rightmost non-zero point is P152=P5(1+2)3=ϕ(5(1+2)22).

Similarly, from Lemma 4.3, we get that: if we use three subdivision steps on initial data by scheme Sa,μ,ν,ω, the leftmost non-zero point is P423=P6(1+2+22)3=ϕ(6(1+2+22)23), and the rightmost non-zero point is P353=P5(1+2+22)3=ϕ(5(1+2+22)23).

If we continue this process, then after k subdivision steps, the leftmost non-zero point is P6(1+2+222k1)k=ϕ(6(1+2+222k1)2k), and the rightmost non-zero point is P5(1+2+222k1)k=ϕ(5(1+2+222k1)2k).

The difference between left and right non-zero points at k-th subdivision steps is Difference=[5(1+2+222k1)2k6(1+2+222k1)2k]=[5(1+2+222k1)2k+6(1+2+222k1)2k]=[(5+6)(1+2+222k12k)]=[11(12+122+..+12k)].

If k, we get the support width of refinement scheme Sa,μ,ν,ω Support Width=limk[11(12+122+..+12k)]=11[12112]=11.

Hence, the support width of our refinement scheme Sa,μ,ν,ω is 11. So, it vanishes outside the closed interval [−5.5, 5.5]. □

Corollary 4.5.

The support width of our refinement scheme St,ν is 7. So, it vanishes outside the closed interval [−3.5, 3.5].

Proof.

The proof of this corollary is trivial, because St,ν is a sub-scheme of scheme Sa,μ,ν,ω and it is obtained by putting μ=ω=0 in Equation(3.6). □

Corollary 4.6.

The support width of our refinement scheme S,μ is 11. So, it vanishes outside the closed interval [−5.5, 5.5].

Proof.

The proof of this corollary is also trivial, because S,μ is a sub-scheme of scheme Sa,μ,ν,ω and it is obtained by putting μ=ω and ν=12μ in Equation(3.6). □

Now, we analyze the support of our refinement scheme graphically.

Experiment 4.1.

In this experiment, we plot an initial sketch by using data points (7,0), (6,0), (5,0), (4,0), (3,0), (2,0), (1,0), (0,1), (1,0), (2,0), (3,0), (4,0), (5,0), (6,0), (7,0). The curves generated by our refinement scheme Sa,μ,ν,ω are shown in . show the curves fitted by our refinement scheme after first, second and third refinement steps respectively. Here, the values of parameters are (μ,ν,ω)=(0.1,1.2,0.1).

Figure 3. Black solid lines and red bullets represent initial control polygons and initial control points respectively. Blue solid lines represent curves fitted by our refinement scheme after first, second and third subdivision steps respectively.

Figure 3. Black solid lines and red bullets represent initial control polygons and initial control points respectively. Blue solid lines represent curves fitted by our refinement scheme after first, second and third subdivision steps respectively.

Experiment 4.2.

In this experiment, we draw initial sketch by using the following initial control points (5,15), (5,7), (2,7), (2,6), (1,6), (1,4), (2,4), (2,3), (5,3), (5,4), (6,4), (6,11), (11,11), (11,16), (8,6), (8,5), (7,5), (7,3), (8,3), (8,2), (11,2), (11,3), (12,3), (12,15), (5,15). The black dashed-dotted lines in represent the initial sketch. While, red curve in is the curve fitted by our scheme after three refinement steps. Now we draw another initial sketch by changing the position of one point of the sketch which is shown in . The new sketch is shown in by black dashed-dotted lines. Which is simply obtained by moving point (8.5,11) of previous sketch to the new position (8.5,7). shows the curve fitted by our scheme after three refinement steps. Here, the values of parameters are: (μ,ν,ω)=(0,1,0). By comparing , we conclude that by moving one control point of the initial sketch, only a very small portion of limit curve is affected. This property shows that our refinement scheme has a good local control.

Figure 4. Local control property of new design-control refinement scheme.

Figure 4. Local control property of new design-control refinement scheme.

5. Continuity analysis of new design control refinement scheme

In this section, we present the convergence and smoothness analysis of the sub-schemes St,ν and S,μ of new design-control refinement scheme. For the analysis, we use the theoretical results of (Hassan et al., Citation2002) and (Dyn & Levin, Citation2002) which are given in Theorem 2.1 and Theorem 2.2 respectively.

5.1. Continuity analysis of refinement scheme St,ν

Here, we analyzed the convergence of binary approximating refinement scheme St,ν by using Eigenvalues of the subdivision matrix. We also check the level of smoothness of our proposed scheme by using the Laurent polynomial method for L=1 and L=2.

Theorem 5.1.

The refinement scheme Equation(3.7) satisfies the necessary conditions for C2 continuity if the range of the tension parameter is 0.7142857143<ν<1.857142857.

Proof.

To find the convergence of the refinement scheme St,ν which is defined in Equation(3.7), consider the local subdivision matrix T of the scheme St,ν. If we put i=1,0,1 in the pair of refinement Equationequations (3.7), then we get a system of refinement equations. Which can be written in matrix form as: P¯k+1=TP¯k, where, P¯k+1=[P2k+1 P1k+1 P0k+1 P1k+1 P2k+1]T, P¯k=[P2k P1k P0k P1k P2k]T and T=(t3t1t1t300t4t2t0t2000t3t1t1t300t4t2t0t2000t3t1t1t300t4t2t0t2), the eigenvalues of the subdivision matrix T are: λ0=1,λ1=12,λ2=14,λ3=18,λ4=116,λ5=964764ν.

From Theorem 2.1, the necessary conditions for C2-continuity are: (5.1) λ0=1, |λi||λi+1| iN and |λ1|2=|λ2|>|λ3|.(5.1)

Now, by putting i=4 in Equation(5.5), and compare the values |116|>|964764ν|.

After simplification we get: 57<ν<137.

Thus, we have 0.7142857143<ν<1.857142857.

Which, implies that the given scheme is convergent in this interval 0.7142857143<ν<1.857142857.

Theorem 5.2.

The binary refinement scheme Equation(3.7) satisfies the sufficient conditions of C2-continuity for 0.7142857143<ν<1.857142857.

Proof.

The Laurent polynomial of refinement scheme Equation(3.7) is (5.2) t(z)=(5128+7128ν)z3+(7128+21128ν)z2+(35128+7128β)z1+(10512835128ν)z0+(10512835128ν)z1+(35128+7128ν)z2+(7128+21128ν)z3+(5128+7128ν)z4.(5.2)

By Theorem 2.2. (5.3) b[m,L](z)=12Ltm[L](z),m=1,2,(5.3) where, tm(z)=2z1+ztm1(z)=(2z1+z)mt(z), and, tm[L](z)=j=0L1tm(z2j). (5.4) (12Stm)L=max{j|bγ+2Lj[m,L]|;γ=0,1,,2L1}<1, m=1,2,3.(5.4)

Now, by putting L=1 and m=1 in Equation(5.3), we get: b11(z)=12t1(z)=zz+1t(z)=(7128ν5128)z4+(764ν164)z3+(7128ν+37128)z2+(732ν+1732)z1+(7128ν+37128)z0+(764ν164)z1+(7128ν5128)z2.

This implies that (12St1)1=max{|7128ν5128|+|7128ν+37128|+|7128ν+37128|+|7128ν5128|,|764ν164|+|732ν+1732|+|764ν164|}<1.

The above relation is true if ν lies between 0.7142857143 to 1.857142857. Hence the scheme is C0-continuous. If we put L=1 and m=2 in Equation(5.3), then, we obtain b21(z)=12t2(z)=2z2(z+1)2t(z)=(764ν564)z4+(764ν+364)z3+(732ν+1732)z2+(732ν+1732)z1+(764ν+364)z0+(764ν564)z1.

This implies that 12St2=max{|764ν564|+|732ν+1732|+|764ν+364|,|732ν+1732|+|764ν564|}<1.

Hence, this scheme is C1-continuous for 0.7142857143<ν<1.857142857.

Now we substitute L=1 and m=3 in Equation(5.3), we get b31(z)=12t3(z)=4z3(z+1)3t(z)=(732ν532)z4+(14)z3+(716ν+1316)z2+(14)z1+(732ν532)z0.

This implies that 12St3=max{|732ν532|+|716ν+1316|+|732ν532|,|14|+|14|}<1.

Thus the scheme is C2 -continuous for 0.7142857143<ν<1.857142857.

In , we present the continuity results of our refinement scheme St,ν by Laurent polynomial method, that we have obtained by using results of Theorem 2.2.

Table 1. The order of smoothness of the refinement scheme St,ν for specific range of parameter.

5.2. Continuity analysis of the refinement scheme S,μ

In this section, we analyzed the convergence of binary approximating refinement scheme S,μ by analyzing the eigenvalues of the subdivision matrix. We also check the level of smoothness of our proposed scheme by using the Laurent polynomial method for L=1 and L=2.

Theorem 5.3.

The refinement scheme Equation(3.8) satisfies the necessary conditions for C2 continuity if the range of the tension parameter is 0.1428571429<μ<0.06578510188.

Proof.

To find the convergence of the refinement scheme S,μ, defined in Equation(3.8), consider the local subdivision matrix T¯ of the scheme S,μ. If we put i=2,1,0,1,2 in the pair of refinement Equationequations (3.8), then we get a system of refinement equations. Which can be written in matrix form as: P̂k+1=T¯P̂k, where P̂k+1=[P3k+1 P2k+1 P1k+1 P0k+1 P1k+1 P2k+1 P3k+1]T, P̂k=[P3k P2k P1k P0k P1k P2k P3k]T and, T¯=(5311350000642024000005311350000642024000005311350000642024000005311350000642024000005311350000642024).

The eigenvalue of the above subdivision matrix are: λ0=1,λ1=12,λ2=14,λ3=18,λ4=116,λ5=132,λ6=164,λ6=164,λ7=732μ,λ8=7128μ+1128+1128833μ2+70μ+1,λ9=7128μ+11281128833μ2+70μ+1.

From Theorem 2.1, the necessary conditions for C2-continuity are: (5.5) λ0=1, |λi||λi+1| iN and |λ1|2=|λ2|>|λ3|.(5.5)

Let |164|>|732μ|.

This implies that 114<μ<114.

Thus, we have (5.6) 0.071429<μ<0.071429.(5.6)

Let, |732μ|>|7128μ+1128+1128833μ2+70μ+1|.

This, implies that 1.290803377<μ<0.06578510188 and0.01824851156<μ<0.7193748053.

By combining the above we get result as: (5.7) 1.290803377<μ<0.7193748053.(5.7)

Let, |7128μ+1128+1128833μ2+70μ+1|>|7128μ+11281128833μ2+70μ+1|.

This, implies that 0.1428571429<μ<0.06578510188 and 0.01824851156<μ.

By combining above we get the result (5.8) 0.1428571429<μ<0.06578510188.(5.8)

If we take the common part of all inequalities Equation(5.6), Equation(5.7) and Equation(5.8), we get the following common interval (5.9) 0.1428571429<μ<0.06578510188.(5.9)

Theorem 5.4.

The refinement scheme Equation(3.8) satisfies the sufficient conditions for C2-smoothness for 0.1071428571<μ<0.01824851156.

In , we summarize the continuity results of our refinement scheme S,μ by Laurent polynomial method which we have obtained by using results of Theorem 2.2.

Table 2. The order of smoothness of the refinement scheme S,μ for specific range of parameter.

Now, we give an experiment to show the smoothness property of our design-control refinement scheme geometrically.

Experiment 5.1.

In this experiment, we draw the initial control polygon by using there initial control points: (14,4), (12,12), (10,13), (0,13), (16,13), (15,9), (10,9), (6,7), (5,11), (5,12), (7,13), (12,13), (11,16), (4,16), (3,15), (2,13), (2,11), (4,1), (6,9), (0,9), (3,9), (5,1), (8,16), (12,16), (9,1), (7,9), (9,9), (10,4) and (14,4). We show the curve generated by our refinement scheme Sa,μ,ν,ω in . shows the initial control polygon. show the curves fitted by our refinement scheme after one, two and three refinement steps respectively. Where (μ,ν,ω) = (0,1,0).

Figure 5. Smooth curve fitted by our refinement scheme.

Figure 5. Smooth curve fitted by our refinement scheme.

6. Gibbs phenomenon analysis

In this section, we theoretically and graphically analyze the Gibbs phenomenon of sub-schemes St,ν and S,μ. By using the mask of these refinement schemes, we obtain certain conditions to analyze whether there exist a Gibbs phenomenon close to the discontinuous points or not ().

Table 3. Values of ζ0[1](i) and ζ1[1](i) for St,ν.

Theorem 6.1.

The binary approximating refinement scheme St,ν defined in Equation(3.7) does not produce Gibbs oscillation in the limiting curves for 0.7142857ν7.

Proof.

By Theorem 2.3, a stationary scheme is free from Gibbs oscillation near to the discontinuity if (6.1) ζl¯[k](i)0   i,k,(6.1) where, (6.2) ζl¯[k](i)={τia2[k]τ+l¯[k]i<0,0,i=0,τia2[k]τ+l¯[k]i>0,(6.2) and, 0l¯<2k.

Since, the Laurent polynomial of our scheme St,ν is: (6.3) t(z)=j=43tjzj,(6.3)

Therefore, if we fix k=1 and put aj[1]=tj:j=4,3,,3 in Equation(6.2), we get (6.4) ζl¯[1](i)={τit2τ+l¯i<0,0,i=0,τit2τ+l¯i>0.(6.4)

Now, we discuss two different cases corresponding to two values of l¯, namely, l¯=0 and l¯=1.

Case 1:

The value of l¯ in this case is fixed, that is l¯=0. Therefore we have (6.5) ζ0[1](i)={τit2τi<0,0,i=0,τit2τi>0.(6.5)

If we use i=2 in Equation(6.5), we get (6.6) ζ0[1](2)=τ2t2τ=t4+t6+t8+=t4.(6.6)

From Equation(6.1), the following relation is required ζ0[1](2)0.

This implies that t4=(5128+7128ν)0.

Thus, we have (6.7) ζ0[1](2)0 for ν0.7142857.(6.7)

If we put i=1 in Equation(6.5), we get (6.8) ζ0[1](1)=τ1t2τ=t2+t4+t6+=t2+t4.(6.8)

From Equation(6.1), the following relation is required ζ0[1](1)0.

This implies that t2+t4=(35128+7128ν)+(5128+7128ν),=(30128+14128ν)0.

Thus, we have (6.9) ζ0[1](1)0 for ν2.142857143.(6.9)

If we put i=0 in Equation(6.5), we get (6.10) ζ0[1](0)=0 forall ν.(6.10)

If we substitute i=1 in Equation(6.5), we get (6.11) ζ0[1](1)=τ1t2τ=t2+t4+t6+=t2.(6.11)

From Equation(6.1), the following relation is required ζ0[1](1)0.

This implies that t2=(7128+21128ν)0.

Thus, we have (6.12) ζ0[1](1)0 for 0.3333333ν.(6.12)

By Combining Equation(6.7), Equation(6.9) and Equation(6.12), we get the following result ζ0[1](2),ζ0[1](1),ζ0[1](0),ζ0[1](1)0 for 0.7142857ν7.

Case 2:

The value of l¯ in this case is fixed, that is l¯=1. Therefore we have (6.13) ζ1[1](i)={τit2τ+1i<0,0,i=0,τit2τ+1i>0.(6.13)

If we substitute i=2 in Equation(6.13), we get (6.14) ζ1[1](2)=τ2t2τ+1=t3+t5+t7+=t3.(6.14)

From Equation(6.1), the following relation is required ζ1[1](2)0.

This, implies that t3=(7128+21128ν)0.

Thus, we have (6.15) ζ1[1](2)0 for 0.3333333ν.(6.15)

Now, if we put i=1 in Equation(6.13), we get (6.16) ζ1[1](1)=τ1t2τ+1=t1+t3+t5+=t1+t3.(6.16)

From Equation(6.1), the following relation is required ζ1[1](1)0.

This implies that t1+t3=(7128+21128ν)+(10512835128ν),=(4964764ν)0.

Thus, we have (6.17) ζ1[1](1)0 for ν7.(6.17)

Now, we put i=0 in Equation(6.13), we get ζ1[1](0)=0 for μ.

Now, we put i=1 in Equation(6.13), we get (6.18) ζ1[1](1)=τ1t2τ+1=t3+t5+t7+=t3.(6.18)

From Equation(6.1), the following relation is required ζ1[1](1)0.

This implies that t3=(5128+7128ν)0.

Thus, we have (6.19) ζ1[1](1)0 for ν0.7142857.(6.19)

Now, we combine the interval for ν from Equation(6.15), Equation(6.17) and Equation(6.19), we get the following result (6.20) ζ1[1](2),ζ1[1](1),ζ1[1](0),ζ1[1](1)0 for 0.7142857ν7.(6.20)

By Combining (6) and Equation(6.20), we get the common interval 0.7142857ν7 for which our scheme St,ν does not produces Gibbs oscillations. □

Theorem 6.2.

The binary approximating refinement scheme S,μ defined in Equation(3.8) does not produce Gibbs oscillation in limiting shapes for μ=0.

Proof.

We can prove this theorem by adopting the steps of Theorem 6.1. □

Experiment 6.1.

Here, in this experiment, we take the initial data from discontinuous function defined as: (6.21) f(x)={sin(πx),x[0,0.5],sin(πx),x[0.5,1].(6.21)

Function Equation(6.21) provides us the initial data which is given in the and shown in . show the Gibbs oscillation free curves fitted by the scheme St,ν for ν=1 and ν=1.5 respectively.

Figure 6. (a) shows the initial polygon and initial control points (b) and (c) show the curves fitted by our scheme after three subdivision steps.

Figure 6. (a) shows the initial polygon and initial control points (b) and (c) show the curves fitted by our scheme after three subdivision steps.

Table 4. Data of taken from function defined in Equation(6.21).

Experiment 6.2.

In this experiment, we plot an initial sketch by using the data points (2,0), (5,0), (5,2), (6,2), (6,3), (7,3), (7,4), (8,4), (8,3), (10,3), (10,2), (12,2), (12,4), (11,4), (11,5), (10,5), (10,6), (11,6), (11,7), (12,7), (12,8), (13,8), (13,9), (14,9), (14,10), (15,10), (15,11), (16,11), (16,12), (17,12), (17,13), (18,13), (18,16), (15,16), (15,15), (14,15), (14,14), (13,14), (13,13), (12,13), (12,12), (11,12), (11,11), (10,11), (10,10), (9,10), (9,9), (8,9), (8,8), (7,8), (7,9), (6,9), (6,10), (4,10), (4,8), (5,8), (5,6), (6,6), (6,5), (5,5), (5,4), (4,4), (4,3), (2,3) and (2,0). We present the curves generated by our refinement scheme St,ν in . show the smooth and oscillation free curves fitted by our refinement scheme when we set ν=1.2 ν=1.8 and ν=1 respectively.

Figure 7. Black dashed-dotted lines represent initial control polygons. Red lines represent curves fitted by our refinement scheme after three subdivision steps.

Figure 7. Black dashed-dotted lines represent initial control polygons. Red lines represent curves fitted by our refinement scheme after three subdivision steps.

7. Summary and conclusions

The summary of this research is:

  • We construct a binary 6-point approximating refinement scheme by using two existing binary 4-point approximating refinement schemes.

  • The support width of our scheme is 11 and its support region is [5.5,5.5].

  • Our refinement scheme produces limiting curves up to C6 smoothness.

  • If we set the value of parameters in the proved fixed range, our scheme produces curve free from artifacts and Gibbs oscillations.

Hence, we conclude that our scheme is a good choice for curve modeling with small support and high continuity, while the extra benefits can be achieved by using special values of parameters.

Disclosure statement

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Data availability

The data used to support the findings of the study is available within this paper.

References

  • Amat, S., Ruiz, J., & Trillo, C. (2018). Analysis of the Gibbs phenomenon in stationary subdivision scheme. Applied Mathematics Letters, 76, 157–163. doi:10.1016/j.aml.2017.08.014
  • Asghar, M., & Mustafa, G. (2019). A family of binary approximating subdivision schemes based on binomial distribution. Mehran University Research Journal of Engineering & Technology, 38(4), 1087–1100. doi:10.22581/muet1982.1904.20
  • Daniel, S., & Shunmugaraj, P. (2010). An extended three point approximating subdivision scheme, 2010 International Conference On Computer Design and Applications, Qinhuangdao, China, 2, 73–77.
  • Deslauriers, G., & Dubuc, S. (1989). Symmetric iterative interpolation processes. Constructive Approximation, 5(1), 49–68. doi:10.1007/BF01889598
  • Doo, D., & Sabin, M. A. (1978). Behaviour of recursive division surfaces near extraordinary points. Computer Aided Geometric Design, 10(6), 356–360. doi:10.1016/0010-4485(78)90111-2
  • Dyn, N., & Levin, D. (2002). Subdivision schemes in geometric modelling. Acta Numerica, 11, 73–144. doi:10.1017/S0962492902000028
  • Garg, A. (2020). Interactive, computation assisted design tools. Columbia University ProQuest Dissertations Publishing. 28026539.
  • Hameed, R., & Mustafa, G. (2017). Family of a-point b-ary subdivision schemes with bell-shaped mask. Applied Mathematics and Computation, 309, 289–302. doi:10.1016/j.amc.2017.04.013
  • Hassan, M. F., Ivrissimitzis, I. P., Dodgson, N. A., & Sabin, M. A. (2002). An interpolating 4-point C2 ternary stationary subdivision scheme. Computer Aided Geometric Design, 19(1), 1–18.
  • Livesu, M. (2021). Scalable mesh refinement for canonical polygonal schemas of extremely high genus shapes. IEEE Transactions on Visualization and Computer Graphics, 27(1), 254–260. doi:10.1109/TVCG.2020.3010736
  • Livesu, M., Pitzalis, L., & Cherchi, G. (2021). Optimal dual schemes for adaptive grid based hexmeshing. ACM Transactions on Graphics (TOG), 41(2), 1–14. doi:10.1145/3494456
  • Mahalingam, D., & Koneru, S. S. (2020). Constructing an Interpolatory Subdivision Scheme from Doo-Sabin Subdivision, Project Report: MEC-572.
  • Meng, Q. X., Xu, W. Y., Wang, H. L., Zhuang, X. Y., Xie, W. C., & Rabczuk, T. (2020). DigiSim—An open source software package for heterogeneous material modeling based on digital image processing. Advances in Engineering Software, 148, 102836. doi:10.1016/j.advengsoft.2020.102836
  • Mustafa, G., & Rehman, N. A. (2010). The mask of (2b+4)-point n-ary subdivision scheme. Computing, 90, 1–14.
  • Ning, X., Gong, K., Li, W., Zhang, L., Bai, X., & Tian, S. (2020). Feature refinement and filter network for person re-identification. IEEE Transactions on Circuits and Systems for Video Technology, 31(9), 3391–3402. doi:10.1109/TCSVT.2020.3043026
  • Rehan, K., & Siddiqi, S. S. (2015). A combined binary 6-point subdivision scheme. Applied Mathematics and Computation, 270(C), 130–135. doi:10.1016/j.amc.2015.08.030
  • Siddiqi, S. S., & Rehan, K. (2010). Improved binary four point subdivision scheme and new corner cutting scheme. Computers and Mathematics with Applications, 59, 2647–2657. doi:10.1016/j.camwa.2010.01.034
  • Siddiqi, S. S., & Rehan, K. (2011). Curve subdivision schemes for geometric modelling. International Journal of Computer Mathematics, 88(4), 851–863. doi:10.1080/00207160.2010.482987
  • Siddiqi, S. S., & Younis, M. (2013). Construction of m-point binary approximating subdivision schemes. Applied Mathematics Letters, 26(3), 337–343. doi:10.1016/j.aml.2012.09.016
  • Thorne, T. (2021). Computer Graphics 17- Curves and Surfaces 2. cit, 04–11.
  • Xumin, L., Xiaojun, W., Xianpeng, Y., & Cailing, L. (2013). Adaptive Doo-Sabin subdivision algorithm. Journal of Theoretical & Applied Information Technology, 49(1), 311–315.
  • Zhang, L., Wu, J., Wang, T., Borji, A., Wei, G., & Lu, H. (2020). A multistage refinement network for salient object detection. IEEE Transactions on Image Processing, 29, 3534–3545. doi:10.1109/TIP.2019.2962688