Research On Parameterization And Fitting Technologies In Geometric Modeling

Geometric modeling studies how to describe, analysis and processing 3D data using computers. It integrates the high speed, massive data processing capability of computer and the creative ability of human together. It plays an important role in speeding up product development, shortening the design cycle, improving quality, decreasing cost and enhancing enterprise's ability of market competition.Curve and surface modeling is one of the kernel technologies of geometric modeling. It studies how to describe the geometric shapes of free curves and surfaces using computers.The kernel problem of curve and surface modeling is how to represent free form curves and surfaces with computers, i.e., to find an effective method to satisfy the geometric design goals and represent geometric shapes conveniently. Compared with non-parametric representation, the parametric representation has many advantages. For a long time, parametric curves and surfaces have been the primary tools in geometric modeling and have become the standard of STEP (Standard for The Exchange of Product Model Data).According the initial information, curves and surfaces modeling can be divided into two methods. One is free form designing, based on control points and parameters, designers can define curves and surfaces and modify interactively until the shapes satisfy the design goal. The other is the technology of interpolation and approximation. Curves and surfaces reconstructed from the given points by interpolation are called as interpolation curves and surfaces or by approximation called as approximation curves and surfaces. These two methods are all influenced by parameterization. So curves and surfaces parameterization and the technologies of interpolation and approximation are the foundation of geometric modeling. In this dissertation we have made a systemic theoretic research on curves and surfaces parameterization and the technologies of interpolation and approximation and have obtained some new ideas on the following three aspects:1.The optimal polygonal approximation of parametric curves is studied The traditional approximation algorithms including parametric algorithm and geometric algorithm is discussed. Compared with parametric algorithm, the geometric algorithm can achieve fewer approximation points. Based on the traditional geometric approximation algorithm, this dissertation presents an optimal polygonal approximation algorithm. For the convex parametric curve, the algorithm provides a polygon with the minimal number of the points to approximate the parametric curve with a given tolerance. For each line segment except the last one on the polygon, the maximal distance to the curve is equal to the given tolerance, while the traditional geometric algorithm can't guarantee this. Beginning from the first endpoint of the curve or the last one, the algorithm may get different approximation polygon, but the same number of the points. With the properties of Bezier curve, a technique for reducing the computing complexity of the algorithm is presented, which makes the algorithm has the precise solution for approximating the Bezier curve of degree two.In the dissertation, three computing instances are given to compare new algorithm and traditional algorithm, verifying that new algorithm acquires the least number of approximation points within the same given tolerance.The algorithm's disadvantage is that, to concave parametric curves, the algorithm can't guarantee the optimal result. But the difference between our algorithm and optimal result isn't over the number of inflection points. As there are limit inflection points of a curve in practice, so our algorithm can achieve the almost optimal result.2. The optimal parameterization of parametric curves is studied.This dissertation exercises the freedoms of re-parameterization of polynomial curve segments to achieve a "parametric flow" closeness to unit-speed or arc-length representation. Rational re-parameterizations of a polynomial curve that preserve the curve degree and parameter domain are characterized by a single degree of freedom. The optimal re-parameterization in this family can be identified but the present method may exhibit too much residual parametric speed variation for motion control and other applications. In this dissertation, a re-parameterization method to optimal parameterization is presented and the optimal parameterization in this family satisfies that the maximum deviation from unit-speed is the minimum.This algorithm's disadvantage is that for a higher-order curve that has several undulations of its speed above and below unity, the scope for "damping" these variations by re-parameterization is rather limited, so our method can't guarantee the parametric speed of the optimal parameterization is close to unit speed everywhere.3. Curve fitting is studied.Spline function is widely used and has become the important method of construction curves. Fitting high intensity data points with traditional spline function causes too many curve segments and high costs. In this dissertation, based on quadratic spline, an algorithm is given to fitting high intensity data points. First, the algorithm approximates a set of ordered planar points with a polygon and divides these data points into subsets. The data points in a subset lie on a same line within the given tolerance, fitted by a quadratic curve segment and all data points are fitted by a C~1 quadratic spline curve. The algorithm preserves spline function 's simple computing, decreases the number of interpolation curve segments and holds the approximating accuracy. It can be used in fitting high intensity data points.The primary contributions of this dissertation are summarized as below:(1) The approximation of NURBS curves with line segments is studied. An optimal polygonal approximation algorithm is presented. For the convex parametric curve, the algorithm provides a polygon with the minimal number of the points to approximate the parametric curves with a given tolerance. For each line segment except the last one on the polygon, the maximal distance to the curve is equal to the given tolerance, while the traditional algorithm can't guarantee this. With the properties of Bezier curve, a technique for reducing the computing complexity of the algorithm is presented, which makes the algorithm has the precise solution for approximating the Bezier curve of degree two.(2) This dissertation exercises the freedoms of re-parameterization of polynomial curve segments to achieve a "parametric flow" closeness to unit-speed or arc-length representation. A re-parameterization method to achieve the optimal parameterization of polynomial Bezier curves is presented. The optimal parameterization in this family satisfies that the maximum deviation from unit-speed is the minimum.(3) Based on quadratic spline, an algorithm is given to fitting high intensity data points. The algorithm preserves simple computing of spline function, decreases the number of interpolation curve segments and holds the approximating accuracy. It can be used in fitting high intensity data points.This dissertation provides new methods to these above key problems in geometric modeling. The algorithm of optimal polygonal approximation of parametric curves will improve working efficiency in CNC; the optimal parameterization algorithm is valuable to the study of parametric theory and CAM practice; the fitting algorithm obtains a good result.