Modelling Methods Of Subdivision And Fitting In CAGD

In this paper,we have made a systemic theoretic research on modelling methods of subdivision and fitting in CAGD.The creative productions are given as follows.At first,we prove that the degree elevation of B-spline curves is corner cutting and point out the geometric meaning of the auxiliary control points during the corner cutting.Given a B-spline curve,in each step we only increase the multiplicity of one knot and elevate the degree only in this knot interval.Then the old basis functions can be represented by no more than 2 new basis functions,so the new control points can be represented by no more than 2 old control points,i.e.,the new control points are derived from the old control points by corner cutting. When the multiplicities of all the knots are increased,we obtain the control points of the degree-elevation curve by corner cutting.To elevate the degree of B-spline curves just in one knot interval per step,we define the bi-degree B-spline basis functions by the integer definitions of spline functions.The transformation formulas between usual and bi-degree B-spline basis functions lead to the corner cutting for degree elevation of B-spline curves.The auxiliary control points during the corner cutting are the control points of the bi-degree curves.Secondly,we propose a local fitting algorithm for converting smooth planar curves to B-splines.For a smooth planar curve a set of points together with their tangent vectors are first sampled from the curve such that the connected polygon approximates the curve with high accuracy and inflexions are detected by the sampled data efficiently.Then,a G¹ continuous Bézier spline curve is obtained by fitting the sampled data with shape preservation as well as within a prescribed accuracy. Finally,the Bézier spline is merged into a C² continuous B-spline curve by subdivision and control points adjustment.The merging is guaranteed to be within another error bound and with no more inflexions than the Bézier spline.In addi- tion to shape preserving and error control,this conversion algorithm also benefits that the knots are selected automatically and adaptively according to local shape and error bound.A few experimental results are included to demonstrate the validity and efficiency of the algorithm.Thirdly,we propose a incentres subdivision scheme for curve interpolation.The scheme is said to be incentres subdivision scheme due to the fact that the new added vertex corresponding to an edge is the incentres of a triangle which is defined by the edge and two tangent lines of its end points.Given a sequence of vertices and their tangent vectors,using a three-vertex based tangent adjusting method,a G² continuous and shape preserving curve is obtained by the incentres subdivision scheme.With a five-vertex based tangent adjusting method,the incentres subdivision scheme can generate a spiral from a two-point G¹ Hermite data.By the incentres subdivision scheme,separate line segments can be inserted into a subdivision curve with curvature continuity.If all the initial vertices and their initial tangent vectors are sampled from a circular arc segment,the arc segment will be reproduced.The convergence and smoothness analysis of this new scheme are also provided.Several examples are given to demonstrate the excellent properties of the scheme.At last,we propose a method for interpolating arbitrary topology meshes using the approximation subdivision scheme.For approximation subdivision scheme such as Loop subdivision scheme, the limit points of a vertex can be computed by explicit formula.Using the formula we propose a very simple and efficient method to interpolate meshes by approximation subdivision scheme.We give the explicit formula of the new vertices corresponding the edges and vertices.Though we only discuss the Loop subdivision scheme in this paper,the method can be used to other subdivision schemes such as Catmull-Clark subdivision scheme,3^1/2 subdivision scheme and so on.