Evaluation, Degree Reduction And Offset Approximation Of Curves And Surfaces

This thesis makes an in-depth study in three types of operations-evaluationfor Bezier curves and surfaces, offset approximation for Bezier curves and rational Bezier curves, degree reduction for NURBS curves and surfaces, all of which are of great importance in CAGD researches. Based on a systematic discussion on the contents, characteristics and the up-to-now accomplishments of these three operations in CAGD, we present our researches in three ways as follows:(1) Efficient evaluation for parametric curves and surfaces based on generalized Ball basesBased on the generalization of mathematical model of surface lofting program in the CONSURF system, two generalized Ball surfaces and the recursive algorithms for evaluating them are given. Furthermore, the conversion algorithms from Bezier form of a surface to these two generalized Ball forms are presented.Using the above algorithms, this thesis proposes two efficient algorithms for evaluating parametric surfaces. One is to use generalized Ball forms directly, and the other is to convert the given Bezier surface to generalized Ball surface, and then evaluate it. The examples and the corresponding time complexity analysis are given too.Theoretical analysis and example computations both show that the two new algorithms are more efficient than the de-Casteljau algorithm. Especially when Wang-Ball forms are used, the time complexity for evaluating would be reduced from cubic to quadratic, of the degree of the surface. If these algorithms are applied in display, interactive rendering, design, finding intersection, approximating and offsetting for surfaces, considerable economic results can be achieved.(2) Offset approximation for Bezier curvesThe problem of parametric speed approximation of a curve is raised. The author points out that the crux of offset curve approximation lies in the approximation of parametric speed. The parametric speed of the curve is firstly approximated by the Bezier polynomial which takes the lengths of control polygon's edges of the direction curve of normal as Bezier coordinates. Then the corresponding geometric offset approximation algorithm is given. Moreover, anoffset approximation with high precision is obtained by degree elevation of the direction curve of normal.After giving the Legendre polynomials approximation to parametric speed of the curve, the author gives the Jacobi polynomials approximation to parametric speed with endpoints interpolation. From this, two algebraic offset approximation algorithms, which preserve the direction of normal, are derived. The above idea is also applied to rational curves and an algorithm for offset approximation of rational Bezier curves is presented.The above algorithms for geometrical approximation and algebraic approximation to offset curves take a new look on offset researches. Most of offset approximation curves in the current investigations of offset approximation cannot preserve the normal direction of base curve generally. The author's work gives new way, which is beneficial to real time interaction and can efficiently reduce computing time as well as data storage amount. These algorithms can find good use in numerical machining, robotics, form-position tolerance and computer graphics.(3) Degree reduction for NURBS curves and surfacesBy applying the theory of the best uniform approximation of Chebyshev polynomials and the explicit matrix representation of NURBS curves, this thesis centers on the research of the explicit nearly best approximation of multi-degree reduction of NURBS curves. The necessary and sufficient condition for degree reducible NURBS curves in an explicit form is given. And a new way of doing degree reduction of NURBS curves is also presented in detail, including the multi-degree reduction of a NURBS curve on each knot span and the multi-degree reduction of a whole NURBS curve. The corresponding formula of error estimation and error bound are given also. Finally the algorithm is generalized to the cases of NURBS...