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 0 then the scheme Sa 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).