Three Kinds Of Geometric Approximation In Curves And Surfaces Modeling

For data compression or easy computation in computer aided geometric design(CAGD), curves and surfaces in simple form are usually used to replace the existing curves and surfaces such that the geometric error between them is minimized. This approximation is different from traditional function approximation. Its approximation object is geometry. And its approximation error is geometric position error. So it is called geometric approximation, which is an important subject in geometric design. In this paper we make a systemic theoretic research on the techniques of three geometric approximation, that is the approximation of degree reduction and derivative bounds for parametric curves and surfaces, and piecewise linear approximation of rational triangular surfaces. The main creative results are presented as follows.(1) In respect of degree reduction of Bezier curves:we present an algorithm for optimal explicit multi-degree reduction of Bezier curves with constraints of parametric continuity or geometric continuity at two endpoints. With endpoints high interpolation, we decompose the control points of degree-reduced curves into two parts, constrained control points and unstrained control points by using the method of'divide and conquer'. The constrained control points can be easily derived by the interpolation condition. The others are derived by using the orthonormality of Jacobi polynomials and the least square method of unequally accurate measurement. This algorithm has several advantages including maintaining high continuity at the two endpoints of the curve, doing multi-degree reduction only once, using explicit approximation expressions, estimating error in advance, low time cost and high precision. Particularly, by taking the approximation error as the objective function and minimizing this function, the optimal explicit solution to multi-degree reduction of Bernstein polynomials with high geometric continuity at the two endpoints is given. And then the optimal explicit solution to multi-degree reduction of Bezier curves with G1 constraints is also given. The control points of the degree reduced curves and the approximation error are derived from two matrix representations respectively while the existing algorithm only provides a numerical solution for degree reduction of curves with G1 continuity. These results can be extensively applied to data communication, data compression, interactive integration and intersection finding in CAD/CAM systems.(2) In respect of degree reduction of tensor product Bezier surfaces:we present optimal explicit multi-degree reduction under three different constraints. When the corners and boundaries of the surface are not constrained, we apply the transformation relation between Bernstein and Jacobi polynomials, and then obtain the matrix representation of the control points of degree-reduced surfaces and the approximation error. When interpolating four corners of high degree, the optimal multi-degree reduction of Bezier surfaces is achieved by applying dimension reduction method in surface control points in a least squares minimization manner. When keeping boundary curves continuity, the optimal degree reduction of the surface is obtained by least-squares subtracting the degree-reduced surface from the original surface. After using the degree reduction to the piecewise surfaces, the resulting piecewise approximating surfaces can keep original continuity. It meets the design requirement of CAD/CAM.(3) In respect of degree reduction of triangular Bezier surfaces:we present an algorithm for optimal explicit multi-degree reduction of triangular Bezier surfaces with boundary C1 continuity. This algorithm is suitable for performing degree reduction of joined patches and subdivision patches. First, we sort the two-dimensional control points of triangular Bezier surfaces in a row vector. And then using the property of bivariate Jacobi basis functions, we obtain explicit representation of the optimal degree-reduced surfaces and the approximation error in both boundary constraints and corners constraints. This method has entirely three fine characters, easy performing, high precision and high speed.(4) In respect of improving derivative bounds of rational parametric curves and surfaces: to improve derivative bounds of rational parametric curves and surfaces, we use a particular linear fractional transformation to reparameterize the curves and surfaces. After reparameterization, the control points and the parameter domain remained unchanged. What changes were only the weights and the parameter distribution. Using reparameterization technique, two methods were given to optimize the reparameterized weights. One was to minimize the maximal ratio of the weights; another was to minimize the variance of the log weights. Then the tighter bounds on derivatives of the reparameterized rational curves and surfaces were obtained based on the existing results. So this algorithm improves the results and efficiencies of the geometry design system.(5) In respect of piecewise linear approximation of rational parametric surfaces:we present a piecewise linear approximation of rational parametric surfaces which are defined in any arbitrary triangle. Using the reparameterization technique, we improve the effect of piecewise linear approximation of rational triangular Bezier surfaces. This is useful in surfaces intersection and surfaces rendering.