﻿ Construction and Application of Subdivision Surface Scheme Using Lagrange Interpolation Polynomial

Applied Mathematics
Vol.5 No.3(2014), Article ID:42744,11 pages DOI:10.4236/am.2014.53040

Construction and Application of Subdivision Surface Scheme Using Lagrange Interpolation Polynomial

Faheem Khan*, Noreen Batool, Iram Mukhtar

Department of Mathematics, University of Sargodha, Sargodha, Pakistan

Email: *fahimscholar@gmail.com, noreen_batool@yahoo.com, irammukhtar1133@hotmail.com

Received April 22, 2013; revised May 22, 2013; accepted May 30, 2013

ABSTRACT

This paper offers a general formula for surface subdivision rules for quad meshes by using 2-D Lagrange interpolating polynomial [1]. We also see that the result obtained is equivalent to the tensor product of (2N + 4)-point n-ary interpolating curve scheme for N ≥ 0 and n ≥ 2. The simple interpolatory subdivision scheme for quadrilateral nets with arbitrary topology is presented by L. Kobbelt [2], which can be directly calculated from the proposed formula. Furthermore, some characteristics and applications of the proposed work are also discussed.

Keywords:Subdivision Scheme; Interpolating Subdivision Scheme; Tensor Product Scheme; Auxiliary Points; Lagrange Interpolation Polynomial

1. Introduction

There are two general classes of subdivision schemes, namely, approximating and interpolating schemes. The limit curve of an approximating scheme usually does not pass through the control points of control polygon. As the level of refinement increases, the polygon usually shrinks towards the final limit curve. The interpolating schemes are more attractive than approximating schemes because of their interpolation property. All vertices in the control polygon are located on the limit curve of the interpolation scheme, which facilitates and simplifies the graphics algorithms and engineering designs.

Lian generalized the classical binary 4-point and 6-point interpolatory subdivision schemes to a-ary setting for any integer a ≥ 3. After that, the a-ary 3-point and 5-point interpolatory subdivision schemes for curve design for arbitrary odd integer a ≥ 3 [3,4] were introduced. After that, Lian [5] investigated both the 2m-point, a-ary for any a ≥ 2 and (2m + 1)-point, a-ary for any odd a ≥ 3 interpolatory subdivision schemes for curve design. Ko [6] presented explicitly a new formula for the mask of (2N + 4)-point binary interpolating and approximating subdivision schemes with two parameters. The proposed work presents a new observation about the curve case given by Najma [7]. In this work, we avoid finding the mask of subdivision schemes separately, as a result, its approach is simple and avoids complex computation when deriving subdivision rules.

The rest of the paper is organized as follows. Section 2 gives some preliminaries results and a new relation for (2N + 4)-point n-ary interpolating curve scheme for closed and open polygon to access main result. Section 3 presents the construction for general formula of the surface case using Lagrange interpolating polynomial, and some characteristics are also discussed. In Section 4, we also give some numerical examples for the visual performance of the proposed work. This work also provides some special cases of the classical subdivision schemes.

2. Preliminary Results

Let be the set of integers and a set of constants. The general form of univariaten-ary subdivision scheme which maps a polygon is defined by

(2.1)

where the set of coefficients is called mask of the subdivision scheme. A necessary condition for the uniform convergence of the subdivision scheme is

(2.2)

Let be the space of all polynomials of degree. Where, is a non-negative integer. If

is fundamental Lagrange polynomial corresponding to the nodes defined by

(2.3)

for which

and

where, is the Kronecker delta, defined as

(2.4)

Using all the above mentioned identities Ko [6] presented the general formula for the mask of -point binary interpolating symmetric subdivision schemes. After that Najma [7] generalized the result for -point n-ary interpolating symmetric subdivision scheme and gave the following formula for the mask of n-ary interpolating schemes.

(2.5)

where

and

(2.6)

The free parameters can be explicitly defined as

where.

Here, n stands for n-ary subdivision scheme (i.e. n = 2(binary), 3(Ternary), 4(quaternary)···),. Considering the symmetry of the scheme and construction of the mask formula described above, -point interpolating subdivision schemes are presented in the following form

(2.7)

Here, with the symmetry condition is

Setting and, the mask of the schemes comes from the generalized formula for the mask of -point interpolating schemes (2.5). Following the procedure of binary case, we have derived the following form of -point ternary interpolating subdivision schemes are presented in the following form

(2.8)

Here, and for the symmetry condition,

Setting and, the mask is calculated from the same mask formula (2.5). In the same way, -point quaternary interpolating subdivision scheme has the form

(2.9)

where, and for the symmetry of the scheme,.

Setting and. Finally, from (2.7)-(2.9), -point n-ary interpolating schemes has the following form

(2.10)

With, and for the following symmetry condition

(2.11)

where and.

Construction of the Schemes for Open Polygon

When dealing with open initial polygon it is not possible to refine the first and last edges by rules (2.10) for interpolating subdivision schemes. However the extension of this strategy to deal with open polygon requires a well-define neighborhood of end points. Since the first and last edges can be treated analogously, it will be sufficient to derive the rules only for one side of the polygon. To this aim define the auxiliary point as extrapolatory rule in the initial polygon. Then the nonrefined open polygon

can be refined by the rules defined below. The formula described in (2.10) for interpolating scheme is not helpful to refine first and last edges of open polygon. Then to refine the open polygon by

-point interpolating scheme using auxiliary points is defined as following

(2.12)

where, , where, the weights satisfies the same condition (2.11).

Example: If an open polygon is refined by using the 6-point ternary interpolating subdivision scheme using (2.10), then two auxiliary points and has to be defined in the coarsest polygon

. The first two edges and of the nonrefined polygon can be refined by the rules that can be calculated directly by (2.12). Substituting in (2.12),

where

Then, for,

For,

3. Tensor Product of (2N + 4)-Point Interpolating Subdivision Scheme

Given a set of control points where k is a non-negative integer indicates the subdivision level. n-ary subdivision surface is tensor product of n-ary subdivision curve defined by

(3.1)

where, satisfies

(3.2)

Given initial values then in the limit, the process (3.1) defines an infinite set of points in. The sequence of values is related, in a natural way, with a diadic mesh points

The process then defines a scheme whereby replaces the value at the mesh point for, while the values are inserted at the new mesh points for (where α and β are not zero at the same time). Labeling of old and new points is shown in Figure 1, which illustrates subdivision schemes (3.1).

(a)(b)(c)

Figure 1. Solid lines show one face of coarse polygons whereas dotted lines are refined polygons. (a)-(c) can be obtained by subdividing one face into four, nine and sixteen new faces by using (3.1) for n = 2,3,4 respectively.

Construction

Let be the set of integers and the space of all polynomials of degrees and is denoted by and respectively. If are fundamental Lagrange interpolating polynomials corresponding to the nodes and. The Lagrange interpolation polynomial for tensor product case is defined as [1],

where

(3.3)

and are Kroneker delta symbols defined as,

and

Here, some important results for the formulation of required form of tensor product scheme can be verified using (2.3). That is for each and (Using the result [1]),

The mask of a subdivision scheme shows the contribution of a single original vertex to each new, subdivided vertex. To find the mask of a scheme, we need to find all ways to get from the origin to each point in the grid. For the tensor product scheme, this is simply the tensor product of the univariate case.

Lemma 3.1. [8] Given initial control polygon,，let the values be defined recursively by subdivision process (3.1) together with (3.2) then the scheme derived by tensor product naturally get four-sided support region.

It can be loosely say that the support is the tensor product of the supports of the two regions, just as one can loosely say that Doo-Sabin is the generalization of the tensor product of two Chaikin constructions.

Lemma 3.2. [9] Given initial control polygon , let the values be defined recursively by subdivision process (3.1) together with (3.2), then if a scheme is derived from a tensor product, then the level of continuity can be determined between pieces by reference to the underlying basis functions, i.e. all the tensor product schemes have the same continuity as their counterparts.

The general formula which generates the mask and of n-ary approximating schemes presented by [7] is

(3.4)

and

(3.5)

where

Here, n, m stands for n-ary, m-ary subdivision schemes respectively (i.e n, m = 2(binary), 3(ternary), 4(quaternary)···), , , , and

The free parameter and are defined as

(3.6)

where and

(3.7)

where.

As each mask of the refinement rule satisfies, where are the mask of univariate subdivision schemes, then

.

The tensor product of -point interpolating subdivision scheme is presented as,

(3.8)

where, , , and and symmetry conditions are,

(3.9)

Taking, and the constants and could be evaluated by using the results (3.4) and (3.5).

Example: Consider the tensor product of the 4-point DD interpolating subdivision scheme, while DD scheme can be calculated using the result (2.5) mentioned in Section 2. The Laurent polynomial of the scheme is given as

This implies

Since, then, we can obtain the Laurent polynomial of the 4-point tensor product binary interpolating scheme. So that the suggested 4-point tensor product binary interpulating scheme is

(3.10)

Using the result obtained above for the tensor product of interpolatory scheme (3.8), tensor product of 4-point DD scheme can be calculated directly. Since the DD scheme has continuity, then by lemma (3.2) its tensor product has the same continuity. Substituting in (3.8) and (3.9), and, the symmetry conditions becomes

(3.11)

then formula (3.8) attains the form,

(3.12)

As each mask of the refinement rule satisfies, then

As so for both n and m, when, , and is substituted in (3.8) and (3.9) our requirement is fulfilled, that is the rules (3.10) are obtained.

Example: A simple interpolatory subdivision scheme for quadrilateral nets with arbitrary topology is presented by L. Kobbelt [2] which generates surfaces in the limit. In the first step they present the refinement rules derived by the modification of the well-known Dyn et al. [10] 4-point interpolatory subdivision scheme for curve design. The natural way to define refinement operators for quadrilateral nets is therefore to modify a tensor product scheme such that special rules for the vicinity of non regular vertices are found.

The modified form of Dyn scheme can be evaluated by setting the value of n = 2, N = υ = 0, and (where) in (2.10) and (2.11), the following refinement rules are obtained

(3.13)

They used the simple tensor product as the basis for the modification of refinement rules of irregular quadrilateral nets. Since it is interpolating scheme, so and the edge points and are given as,

Finally, the face point is,

(3.15)

Instead of taking the tensor product the above rules can be directly obtained by substituting in (3.8) and (3.9), then and, the symmetry conditions are then written as,

(3.16)

then the formula (3.8) acquires the form,

(3.17)

At each mask of the refinement rule satisfies, then

Using the result (3.4) and (3.5) the constants are evaluated by substituting, , and for both n and m. After substituting the weights in (3.17) we get the same rules (3.14) and (3.15).

Example: Using the results for the interpolating curve subdivision schemes (2.10) the 4-point interpolatory scheme [3] is obtained. Further here the tensor product of the scheme is evaluated by using the result (3.8).

Put in (3.8),

(3.18)

Also, from (3.9)

Taking, , ,. Also for interpolatory scheme, as gives for both n and m.

After calculating the mask from (3.4) and (3.5) and substituting all the results in equation (3.18) following 4-point ternary interpolating tensor product scheme is obtained

(a)(b)(c)(d)

Figure 2. Performance of tensor product of 4-point ternary interpolating scheme: (a), (b), (c) and (d) show the initial polygon, 1st, 2nd subdivision levels and limit surface respectively. (a) Initial polygon; (b) 1st level; (c) 2nd level; (d) Limit surface.

(a)(b)(c)(d)

Figure 3. Performance of tensor product of 4-point binary interpolating scheme: (a), (b), (c) and (d) show the initial polygon, 1st, 2nd subdivision levels and limit surface respectively. (a) Initial polygon; (b) 1st level; (c) 2nd level; (d) Limit surface.

(3.19)

4. Numerical Examples

Here, the performances of some of the schemes which are deduced from the proposed formula are shown. Figure 2 shows the tensor product of 4-point ternary interpolating scheme (3.19), and Figure 3 gives the performance of the proposed 4-point binary scheme (3.10).

REFERENCES

1. G. Dahlquist and A. Bjork, “Numerical Methods in Scientific Computing,” SIAM, Vol. 1, 2008. http://dx.doi.org/10.1137/1.9780898717785

2. L. Kobbelt, “Interpolatory Subdivision on Open Quadrilateral Nets with Arbitrary Topology,” Computer Graphics Forum, Vol. 15, No. 3, 1996, pp. 409-420. http://dx.doi.org/10.1111/1467-8659.1530409

3. J. A. Lian, “On A-Ary Subdivision for Curve Design: 4-Point and 6-Point Inerpolatory Schemes” Application and Applied Mathematics: International Journal, Vol. 3, No. 1, 2008, pp. 18-29.

4. J. A. Lian, “On A-Ary Subdivision for Curve Design. II. $3$-Point and $5$-Point Interpolatory Schemes,” Applications and Applied Mathematics: International Journal, Vol. 3, No. 2, 2008, pp. 176-187.

5. J. A. Lian, “On A-Ary Subdivision for Curve Design. III. 2m-Point and (2m+1)-Point Interpolatory Schemes,” Applications and Applied Mathematics: International Journal, Vol. 4, No. 2, 2009, pp. 434-444.

6. K. P. Ko, “A Study on Subdivision Scheme-Draft,” Dongseo University Busan South Korea, 2007. http://kowon.dongseo.ac.kr/$\sim$kpko/publication/2004book.pdf

7. G. Mustafa and A. R. Najma, “The Mask of (2b+4)-Point n-Ary Subdivision Scheme,” Computing, Vol. 90, No. 1-2, 2010, pp. 1-14.

8. M. Sabin, “Eigenanalysis and Artifacts of Subdivision Curves and Surfaces,” In: A. Iske, E. Quak and M. S. Floater, Eds., Tutorials on Multiresolution in Geometric Modelling, Chapter 4 Springer, Berlin, 2002, pp. 51-68.

9. N. A. Dodgson, U. H. Augsdorfer, T. J. Cashman and M. A. Sabin, “Deriving Box-Spline Subdivision Schemes,” Springer-Verlag, Berlin, 2009, pp. 106-123.

NOTES

*Corresponding author.