# A Convolution-Based Computational Technique for Subdivision Depth of Doo-Sabin Subdivision Surface

Authors: Faheem Khan; Bushra Shakoor; Ghulam Mustafa; Sidra Razaq
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Subdivision surface schemes are used to produce smooth shapes, which are applied for modelling in computer-aided geometric design. In this paper, a new and efficient numerical technique is presented to estimate the error bound and subdivision depth of the uniform Doo-Sabin subdivision scheme. In this technique, first, a result for computing bounds betweenPk (a polygon at kth level) and P∞ (limit surface) of the Doo-Sabin scheme is obtained. After this, subdivision depth (the number of iterations) is computed by using the user-defined error tolerance. In addition, the results of the proposed technique are verified by taking distinct valence numbers of the Doo-Sabin surface scheme.


---

## Body

## 1. Introduction

The subdivision scheme is a powerful tool to design high-quality smooth curves, surfaces, and other geometrical objects. The subdivision scheme gives the rules to create a new polygon by using the vertices as a linear combination of old vertices for each step. Then, repeating the rule leads to a limit curve or surfaces. Recent work has been done on construction and properties of subdivision curves and surfaces by [1, 2]. Many subdivisions can be regarded as schemes for arbitrary topologies, such as 3 subdivision [3], which twice causes a uniform refinement with trisection of every original edge, hence, it is named 3 subdivision scheme.The stencil for the subdivision rule has a minimum size and maximum symmetry. Similarly, much research work for estimating error bounds/subdivision depth has been done, such as Doo-Sabin [4], Catmull-Clark subdivision [5], Loop subdivision [6], 4-8 subdivision [7], quad/triangle subdivision [8, 9], and Butterfly scheme [10, 11]. By given user-defined error tolerance, how many subdivision steps are needed to subdivide the control polygon is called subdivision depth. This error control technique is called subdivision depth computation. It is required in all tessellation-based applications such as subdivision surface trimming, finite element polygon generation, Boolean operators, and surface tessellation for rendering.Some novel numerical techniques are presented to estimate the error bounds and subdivision depths only for binary subdivision curves and surfaces [12–14]. Still, there is space to extend this work to find the error bound/subdivision depth for well-known subdivision schemes for arbitrary topology.It is valuable for precomputing the error bounds and subdivision depth of subdivision curves/surfaces in advance in many engineering applications such as curve/surface intersection, mesh generation, NC machining, and surface rendering [15]. In this paper, we answer the question: how well does the Do-Sabin scheme approximate the initial polygon/polyhedron to the limiting curve/surface? In another way, given an error tolerance, how many levels of subdivision should be performed on the initial polygon/polyhedron so that the error between the resulting control polygon/polyhedron and the limiting curve/surface would be less than the error tolerance? So, an efficient and optimal approach is presented to estimate error bounds and subdivision depth for a uniform Doo-Sabin surface scheme. For a good understanding of the present work, a brief introduction of the Doo-Sabin scheme is presented. The main feature of the paper is to demonstrate the proposed results with the help of some experimental tests on distinct valence numbers of Doo-Sabin surfaces. Graphical representations are also given to illustrate the efficiency of the proposed work. In the end, the conclusion of the work is presented.


## 2. Analysis of Uniform Doo-Sabin Scheme

The uniform biquadratic B-spline is used to construct Doo-Sabin subdivision scheme on arbitrary control grids. The rules for the scheme are an iterative process that takes arbitrary mesh as an input and applies the rules to get a new refined mesh. In this scheme, each vertex of each face at thek-th stage generates a new vertex point of the k+1-th stage as a linear combination of vertices of the same face. For each face, connect the new refined points that have been generated for each vertex of the face to form a new refined n face. Connect the newly obtained points that were generated for the faces adjacent to each vertex to form a valence of n. Finally, connect the new points to obtain the new edges that have been generated for the new faces. The scheme of computation for Doo-Sabin surfaces is shown in Figure 1.Figure 1
Scheme of computation of new face points by using Doo-Sabin subdivision scheme.In the control mesh (or polygon, polyhedron), the number of vertices directly adjacent to a vertex is called the vertex’s valence. If it has a vertex of valence four, it is called a regular; otherwise, it is called an irregular. Similarly, any face with four sides (face valence is four) is regular, otherwise, irregular. In the Doo-Sabin scheme, at each subdivision step, new vertices are generated and then connected to form new faces. After each subdivision, every vertex of a refined polygon will be regular, and the number of irregular faces will remain constant.The subdivision rule of Doo-Sabin scheme can be formalized in a specific way. In this a valencen face in level k with vertices Pik, i=0,1,2,⋯,n−1, after subdivision, a new valence n face with vertices Pik+1, i=0,1,2,⋯,n−1 are computed. Each vertex Pik+1 is a linear combination of the vertex Pik as follows;
(1)Pik+1=∑j=0n−1ωi,juPjk.i=0,1,2,⋯,n−1,where the weights ωi,ju are
(2)ωi,ju=n+54n,ifi=j;3+2cos2j−iπ/n4n,else.The geometrical computation of the scheme (1) is shown in Figure 2, which will help out to find our proposed results.Figure 2
Geometric rules for Doo-Sabin surface for each face.Now, some new iterative points are presented to see the applicability of the scheme (1).From (1) and (2)
(3)P0k+1=∑j=0n−1ω0,juPjk=ω0,0uP0k+ω0,1uP1k+ω0,2uP2k+⋯+ω0,n−1uPn−1k=14+54nP0k+3+2cos2π/n4nP1+3+2cos4π/n4nP2k+⋯+3+2cos2n−1π/n4nPn−1=14+54nP0k+∑j=1n−13+2cos2jπ/n4nPjk.Again using (1) and (2)
(4)P1k+1=∑j=0n−1ω1,juPjk=ω1,0uP0k+ω1,1uP1k+ω1,2uP2k+⋯+ω1,n−1uPn−1k=3+2cos2π/n4nP0k+14+54nP1k+3+2cos2π/n4nP2k+⋯+3+2cos2n−2π/n4nPn−1k=3+2cos2π/n4nP0k+14+54nP1k+∑j=1n−23+2cos2jπ/n4nPj+1k.Similarly(5)P2k+1=∑j=0n−1ω2,juPjk=ω2,0uP0k+ω2,1uP1k+ω2,2uP2k+⋯+ω2,n−1uPn−1k=3+2cos4π/n4nP0k+3+2cos2π/n4nP1k+14+54nP2k+∑j=1n−33+2cos2jπ/n4nPj+2k.Continuing in the same way, we have(6)Pn−1k+1=∑j=0n−1ωn−1,juPjk=∑j=1n−13+2cos2jπ/n4nPj−1k+14+54nPn−1k.


### 2.1. Reformulation of Successive Convolutions

With the use of analysis developed in [13], there are some useful results, which will be used to construct the new technique for Doo-Sabin surfaces scheme in upcoming sections. Now, we move forward and construct associated constants for the Doo-Sabin surface scheme by using successive convolutions for a one-dimensional array of finite length vectors.Lemma 1.
Letu=ui be the vector of finite length and g=gii=0n−2, h=hii=0n−2 with gi=hi=0 for i≥n−1. The convolution product of u=ui, g=gi,i≥0, and h=hj,j≥0 for Doo-Sabin subdivision surface scheme (1) along with (2) is given by
(7)ui,jς0=uς0−1;0∗ghi,j=∑m=0i/2∑l=0j/2um,lς0−1gi−2mhj−2l.
Similarly, we get the following reformulation of generalizedς0−th convolution
(8)ui,jς0=⋯uς0−1;0∗gh∗gh∗⋯∗gh∗ghi,j=∑m=0i/2∑l=0j/2um,l0Cm,iς0,gCl,jς0,h,
where(9)Cm,iς0,g=∑p=2mi/2ς0−1Cm,pς0−1,gCp,iς0−1,g,Cl,jς0,h=∑r=2lj/2ς0−1Cl,sς0−1,hCl,jς0−1,h.Proof.
See in [13].Corollary 2.
The associated constants of aς0-th convolution with vector g=g0,g1,⋯,gn−2 and h=h0,h1,⋯,hn−2 for subdivision surface scheme are defined as
(10)Gς0=maxi∈Σς0,n∑m=0i/2ς0Cm,iς0,(11)Hς0=maxj∈Σς0,n∑l=0j/2ς0Cl,jς0.
Here(12)j∈Σς0,n=Ως0,n−2ς0+1,Ως0,n−2ς0+2,⋯,Ως0,n,
where(13)Ως0,n=2ς0−12n−1.Proof.
See in [13].


### 2.2. Recursion Formula for Uniform Doo-Sabin Subdivision Scheme

In this section, using the subdivision scheme (1) with weights given in (2), the recursion formula For Doo-Sabin subdivision scheme for k+1th level is constructed, which will be used in the main results.Theorem 3.
Given initial control polygonP0=pj0;j∈ℤ and the polygon Pk+1=pjk+1;j∈ℤ,k≥1 be defined recursively by uniform Doo-Sabin subdivision process (1) together with (2). Then, the following inequalities hold for consecutive levels k and k+1(14)Δk+1≤∑j=1n−2gjuΔk,and
(15)Δk+1≤∑j=1n−2hjuΔk.
Where(16)gju=∑l=0jωi,lu−ωi+1,lu,(17)hjj=∑l=0jωn−1,lu−ω0,lu,and
(18)Δk=Pj+1k−Pjk.Proof.
To obtain recursion formula of Uniform Doo-Sabin subdivision with the help from Figure2. First, consider
(i)
Forn=3
The first difference is(19)P1k+1−P0k+1=∑j=02ω1,ju−ω0,juPjk=ω1,0u−ω0,0uP0k+ω1,1u−ω0,1uP1k+ω1,2u−ω0,2uP2k,
By the scheme defined in (1) and (2)
(20)P1k+1−P0k+1=ω0,0u−ω1,0uP1k−P0k+ω0,0u−ω1,0u+ω0,1u−ω1,1uP2k−P1k,this implies
(21)P1k+1−P0k+1=∑j=01∑l=0jω0,lu−ω1,luPj+1k−Pjk.
Now, the second difference is(22)P2k+1−P1k+1=∑j=02ω2,ju−ω1,juPjk=ω2,0u−ω1,0uP0k+ω2,1u−ω1,1uP1k+ω2,2u−ω1,2uP2k=ω1,0u−ω2,0uP1k−P0k+ω1,0u−ω2,0u+ω1,1u−ω2,1uP2k−P1k.
This implies(23)P2k+1−P1k+1=∑j=01∑l=0jω1,lu−ω2,luPj+1k−Pjk.
By the same procedure, the end point difference is(24)P0k+1−P2k+1=∑j=01∑l=0jω0,lu−ω2,luPj+1k−Pjk.(ii)
Forn=4
The difference betweenP1 and P0 at k+1th level is
(25)P1k+1−P0k+1=∑j=03ω1,ju−ω0,juPjk=ω1,0u−ω0,0uP0k+ω1,1u−ω0,1uP1k+ω1,2u−ω0,2uP2k+ω1,3u−ω0,3uP3k,this implies
(26)P1k+1−P0k+1=∑j=02∑l=0jω0,lu−ω1,luPj+1k−Pjk.
Now, the second difference is(27)P2k+1−P1k+1=∑j=03ω2,ju−ω1,juPjk=ω2,0u−ω1,0uP0k+ω2,1u−ω1,1uP1k+ω2,2u−ω1,2uP2k+ω2,3u−ω1,3uP3k,
this implies(28)P2k+1−P1k+1=∑j=02∑l=0jω1,lu−ω2,luPj+1k−Pjk.
Similarly,(29)P3k+1−P2k+1=∑j=03ω3,ju−ω2,juPjk=ω3,0u−ω2,0uP0k+ω3,1u−ω2,1uP1k+ω3,2u−ω2,2uP2k+ω3,3u−ω2,3uP3k,this implies
(30)P3k+1−P2k+1=∑j=02∑l=0jω1,lu−ω2,luPj+1k−Pjk.
By the same procedure the end point difference is(31)P0k+1−P3k+1=∑j=03ω0,ju−ω3,juPjk=ω0,0u−ω3,0uP0k+ω0,1u−ω3,1uP1k+ω0,2u−ω3,2uP2k+ω0,3u−ω3,3uP3k,this implies
(32)P0k+1−P3k+1=∑j=02∑l=0jω3,lu−ω0,luPj+1k−Pjk.
In general, it can be expressed as(33)Pi+1k+1−Pik+1=∑j=0n−2∑l=0jωi,lu−ωi+1,luPj+1k−Pjk,for i=0,1,2,⋯,n−2and
(34)P0k+1−Pn−1k+1=∑j=0n−2∑l=0jωn−1,lu−ω0,luPj+1k−Pjk.
Taking norm on both sides of (33), the following inequality will be obtained
(35)Pi+1k+1−Pik+1≤∑j=0n−2∑l=0jωi,lu−ωi+1,luPj+1k−Pjk.
ConsiderPi+1k−Pik=Δk, which implies
(36)Δk+1≤∑j=0n−2gjuΔk,where gju=∑l=0jωi,lu−ωi+1,lu.
Taking norm on both sides of (34), we have
(37)P0k+1−Pn−1k+1≤∑j=0n−2∑l=0jωn−1,lu−ω0,luPj+1k−Pjk,
which implies(38)Δk+1≤∑j=0n−2hjuΔk,where hju=∑l=0jωn−1,lu−ω0,lu.Now using Lemma1 and Corollary 2 with (36) and (38), we have the associated constants Gς0u and Hς0u, where ς0 is the order of convolution. These constants can be used in above result as follows
(39)Δk+1≤Gς0uHς0uΔk.So recursively, the following main result is obtained(40)Δk≤Gς0uHς0ukΔ0.


## 2.1. Reformulation of Successive Convolutions

With the use of analysis developed in [13], there are some useful results, which will be used to construct the new technique for Doo-Sabin surfaces scheme in upcoming sections. Now, we move forward and construct associated constants for the Doo-Sabin surface scheme by using successive convolutions for a one-dimensional array of finite length vectors.Lemma 1.
Letu=ui be the vector of finite length and g=gii=0n−2, h=hii=0n−2 with gi=hi=0 for i≥n−1. The convolution product of u=ui, g=gi,i≥0, and h=hj,j≥0 for Doo-Sabin subdivision surface scheme (1) along with (2) is given by
(7)ui,jς0=uς0−1;0∗ghi,j=∑m=0i/2∑l=0j/2um,lς0−1gi−2mhj−2l.
Similarly, we get the following reformulation of generalizedς0−th convolution
(8)ui,jς0=⋯uς0−1;0∗gh∗gh∗⋯∗gh∗ghi,j=∑m=0i/2∑l=0j/2um,l0Cm,iς0,gCl,jς0,h,
where(9)Cm,iς0,g=∑p=2mi/2ς0−1Cm,pς0−1,gCp,iς0−1,g,Cl,jς0,h=∑r=2lj/2ς0−1Cl,sς0−1,hCl,jς0−1,h.Proof.
See in [13].Corollary 2.
The associated constants of aς0-th convolution with vector g=g0,g1,⋯,gn−2 and h=h0,h1,⋯,hn−2 for subdivision surface scheme are defined as
(10)Gς0=maxi∈Σς0,n∑m=0i/2ς0Cm,iς0,(11)Hς0=maxj∈Σς0,n∑l=0j/2ς0Cl,jς0.
Here(12)j∈Σς0,n=Ως0,n−2ς0+1,Ως0,n−2ς0+2,⋯,Ως0,n,
where(13)Ως0,n=2ς0−12n−1.Proof.
See in [13].


## 2.2. Recursion Formula for Uniform Doo-Sabin Subdivision Scheme

In this section, using the subdivision scheme (1) with weights given in (2), the recursion formula For Doo-Sabin subdivision scheme for k+1th level is constructed, which will be used in the main results.Theorem 3.
Given initial control polygonP0=pj0;j∈ℤ and the polygon Pk+1=pjk+1;j∈ℤ,k≥1 be defined recursively by uniform Doo-Sabin subdivision process (1) together with (2). Then, the following inequalities hold for consecutive levels k and k+1(14)Δk+1≤∑j=1n−2gjuΔk,and
(15)Δk+1≤∑j=1n−2hjuΔk.
Where(16)gju=∑l=0jωi,lu−ωi+1,lu,(17)hjj=∑l=0jωn−1,lu−ω0,lu,and
(18)Δk=Pj+1k−Pjk.Proof.
To obtain recursion formula of Uniform Doo-Sabin subdivision with the help from Figure2. First, consider
(i)
Forn=3
The first difference is(19)P1k+1−P0k+1=∑j=02ω1,ju−ω0,juPjk=ω1,0u−ω0,0uP0k+ω1,1u−ω0,1uP1k+ω1,2u−ω0,2uP2k,
By the scheme defined in (1) and (2)
(20)P1k+1−P0k+1=ω0,0u−ω1,0uP1k−P0k+ω0,0u−ω1,0u+ω0,1u−ω1,1uP2k−P1k,this implies
(21)P1k+1−P0k+1=∑j=01∑l=0jω0,lu−ω1,luPj+1k−Pjk.
Now, the second difference is(22)P2k+1−P1k+1=∑j=02ω2,ju−ω1,juPjk=ω2,0u−ω1,0uP0k+ω2,1u−ω1,1uP1k+ω2,2u−ω1,2uP2k=ω1,0u−ω2,0uP1k−P0k+ω1,0u−ω2,0u+ω1,1u−ω2,1uP2k−P1k.
This implies(23)P2k+1−P1k+1=∑j=01∑l=0jω1,lu−ω2,luPj+1k−Pjk.
By the same procedure, the end point difference is(24)P0k+1−P2k+1=∑j=01∑l=0jω0,lu−ω2,luPj+1k−Pjk.(ii)
Forn=4
The difference betweenP1 and P0 at k+1th level is
(25)P1k+1−P0k+1=∑j=03ω1,ju−ω0,juPjk=ω1,0u−ω0,0uP0k+ω1,1u−ω0,1uP1k+ω1,2u−ω0,2uP2k+ω1,3u−ω0,3uP3k,this implies
(26)P1k+1−P0k+1=∑j=02∑l=0jω0,lu−ω1,luPj+1k−Pjk.
Now, the second difference is(27)P2k+1−P1k+1=∑j=03ω2,ju−ω1,juPjk=ω2,0u−ω1,0uP0k+ω2,1u−ω1,1uP1k+ω2,2u−ω1,2uP2k+ω2,3u−ω1,3uP3k,
this implies(28)P2k+1−P1k+1=∑j=02∑l=0jω1,lu−ω2,luPj+1k−Pjk.
Similarly,(29)P3k+1−P2k+1=∑j=03ω3,ju−ω2,juPjk=ω3,0u−ω2,0uP0k+ω3,1u−ω2,1uP1k+ω3,2u−ω2,2uP2k+ω3,3u−ω2,3uP3k,this implies
(30)P3k+1−P2k+1=∑j=02∑l=0jω1,lu−ω2,luPj+1k−Pjk.
By the same procedure the end point difference is(31)P0k+1−P3k+1=∑j=03ω0,ju−ω3,juPjk=ω0,0u−ω3,0uP0k+ω0,1u−ω3,1uP1k+ω0,2u−ω3,2uP2k+ω0,3u−ω3,3uP3k,this implies
(32)P0k+1−P3k+1=∑j=02∑l=0jω3,lu−ω0,luPj+1k−Pjk.
In general, it can be expressed as(33)Pi+1k+1−Pik+1=∑j=0n−2∑l=0jωi,lu−ωi+1,luPj+1k−Pjk,for i=0,1,2,⋯,n−2and
(34)P0k+1−Pn−1k+1=∑j=0n−2∑l=0jωn−1,lu−ω0,luPj+1k−Pjk.
Taking norm on both sides of (33), the following inequality will be obtained
(35)Pi+1k+1−Pik+1≤∑j=0n−2∑l=0jωi,lu−ωi+1,luPj+1k−Pjk.
ConsiderPi+1k−Pik=Δk, which implies
(36)Δk+1≤∑j=0n−2gjuΔk,where gju=∑l=0jωi,lu−ωi+1,lu.
Taking norm on both sides of (34), we have
(37)P0k+1−Pn−1k+1≤∑j=0n−2∑l=0jωn−1,lu−ω0,luPj+1k−Pjk,
which implies(38)Δk+1≤∑j=0n−2hjuΔk,where hju=∑l=0jωn−1,lu−ω0,lu.Now using Lemma1 and Corollary 2 with (36) and (38), we have the associated constants Gς0u and Hς0u, where ς0 is the order of convolution. These constants can be used in above result as follows
(39)Δk+1≤Gς0uHς0uΔk.So recursively, the following main result is obtained(40)Δk≤Gς0uHς0ukΔ0.


## 3. The Subdivision Depth for Uniform Doo-Sabin Subdivision Scheme

In this section, first error bounds for the uniform Doo-Sabin subdivision scheme for distinct valence numbers and order of convolution are computed. Then, a numerical technique to find the subdivision depth within a given error tolerance is presented. Before going to the main work, consider two sequences,gqu and hqu, such that
(41)h2qu=∑l=02qωn−1,lu−ω0,lu,h2q+1u=∑l=02q+1ωn−1,lu−ω0,lu,g2qu=∑l=02qωi,lu−ωi+1,lu,g2q+1u=∑l=02q+1ωi,lu−ωi+1,lu,q=0,1,2,⋯,n−22.Theorem 4.
Consider the initial control polygonP0=pν0;ν∈ℤ and the polygon Pk=pμk;μ∈ℤ,k≥1, recursively at k−th level defined by uniform Doo-Sabin scheme (1) together with (2). The error bound between two consecutive levels k and k+1 with associated constants Gς0u and Hς0u is
(42)Pk+1−Pk∞≤buGς0uHς0ukβ,with
(43)β=Δ0=Pi+10−Pi0,(44)bu=maxb0u,b1u,b2u,⋯,bn−1u,where
(45)bju=∑i=1n−13+2cos2iπ/n4ni,ifj=0,n−1;∑i=1n−j−13+2cos2iπ/n4ni+∑i=1j3+2cos2iπ/n4i,ifj=1,2,⋯,n−2.Proof.
Let.∞ denote the uniform norm. Consider the first difference between k+1th and kth level is
(46)P0k+1−P0k=14+54nP0k+∑j=1n−13+2cos2jπ/n4nPjk−P0k.
Using (1), the above equation can be rewritten as follows
(47)P0k+1−P0k=14+54nP0k+∑i=1n−13+2cos2iπ/n4nPik−14+54n+∑i=1n−13+2cos2iπ/n4nP0k=∑i=1n−13+2cos2iπ/n4nPik−P0k,
By takingPik=∑j=1i−1Pj+1k−Pjk+P1k, we have
(48)P0k+1−P0k=∑i=1n−13+2cos2iπ/n4nP1k−P0k+∑i=2n−13+2cos2iπ/n4n×∑j=1i−1Pj+1k−Pjk.
Taking norm., we have
(49)P0k+1−P0k≤∑i=1n−13+2cos2iπ/n4nP1k−P0k+∑i=2n−13+2cos2iπ/n4n∑j=1i−1Pj+1k−Pjk.
ConsiderPi+1k+1−Pik=Δk; then, the above expression leads
(50)P0k+1−P0k≤∑i=1n−13+2cos2iπ/n4nΔk+∑i=2n−13+2cos2iπ/n4n×∑j=1i−1Δk=∑i=1n−13+2cos2iπ/n4niΔk,which implies
(51)P0k+1−P0k≤b0uΔk,where
(52)b0u=∑i=1n−13+2cos2iπ/n4ni.
Consider(53)P1k+1−P1k=3+2cos2π/n4nP0k+14+54nP1k+∑i=1n−23+2cos2iπ/n4nPi+1k−P1k,
Using (2), we have
(54)P1k+1−P1k=3+2cos2π/n4nP0k+14+54nP1k+∑i=1n−23+2cos2iπ/n4nPi+1k−14+54n+∑i=1n−13+2cos2iπ/n4nP1k=3+2cos2π/n4nP2k−P1k+∑i=1n−23+2cos2iπ/n4nPi+1k−P1k−3+2cos2π/n4nP1k−P0k.
By takingPi+1k=∑j=1i−1Pj+2k−Pj+1k+P2k, the above expression can be written as
(55)P1k+1−P1k=∑i=1n−23+2cos2iπ/n4nP2k−P1k+∑i=2n−23+2cos2iπ/n4n∑j=1i−1Pj+2k−Pj+1k−3+2cos2π/n4nP1k−P0k
Taking norm., we have
(56)P1k+1−P1k≤∑i=1n−23+2cos2iπ/n4nP2k−P1k+∑i=2n−23+2cos2iπ/n4n∑j=1i−1Pj+2k−Pj+1k+3+2cos2π/n4nP1k−P0k,which implies
(57)P1k+1−P1k≤b1uΔk,where
(58)b1u=∑i=1n−23+2cos2iπ/n4n+3+2cos2π/n4n.
By the same procedure, we have(59)P2k+1−P2k≤b2uΔk,where
(60)b2u=∑i=1n−33+2cos2iπ/n4ni+3+2cos2π/n4n+23+2cos4π/n4n.
Similarly(61)P3k+1−P3k≤b3uΔk,where
(62)b3u=∑i=1n−43+2cos2iπ/n4ni+3+2cos2π/n4n+3+2cos4π/n4n+3+2cos6π/n4n.
In the same way, we get(63)Pn−1k+1−Pn−1k≤bn−1uΔk,where
(64)bn−1u=∑i=1n−13+2cos2iπ/n4ni.
From (51), (57), (59), (63), and (64), the following general form is obtained
(65)Pk+1−Pk≤buΔk,with
(66)bu=maxb0u,b1u,b2u,⋯,bn−1u,where
(67)bju=∑i=1n−13+2cos2iπ/n4ni,ifj=0,n−1;∑i=1n−j−13+2cos2iπ/n4ni+∑i=1j3+2cos2iπ/n4i,ifj=1,2,⋯,n−2.
From (40), the following inequality holds
(68)Pk+1−Pk≤buGς0uHς0ukΔ0.
If we takeΔ0=β, then
(69)Pk+1−Pk≤buGς0uHς0ukβ.
This completes the proof.Theorem 5.
LetP∞ be the limit surface generated from uniform Doo-Sabin scheme; then, under the same conditions used in Theorem 4, the following inequality holds
(70)P∞−Pk∞≤buGς0uHς0uk1−Gς0uHς0uβ.Proof.
Consider(71)Pk−P∞∞=Pk−Pk+1+Pk+1−Pk+2+Pk+2+⋯∞≤Pk−Pk+1∞+Pk+1−Pk+2∞+⋯,
Using (69), the following inequality holds
(72)Pk−P∞∞≤bu∑m=k∞Gς0uHς0umβ.
Sum of infinite geometric series implies(73)P∞−Pk∞≤buGς0uHς0uk1−Gς0uHς0uβ.
This complete the proof.Theorem 6.
Letk be subdivision depth and let ∇k=Pk+1−Pk be the error bound between uniform Doo-Sabin subdivision surface P∞ and its k-th level control polygon Pk. For arbitrary ϵ>0, if
(74)k≥logGς0uHς0u−1buβϵ1−Gς0uHς0u.then P∞−Pk≤ϵ.Proof.
See in [13].


## 4. Numerical Experiments

Some numerical tests for calculating the Doo-Sabin subdivision depths (number of iterations) for distinct valencesn are presented. Before proceeding to the main task, the associated constants Gς0uHς0u, ς0≥1 are estimated using Corollary 2, which are shown in Table 1 for n=3,4,5,6,7.Table 1
Associated constants of Doo-Sabin subdivision scheme for distinct valence numbers.
n/Gς0uHς0uG1uH1uG2uH2uG3uH3uG4uH4uG5uH5u30.250000.062500.015630.003910.000976540.281250.043940.006320.000870.000088950.155470.018170.001520.000130.000011060.166670.021770.002950.000390.000023770.231060.049660.010010.002040.0001244


### 4.1. Experiment 1

Theorem3 and Theorem 5 were used to estimate error bounds and subdivision depth in this experimental test for valence number n=3. From (1) and (2)
(75)P0k+1=23P0k+16P1k+16P2k,P1k+1=16P0k+23P1k+16P2k,P2k+1=16P0k+16P1k+23P2k.From (41)
(76)g0u=12,g1u=0,h0u=−12,h1u=−12.From (10) and (11)
(77)Gς0u=maxi∈Σς0,3∑m=0i/2ς0Cm,iς0,(78)Hς0u=maxj∈Σς0,3∑l=0j/2ς0Cl,jς0.(i)
First convolutionς0=1HereΩ1,3=5 and Σ1,3=4,5, G1uH1u is given by
(79)G1uH1u=maxi,j∈Σ1,3∑p=0j/2∑q=0i/2Cq,i1,guCp,j1,hu=maxi,j∈4,5∑p=0j/2∑q=0i/2Cq,i1,guCp,j1,hu=max∑p=04/2∑q=04/2Cq,41,guCp,41,hu,∑p=05/2∑q=05/2Cq,51,guCp,51,hu=max∑p=02∑q=02g4−2quh4−2pu,∑p=02∑q=02g5−2quh5−2pu=max0.2500,0,(80)G1uH1u=0.2500.(ii)
Second convolutionς0=2Now forΩ2,3=15 and Σ2,3=12,13,14,15, G2uH2u is given by
(81)G2uH2u=maxi,j∈12,13,14,15∑p=0j/22∑q=0i/22Cq,i2,guCp,j2,hu=max∑p=012/4∑q=012/4Cq,122,guCp,122,hu,∑p=013/4∑p=013/4Cp,132,guCp,132,hu,∑p=014/4∑q=014/4Cq,202,guCp,142,hu,∑p=015/4∑q=015/4Cq,152,guCp,152,hu=max∑p=03∑q=03∑r=2q12/2Cq,r1,guCr,121,gu∑s=2p12/2Cp,s1,huCs,121,hu,∑p=03∑q=03∑r=2q13/2Cq,r1,guCr,131,gu∑s=2p13/2Cp,s1,huCs,131,hu,∑p=03∑q=03∑r=2q14/2Cq,r1,guCr,141,gu∑s=2p14/2Cp,s1,huCs,141,hu,∑p=03∑q=03∑r=2q15/2Cq,r1,guCr,151,gu∑s=2p15/2Cp,s1,huCs,151,hu=max∑p=03∑q=03∑r=2q6gr−2qug12−2ru∑s=2p6hs−2puh12−2su,∑p=03∑q=03∑r=2q6gr−2qug13−2ru∑s=2p6hs−2puh13−2su,∑p=03∑q=03∑r=2q7gr−2qug14−2ru∑s=2p7hs−2puh14−2su,∑p=03∑q=03∑r=2q7gr−2qug15−2ru∑s=2p7hs−2puh15−2su=max0.062500,0.062500,0.062500,0.062500,(82)G2uH2u=0.062500.Similarly, computeGς0uHς0u values for ς0≥3. Table 2 displays the values computed up to ς0=5 for convenience.Table 2
Error bound of the uniform Doo-Sabin subdivision surfaces. Here,k presents the subdivision level, and n presents the valence number.
n/k1234567ς0=130.01660.00420.00100.00030.000070.000020.00000440.03430.00960.00270.00080.00020.000060.000017100.38110.20940.11510.06320.03470.019090.0105ς0=230.00330.00020.000018.14×10−75.09×10−83.18×10−91.99×10−1040.00400.00020.0000083.41×10−71.49×10−86.59×10−102.89×10−10100.10110.02470.006030.00150.000360.0000880.000021ς0=330.00080.000021.94×10−73.03×10−94.74×10−117.40×10−111.16×10−1440.00050.0000032.22×10−81.41×10−108.88×10−135.61×10−153.50×10−17100.03450.00340.000030.0000030.000363.27×10−73.23×10−8ς0=430.00027.67×10−73.03×10−91.17×10−114.58×10−141.79×10−167.01×10−1940.000086.63×10−85.77×10−115.02×10−144.37×10−173.80×10−203.30×10−23100.01290.000520.0000028.28×10−73.30×10−81.32×10−95.27×10−11ς0=530.000054.77×10−84.66×10−114.55×10−144.44×10−174.34×10−174.23×10−2340.0000086.91×10−106.15×10−145.47×10−184.86×10−224.32×10−263.84×10−30100.00470.000070.0000011.49×10−82.19×10−103.23×10−124.75×10−14After the calculation of the convolution constant of the uniform Doo-Sabin Subdivision scheme, it can be observed that the values ofGς0uHς0u decrease with the increase of the level of convolution ς0 which is the main approach of the proposed work.Calculate the errors of the proposed results using Theorem4 for different subdivision levels k and distinct face valence numbers n=3,4,10, as shown in Table 2. Estimate the subdivision depth of uniform Doo-Sabin subdivision at valence n=3 using Theorem 5 and Table 3.Table 3
Subdivision depth of the uniform Doo-Sabin subdivision surface at face valencen=3.
Gς0uHς0u/ϵ0.00004884.77×10−84.66×10−114.55×10−144.44×10−174.34×10−204.12×10−22G1uH1u5101520253031G2uH2u25710131515G3uH3u235781010G4uH4u1345678G5uH5u1234567Figure3(a) depicts a graphical representation of the subdivision depth for valance n=3 at various convolution levels. From the figure, it is clear that the subdivision depth (the number of iterations) decreases by increasing the order of convolution ς0.Figure 3
Presentation of subdivision depth by taking first, second, and fifth level of convolutions.
(a)
Graph for valencen=3(b)
Graph for valencen=6


### 4.2. Experiment 2

Consider the following uniform Doo-Sabin surface scheme for face valance numbern=6 given in (1) and (2).
(83)P0k+1=1124P0k+16P1k+112P2k+124P3k+112P4k+16P5k,P1k+1=16P0k+124P1k+16P2k+112P3k+124P4k+112P5k,P2k+1=112P0k+16P1k+1124P2k+16P3k+112P4k+124P5k,P3k+1=124P0k+112P1k+16P2k+1124P3k+16P4k+112P5k,P4k+1=112P0k+124P1k+112P2k+16P3k+1124P4k+16P5k,P5k+1=16P0k+112P1k+124P2k+112P3k+16P4k+1124P5k.To find the error bounds and subdivision depth of above scheme, first consider(84)g0u=724,g1u=0,g2u=−112,g3u=−18,g4u=−112,g5u=0,h0u=−524,h1u=−724,h2u=−13,h3u=−724,h4u=524,h5u=58.From (10) and (11), we have
(85)Gς0u=maxi∈Σς0,6∑m=0i/2ς0Cm,iς0,(86)Hς0u=maxj∈Σς0,6∑l=0j/2ς0Cl,jς0.Now, we apply Theorem4, the error bounds Gς0uHς0u, for ς0≥1, are shown in Table 2 at distinct valence numbers. Further, the subdivision depth of the subdivision scheme for n=6 is shown in Table 4. The graphical representation of the subdivision depth for distinct valences n at distinct convolution level is shown in Figure 3(b). From the figure, it is clear that the subdivision depth (number of iterations) decreases by increasing the order of convolution ς0.Table 4
Subdivision depth of uniform Doo-Sabin subdivision surface at valencen=6.
Gς0uHς0u/ϵ0.00004884.77×10−84.66×10−114.55×10−144.44×10−174.34×10−204.12×10−22G1uH1u581216202426G2uH2u246891112G3uH3u2345679G4uH4u1234578G5uH5u1234567


## 4.1. Experiment 1

Theorem3 and Theorem 5 were used to estimate error bounds and subdivision depth in this experimental test for valence number n=3. From (1) and (2)
(75)P0k+1=23P0k+16P1k+16P2k,P1k+1=16P0k+23P1k+16P2k,P2k+1=16P0k+16P1k+23P2k.From (41)
(76)g0u=12,g1u=0,h0u=−12,h1u=−12.From (10) and (11)
(77)Gς0u=maxi∈Σς0,3∑m=0i/2ς0Cm,iς0,(78)Hς0u=maxj∈Σς0,3∑l=0j/2ς0Cl,jς0.(i)
First convolutionς0=1HereΩ1,3=5 and Σ1,3=4,5, G1uH1u is given by
(79)G1uH1u=maxi,j∈Σ1,3∑p=0j/2∑q=0i/2Cq,i1,guCp,j1,hu=maxi,j∈4,5∑p=0j/2∑q=0i/2Cq,i1,guCp,j1,hu=max∑p=04/2∑q=04/2Cq,41,guCp,41,hu,∑p=05/2∑q=05/2Cq,51,guCp,51,hu=max∑p=02∑q=02g4−2quh4−2pu,∑p=02∑q=02g5−2quh5−2pu=max0.2500,0,(80)G1uH1u=0.2500.(ii)
Second convolutionς0=2Now forΩ2,3=15 and Σ2,3=12,13,14,15, G2uH2u is given by
(81)G2uH2u=maxi,j∈12,13,14,15∑p=0j/22∑q=0i/22Cq,i2,guCp,j2,hu=max∑p=012/4∑q=012/4Cq,122,guCp,122,hu,∑p=013/4∑p=013/4Cp,132,guCp,132,hu,∑p=014/4∑q=014/4Cq,202,guCp,142,hu,∑p=015/4∑q=015/4Cq,152,guCp,152,hu=max∑p=03∑q=03∑r=2q12/2Cq,r1,guCr,121,gu∑s=2p12/2Cp,s1,huCs,121,hu,∑p=03∑q=03∑r=2q13/2Cq,r1,guCr,131,gu∑s=2p13/2Cp,s1,huCs,131,hu,∑p=03∑q=03∑r=2q14/2Cq,r1,guCr,141,gu∑s=2p14/2Cp,s1,huCs,141,hu,∑p=03∑q=03∑r=2q15/2Cq,r1,guCr,151,gu∑s=2p15/2Cp,s1,huCs,151,hu=max∑p=03∑q=03∑r=2q6gr−2qug12−2ru∑s=2p6hs−2puh12−2su,∑p=03∑q=03∑r=2q6gr−2qug13−2ru∑s=2p6hs−2puh13−2su,∑p=03∑q=03∑r=2q7gr−2qug14−2ru∑s=2p7hs−2puh14−2su,∑p=03∑q=03∑r=2q7gr−2qug15−2ru∑s=2p7hs−2puh15−2su=max0.062500,0.062500,0.062500,0.062500,(82)G2uH2u=0.062500.Similarly, computeGς0uHς0u values for ς0≥3. Table 2 displays the values computed up to ς0=5 for convenience.Table 2
Error bound of the uniform Doo-Sabin subdivision surfaces. Here,k presents the subdivision level, and n presents the valence number.
n/k1234567ς0=130.01660.00420.00100.00030.000070.000020.00000440.03430.00960.00270.00080.00020.000060.000017100.38110.20940.11510.06320.03470.019090.0105ς0=230.00330.00020.000018.14×10−75.09×10−83.18×10−91.99×10−1040.00400.00020.0000083.41×10−71.49×10−86.59×10−102.89×10−10100.10110.02470.006030.00150.000360.0000880.000021ς0=330.00080.000021.94×10−73.03×10−94.74×10−117.40×10−111.16×10−1440.00050.0000032.22×10−81.41×10−108.88×10−135.61×10−153.50×10−17100.03450.00340.000030.0000030.000363.27×10−73.23×10−8ς0=430.00027.67×10−73.03×10−91.17×10−114.58×10−141.79×10−167.01×10−1940.000086.63×10−85.77×10−115.02×10−144.37×10−173.80×10−203.30×10−23100.01290.000520.0000028.28×10−73.30×10−81.32×10−95.27×10−11ς0=530.000054.77×10−84.66×10−114.55×10−144.44×10−174.34×10−174.23×10−2340.0000086.91×10−106.15×10−145.47×10−184.86×10−224.32×10−263.84×10−30100.00470.000070.0000011.49×10−82.19×10−103.23×10−124.75×10−14After the calculation of the convolution constant of the uniform Doo-Sabin Subdivision scheme, it can be observed that the values ofGς0uHς0u decrease with the increase of the level of convolution ς0 which is the main approach of the proposed work.Calculate the errors of the proposed results using Theorem4 for different subdivision levels k and distinct face valence numbers n=3,4,10, as shown in Table 2. Estimate the subdivision depth of uniform Doo-Sabin subdivision at valence n=3 using Theorem 5 and Table 3.Table 3
Subdivision depth of the uniform Doo-Sabin subdivision surface at face valencen=3.
Gς0uHς0u/ϵ0.00004884.77×10−84.66×10−114.55×10−144.44×10−174.34×10−204.12×10−22G1uH1u5101520253031G2uH2u25710131515G3uH3u235781010G4uH4u1345678G5uH5u1234567Figure3(a) depicts a graphical representation of the subdivision depth for valance n=3 at various convolution levels. From the figure, it is clear that the subdivision depth (the number of iterations) decreases by increasing the order of convolution ς0.Figure 3
Presentation of subdivision depth by taking first, second, and fifth level of convolutions.
(a)
Graph for valencen=3(b)
Graph for valencen=6


## 4.2. Experiment 2

Consider the following uniform Doo-Sabin surface scheme for face valance numbern=6 given in (1) and (2).
(83)P0k+1=1124P0k+16P1k+112P2k+124P3k+112P4k+16P5k,P1k+1=16P0k+124P1k+16P2k+112P3k+124P4k+112P5k,P2k+1=112P0k+16P1k+1124P2k+16P3k+112P4k+124P5k,P3k+1=124P0k+112P1k+16P2k+1124P3k+16P4k+112P5k,P4k+1=112P0k+124P1k+112P2k+16P3k+1124P4k+16P5k,P5k+1=16P0k+112P1k+124P2k+112P3k+16P4k+1124P5k.To find the error bounds and subdivision depth of above scheme, first consider(84)g0u=724,g1u=0,g2u=−112,g3u=−18,g4u=−112,g5u=0,h0u=−524,h1u=−724,h2u=−13,h3u=−724,h4u=524,h5u=58.From (10) and (11), we have
(85)Gς0u=maxi∈Σς0,6∑m=0i/2ς0Cm,iς0,(86)Hς0u=maxj∈Σς0,6∑l=0j/2ς0Cl,jς0.Now, we apply Theorem4, the error bounds Gς0uHς0u, for ς0≥1, are shown in Table 2 at distinct valence numbers. Further, the subdivision depth of the subdivision scheme for n=6 is shown in Table 4. The graphical representation of the subdivision depth for distinct valences n at distinct convolution level is shown in Figure 3(b). From the figure, it is clear that the subdivision depth (number of iterations) decreases by increasing the order of convolution ς0.Table 4
Subdivision depth of uniform Doo-Sabin subdivision surface at valencen=6.
Gς0uHς0u/ϵ0.00004884.77×10−84.66×10−114.55×10−144.44×10−174.34×10−204.12×10−22G1uH1u581216202426G2uH2u246891112G3uH3u2345679G4uH4u1234578G5uH5u1234567



---

*Source: 2510204-2022-09-24.xml*