Geometric Approximation And Graphics Transformation In Shape Modeling

This thesis centers on two types of graphics operation techniques——geometric approximation and graphics transformation, which are of great importance in CAGD researches.Geometric approximation in computer aided geometric design studies the problem of how to use other simple curve/surface to substitute the original complicated objects by applying the way of approximation. In this thesis, our studies in this area include offset approximation, PH approximation, degree reduction approximation, approximate merging and approximating rational curve by polynomial curve based on degree elevation of weight function.Graphics transformation in computer aided geometric design aims at the problem of gradually changing graphics or identical conversion of graphics. In this thesis, our studies in this area include shape blending of artistic brushstrokes and the conversion between different basis functions.Based on a systematic discussion on the contents, characteristics, significance and the up-to-now accomplishments of the two techniques, we present our innovative results in several ways as follows:(I) Geometric approximation(1) The traditional way of offset approximation is using polynomial functions, which will directly result in high degree of approximation functions. In this thesis, it is pointed out that the crux of offset curve approximation lies in the approximation of parametric speed. Based on the Jacobi polynomials approximation with endpoints interpolation of parametric speed of the curve, algebraic rational approximation algorithms of offset curves, which preserve the direction of normal, are derived. The above idea is applied to rational curves and an algorithm for offset approximation of rational Bézier curves is presented.(2) The Pythagorean-hodograph curves offer unique computational advantages in computer aided design and manufacturing, for their arc lengths are expressible as polynomial functions of the parameter and their offsets are rational curves. But recent researches of PH curves including interpolation and approximation have not strengthened much attention to the geometric parameters of the curve, which leads to the result that the designed curves lack geometric intrinsic property. Our study deals with the cubic PH curves, which are most commonly used in design. A system of geometric parameters based cubic PH curve interpolation and approximation algorithms are presented. The essential geometric parameters include the ratioρof the adjacent control polygon legs, the control polygon angleθ, the first control polygon leg L, the included angle 8 between the first control polygon edge and the edge joining the origin O and the first control point, as well as the coefficient Dir of curve rotation. For the problem of end points interpolation of a cubic PH curve, the condition equations in terms of Bernstein-Bézier forms are presented. Furthermore the problem of PH curve approximation with endpoints interpolation to a cubic non-PH curve is studied, including the algorithms based on different geometric parameters input {δ,θ}, {ρ,θ} and {ρ,δ} respectively. The corresponding error bounds are also obtained.(3) The difficulty of degree reduction of NURBS surfaces lies in the complicated dealing process with knots. Based on the explicit matrix representation of NURBS surfaces and combing with the theory of Chebyshev polynomials approximation, a new method of degree reduction of NURBS surfaces is presented, including the degree reduction of a NURBS surface on each knot span region and the degree reduction of a whole NURBS surface respectively. The error bound is also provided. Multi-degree reduction of a whole NURBS surface includes multi-degree reduction to each surface segment respectively and calculating the weighted average of the obtained control points, of which the subscripts are the same. The new algorithm can do multi-degree reduction each time and the degree reduced NURBS surfaces have explicit representations. The optimal or nearly optimal uniform approximation is obtained for the degree reduction of NURBS surfaces.(4) The approximate merging problem of multiple adjacent Bézier curves by a single Bézier curve is needed in industry, but lacks researching. In this thesis, a unified matrix representation for precise merging is given first, and then by introducing the Moore-Penrose generalized inverse matrix, the approximate merging curve can be achieved. Continuity at the endpoints of curves is discussed in the merging process also.(5) The problem of approximating rational curves by polynomial curves is studied in this thesis. The contradictory equations of precise approximating rational curve by polynomial curve are deduced first. Then based on the theory of generalized inverse matrix, the least square solution in matrix form is obtained. Combined with degree elevation of the function which takes the weights of the original rational curve as Bézier lengths, new way of approximating rational curve by polynomial curve can be achieved. In this way, one can get better approximating result with less error, while meanwhile preserves the same approximating degree. (II) Graphics transformation(1) Artistic brushstrokes are of great use in industry, but are cost consuming. An algorithm for automatically generating in-between frames of two artistic brushstrokes is presented. The basic idea is to represent the two key frames of artistic brushstrokes in disk B-spline curves, and then make blending of their geometric intrinsic variables. Given two key frames of artistic brushstrokes, the skeleton curves can be obtained by certain skeleton based techniques. After generating the disk B-spline representation of the key frames, interpolation of the intrinsic variables of the initial and the target disk B-spline curves is carried out. This method can efficiently create in-between frames of artistic brushstrokes.(2) B-spline basis is widely used in construction of curves and surfaces for its excellent property of being totally positive and locally adjustable. In the year 2003, Delgado and Pe(n|～)a had given another new form of curve, which is constructed by a new totally positive basis (DP-NTP basis). This kind of curve shows obvious advantage in computing, for the reason that it has linear complexity. Meanwhile, it has good shape preserving property. But regretfully it is not locally adjustable as how B-spline curves do. As to achieve the advantages of both, and as well make exchanging and transferring data possible between various systems, the conversion between uniform B-spline curves and DP-NTP curves is presented. This result can be widely used in efficient evaluation of locally adjustable curves and surfaces.