Construction Of Exponentials Reproducing Subdivision Schemes And Rapid Evaluation Of Interpolatory Subdivision Surfaces

Subdivision method has been a powerful tool to generate surfaces with arbitrary topology by applying simple refinement rules to the given control mesh.Subdivision surfaces are a topic of practical importance in Computer Graphics,Computer animation. Computer Aided Design etc.The last few years have seen rapid development of fairly comprehensive theories and algorithms for basic surface subdivision,reaching a certain level of maturity.However,most of the research on subdivision focused on construction, analysis of convergence and smoothness,applications and other fields based on polynomial reproducing schemes.And much more works should be done in some fields such as construction and theoretical analysis of non-stationary schemes,special curves(e.g. conics) reproduction,exactly evaluation of non-polynomial schemes(e.g.interpolatory schemes) etc.Firstly a brief review of the background,main advantages,developing history and main research fields of subdivision are given.Then some necessary definitions and lemmas on subdivision methods,and two classifications of subdivision schemes and basic knowledge of convergence and smoothness are introduced as well.In this dissertation. we proposed a complete theoretical framework on the non-stationary subdivision schemes reproducing exponential polynomial spaces,and a class of Hermite type schemes reproducing conics,a class of evaluation algorithms for interpolatory subdivision surfaces and other non-polynomial subdivision schemes.More work which focused on stationary schemes has been done.Unfortunately,generally speaking,only polynomial surfaces can be reproduced by stationary schemes,but some other simple curves such as conics are difficult to obtain by stationary subdivision schemes.We propose a novel approach to construct non-stationary subdivision schemes with a tensor control parameter which can reproduce functions in a finite-dimensional subspace of exponential polynomials.The construction process is mainly implemented by solving linear systems for primal and dual subdivision schemes respectively,which are based on different parameterizations.The schemes constructed in this dissertation contain most of the interpolatory subdivision schemes reproducing polynomials.The rule at refinement level k,operates on values taken from an exponential polynomial of the aforesaid space,reproducing values of the same exponential polynomial at refinement level k + 1.Compute the mask after giving the system according to the reproduction condition.Also,the existence and uniqueness of the solution are analyzed.The space of exponential polynomials is derived from constant differential equation and the discrete values of the same function can be obtained from the corresponding difference equation. Since the refinement is operated on the values of equidistant parameters,there is a strong connection between mask and difference equation and some specific formations of the mask are mainly based on this fact.In this dissertation,the masks we construct for polynomials is easy to compute and some uniform expressions are given.As a necessary step,the convergence and smoothness are analyzed and there are stationary subdivision schemes which are asymptotically equivalent to the non-stationary schemes in this dissertation. Hence the smoothness order can be given based on classical theorem.As a special case,the conic curves can be reproduced easily by our construction method.Since there are tensor control parameters in our schemes,we can select the parameters to make the schemes reproduce polynomials.In order to reproduce conics exactly,we propose a Hermite subdivision scheme with a tensor parameter to control the shapes of the limit curves.The scheme can also represent elements in cubic polynomials,trigonometric functions and hyperbolic functions. Through solving the linear system associated with the functions,the scheme mask is obtained. The convergence and smoothness of the scheme are also given by the power tools - asymptotic equivalence and traditional results of linear Hermite-interpolatory schemes. The scheme provides users with a tensor parameter which can control the shapes very well.Through proper adjustment within its range of definition,the scheme can reproduce cubic polynomials,trigonometric functions and hyperbolic functions.Moreover,for certain given parameters,all conic sections can be reproduced exactly by this scheme.The convergence analysis of the subdivision method is given as well.Finally,we illustrate the effects of using the tension parameter and tangent vectors to generate different subdivision curves.In many applications such as fitting,reparameterization and resampling,it is required to evaluate points on the subdivision surfaces at an arbitrary domain location. The interpolatory subdivision scheme is widely used due to its behavior of preserving old vertices on the initial mesh.However,unlike approximating schemes,the geometry of the limit surface obtained via interpolatory subdivision schemes does not have closed-form analytic expression even for a regular mesh,so it is very difficult to evaluate limit surfaces generated by the interpolatory schemes.This dissertation presents a new method for exact evaluation of a limit surface generated by stationary interpolatory subdivision schemes and its associated tangent vectors at arbitrary rational points.The algorithm is designed based on the parametric m-ary expansion and construction of associated matrix sequence.The evaluation stencil of the control points on the initial mesh is obtained, through computation by multiplying the finite matrix sequence corresponding to the expansion sequence and eigen decomposition of the contractive matrix related to the period of rational numbers.The evaluation of the surfaces with extraordinary vertices(EOP) is quite simple.The method proposed in this dissertation works for other non-polynomial subdivision schemes as well.An method for evaluation of Butterfly subdivision surfaces is given.The algorithm is proposed based on the parametric binary decomposition,matrix eigen-decomposition and related operations.A method of local parameterization of Butterfly limit surfaces is given through analysis of the local refinement behavior.The weights associated with control points on the initial mesh are obtained by computation of the matrix sequences corre-sponding to the decomposition sequences.We give the method around EOP to evaluate the surfaces generated by arbitrary topology meshes.Some remeshing examples via our evaluation algorithm are given as well.The algorithm is independent of the mesh data. structure,avoiding those exhausting operations such as computation of neighborhoods, and can be generalized to other triangular interpolatory subdivision schemes easily,e.g. 3^1/2 subdivision scheme.