Subdivision Curves And Surfaces Modeling With Geometric Constraints And Subdivision Parametrization

With the rapid development and wide application of computer science, subdivisionhas become a powerful tool in the fields of computer aided design (CAD) and computergraphics (CG). Many subdivision schemes have been proposed in the recent three decades,but most of them have the difficulty of controlling the shape of limit curves or surfaces, andcan not satisfy the requirements of fine design in mechanism. So, in this theis, we discussthe problems of subdivision curves and surfaces design with some geometric constraintsand surface parametrization. We propose an algorithm to design a subdivision curvesatisfying given arc length constraint by adjusting the tension parameter, and we proposea modified 4-point approximating subdivision rule with local interpolated constraint tointerpolate a point or a curve. And we also give a novel parametrization algorithm basedon the approximating property of the modified 4-point approximating subdivision.This thesis reviews the general situation and history of subdivision at first, andappraises some research results and applications of subdivision. At the same time, weintroduce the researches on continuity analysis of subdivision, and several kinds of subdi-vision schemes in common use, especially 4 kinds of newly proposed 4-point approximatingsubdivision schemes which are the bases of our research in this thesis.There are usually some geometric or physical constraints in practical product design.For example, the design of the air-path in an airplane is to construct a smooth surfacewith constrained area. In the surface design of airplane or automobile, the aerodynamics,even aesthetics should be considered. In computer animation, the length of frameworkof objects should be kept in true and natural deformation. In this thesis, we discuss thesubdivision curve design with arc length constraint by using of the four newly proposed 4-point approximation subdivision schemes by adjusting the tension parameter. A sufficientcondition for the feasibility of the arc length constrained subdivision curve design is given.After extending the 4-point approximating subdivision schemes to non-stationary ones,we give sufficient conditions for C~1 continuity of the 4-point approximating subdivisionschemes. For the arc length constrained curve design problem, we find a kind of specialcontrol polygon named (strong) degenerated control polygon and prove the relationship between the strong degenerated control polygon and the degenerated control polygon. Anew algorithm of generating accurate circle based on arc length constrained subdivisionis given which facilitates the design of surfaces of revolution.There are two kinds of subdivision schemes according to the relationship of subdivi-sion limit surfaces and their control meshes: interpolatory subdivision and approximatingsubdivision. While interpolatory subdivision usually does not generate faring curves orsurfaces due to disturbance of initial data. For some interpolation requirements, approx-imating subdivision schemes should be modified to satisfy local interpolated constraint.In this thesis, we propose a modified 4-point approximating subdivision method with lo-cal interpolated constraint, the modified limit curve could interpolate any of the initialcontrol vertices, it is C~2 continuous except at the interpolated vertex where it is C~1 con-tinuous. We give a G~1 smooth condition for two subdivision curves or surfaces meetingat a common vertex or curve based on the modified 4-point approximating subdivision.We also extend the 4-point approximating curve subdivision to surface case on arbitrarytopological meshes. This novel surface subdivision produces limit surface of C~2 continu-ous on regular meshes, and C~1 continuous limit surfaces on irregular meshes. The novelsubdivision will become the famous Catmull-Clark subdivision if the tension parameteris set to be 0. The surface subdivision is also modified to interpolate a given C~1 parametercurve. It can interpolate not only on the boundary but also in the interior of the controlmesh, and the curve to be interpolated could be an arbitrary C~1 parameter curve.Parametrization of triangular mesh has become a key topic in CAGD because it playsan important role in texture mapping, spline surface approximation, scattered data fitting,animation, multi-resolution analysis, etc. In this thesis, we propose a new parametrizationmethod based on the approximating property of the 4-point approximating subdivision.By proving that the approximating property is the same as cubic B-spline subdivision and4-point interpolatory subdivision that they can approximating a C~2 smooth function tothe second order, we propose a simple mesh approximating algorithm by using subdivisionschemes, and the parametrization algorithm is a linear search on the subdivision surface,the parameter of the nearest vertex on subdivision surface is the required parametervalue. This algorithm can be considered as an extension of the chordal parametrizationto surface case. Since there is no computation of linear system of equations in the novelparametrization method, it is shown through some numerical examples in this thesis thatthe algorithm is faster than some classical surface parametrization methods when thenumbers of vertices and triangles are large. The technology of image matching plays an important role in computer vision andits application in engineering. Not only the accuracy but also the computation speed isusually considered by many scholars. In the last of the thesis, a fast image matchingalgorithm is given, and it could be used for real-time computation.