ABSTRACT

In this paper, we propose and analyze a tensor product subdivision scheme which is the extension of three point scheme for curve modeling. The usefulness of the scheme is illustrated by considering different examples along with its application in surface modeling.

1. Introduction

Surface modeling method is one of the important study contents in the fields of computer aided geometric design and computer graphics. Subdivision methods are effective algorithms of surface modeling in computeraided geometric design. They are a kind of models from discrete data to discrete data, so they are fast methods of producing curves and surfaces. Subdivision modeling methods have been developed fast since 90’s and they combine excellences of polygon modeling and NURBS (NonUniform Rational B-Spline) modeling. So subdivision modeling has an extensive application in computer animation and movies, CAD, finite element analysis, etc.

The initial subdivision schemes were proposed in the late seventies [1,2], while later researches have been focused generally on the properties of the limit surfaces, such as smoothness [3,4] and evaluation [5]. Properties of subdivision surfaces are now well understood, making them attractive in geometric design applications. Hoppe et al. [6] presented a method to reconstruct piecewise smooth surface models from scattered range data using a variation of Loop’s scheme [7]. Morin et al. [8] addressed the issue of reconstructing rotational features in surfaces as special cases. Jena et al. [9] presented a non-interpolatory scheme for tensor product bi-quadratic trigonometric spline surfaces. Li and Zheng [10] presented a new perspective for constructing interpolatory subdivision from primal approximating subdivision. The new perspective also showed a link between those classic approximating and interpolatory subdivision schemes.

In this paper, we restrict ourselves to binary case. The simplest way to extend univariate scheme to bivariate scheme is tensor-product scheme. Laurent polynomial of tensor product scheme can be obtained by the following rule.

(1.1)

where and are the Laurent polynomials of univariate schemes.

A general compact form of binary subdivision scheme S which maps a polygon to a refined polygon is defined by

(1.2)

where for curves and for surfaces.

In the case of bivariate subdivision scheme there are four rules depending on the parity of each component in the multi-index. Writing all the multi-indices by components, we have four rules

A necessary condition for uniform convergence of scheme (1.2) is given in the following theorem.

Theorem 1.1. [11] Let

be the symbol or Laurent polynomial of bivariate subdivision schemes, which is defined on quad-meshes. Then a necessary condition for the convergence of is

(1.3)

this implies

(1.4)

Theorem 1.2. [11] Suppose the schemes with symbols

and

, are both contractive, namely

for any initial data f ⁰ then the scheme S_a with the symbol

is convergent.

Conversely, if is convergent then and are contractive.

Remark 1.1. Thus convergence is checked in this case by checking the contractivity of two subdivision schemes

and If, which is typical for schemes having the symmetry of the square grid, then, and the contractivity of only one scheme has to be checked.

Theorem 1.3. [11] Let

(1.5)

If the schemes with the masks

are convergent, then generates function.

Remark 1.2. For continuity of, we have to show that the subdivision schemes, corresponding to masks for are convergent and it is equivalent to checking whether schemes and corresponding to the masks

and

are contractive, which is equivalent to checking whether

and for some integer

. Since there are 4 rules for computing the values at next refinement level, we define the norm

where

The rest of this paper is organized as follows. In the next section we briefly review the construction of a 3- point tensor product scheme. We discuss the continuity of these schemes in Section 3. Finally, in Section 4 we present some examples of surfaces generated with our new algorithm and conclude in Section 6.

2. Construction of 3-Point Tensor Product Binary Scheme

In this section, we present continuous, 3-point tensor product binary approximating scheme. Consider the mask of 3-point binary univariate subdivision scheme proposed in m-point approximating scheme [12], for particular value of we get

and its Laurent polynomial is given as

This implies

Since then we have the following Laurent polynomial of 3-point tensor product binary approximating scheme

(2.1)

From (2.1), we suggest the following 3-point tensor product binary approximating scheme

(2.2)

Analysis of 3-Point Tensor Product Scheme

To check the continuity of the 3-point tensor product scheme (2.2), we apply similar analysis tools to those in the univariate case for the bivariate subdivision schemes defined on regular quadrilateral meshes.

From (1.6) for and then from (2.1), we get

This implies

If and are subdivision schemes corresponding to the masks and respectively, then

and

This implies

and

By utilizing (1.7), we get

(2.3)

and

(2.4)

From (2.3) and (2.4), are contractive, so by the Theorem 1.2, the subdivision schemes, corresponding to masks for are convergent. Hence by Theorem 1.3, the proposed scheme is continuous.

To check continuity we now take in (1.6) and then from (2.1), we get

,

,

.

If and are a subdivision schemes corresponding to the masks and respectively, then for, we get

,

,

,

,

,

.

This implies

By utilizing (1.7), we get

(2.5)

(2.6)

(2.7)

(2.8)

(2.9)

(2.10)

From (2.3)-(2.10), are contractive, so by the Theorem 1.2, the subdivision schemes, corresponding to masks for are convergent. Hence by Theorem 1.3, the proposed scheme is continuous.

To check continuity we now take in (1.6) and then from (2.1), we get

,

,

.

.

.

If and are a subdivision schemes corresponding to the masks and respectively, then for, we get

,

,

,

,

,

,

,

,

,

.

This implies

,

,

,

,

,

,

,

,

By utilizing (1.7), we get

(2.11)

(2.12)

(2.13)

(2.14)

(2.15)

(2.16)

(2.17)

(2.18)

From (2.3)-(2.18), are contractive, so by the Theorem 1.2, the subdivision schemes, corresponding to masks for are convergent. Hence by Theorem 1.3, the proposed scheme is continuous.

3. Numerical Examples

In this section, the performance of our 3-point tensor product binary approximating scheme is shown. The refinement algorithm of 3-point tensor product scheme involves computing a new vertex corresponding to each (vertex, face) pair of the original mesh. The new vertices are found as weighted averages of the points belonging to each face of the original mesh. For the 3-point tensor product case, these weights (going around a face) are

. The newly created vertices are then connected to form the faces of the refined control mesh. We have implemented our new scheme as a plugin in our modeling and animation, by using MATLAB software. We are able to obtain the required model after 6th subdivision level of the proposed scheme. In Figures 1(a)-(d), models of visual performance of our proposed scheme are displayed.

4. Conclusion and Future Work

In this paper, we employ Laurent polynomial method to analyze the continuity of the proposed scheme. The motivation behind our work was to provide users with a simple smoothing tool for polygonal meshes. The smoothing operation allows users to create refined versions of their models. Crucial to the success of such a model is that the transitions between the different resolu-

tions of the meshes are almost imperceptible. The examples show that our scheme can generate good models by using regular meshes, but cannot reconstruct parametric surfaces that contain non-exponential polynomials such as a logarithmic functions and division terms, which actually require non-uniform masks of subdivision for the exact reconstruction of such functions. Nor can it handle a mesh with arbitrary topology. There are several areas for future work. First of all, extending our scheme to a mesh with arbitrary topology is an immediate challenge. We would also like to work on regenerating exact surface normal by subdivision. And if we could reconstruct surfaces containing singular points we would be able to address many additional interesting applications.

5. Acknowledgements

This work is supported by the Beijing Municipal Natural Science Foundation (4102027), the National Natural Science Foundation of China (60973101) and Higher Education Commission of Pakistan (HEC).

REFERENCES