Research And Application On Subdivision Schemes In Geometric Modeling

Subdivision method has become a powerful tool to describe curves, surfaces andother geometric objects recently. Subdivision allows to generate smooth curve andsurface by applying simple refinement rules to the given control polygon and controlmesh. After the first subdivision schemes were proposed in 1970 s, many peoplefocus their attention on this subject because of its efficiency and simplicity. So thatsubdivision is now an important subject in its own right with may applications in thefields like Computer Aided Geometric Design, Computer Graphics, ComputerAnimation, Surgical Simulation and Medical Image Processing etc. To extendapplication areas more widely, however, many problems have to be solved. Theproblems include constructing subdivision schemes of higher continuity, fusingsubdivision and analytic methods, developing mathematical tool for analysis ofsubdivision schemes and constructing new subdivision schemes satisfying all kinds ofrequirements etc. The thesis analyzes and investigates some effective subdivisionschemes for enhancing their modeling abilities. The major research contents andachievements of the thesis are the analysis of the control roles of the subdivisionparameters in the two existing interpolatory subdivision schemes, the constructionand analysis of some effective ternary subdivision schemes to elevate the ability ofmodeling smooth subdivision curves and surfaces and the quicker generation andgeometric construction methods for B-splines of arbitrary degree by using p-narysubdivision.After briefly reviewing the classification and history of curve and surfacemodeling, this thesis discusses the basic constructing ideas, the characters, thehistory, the classification, and the research contents of subdivision schemes. A surveyof interpolatory subdivision schemes is presented.Much work in the area of subdivision schemes has focused on the construction,convergence and smoothness analysis of a certain subdivision scheme and itsapplications in curve or surface modeling. Very little attention has been paid to thedeep analysis of the effect of the subdivision parameters involving in the subdivisionscheme on the shape of the subdivision curve. The thesis analyzes the control effectof the parameters in the 4-point binary and the 3-point ternary interpolatorysubdivision schemes on the shapes of the subdivision curves, especially, on the fractalbehavior. First this thesis analyzes their local effect on the shape of the subdivisioncurve segment near an arbitrary initial control point, then depicts their effect on thewhole subdivision curve. The relationships between the parameters and the fractal behaviors of the limit curves of the two schemes are presented at the first time. As anapplication of the obtained results, the generation of fractal curves and surfaces isdiscussed. Many examples show that the results presented in this thesis offer a directmeans for a fast generation of fractals.On the construction of subdivision scheme with good controllability, locality andsmoothness, the thesis first presents a non-uniform 3-point ternary interpolatorysubdivision scheme with variable subdivision parameters. Its support is computed.The C⁰ and C¹ convergence analyses are presented. To elevate its controllability, amodified edition with initial shape weights is proposed. For every initial control pointon the initial control polygon a shape weight is introduced. These weights can be usedto control the shape of the corresponding subdivision curve easily and purposefully.The role of the initial shape weight is analyzed theoretically. Then the application ofthe presented non-uniform 3-point ternary interpolatory subdivision schemes indesigning smooth interpolatory curves and surfaces is discussed. In contrast to mostof the conventional interpolatory subdivision schemes, the presented subdivisionschemes can be used to generate C⁰ or C¹ interpolatory subdivision curves or surfacesand control their shapes wholly or locally. Finally, as an application of the obtainedresults, a method of terrain generation is discussed, which can be used to generatecontrollable terrain.On ternary surface modeling scheme based on initial triangular control mesh thethesis first presents a ternary interpolatory subdivision scheme for initial regulartriangular control mesh based on interpolatory, 3^1/2-subdivision scheme. The limitsurface is C¹-continuous. But the stencils for new points are big and the shape of thesubdivision surface is determined only by the initial control mesh and can not beadjusted. To overcome the two shortcomings, the thesis then studies the constructionand the analysis of a kind of ternary interpolatory surface subdivision scheme withsubdivision parameter. By analyzing the discrete Fourier transforms of discretefunctions and the eigenstructure of the subdivision matrix the thesis puts forward thesufficient conditions on the convergence and G¹-continuity of the ternaryinterpolatory surface subdivision scheme with subdivision parameter. It is proved thatfor a certain range of the parameter the resulting surface can be G¹-continuous.On further discussion about C² ternary interpolatory subdivision scheme for curvemodeling the thesis presents a class of 4-point ternary interpolatory subdivisionschemes with two shape parameters which have distinct geometric characteristicsmotivated by the observation that existing interpolatory subdivision schemes eitherhave low continuity properties, such as the 4-point binary scheme proposed by Dyn,or their subdivision parameters are without explicit meaning, such as the 4-pointternary scheme proposed by Hassan et al. The two shape parameters are introduced to control and modify the shapes of the subdivision curves. The original 4-point ternaryscheme can be treated as a special case of this kind of subdivision. Three theoremsdescribing the convergence and the C¹ and C² continuity properties of the presentedschemes are derived and proved. Given original control data, using the presentedschemes one can not only model C¹ or C² smooth interpolatory curves easily andefficiently, but also can modify and control their shapes by choosing these twoparameters appropriately. Three examples of modeling interpolatory subdivisioncurves are given. To extend the application of the original 4-point ternary scheme inthe modeling of smooth curves with different continuity, some other importantproperties of this scheme such as the conditions of C⁰, C¹ continuous, H(?)lderexponent and the derivatives of the limit function are analyzed in this thesis. Itsapplication in function approximation is discussed. Finally a modified 4-point ternarysubdivision scheme is proposed to design smooth and open interpolatory curveswithout supplying any additional control points.On the p-nary subdivision and the geometric construction method of thegeneration of B-splines of arbitrary degree the thesis studies the p-nary subdivisionprocess for B-splines. Discrete convolution and generating polynomial are introducedto get the subdivision coefficients. The properties of the subdivision coefficients arediscussed. The subdivision formulae for rational and non-rational B-spline curves aregiven and proved. Based on the p-nary recursive subdivision algorithms of uniformB-splines of any degree presented in this thesis, a geometric construction method ofthe generation of uniform B-splines of arbitrary degree by using p-nary subdivisionscheme is obtained. Our methods are easy to implement, regardless of degree. Due tothe high performance property of p-nary subdivision algorithm, using the methodspresented in this thesis one can plot uniform B-splines of arbitrary degree effectivelyand rapidly.