The Mask of Odd Points n-Ary Interpolating Subdivision Scheme

1. Introduction

Subdivision is an algorithmic technique to generate smooth curves and surfaces as a sequence of successively refined control polygons. We can survey subdivision as a process of taking a coarse shape and refining it to produce another shape that is more visually nice looking and smooth. Subdivision schemes are performed such that we take initial control polygon and make some iterations on it to make another shape. The resulting shape is then fed back into the subdivision scheme again and again until we get a reasonable level of detail. Beauty of this iterative process lies in elegant mathematical formulation and simple implementation.

Higher arity schemes are taking more attention now a days because of their useful and valuable properties. Higher arity schemes give a variety of different behaviors than lower arity schemes. It is noticed that higher arity schemes have higher smoothness and approximation order while their support is smaller compared to lower arity schemes. It is also observed that lower arity schemes have higher computational cost than higher arity schemes. Similarly increasing the number of points (complexity of the scheme) has also valuable upshots on smoothness of subdivision scheme.

There are many even-point n-ary subdivision schemes [1–5] in the literature for any n⩾2. Mustafa and Rehman [6] generalized and unified existing even-point n-ary subdivision schemes for any n⩾2.

There are also odd-point n-ary interpolating subdivision schemes [3, 7–9] in the literature for any odd n⩾3. So it is natural to look for a general formula which not only generalize and unify existing odd-point n-ary subdivision schemes but also provide the mask of higher arity schemes in a simple and efficient way. In this paper, we introduce an explicit formula which generalizes and unifies all existing odd-point n-ary interpolating subdivision schemes.

Subdivision scheme offers a well-defined and competent way to represent smooth curves but question arises: How well control polygon of subdivision scheme approximates the limiting curve? To answer this question error bounds of subdivision schemes are to be computed. In [10], Mustafa and Hashmi presented an algorithm to calculate error bounds of n-ary subdivision schemes. By making use of this algorithm we present a brief comparison of the error bounds of some of our schemes. The result shows that as we increase arity of subdivision scheme the error bound decreases.

A very frequent criterion to assess the worth of a subdivision scheme is its shape preserving properties. Convexity preservation is one of such properties. It is considered to be a geometrical property of subdivision scheme. So keeping this in mind, we describe convexity preserving property of one of the schemes. Moreover, some other important properties of subdivision like total absolute curvature and measure of deviation from convexity are also analyzed. Curvature is a geometrical criteria which truly describe the shape of objects. A brief comparison of our proposed family of schemes with other existing schemes is given. Some geometrical examples to show visual performance of scheme are also given.

The paper is organized as follows: in Section 2, some preliminary concepts are given, which are useful in the next sections. In Section 3, mask of odd-point n-ary scheme and some important results are given. In Section 4, comparison, application, error bounds, and total curvature of proposed family of schemes are presented. In Section 5, convexity preserving conditions of 5-point ternary scheme are derived. In the end of the paper, Section 6 which illustrates results and findings of the paper.

2. Preliminary Results

Here, we present some preliminary identities which play an important role in the construction of explicit formula for the mask of odd-points n-ary interpolating schemes for any odd n⩾3.

3. Mask of (2b + 3)-Point n-Ary Interpolating Scheme

In this section, we first find the mask of (2b + 3)-point ternary and quinary interpolating schemes then by induction, we formulate a general formula for the mask of (2b + 3)-point n-ary interpolating symmetric subdivision scheme.

By Lemmas 3.1 and 3.2 with change of notations and by induction, we get the following theorem.

4. Comparison, Applications, Error Bounds, and Total Absolute Curvature

In this section, first we present comparison of our proposed explicit formula with the existing explicit formula/algorithms for generating the masks of schemes. After that, we give visual performance among lower and higher arity schemes. Then we give a brief overview of error bounds of schemes. At the end, we give a comparison of total curvature of subdivision schemes for different arity with different complexity.

4.2. Applications

In Figure 1, we give comparison among different arity schemes generated in this paper to show their performance. Refined polygons generated by different arity schemes after first subdivision level are shown and compared in this figure. This figure indicates that higher arity schemes converge to limit curve faster than lower arity schemes.

4.3. Error Bounds

Subdivision is considered to be a very important tool in geometric modeling and shape designing. This approach is included in the control polygon paradigm. There arises an important question in the application of this type of procedure. How to estimate the error (distance) between limit curve and its control polygon? To respond this question, here we present a collection of expressions, inequalities, and results described in [10].

Given a control polygon composed of a sequence of control points $$, i ∈ ℤ, N⩾1. An n-ary subdivision curve (1.1) is re-defined by

$$ ()

where m > 0 and

$$ ()

The set of coefficients $$ is called subdivision mask. Given initial values  $$, i ∈ ℤ. Then in the limit k → ∞, the process (4.1) defines an infinite set of points in ℝ^N. The sequence of control points $$ is related, in a natural way, with the diadic mesh points $$, i ∈ ℤ. The process then defines a scheme whereby $$ and $$ replace the values $$ and $$ at the mesh points $$ and $$, respectively, while $$ is inserted at the new mesh points $$ for α = 1,2, …, n − 1.

Given initial control polygon $$, i ∈ ℤ, let the values $$, k⩾1 be defined recursively by subdivision process (4.1) together with (4.2). Suppose F^k is the piecewise linear interpolant to the values $$ and F^∞ is the limit curve of the process (4.1). If δ < 1 then the error bound between limit curve and its control polygon after k-fold subdivision is

$$ ()

where

$$ ()

where

$$ ()

also

$$ ()

where

$$ ()

Rest of the section is devoted to the computation of error bounds between limit curve and their control polygon after k-fold subdivision of (2b  +  3)-point n-ary interpolating scheme for different values of b ≥ 0, k ≥ 1, and  n ≥ 3, by using (4.3) with χ = 0.1.

Error bounds of proposed odd-point n-ary subdivision scheme at different subdivision levels are shown in Figure 2. From this figure, we have the following conclusions: Error bounds decrease with the increase of subdivision levels. Error bounds are directly proportional to the number of points involved (complexity of the scheme) to insert a point at next subdivision level. It is also observed that error bounds decrease with the increase of arity of the schemes.

4.4. Total Absolute Curvature

Here is the brief comparison of total absolute curvature (TAC) of interpolating subdivision schemes of different arity and complexity of the scheme. TAC of 3-point, 5-point, and 7-point interpolating scheme is computed by keeping arity 3. Also TAC is calculated for 3-point, 5-point, and 7-point interpolating scheme by keeping arity 5. Figure 3 shows graphical representation of TAC of subdivision schemes. Same initial polygon is taken for all subdivision schemes to compute TAC. From Figure 3, it is clear that as we increase the arity TAC is also increased and as we increase the complexity of the scheme TAC is decreased. Figure 4 presents comparison of TAC among different values of parameter of 3-point ternary interpolating scheme (3.21), here we set v₂ = v₁ − 1/3 and range of v₂ is (0.2222,0.3333). From Figure 4, it is clear that as we increase value of parameter from left to right in the parametric interval (0.2222,0.3333), TAC of 3-point ternary interpolating scheme (3.21) is decreased.

The total curvature and total absolute curvature are same for a closed convex polygonal curve and both are equal to 2π. Hence for a nonconvex curve the measure of deviation (referred as D) from the convex curve can be calculated by subtracting TAC of nonconvex curve from TAC of convex curve that is 2π. In Table 1, we have calculated measure of deviation of convexity of 3-point and 5-point ternary interpolating scheme at different subdivision level. Figure 5 presents graphical representation of measure of deviation of 3-point and 5-point ternary interpolating scheme.

Table 1. Measure of deviation of convexity of 3-point and 5-point ternary scheme. Here k presents the level of iteration and D is measure of deviation.

k	Scheme	D	Scheme	D
2	3-point	0.000000	5-point	0.000000
3	⋯	−0.716814	⋯	0.000000
4	⋯	−3.716814	⋯	−0.000001
5	⋯	−8.716814	⋯	−0.000011

5. Convexity Preservation of Subdivision Scheme

In this section, we discuss condition which guarantee convexity preservation of interpolating scheme. Here we derive conditions for convexity preservation of 5-point ternary interpolating scheme (3.20). Convexity of other schemes can be discussed analogously. We adopt the same procedure as described by [11].

5.1. Convexity Preservation of 5-Point Ternary Scheme

Let us suppose that the initial control points are strictly convex, that is,  $$ (by [12]). For v₂ = u and v₁ = u + 4/81, the scheme (3.20) for second-order divided differences $$ is given by

$$ ()

For simplicity, we put w = 4/9 + 18u, −7/18 < w < −1/3, in above three equations, we get

$$ ()

$$ ()

$$ ()

The conditions which guarantee the convexity preservation are as follows.

Theorem 5.1. Denote $$, $$ and let

$$ ()

If the initial control points are all strictly convex, −7/18 < w < −1/3 and

$$ ()

then the 5-point ternary scheme (3.20), for  v₂ = w and v₁ = w + 4/81 preserves convexity.

Proof. For convexity preservation it is sufficient to show that $$ and r^k > λ. We will use mathematical induction to prove $$ and r^k > λ. As we know that for k = 0, $$ and r⁰ > λ by (5.6). Let us suppose that $$ and r^k > λ. Now we will prove it for k + 1. To show $$, we have to show that $$, $$ and $$.

From (5.3), we have that

$$ ()

This implies for −7/18 < w < −1/3

$$ ()

From (5.3), we have that

$$ ()

This implies for −7/18 < w < −1/3

$$ ()

Similarly from (5.4), for −7/18 < w < −1/3 we have that

$$ ()

By combining (5.8), (5.10), and (5.11), we have $$.

Now we prove r^k+1 > λ.

For $$, we get

$$ ()

Now

$$ ()

Since both the numerator and denominator of above expression are positive for −7/18 < w < −1/3, therefore

$$ ()

This implies that for −7/18 < w < −1/3

$$ ()

For $$, we get

$$ ()

Now

$$ ()

Since both the numerator and denominator of above expression are positive for −7/18 < w < −1/3, therefore

$$ ()

This implies that for −7/18 < w < −1/3

$$ ()

Similarly by taking $$ and by using (5.3)–(5.6), we can easily show that for −7/18 < w < −1/3

$$ ()

Through the same channel for −7/18 < w < −1/3, we have

$$ ()

Similarly for $$ and by using (5.2), (5.4)–(5.6) for −7/18 < w < −1/3

$$ ()

Through the similar channel for −7/18 < w < −1/3, we have

$$ ()

By combining (5.15)–(5.23), we have $$, $$. Thus r^k+1 > λ. Since both conditions are satisfied so we concluded that 5-point ternary interpolating scheme (3.20) preserves convexity for v₂ = u and v₁ = u + 4/81.

Finally, we give an example to illustrate our result. Figure 6 shows the result after two iteration with u = −11/250. In this figure, the initial control polygon is convex and represented by dotted line and limit curve after two times iterations is represented by solid line and is also convex.

6. Conclusion

In this paper, we offered an explicit general formula to generate the mask of odd-points n-ary interpolating symmetric schemes for any odd n⩾3. From this formula one can easily generate the mask of odd-points, lower and higher arity interpolating schemes with and without free parameters. Moreover, odd-point n-ary schemes of Hassan and Dodgson [7], Zheng et al. [8], Lian [3, 9] are special cases of our proposed explicit formula. Moreover, we have concluded that error bounds between limit curve and control polygon of subdivision scheme at k-th level decreases with the increase of arity of the scheme. We also noticed that error bound is directly proportional to the number of points involved to insert new point in the control polygon (i.e., complexity of the scheme). We also calculated total absolute curvature for subdivision schemes having different arity and different complexity. We have concluded that total absolute curvature is directly proportional to arity and inversely proportional to complexity of the scheme. Convexity preservation is an important geometrical property of subdivision scheme. Therefore we discussed the convexity of some of our scheme. Convexity of other schemes can be discussed analogously.