Research On Geometric Approximation Problems In Curves And Surfaces Modeling

The knowledge and advancement of CAD/CAM in a country partially determines its degree of automation. As curve and surface modeling techniques form the foundation of CAD/CAM, the precision of the representation of curves and surfaces and the flexibility of the modeling techniques are two key factors that determine how powerful a CAD system is. Spurred by the national 863 project——product modeling and system design GEMS 5.0 based on wireframe, surfaces modeling, solid modeling, and features——this dissertation focuses on solving geometric approximation problems in curve and surface modeling. The major contributions of this dissertation are summarized as follows.1. The polygonal approximation problem is a primary problem in computer graphics, pattern recognition, CAD/CAM, etc. For the two dimensional case, the CIM (Cone Intersection Method) is one of the most efficient algorithms for approximating polygonal curves. Without imposing any additional constraint or changing the error criteria, this dissertation extends the original CIM to solve the three dimensional LS-WMN problem (the weighted minimum number polygonal approximation problem with the line segment error criterion). Its time and space complexities are O(n~3) and O(n~2) respectively. We also present an approximation algorithm that takes O(n~2) time and O(n) space. Results of some examples are given to illustrate the efficiency of these algorithms.2. To describe the tool path of a CNC (Computerized Numerical Control) machine, it is often to approximate curves by G~1 arc splines with the number of arc segments as small as possible. There are two main methods for constructing G~1 arc splines——via biarcs and via single arcs. This dissertation corrects some prevalent errors found in the formulae of the method via biarcs. For the method via single arcs, we present two kinds of bisection algorithms for approximating quadratic Bezier curves, one of which has less time complexity, and produces fewer arcs, than traditional algorithms. 3. This dissertation proposes the generalized B divided difference, with which the mth derivative of B-spline curves of order k can be obtained directly without the need to oompute the first (m-1) derivatives as before. Based on the generalized B divided difference, the necessary and sufficient condition for degree-reducible B-spline curves is presented. Algorithms for degree reduction of B-spline curves are also proposed using the constrained optimization methods.4. We improve the definition of the alpha-spline such that a degree (k+1)α-spline curve has at least C~k continuity. In the original version, degree (2k+1) is required. This dissertation also provides a simple method to interpolate a sequence of given points with a C~2 monotonicity preserving cubic spline curve——a cubicα-spline curve. This method requires less computation time than the B-spline interpolation method.