1. Introduction
Computer Aided Geometric Design (CAGD) considers the mathematical description of curves and surfaces utilized in computer graphics, data structure and computational algebra. CAGD has many fields of research interests. However, surface modeling is one of the important studies and an interesting area in the field of CAGD and computer graphics. Subdivision schemes (SSs) are iterative algorithms of surface modeling in CAGD. They are a type of models from discrete to discrete data having methods of generating curves/surfaces more effectively.
Nowadays, CAGD is the most common tool in the presentation of curves/surfaces. In CAGD, geometric shapes are related to the mathematical representations that satisfy approximation and interpolation properties of curves and surfaces. One of the common tools in CAGD are SSs, which provide an elegant way to describe curves and surfaces. Rham [1] was the first scholar who started work on SSs. He constructed a SS which generated a function with the first derivative. Chaikin [2] also used subdivision to design a curve. SSs gained importance when people generalized the tensor product in an arbitrary topology. This idea was presented by Doo and Sabin [3]. Catmull and Clark [4] used SSs to surface design and to control meshes in an arbitrary topology. Dyn et al. [5] generalized the SS of Dubuc and Deslauriers, known as butterfly SS, and concluded that the SS has smoothness in a certain range of shape parameter. In 1995, Dyn and Levin [6] introduced a technique for analyzing the Hermite-Type SSs for surface designs. In 1998, Stam [7] showed that surfaces and their derivatives can be described in terms of eigen basis functions. In 2002, Hassan et al. [8,9] worked on arity and number of control points. In 2005, Mustafa and Liu [10] worked on the SS of Bajaj with a new parameter that controlled the shape of models and gave them more flexibility to design a model over the soft and rough mesh network. Beccari et al. [11] produced an interpolating SS, which produced conic curve shapes. Mustafa et al. [12] unified the m-point approximating SS and showed that his SS has higher smoothness as compared to other SSs. Aslam et al. [13] introduced a formula that gives the mask of -point ternary interpolating as well as approximating SSs.
Zheng et al. [14] used B-spline to construct a -ary SS. In 2013, Mustafa et al. [15] worked on odd point ternary families of approximating SSs, in which they showed that their SSs have high smoothness. They also worked on subdivision regularization, in which they proposed that unified framework can work well for both over-fitting and noise removal in subdivision as well as regularization. In 2013, Ghaffar et al. [16] designed a three-point tensor product SS and showed some of its applications. Mustafa et al. [17] described a family of -point binary approximating SSs with tension parameters for generating curves. Again, Mustafa et al. [18] presented a general algorithm to generate a new class of binary approximating SSs and also have the derivation of some family members. In 2016, Hameed and Mustafa [19] constructed and analyzed binary SSs using Lane-Riesenfeld algorithm for curves and surfaces with Chaikin SS. In 2016, Ghaffar and Mustafa [20] proposed three different algorithms for approximating SS with application in curve modeling. In 2017, Cheng and Zhou [21] explained the necessary conditions of SSs with finite masks. During 2017, Akram et al. [22] discussed the properties of the binary four-point interpolating non-stationary SS [11]. In 2018, Manan et al. [23] focused on an algorithm to solve the third-order boundary value problem using eight-point approximating SS. In 2019, Kanwal et al. [24] formulated a numerical approximating collocation algorithm that is based on binary six-point approximating SS to generate the curves. Ghaffar et al. [25] introduced odd and even point non-stationary binary SSs for curve designing.
A simple smoothing tool for polygonal meshes is introduced which provide the motivation of our proposed work. The refine versions of the models are achieved by applying smoothing operation. The significance of the research problem to the success of such a model is that the transitions between the different resolutions of the meshes are almost imperceptible. This paper aims to construct a tensor product of nine-tic B-spline subdivision scheme to reduce the execution time needed to compute the subdivision process of quad meshes. The scheme, when computing the tetrahedron (four faces), as the number of faces increases, shows that the suggested technique performs better in model computation. The numerical results illustrate that the proposed SS reconstruct refined version of the models by using smoothing operation on regular meshes, but it doesn’t reproduced parametric curves/surfaces that have logarithmic functions and division terms i.e non-exponential polynomials, which actually needs non-uniform masks of SS for the exact reproduction of such models.
The remainder of this work is organized as follows. Section 2 describe properties of the SS. Section 3 is devoted to the construction and analysis of nine-tic B-spline tensor product SS. Section 4 gives numerical examples. Section 5 is concerned with the conclusion.
2. Properties of the SS
Here, firstly we introduce the nine-tic B-spline SS. We analyze the SS by examining the important features: continuity, hölder exponent, polynomial generation and reproduction, joint spectral radius, local analysis with invariant neighborhood and limiting curve produced by the nine-tic B-spline SS. It is defined as:
(1)
2.1. Smoothness of the SS
([26]). The SS is convergent if and only if the SS is contractive, then for contractiveness for some with , where are the coefficients of the SS with symbol .
If converges, then the limit curves can be denoted by . is the SS for the qth divided differences.
Laurent polynomial of proposed SS (Equation (1)) can be elaborated as:
whereTo prove continuity of the SS related to , we have to show the convergence of . To see this we generate another SS related to collected from as:
whereThe SS is contractive. For this, we have,
Thus, SS is contractive, is convergent and is continuous.
For continuity of the SS, we can rewrite as:
whereTo prove continuity of the SS related to , we have to show the convergence of . To see this, we generate another SS related to collected from as:
For the contractivity of the SS , we have
Thus, SS is contractive, is convergent and is continuous.
For continuity of the SS, we can rewrite as
whereTo prove continuity of the SS related to , we have to show the convergence of . To see this, we generate another SS related to collected from as:
For the contractivity of the SS , we have
Hence, the SS is contractive. This implies the has smoothness. □
2.2. Holder Exponent
Here, we find holder continuity of the nine-tic B-spline.
Consider that the SS (Equation (1)) with symbol produces limit curves with Holder continuity for some m.
The symbol of the SS (Equation (1)) is:
whereHere, and , which implies that □
2.3. Polynomial Generation and Reproduction
In this section, we discuss the degree of polynomial generation and polynomial reproduction of nine-tic B-spline SS.
The degree of polynomial generation of SS (Equation (1)) is 9.
Since the Laurent polynomial of the SS (Equation (1)) is
where then 9 is the degree of polynomial generation. which shows that degree of polynomial generation is 9. □The polynomial reproduction of SS (Equation (1)) is primal parameterization.
For any SS that generates linear functions with symbol
let attach the data to parameter(2)
then the SS also reproduces linear functions. The Laurent polynomial of the SS (Equation (1)) is:After putting , we get
Thus, the value of , putting the value of τ in above Equation (2):
Thus, the nine-tic B-spline SS generates linear reproduction with respect to primal parameterization. This SS is primal parameterization. □
2.4. Local Analysis with Invariant Neighborhood
In this section, we calculate the limit stencil of Nine-tic B-Spline SS by using local analysis. Using limit stencil, we locate the confine position of control point of initial control polygon on the point of confinement curve. For this, by considering the SS (Equation (1)), we can write it in matrix form as:
(3)
The local subdivision matrix of the presented SS is:
The proposed SS has invariant neighborhood size 9 and the corresponding eigenvalues of the subdivision matrix are . For eigenvectors related to eigenvalues, we obtain:
Thus,
and and the eigen decomposition of is whereUsing diagonalization process of a matrix , whereas ∧ = diagonal matrix, indicates that , where , and shows that Since ∧ is a diagonal matrix, for some diagonal matrix, means square of entries diagonally and so on. Thus,
In addition, then . Thus, using eigen decomposition of , we have, and so on. shows that Now, by applying limit , implies that .
Hence, the limit stencils are:
3. Construction and Analysis of Nine-tic B-Spline Tensor Product SS
3.1. Preliminaries
In this section, we construct nine-tic B-Spline tensor product SS. We analyze the SS by reviewing the continuity of the SS and limiting behavior of the curve generated by nine-tic B-spline tensor product SS. The Laurent polynomial of tensor product SS can be acquired by the accompanying principle:
(4)
where and are the Laurent polynomials of univariate SSs.A general compact form of binary SS which maps a polygon to a refined polygon is defined by
(5)
where for curve and for surface. In the case of univariate SSs, the two rules ( for u is even and odd) are given below as:Let , then
To get second rule, we assume , then
In the case of tensor product (bivariate) SS, we have four rules subject to the uniformity of each component in the multi-index .
A necessary condition for uniform convergence of SS (Equation (5)) is given in the following theorem.
([26]). Let be the symbol or Laurent polynomial of bivariate SS , which is defined on quad-meshes. Then, a necessary condition for the convergence of is:
(6)
This implies that:(7)
([26]). Suppose the SSs with symbols and , are both contractive, namely
for any initial data then the SS with the symbol: is convergent. Conversely, if is convergent, then and are contractive.([26]). Thus, convergence is checked in this case by checking the contractivity of two SSs If , which is typical for SSs having the symmetry of the square grid, then , and the contractivity of only one SS has to be checked.
([26]). Let
(8)
If the SSs with the masks(9)
are convergent, then generate function.([26]). For continuity of , we have to show that the SSs , corresponding to masks for are convergent and it is equivalent to checking whether SSs and corresponding to the masks and are contractive, which is equivalent to checking whether and , for some integer . Since there are four rules for computing the values at next refinement level, we define the norm as:
(10)
where3.2. Construction of Nine-tic B-Spline Tensor Product SS
Consider the proposed nine-tic B-spline SS (Equation (1)), and its mask is:
and its Laurent polynomial is given as:This implies that
Since , then we have the following Laurent polynomial of nine-tic B-spline SS :-
(11)
From Equation (1), we suggest the following nine-tic B-spline tensor product SS:
(12)
3.3. Analysis of Nine-tic B-Spline Tensor Product SS
In this section, we present continuous nine-tic B-Spline tensor product SS. To check the continuity of the nine-tic B-Spline tensor product SS (Equation (11)), we apply similar analysis tools to those in the case. From Equation (8) for and then from Equation (9), we get
This implies
If and are SSs corresponding to the masks and , respectively, then
andThis implies
andBy utilizing Equation (10), we get
(13)
(14)
Let be the SS corresponding to the Laurent polynomial, then, by using Equation (10), from Equations (13) and (14), we have that are contractive, thus by Theorem 7, the SSs , corresponding to masks for are convergent. Hence, by Theorem 8, the proposed SS is continuous.
By applying the above procedure repeatedly, we found that the proposed SS has continuity (the proof is given in Appendix A).
4. Numerical Examples
In this section, performance of our nine-tic B spline tensor product SS is discussed. The refinement algorithm of nine-tic B spline tensor product SS creates a new vertex position corresponding to both vertex and face of the original mesh. It is observed that the new vertices are weighted averages of the vertex points belonging to each pair (face, vertex) of the original mesh. For the nine-tic B spline 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.
The refined model is generated from the control polygon in the following way. Each vertex point is obtained in the proportion of [10: 120: 252: 120: 10:]/512 and each edge point is obtained in the proportion of [1: 45: 210: 210: 45: 1:]/512. A face point is achieved as the centroid of every mesh of the given control polygon, and vertex point is achieved as the normal of a vertex mesh in the control polygon. The new points are then associated with each other. There are two edges along each side of each vertex of the previous mesh. These pairs are related and form quadrilaterals over the old edges. Inside every control polygon, there are the same number of new vertices. These are related to each other inside the control polygon. Lastly, around every old vertex there is another vertex in the adjoining corner of each old polygon. These are associated to form another polygon with the same number of edges. The new mesh generates quadrilaterals for each edge in the old vertex, and makes a little n-sided polygon. Each n-sided polygon produces a n-sided polygon for each n-valence (valence being the number of edges that touch the vertex). After the first iteration of our SS, all vertices have a valence of four, thus resulting applications generate quadrilaterals for the vertices. To make a smooth model, the SS is applied repeatedly. In Figure 1, Figure 2 and Figure 3, show the visual performance of our proposed SS. We used MATLAB software for the implementation of our proposed SS as a plug in inanimation and modeling industry and achieved required refine model after applying the 5th level of the proposed SS.
Comparison of NURBS & Proposed SS
This section defines the comparison of the proposed scheme with NURBS. The NURBS is either a torus, disk or a tube and many NURBS patches are applied to form a surface models as shown in Figure 4. After the deformation of the NURBS surfaces, the cracks appears at the joints. In Figure 1, Figure 2 and Figure 3 shows that continues surfaces are generated as the limit of a sequence of successive refinements. All theother properties such as efficiency, compact support, local definition, affine invariance, simplicity and smoothness are the same properties as the NURBS have, but it will work for any topology. Subdivision is a data structure used to store mesh data in a convenient way so that the mesh information can be easily accessed. It is clearly seen that proposed SS shows smoothness in generating different curves.
5. Conclusions and Future Work
This paper contributes the nine-tic B-spline approximating bivariate SS to reduce the execution time needed to compute the subdivision process of quad meshes. We have discussed some interesting features such as polynomial generation, smoothness, joint spectral radius, holder continuity, limit stencils of the proposed SS. We used Laurent polynomial (symbol) method to find the smoothness of our proposed SS and it is observed that our proposed SS gives good results for modeling of curves and surfaces as shown in figures. There are many directions of future work. Firstly, spreading of tensor product SS to a mesh with arbitrary topology. We are also interested to work on reproducing exact surface models by SS. If we could generate exact surface models having singular points, we will be able to solve some additional issues regarding SS.
Author Contributions
Conceptualization, A.G., M.B. and M.I.; methodology, K.S.N. and D.B.; software, A.G., S.M.H. and R.M.; validation, A.G. and K.S.N.; formal analysis, S.M.H., D.B. and R.M.; writing—original draft preparation, A.G., M.I., M.B., S.M.H. and R.M.; writing—review and editing, K.S.N. and D.B.
Funding
This research received no external funding.
Conflicts of Interest
The authors declare no conflict of interest.
Appendix A
To check continuity, we now take in Equation (8) and then from Equation (9), we get
If and are a SSs corresponding to the mask and for , then
This implies
By utilizing Equation (10), we get,
(A1)
(A2)
(A3)
(A4)
(A5)
(A6)
(A7)
(A8)
(A9)
(A10)
(A11)
(A12)
(A13)
(A14)
(A15)
(A16)
(A17)
(A18)
(A19)
(A20)
(A21)
(A22)
(A23)
(A24)
(A25)
(A26)
(A27)
(A28)
(A29)
(A30)
(A31)
(A32)
(A33)
(A34)
(A35)
(A36)
(A37)
(A38)
From Equations (A1)–(A38), we see that are contractive, thus, by Theorem 7, the SSs , corresponding to masks , for are convergent. Hence, by Theorem 8, proposed SS is continuous.
Figures
Figure 1. (a) The initial polygon; and (b–f) the results up to fifth subdivision levels.
Figure 2. (a) The initial polygon; and (b–f) the results up to fifth subdivision levels.
Figure 3. (a) The initial polygon; and (b–f) the results up to fifth subdivision levels.
Figure 4. (a) The results of the NURBS; and (b–f) the deformation of a surface made of NURBS patches.
Figure 4. (a) The results of the NURBS; and (b–f) the deformation of a surface made of NURBS patches.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
© 2019 by the authors.
Abstract
In this paper, we propose and analyze a tensor product of nine-tic B-spline subdivision scheme (SS) to reduce the execution time needed to compute the subdivision process of quad meshes. We discuss some essential features of the proposed SS such as continuity, polynomial generation, joint spectral radius, holder regularity and limit stencil. Some results of the SS using surface modeling with the help of computer programming are shown.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
Details





1 Department of Mathematical Sciences, Balochistan University of Information Technology, Engineering and Management Sciences (BUITEMS), Quetta 87300, Pakistan
2 Department of Mathematics, NCBA&E, Bahawalpur 63100, Pakistan
3 Department of Mathematics, SBK Women University, Quetta 87300, Pakistan
4 Department of Mathematics, College of Arts and Sciences, Prince Sattam bin Abdulaziz University, Wadi Aldawaser 11991, Saudi Arabia
5 Department of Mathematics, Cankaya University, Ankara 06530, Turkey; Institute of Space Sciences, Magurele-Bucharest 76900, Romania