Open AccessFeature PaperArticle

A Novel Numerical Algorithm to Estimate the Subdivision Depth of Binary Subdivision Schemes

Aamir Shahzad

¹,

Faheem Khan

¹,

Abdul Ghaffar

Ghulam Mustafa

³,

Kottakkaran Sooppy Nisar

^4,*

and

Dumitru Baleanu

^5,6,7

Department of Mathematics, University of Sargodha, Sargodha 40100, Pakistan

Department of Mathematical Sciences, BUITEMS, Quetta 87300, Pakistan

Department of Mathematics, The Islamia University of bahawalpur, Punjab 63100, Pakistan

⁴

Department of Mathematics, College of Arts and Sciences, Prince Sattam bin Abdulaziz University, Wadi Aldawaser 11991, Saudi Arabia

⁵

Department of Mathematics, Cankaya University, Ankara 06530, Turkey

⁶

Department of Medical Research, China Medical University Hospital, China Medical University, Taichung 40447, Taiwan

⁷

Institute of Space Sciences, 077125 Magurele-Bucharest, Romania

Author to whom correspondence should be addressed.

Symmetry 2020, 12(1), 66; https://doi.org/10.3390/sym12010066

Submission received: 5 December 2019 / Revised: 20 December 2019 / Accepted: 22 December 2019 / Published: 1 January 2020

(This article belongs to the Special Issue Fixed Point Theory and Computational Analysis with Applications)

Download

Browse Figures

Versions Notes

Abstract

Subdivision schemes are extensively used in scientific and practical applications to produce continuous geometrical shapes in an iterative manner. We construct a numerical algorithm to estimate subdivision depth between the limit curves/surfaces and their control polygons after k-fold subdivisions. In this paper, the proposed numerical algorithm for subdivision depths of binary subdivision curves and surfaces are obtained after some modification of the results given by Mustafa et al in 2006. This algorithm is very useful for implementation of the parametrization.

Keywords:

numerical analysis; algorithm; subdivision schemes; error bounds; subdivision depth

MSC:

65D17; 65D05; 65U07

1. Introduction

Computer Aided Geometric Design (CAGD) foremost deals with curves/surfaces and its computational aspects. Subdivision schemes (SSs) have achieved much popularity in the past few years because of its competitive generation of curves/surfaces, and this magnificence lies in its implementation along with its mathematical formulation. Here we provide an overview of CAGD, subdivision and some other related concepts. The term CAGD was first suggested by Riesenfeld and Barnhill [1] in 1974 and the initial work was performed in the 1960’s. “Computational Geometry for Design and Manufacture” was the first book on CAGD authored by Faux and Pratt [2] in 1979. Subdivision is the most remarkable field for the purpose of modeling in CAGD, and is described as “the act or process of dividing something into smaller parts”. A small number of papers have been published in the field of SSs for error dominance.

Huawei et al. [3] performed error (distance) estimations for the Doo–Sabin scheme. After this, Mustafa et al. [4,5,6,7] estimated error bounds for binary, non-stationary binary, ternary and quaternary SSs. Mustafa et al. computed error bounds for tensor product volumetric models and

\sqrt{3}

subdivision surfaces [8,9]. They also computed triangular surfaces subdivision depths [10]. However, Mustafa and Hashmi [11] determined subdivision depth computation for n-ary subdivision curves/surfaces by using the first forward difference technique. Moncayo and Amat [12] estimated error bounds for the class of SSs based on the two-scale refinement equation. The authors in [4,5,6,7,8,9,10,11] imposed these conditions to find their results. But, it has been observed that all SSs do not satisfy the imposed condition. Amat et al. [12] relaxed the condition in [4] for estimating the error bounds of binary SSs for curve designing. In this paper, we relax the conditions in the work of [5,6,7,8,9,10,11] and generalize the work of [12] to estimating error bounds and subdivision depths of binary SSs for curve and regular surface design.

However, as of yet, no one has found a numerical algorithm to estimate error bounds and subdivision depths of parametric SSs for curve and regular surface design. This motivates us to present a novel numerical algorithm for estimating the subdivision depth of binary subdivision schemes. This paper introduces not only a numerical algorithm for parametric SSs, but also the estimation for the non-parametric SSs. This novel technique has lesser computational cost than numerous other techniques.

Now we present some preliminaries. In the case of the curve: Let

{f_{i}^{k}; i \in Z}

be a sequence of points in

R^{N}

, where

N \geq 2

and k be the non-negative integer which indicates the SS level. A generalized univariate binary SS [13] is illustrated in the following as

\{\begin{matrix} f_{2 i}^{k + 1} = \sum_{m = 0}^{t} a_{0, m} f_{i + m}^{k}, \\ f_{2 i + 1}^{k + 1} = \sum_{m = 0}^{t} a_{1, m} f_{i + m}^{k}, \end{matrix}

(1)

with necessary condition of the convergence

\begin{matrix} \sum_{m = 0}^{t} a_{0, m} = \sum_{m = 0}^{t} a_{1, m} = 1 . \end{matrix}

(2)

By [4], we have

\begin{matrix} b_{0, m} & = & \sum_{l = 0}^{m} (a_{0, l} - a_{1, l}), \\ b_{1, m} & = & a_{0, m} - b_{0, m}, \end{matrix}

(3)

such that

\sum_{m = 0}^{t} | b_{0, m} | < 1 and \sum_{m = 0}^{t} | b_{1, m} | < 1 .

We introduce the coefficients for

m = 0, 1, \dots, t

, such that

\begin{matrix} \{\begin{matrix} d_{2 m} = b_{0, m}, \\ d_{2 m + 1} = b_{1, m} . \end{matrix} \end{matrix}

(4)

In the case of the surface: The points

{f_{i, j}^{k}; i, j \in Z}

represents a sequence in

R^{N}

N \geq 2

and is described as

\begin{matrix} \{\begin{matrix} f_{2 i, 2 j}^{k + 1} = \sum_{p = 0}^{t} \sum_{q = 0}^{t} a_{0, p} a_{0, q} f_{i + p, j + q}^{k}, \\ f_{2 i, 2 j + 1}^{k + 1} = \sum_{p = 0}^{t} \sum_{q = 0}^{t} a_{0, p} a_{1, q} f_{i + p, j + q}^{k}, \\ f_{2 i + 1, 2 j}^{k + 1} = \sum_{p = 0}^{t} \sum_{q = 0}^{t} a_{1, p} a_{0, q} f_{i + p, j + q}^{k}, \\ f_{2 i + 1, 2 j + 1}^{k + 1} = \sum_{p = 0}^{t} \sum_{q = 0}^{t} a_{1, p} a_{1, q} f_{i + p, j + q}^{k}, \end{matrix} \end{matrix}

(5)

with the condition

\begin{matrix} \sum_{p = 0}^{t} a_{0, p} = \sum_{p = 0}^{t} a_{1, p} = \sum_{q = 0}^{t} a_{0, q} = \sum_{q = 0}^{t} a_{1, q} = 1 . \end{matrix}

(6)

By [4], we have

\sum_{p = 0}^{t} | a_{0, p} | \sum_{q = 0}^{t} | b_{0, q} | < 1, \sum_{p = 0}^{t} | a_{0, p} | \sum_{q = 0}^{t} | b_{1, q} | < 1,

\sum_{p = 0}^{t} | a_{1, p} | \sum_{q = 0}^{t} | b_{0, q} | < 1, \sum_{p = 0}^{t} | a_{1, p} | \sum_{q = 0}^{t} | b_{1, q} | < 1,

where

b_{0, q}

and

b_{1, q}

for

q = 0, 1, \dots, t

are defined in (3). We introduce the coefficients

{(f_{n})}_{n \in N}

{(d_{n})}_{n \in N}

for

r, s = 0, 1, \dots, t

, such that

\begin{matrix} \{\begin{matrix} f_{2 r} = a_{0, t - r} \\ f_{2 r + 1} = a_{1, t - r} r = 0, \dots, t . \\ d_{2 s} = b_{0, t - s} \\ d_{2 s + 1} = b_{1, t - s}, s = 0, \dots, t . \end{matrix} \end{matrix}

(7)

2. Preliminaries Results

Here we present some preliminary notations and results. Readers are referred to [12] for more details.

2.1. Univariate Case

Let

{(u_{n})}_{n \geq 0}

be the finite length vector and

{(d_{n})}_{n \geq 0} = {(d_{n})}_{n = 0}^{2 N - 1}

with

d_{n} = 0

for

n \geq 2 N

. The one time convolution product of

u = {(u_{n})}_{n \geq 0}

and

d = {(d_{n})}_{n \geq 0}

for binary subdivision curves is given by

{(u^{(0)} 🟉 d)}_{j} = \sum_{n = 0}^{[j / 2]} u_{n} d_{j - 2 n} .

(8)

Similarly, we have the following reformulation for

k_{0}

convolutions

{({(\dots {(({(u^{(0)} 🟉 d)}^{(0)}) 🟉 d)}^{(0)} 🟉 \dots 🟉 d)}^{(0)} 🟉 d)}_{j} = \sum_{m = 0}^{[j / 2^{k_{0}}]} u_{m} C_{m, j}^{[k_{0}]},

(9)

with

\begin{matrix} \{\begin{matrix} C_{m, j}^{[1]} = A_{m, j} = d_{j - 2 m}, \\ C_{m, j}^{[k_{0}]} = \sum_{n = 2 m}^{[j / 2^{k_{0} - 1}]} A_{m, n} C_{n, j}^{[k_{0} - 1]}, k_{0} \geq 2 . \end{matrix} \end{matrix}

(10)

Hence by (9), we get

\begin{matrix} ∥ ({(\dots {(({(u^{(0)} 🟉 d)}^{(0)}) 🟉 d)}^{(0)} 🟉 \dots 🟉 d)}^{(0)} 🟉 d) ∥_{\infty} \leq {∥ u ∥}_{\infty} max_{j} \{\sum_{m = 0}^{[j / 2^{k_{0}}]} | C_{m, j}^{[k_{0}]} |\}, \end{matrix}

(11)

and

sup_{j} \{\sum_{m = 0}^{[j / 2^{k_{0}}]} | C_{m, j}^{[k_{0}]} |\} = sup_{j \in \sum (k_{0}, N)} \{\sum_{m = 0}^{[j / 2^{k_{0}}]} | C_{m, j}^{[k_{0}]} |\},

(12)

where

\begin{matrix} \sum (k_{0}, N) = {Ω (k_{0}, N) - 2^{k_{0}} + 1, Ω (k_{0}, N) - 2^{k_{0}} + 2, \dots, Ω (k_{0}, N)}, \end{matrix}

(13)

and

\begin{matrix} Ω (k_{0}, N) = (2^{k_{0}} - 1) (2 N - 1) . \end{matrix}

(14)

Lemma 1.

The associated constant of

k_{0}

-th convolution with coefficients

d = (d_{0}, d_{1}, \dots, d_{2 N - 1})

for binary subdivision curves is defined as

D_{k_{0}} = sup_{j \in \sum (k_{0}, N)} \{\sum_{m = 0}^{[j / 2^{k_{0}}]} | C_{m, j}^{[k_{0}]} |\} .

(15)

2.2. Bivariate Case

Let

{(u_{n})}_{n \geq 0}

be a vector and

{(d_{n})}_{n \geq 0} = {(d_{n})}_{n = 0}^{2 N - 1}

{(f_{n})}_{n \geq 0} = {(f_{n})}_{n = 0}^{2 N - 1}

with

d_{n} = f_{n} = 0

for

n \geq 2 N

. The convolution product of

u = {(u_{n})}_{n \geq 0}

d = {(d_{n})}_{n \geq 0}

and

f = {(f_{n})}_{n \geq 0}

for binary subdivision surfaces is given by

u_{i, j}^{k_{0}} = {(u^{k_{0} - 1; 0} * f d)}_{i, j} = \sum_{m = 0}^{[i / 2]} \sum_{n = 0}^{[j / 2]} u_{m, n}^{k_{0} - 1} d_{j - 2 n} f_{i - 2 m} .

(16)

Similarly, we get the following reformulation of

k_{0}

convolutions for surface case

\begin{matrix} u_{i, j}^{k_{0}} = {(\dots (((u^{k_{0} - 1; 0} * f d) * f d) * \dots * f d) * f d)}_{i, j} = \sum_{m = 0}^{[i / 2^{k_{0}}]} \sum_{n = 0}^{[j / 2^{k_{0}}]} u_{m, n}^{0} C_{n, j}^{[k_{0}, d]} C_{m, i}^{[k_{0}, f]}, \end{matrix}

(17)

with

\begin{matrix} \{\begin{matrix} C_{n, j}^{[k_{0}, d]} = \sum_{s = 2 n}^{[j / 2^{k_{0} - 1}]} C_{n, s}^{[k_{0} - 1, d]} C_{s, j}^{[k_{0} - 1, d]}, \\ C_{m, i}^{[k_{0}, f]} = \sum_{p = 2 m}^{[i / 2^{k_{0} - 1}]} C_{m, p}^{[k_{0} - 1, f]} C_{p, i}^{[k_{0} - 1, f]} . \end{matrix} \end{matrix}

(18)

From (17), we have

max_{i, j} | u_{i, j}^{k_{0}} | \leq max_{m, n} | u_{m, n}^{0} | max_{i, j} \sum_{m = 0}^{[i / 2^{k_{0}}]} \sum_{n = 0}^{[j / 2^{k_{0}}]} | C_{n, j}^{[k_{0}, d]} | | C_{m, i}^{[k_{0}, f]} |,

(19)

and

max_{i, j} \{\sum_{m = 0}^{[i / 2^{k_{0}}]} \sum_{n = 0}^{[j / 2^{k_{0}}]} | C_{n, j}^{[k_{0}, d]} | | C_{m, i}^{[k_{0}, f]} |\} = max_{i, j \in \sum (k_{0}, N)} \{\sum_{m = 0}^{[i / 2^{k_{0}}]} \sum_{n = 0}^{[j / 2^{k_{0}}]} | C_{n, j}^{[k_{0}, d]} | | C_{m, i}^{[k_{0}, f]} |\},

(20)

where

\sum (k_{0}, N)

is defined in (13).

Lemma 2.

The associated constants of

k_{0}

-th convolution with coefficients

d = (d_{0}, d_{1}, \dots, d_{2 N - 1})

and

f = (f_{0}, f_{1}, \dots, f_{2 N - 1})

for binary subdivision surfaces are defined as

F_{k_{0}} = sup_{i \in \sum (k_{0}, N)} \{\sum_{m = 0}^{[i / 2^{k_{0}}]} | C_{m, i}^{[k_{0}, f]} |\},

(21)

G_{k_{0}} = sup_{j \in \sum (k_{0}, N)} \{\sum_{n = 0}^{[j / 2^{k_{0}}]} | C_{n, j}^{[k_{0}, d]} |\} .

(22)

3. Subdivision Depth for Binary Subdivision Curves

Now firstly, the modified technique for finding the error bounds is presented. Secondly, an altered subdivision depth computation technique based on the proposed error bounds is demonstrated with the help of tables.

Theorem 1.

Consider

f_{i}^{0}, i \in Z

to be the control polygon and

f_{i}^{k}

to be the values for non-negative integers recursively described by

(1)

together with mask condition

(2)

. Suppose

F^{k}

denotes the initial at the points

{f_{i}^{k}}

. Then after two successive iterations the error bounds between k and

k + 1

stage is

\begin{matrix} ∥ F^{k + 1} - F^{k} ∥_{\infty} \leq γ β D_{k_{0}}, \end{matrix}

(23)

where

D_{k_{0}}, k_{0} \geq 1

defined in (15) and

β = max_{i} ∥Δ p_{i}^{0}∥,

\begin{matrix} γ = max (\sum_{j = 0}^{t - 1} |{\tilde{a}}_{0, j}|, \sum_{j = 0}^{t - 1} |{\tilde{a}}_{1, j}|), {\tilde{a}}_{0, j} = \sum_{i = j + 1}^{t} a_{0, i}, \\ {\tilde{a}}_{1, 0} = \sum_{i = 1}^{t} a_{1, i} - \frac{1}{2}, {\tilde{a}}_{1, j} = \sum_{i = j + 1}^{t} a_{1, i}, j \neq 0 . \end{matrix}

Theorem 2.

Under the same conditions used in Theorem 1, let

F^{\infty}

be the limit curve associated with the subdivision process, then

{∥F^{\infty} - F^{k}∥}_{\infty} \leq γ β (\frac{D_{k_{0}}^{k}}{1 - D_{k_{0}}}),

(24)

where

k_{0} \geq 1

be a natural number, such that

D_{k_{0}} < 1

Remark 1.

In this paper

D_{k_{0}}

for

k_{0} = 1

is equal to δ defined in [4]. Note that in [4], if

δ > 1

then the error bounds can not be computed. But by [12] and by using our technique, we increase the value of

k_{0}

until

D_{k_{0}}

becomes less than one.

Theorem 3.

Let k be the subdivision depth and let

\nabla^{k}

be the error bound between binary subdivision curve

F^{\infty}

and its k-level control polygon

F^{k}

. For arbitrary

ϵ > 0

, if

k \geq {log}_{D_{k_{0}}^{- 1}} (\frac{γ χ}{ϵ (1 - D_{k_{0}})}),

(25)

then

\nabla^{k} \leq ϵ

Proof.

Let

\nabla^{k}

be the distance between limit curve

F^{\infty}

and control polygon

F^{k}

at the k-th subdivision level, then

\nabla^{k} = {∥F^{\infty} - F^{k}∥}_{\infty} \leq γ β (\frac{D_{k_{0}}^{k}}{1 - D_{k_{0}}}) .

(26)

To obtain the given error tolerance

ϵ > 0

, the subdivision depth k satisfies the following relation, which is in inequality form as

k \geq {log}_{D_{k_{0}}^{- 1}} (\frac{γ χ}{ϵ (1 - D_{k_{0}})}),

(27)

then

\nabla^{k} \leq ϵ

Hence, this completes the proof. □

Application for Univariate Case

Here, we present some numerical examples to compute subdivision depths of binary SSs for curves. The associated constants

D_{k_{0}}, k_{0} \geq 1

defined in (15) of some binary subdivision curves are shown in Table 1.

Example 1.

Consider the 2-point Chaikin’s binary SS [14]:

\begin{matrix} p_{2 i}^{k + 1} = \frac{3}{4} p_{i}^{k} + \frac{1}{4} p_{i + 1}^{k}, \\ p_{2 i + 1}^{k + 1} = \frac{1}{4} p_{i}^{k} + \frac{3}{4} p_{i + 1}^{k} . \end{matrix}

(28)

Its subdivision depth by Theorem 3 for

D_{k_{0}}, k_{0} \geq 1

(computed in Table 1) are shown in Table 2. From this table, we see that as

k_{0}

increases the subdivision depth decreases. This shows that the sharp depth can be obtained by using our technique. In other words, we need a smaller number of iterations to get the sharp depth compared to the technique of [11]. For example, by [11], it needs thirty one iterations for

ϵ = 2.40 \times 10^{- 11}

, but using our technique, it needs only six iterations corresponding to

D_{5}

, which are shown in Figure 1a.

Example 2.

Consider the 3-point approximating SS [15]:

\begin{matrix} f_{2 i}^{k + 1} & = & \frac{1}{2} f_{i + 1}^{k} + \frac{1}{2} f_{i + 2}^{k}, \\ f_{2 i + 1}^{k + 1} & = & \frac{1}{8} f_{i}^{k} + \frac{3}{4} f_{i + 1}^{k} + \frac{1}{8} f_{i + 2}^{k} . \end{matrix}

(29)

From Table 3,

D_{1} > 1

and

D_{2} > 1

, so error bounds cannot be computed by [4]. Consequently, it is not possible to compute subdivision depths. In this case, we increase the value of

k_{0}

until

D_{k_{0}} < 1

. The subdivision depths of the 3-point scheme are shown in Table 3 at different values of error tolerance. It is also demonstrated with the help of Figure 1b.

Example 3.

The initial polygon have values

f_{i}^{k}, k \geq 1

by following the 4-point approximating binary SS [14] with subdivision mask

\begin{matrix} (a_{0, 0}, a_{0, 1}, a_{0, 2}, a_{0, 3}) = (- \frac{7}{128}, \frac{105}{128}, \frac{35}{128}, - \frac{5}{128}), \\ (a_{1, 0}, a_{1, 1}, a_{1, 2}, a_{1, 3}) = (- \frac{5}{128}, \frac{35}{128}, \frac{105}{128}, - \frac{7}{128}) . \end{matrix}

(30)

Its subdivision depths by using Theorem 3 are given in Table 4. The comparison of the first and fifth convolution results is shown in Figure 1c.

Example 4.

Consider

f_{i}^{0} = f_{i}, i \in Z

denotes the initial polygon with values

f_{i}^{k}, k \geq 1

, which can be expressed recursively by the 4-point interpolating binary SS [17] with weights

\begin{matrix} (a_{0, 0}, a_{0, 1}, a_{0, 2}, a_{0, 3}) & = & (0, 1, 0, 0), \\ (a_{1, 0}, a_{1, 1}, a_{1, 2}, a_{1, 3}) & = & (- w, \frac{1}{2} + w, \frac{1}{2} + w, - w) . \end{matrix}

(31)

Its subdivision depths are given in Table 5. It is also illustrated with the help of the graph given in Figure 1d.

Example 5.

Given the initial polygon

f_{i}^{0} = f_{i}, i \in Z

with values

f_{i}^{k}, k \geq 1

can be expressed recursively by the 6-point interpolating binary SS [18] as

\begin{matrix} (a_{0, 0}, a_{0, 1}, a_{0, 2}, a_{0, 3}, a_{0, 4}, a_{0, 5}) & = & (0, 0, 1, 0, 0, 0), \\ (a_{1, 0}, a_{1, 1}, a_{1, 2}, a_{1, 3}, a_{1, 4}, a_{1, 5}) & = & (w, - \frac{1}{16} - 3 w, \frac{9}{16} + 2 w, \frac{9}{16} + 2 w, - \frac{1}{16} - 3 w, w) . \end{matrix}

(32)

In Table 6, subdivision depths are presented and its performance is shown in Figure 1e.

4. Subdivision Depth for Binary Subdivision Surfaces

In the following section, firstly we calculate error bounds for subdivision surfaces. Secondly, we use these error bounds to compute subdivision depths.

Theorem 4.

Consider

f_{i, j}^{0}, i, j \in Z

to be the initial polygon and

f_{i, j}^{k}

to be the values for all non-negative integers recursively given in

(5)

along with the condition

(6)

. Also let

F^{k}

be the representation of the polygon at the points

f_{i, j}^{k}

. Then the error bounds of two successive refinements between the level k and

k + 1

by using the same technique given in [4] is

\begin{matrix} ∥ F^{k + 1} - F^{k} ∥_{\infty} \leq (η β_{1} + τ β_{2} + ξ β_{3}) F_{k_{0}} G_{k_{0}}, \end{matrix}

(33)

where

F_{k_{0}}, G_{k_{0}}, k_{0} \geq 1

defined in (21) and (22),

β_{t} = {max}_{i, j} ∥ Δ_{i, j}^{0, t} ∥

, t = 1,2,3,

Δ_{i, j}^{k, 1} = p_{i + 1, j}^{k} - p_{i, j}^{k}, Δ_{i, j}^{k, 2} = p_{i, j + 1}^{k} - p_{i, j}^{k}, Δ_{i, j}^{k, 3} = p_{i + 1, j + 1}^{k} - p_{i, j + 1}^{k},

and η, τ and ξ are defined by

\begin{matrix} η_{1} = |a_{0, 0}| (\sum_{r = 1}^{t} |a_{0, r}| + \sum_{q = 1}^{t - 1} |{\tilde{a}}_{0, q}|), η_{2} = |a_{0, 0}| (\sum_{r = 1}^{t} |a_{1, r}| + \sum_{q = 1}^{t - 1} |{\tilde{a}}_{1, q}|) + \frac{1}{2}, \\ η_{3} = |a_{1, 0}| (\sum_{r = 1}^{t} |a_{0, r}| + \sum_{q = 1}^{t - 1} |{\tilde{a}}_{0, q}|), η_{4} = |a_{1, 0}| (\sum_{r = 1}^{t} |a_{1, r}| + \sum_{q = 1}^{t - 1} |{\tilde{a}}_{1, q}|) + \frac{1}{4}, \end{matrix}

\begin{matrix} τ_{1} = \sum_{r = 1}^{t} |a_{0, r}| + \sum_{m = 0}^{t} |a_{0, m}| \sum_{q = 1}^{t - 1} |{\tilde{a}}_{0, q}|, τ_{2} = \sum_{r = 1}^{t} |a_{0, r}| + \sum_{m = 0}^{t} |a_{1, m}| \sum_{q = 1}^{t - 1} |{\tilde{a}}_{0, q}|, \\ τ_{3} = \sum_{r = 1}^{t} |a_{1, r}| + \sum_{m = 0}^{t} |a_{0, m}| \sum_{q = 1}^{t - 1} |{\tilde{a}}_{1, q}| + \frac{1}{2}, τ_{4} = \sum_{r = 1}^{t} |a_{1, r}| + \sum_{m = 0}^{t} |a_{1, m}| \sum_{q = 1}^{t - 1} |{\tilde{a}}_{1, q}| + \frac{1}{2}, \end{matrix}

\begin{matrix} ξ_{1} = \sum_{r = 1}^{t} |a_{0, r}| (\sum_{r = 1}^{t} |a_{0, r}| + \sum_{q = 1}^{t - 1} |{\tilde{a}}_{0, q}|), ξ_{2} = \sum_{r = 1}^{t} |a_{0, r}| (\sum_{r = 1}^{t} |a_{1, r}| + \sum_{q = 1}^{t - 1} |{\tilde{a}}_{1, q}|), \\ ξ_{3} = \sum_{r = 1}^{t} |a_{1, r}| (\sum_{r = 1}^{t} |a_{0, r}| + \sum_{q = 1}^{t - 1} |{\tilde{a}}_{0, q}|), ξ_{4} = \sum_{r = 1}^{t} |a_{1, r}| (\sum_{r = 1}^{t} |a_{1, r}| + \sum_{q = 1}^{t - 1} |{\tilde{a}}_{1, q}|) + \frac{1}{4} . \end{matrix}

Finally,

\begin{matrix} η = m a x {η_{t}; t = 1, 2, 3, 4}, τ = m a x {τ_{t}; t = 1, 2, 3, 4}, ξ = m a x {ξ_{t}; t = 1, 2, 3, 4} . \end{matrix}

Theorem 5.

Under the same circumstances used in Theorem 4. Let

F^{\infty}

be the limit surface associated with the subdivision process. Then

∥ F^{\infty} - F^{k} ∥_{\infty} \leq (η β_{1} + τ β_{2} + ξ β_{3}) (\frac{{(F_{k_{0}} G_{k_{0}})}^{k}}{1 - F_{k_{0}} G_{k_{0}}}),

(34)

where

k_{0} \geq 1

is a natural number, such that

F_{k_{0}} G_{k_{0}} < 1

Remark 2.

Again

F_{1} G_{1}

is also equal to δ which is defined in [4].

Theorem 6.

Let k be the subdivision depth and let

\nabla^{k}

be the error bound between binary subdivision surface

F^{\infty}

and its k-level control polygon

F^{k}

. For arbitrary

ϵ > 0

, if

k \geq {log}_{{(F_{k_{0}} G_{k_{0}})}^{- 1}} (\frac{ψ}{ϵ (1 - F_{k_{0}} G_{k_{0}})}),

(35)

then

\nabla^{k} \leq ϵ

Proof.

Let

\nabla^{k}

denote the distance between limit curve

F^{\infty}

and initial curve (polygon)

F^{k}

at the k-th level. Then

\nabla^{k} = {∥ F^{\infty} - F^{k} ∥}_{\infty} \leq (η β_{1} + τ β_{2} + ξ β_{3}) (\frac{{(F_{k_{0}} G_{k_{0}})}^{k}}{1 - F_{k_{0}} G_{k_{0}}}) .

(36)

To obtain given error tolerance

ϵ > 0

the subdivision depth k satisfies the following inequality:

k \geq {log}_{{(F_{k_{0}} G_{k_{0}})}^{- 1}} (\frac{ψ}{ϵ (1 - F_{k_{0}} G_{k_{0}})}),

(37)

then

\nabla^{k} \leq ϵ

This completes the proof. □

Application for Bivariate Case

Here, we present some numerical examples to compute subdivision depths for subdivision surfaces. The associated constants

F_{k_{0}} G_{k_{0}}, k_{0} \geq 1

for some binary subdivision surfaces by using (21) and (22) are shown in Table 7. We see that the values of

F_{k_{0}} G_{k_{0}}

decrease with the increase of

k_{0}

. This is the advantage of our approach.

Example 6.

Given the initial polygon

F_{i, j}^{0} = F_{i, j}, i, j \in Z

and the values

F_{i, j}^{k}, k \geq 1

be described recursively by the tensor product of (28), then the subdivision depths for

F_{k_{0}} G_{k_{0}}, k_{0} \geq 1

by using Theorem 35 are shown in Table 8 and the comparison of the first and fifth convolution result is shown in Figure 2a.

Example 7.

Consider the tensor product of the 3-point approximating SS defined in (29). The mask of SS satisfies

F_{k_{0}} G_{k_{0}} < 1

, for

k_{0} \geq 3

. Therefore its subdivision depths can be computed at different values of error tolerance which are shown in Table 9. Here, the comparison of the third and fifth convolutions is demonstrated in Figure 2b.

Example 8.

Given that

f_{i, j}^{0} = f_{i, j}, i, j \in Z

, let the values

f_{i, j}^{k}, k \geq 1

be described recursively by the tensor product of (30). Then the subdivision depths for

F_{k_{0}} G_{k_{0}}, k_{0} \geq 1

by using Theorem 35 are shown in Table 10 which is illustrated in Figure 2c.

Example 9.

Consider the initial control polygon

f_{i, j}^{0} = f_{i, j}, i, j \in Z

and let the values

f_{i, j}^{k}

for all positive integers be defined recursively by the tensor product of (31). Then the subdivision depths for

F_{k_{0}} G_{k_{0}}, k_{0} \geq 1

are shown in Table 11. It is also presented with the help of the graph in Figure 2d.

Example 10.

Given the initial control polygon

f_{i, j}^{0} = f_{i, j}, i, j \in Z

and that the values

f_{i, j}^{k}, k \geq 1

can be described recursively by the tensor product of (32), then in Table 12, subdivision depths for

F_{k_{0}} G_{k_{0}}, k_{0} \geq 1

are presented and a graphical representation is shown in Figure 2e.

5. Conclusions

In this paper, the modified version of the numerical algorithm of [4,11,12] have been presented to compute the subdivision depths of the SSs for curves and surfaces design. Our algorithm can be used when the computation techniques of [4,11] fail. Moreover, we a smaller number of iterations to get the sharp subdivision depth compared to the existing algorithm. The proposed method is an efficient way of estimating subdivision depths for binary subdivision curves and surfaces.

Author Contributions

Conceptualization, F.K. and K.S.N.; Formal analysis, G.M. and D.B.; Methodology, A.G. and D.B.; Supervision, D.B.; Writing—original draft, A.S., F.K. and G.M.; Writing—review & editing, A.G. and K.S.N. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Conflicts of Interest

The authors declare no conflict of interest.

References

Barnhill, R.E.; Riesenfeld, R.F. Computer Aided Geometric Design; Academic Press: New York, NY, USA, 1974. [Google Scholar]
Faux, I.; Pratt, M. Computational Geometry for Design and Manufacture; Ellis Horwood: New York, NY, USA, 1979. [Google Scholar]
Huawei, W.; Youjiang, G.; Kaihuai, Q. Error estimation for Doo-Sabin surfaces. Prog. Nat. Sci. 2002, 12, 697–700. [Google Scholar]
Mustafa, G.; Chen, F.; Deng, J. Estimating error bounds for binary subdivision curves/surfaces. J. Comput. Appl. Math. 2006, 193, 596–613. [Google Scholar] [CrossRef] [Green Version]
Mustafa, G.; Hashmi, S.; Faheem, K. Estimating error bounds for non-stationary binary subdivision curves/surfaces. J. Inf. Comput. Sci. 2007, 2, 179–190. [Google Scholar]
Mustafa, G.; Deng, J. Estimating error bounds for ternary subdivision curve/surfaces. J. Comput. Math. 2007, 25, 473–484. [Google Scholar]
Mustafa, G.; Hashmi, S. Estimating error bounds for quaternary subdivision schemes. J. Math. Anal. Appl. 2009, 358, 159–167. [Google Scholar]
Mustafa, G.; Hashmi, S.; Noshi, N.A. Estimating error bounds for tensor product binary subdivision volumetric model. Int. J. Comput. Math. 2006, 83, 879–903. [Google Scholar] [CrossRef]
Mustafa, G.; Hashmi, S.; Faheem, K. Error bounds for $\sqrt{3}$ subdivision surfaces. J. Univ. Sci. Technol. China 2009, 39, 1–9. [Google Scholar]
Mustafa, G.; Hashmi, S.; Faheem, K. Subdivision depth for triangular surfaces. Alex. Eng. J. 2016, 55, 1647–1653. [Google Scholar] [CrossRef] [Green Version]
Mustafa, G.; Hashmi, S. Subdivision depth computation for n-ary subdivision curves/surfaces. J. Vis. Comput. 2010, 26, 841–851. [Google Scholar] [CrossRef] [Green Version]
Moncayo, M.; Amat, S. Error bounds for a class of subdivision schemes based on the two-scale refinement equation. J. Comput. Appl. Math. 2011, 236, 265–278. [Google Scholar] [CrossRef] [Green Version]
Dyn, N.; Gregory, A.; Levin, D. Analysis of uniform binary subdivision scheme for curve design. Constr. Approx. 1991, 7, 127–147. [Google Scholar] [CrossRef] [Green Version]
Chaikin, G.M. An algorithm for high speed curve generation. Comput. Graph. Image Process. 1974, 3, 346–349. [Google Scholar] [CrossRef]
Dyn, N.; Levin, D.; Micchelli, C.A. Using parameters to increase smoothness of curves and surfaces generated by subdivision. Comput. Aided Geom. Des. 1990, 7, 129–140. [Google Scholar] [CrossRef]
Dyn, N.; Floater, M.S.; Hormann, K. A four-point subdivision scheme with fourth order accuracy and its extensions. In Mathematical Methods for Curves and Surfaces: Modern Methods in Mathematics; Springer: Troms, Norway, 2004; pp. 145–156. [Google Scholar]
Dyn, N.; Levin, D.; Gregory, J.A. A 4-Point Interpolatory SS for Curve Design. Comput. Aided Geom. Des. Acad. Press. 1987, 4, 257–268. [Google Scholar] [CrossRef]
Weissman, A. A 6-Point Interpolatory Subdivision Scheme for Curve Design. Master’s Thesis, Tel Aviv University, Tel Aviv-Yafo, Israel, 1990. [Google Scholar]

Figure 1. The performance of different subdivision schemes for univariate case. Here k presents the subdivision depth (level of subdivision process) obtained after user-specified error tolerance.

Figure 2. Presents the performance of different subdivision schemes for bivariate case. Here k presents the subdivision depth (level of subdivision process) obtained after user-specified error tolerance.

Table 1. Associated constants of binary subdivision schemes (SSs).

Scheme/ $D_{k_{0}}$	$D_{1} = δ$	$D_{2}$	$D_{3}$	$D_{4}$	$D_{5}$
2-point scheme [14]	0.50000	0.25000	0.12500	0.06250	0.03125
3-point scheme [15]	1.50000	1.03125	0.83203	0.52685	0.36584
4-point scheme [16]	0.65625	0.36829	0.21610	0.12153	0.06912
4-point scheme [17]	0.80800	0.55800	0.40343	0.28765	0.20595
6-point scheme [18]	0.74200	0.44218	0.28589	0.18321	0.11768

Table 2. Subdivision depth of 2-point binary subdivision curve.

$D_{k_{0}}$ / $ϵ$	0.0008	0.00002	$7.87 \times 10^{- 7}$	$2.46 \times 10^{- 8}$	$7.69 \times 10^{- 10}$	$2.40 \times 10^{- 11}$
$D_{1} = δ$	6	11	16	21	26	31
$D_{2}$	3	5	8	10	13	15
$D_{3}$	1	3	5	7	8	10
$D_{4}$	1	3	4	5	6	8
$D_{5}$	1	2	3	4	5	6

Table 3. Subdivision depth of 3-point binary subdivision curve.

$D_{k_{0}}$ / $ϵ$	0.0086	0.0031	0.0011	0.0004	0.0001	$5.67 \times 10^{- 5}$	$2.07 \times 10^{- 5}$
$D_{3}$	19	25	30	36	41	47	52
$D_{4}$	4	5	7	9	10	12	13
$D_{5}$	2	3	4	5	6	7	8

Table 4. Subdivision depth of 4-point binary subdivision curve.

$D_{k_{0}}$ / $ϵ$	0.0092	0.0006	$4.43 \times 10^{- 5}$	$3.06 \times 10^{- 6}$	$2.11 \times 10^{- 7}$	$1.46 \times 10^{- 8}$
$D_{1}$	9	16	21	28	34	40
$D_{2}$	3	6	8	11	14	16
$D_{3}$	2	4	5	7	9	11
$D_{4}$	1	3	4	5	6	8
$D_{5}$	1	2	3	4	5	6

Table 5. Subdivision depth of 4-point binary subdivision curve.

$D_{k_{0}}$ / $ϵ$	0.0259	0.0053	0.00109	0.0002	$4.66 \times 10^{- 5}$	$9.59 \times 10^{- 6}$	$1.97 \times 10^{- 6}$
$D_{1}$	14	21	29	36	44	51	59
$D_{2}$	4	6	9	12	15	17	20
$D_{3}$	2	4	6	7	9	11	12
$D_{4}$	1	3	4	5	6	8	9
$D_{5}$	1	2	3	4	5	6	7

Table 6. Subdivision depth of 6-point binary subdivision curve.

$D_{k_{0}}$ / $ϵ$	0.0266	0.0031	0.0003	$4.35 \times 10^{- 5}$	$5.12 \times 10^{- 6}$	$6.02 \times 10^{- 7}$	$7.09 \times 10^{- 8}$
$D_{1}$	11	18	26	33	40	47	54
$D_{2}$	3	6	8	11	14	16	19
$D_{3}$	2	4	5	7	9	10	12
$D_{4}$	1	3	4	5	6	8	9
$D_{5}$	1	2	3	4	5	6	7

Table 7. Associated constants of binary SSs.

Scheme/ $F_{k_{0}} D_{k_{0}}$	$F_{1} G_{1} = δ$	$F_{2} G_{2}$	$F_{3} G_{3}$	$F_{4} G_{4}$	$F_{5} G_{5}$
2-point scheme [14]	0.50000	0.25000	0.12500	0.06250	0.03125
3-point scheme [15]	1.50000	1.00000	0.81250	0.60937	0.47265
4-point scheme [16]	0.77930	0.40902	0.20020	0.09959	0.04953
4-point scheme [17]	0.84500	0.43741	0.22635	0.11557	0.05801
6-point scheme [18]	0.89780	0.45218	0.23205	0.11764	0.05902

Table 8. Subdivision depth of 2-point binary subdivision surface.

$F_{k_{0}} G_{k_{0}}$ / $ϵ$	0.0020	0.00006	$1.96 \times 10^{- 6}$	$6.15 \times 10^{- 8}$	$1.92 \times 10^{- 9}$	$6.008 \times 10^{- 11}$
$F_{1} G_{1}$	6	11	16	21	26	31
$F_{2} G_{2}$	3	5	8	10	13	15
$F_{3} G_{3}$	2	3	5	7	8	10
$F_{4} G_{4}$	1	3	4	5	6	8
$F_{5} G_{5}$	1	2	3	4	5	6

Table 9. Subdivision depth of the 3-point binary subdivision surface.

$F_{k_{0}} G_{k_{0}}$ / $ϵ$	0.2688	0.1270	0.06007	0.0283	0.0134	0.0063	0.0029
$F_{3} G_{3}$	9	12	16	19	23	27	30
$F_{4} G_{4}$	2	4	5	7	8	10	11
$F_{5} G_{5}$	1	2	3	4	5	6	7

Table 10. Subdivision depth of 4-point binary subdivision surface.

$F_{k_{0}} G_{k_{0}}$ / $ϵ$	0.0192	0.0009	$4.72 \times 10^{- 5}$	$2.33 \times 10^{- 6}$	$1.15 \times 10^{- 7}$	$5.73 \times 10^{- 9}$
$F_{1} G_{1}$	18	30	42	54	66	78
$F_{2} G_{2}$	4	7	10	14	17	21
$F_{3} G_{3}$	2	4	6	8	9	11
$F_{4} G_{4}$	1	3	4	5	7	8
$F_{5} G_{5}$	1	2	3	4	5	6

Table 11. Subdivision depth of 4-point binary subdivision surface.

$F_{k_{0}} G_{k_{0}}$ / $ϵ$	0.0184	0.00107	$6.21 \times 10^{- 5}$	$3.6 \times 10^{- 6}$	$2.09 \times 10^{- 7}$	$1.21 \times 10^{- 8}$
$F_{1} G_{1}$	28	45	61	78	95	112
$F_{2} G_{2}$	4	7	11	14	18	21
$F_{3} G_{3}$	2	4	6	8	10	12
$F_{4} G_{4}$	1	3	4	5	7	8
$F_{5} G_{5}$	1	2	3	4	5	6

Table 12. Subdivision depth of 6-point binary subdivision surface.

$F_{k_{0}} G_{k_{0}}$ / $ϵ$	0.0313	0.0018	0.0001	$6.44 \times 10^{- 6}$	$3.80 \times 10^{- 7}$	$2.24 \times 10^{- 8}$
$F_{1} G_{1}$	47	73	99	126	152	178
$F_{2} G_{2}$	4	8	11	15	18	22
$F_{3} G_{3}$	2	4	6	8	10	12
$F_{4} G_{4}$	1	3	4	5	7	8
$F_{5} G_{5}$	1	2	3	4	5	6

© 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Shahzad, A.; Khan, F.; Ghaffar, A.; Mustafa, G.; Nisar, K.S.; Baleanu, D. A Novel Numerical Algorithm to Estimate the Subdivision Depth of Binary Subdivision Schemes. Symmetry 2020, 12, 66. https://doi.org/10.3390/sym12010066

AMA Style

Shahzad A, Khan F, Ghaffar A, Mustafa G, Nisar KS, Baleanu D. A Novel Numerical Algorithm to Estimate the Subdivision Depth of Binary Subdivision Schemes. Symmetry. 2020; 12(1):66. https://doi.org/10.3390/sym12010066

Chicago/Turabian Style

Shahzad, Aamir, Faheem Khan, Abdul Ghaffar, Ghulam Mustafa, Kottakkaran Sooppy Nisar, and Dumitru Baleanu. 2020. "A Novel Numerical Algorithm to Estimate the Subdivision Depth of Binary Subdivision Schemes" Symmetry 12, no. 1: 66. https://doi.org/10.3390/sym12010066

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

A Novel Numerical Algorithm to Estimate the Subdivision Depth of Binary Subdivision Schemes

Abstract

1. Introduction

2. Preliminaries Results

2.1. Univariate Case

2.2. Bivariate Case

3. Subdivision Depth for Binary Subdivision Curves

Application for Univariate Case

4. Subdivision Depth for Binary Subdivision Surfaces

Application for Bivariate Case

5. Conclusions

Author Contributions

Funding

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI