几何造型中参数化与拟合技术的研究(参数速度,)

huangyhg

http://www.niubiao.com/xinxi/19768.html
【中文摘要】：几何造型研究三维几何信息如何在计算机内表示、分析和综合．几何造型是CAD／CAM内在的理论基础和关键技术，是随着航空、汽车等现代工业发展与计算机的出现而产生与发展起来的一门学科．几何造型作为信息技术的一个重要组成部分，将计算机高速、海量数据存储及处理和挖掘能力与人的综合分析及创造性思维能力结合起来，对加速产品开发、缩短设计制造周期、提高质量、降低成本、增强企业市场竞争能力与创新能力发挥着重要作用．不论是军事工业和民用工业，建筑行业和制造加工业，机械、电子、轻纺产品，还是文体、影视广告制作都离不开几何造型技术．曲线曲面造型是几何造型的核心之一．曲线曲面造型研究在计算机内如何描述曲线曲面，如何对它的形状进行交互式的显示与控制．传统的数学方法虽然提供了平面、圆柱面、圆锥面、球面等一类规则形状的曲面，但很难用以表达飞机、轮船、汽车等现实生活中千姿百态的自由曲线曲面形状．早期，在飞机和船舶的制造工厂里，传统的设计方法要求设计与制造人员必须具备丰富的设计经验，付出繁重的体力劳动，设计制造周期长，制造精度低，互换协调性差，不能适应现代工业的发展．曲线曲面造型就是应现代工业发展的要求而产生与发展起来的，又对现代工业的发展起着巨大推动作用．曲线曲面造型的核心问题是计算机表示，即要找到既适合计算机处理且有效地满足形状表示与几何设计要求，又便于形状信息传递和产品数据交换的形状描述的数学方法．在曲线曲面造型中，参数曲线曲面以其构造简单直观、易于显示等特点而流行于世．这种曲线曲面表示方法脱离了对坐标系的依赖，给许多应用带来了极大的方便．与非参数表示相比，参数曲线曲面能较好的满足形状数学描述的要求．长期以来，参数曲线曲面一直是描述几何形状的主要工具，早在20世纪60年代初被美国波音公司的弗格森所采用，由Coons、Bézier等大师奠定其理论基础．Coons曲面、Bézier曲面、NURBS(Non-Uniform Rational B-Spline)曲面等不仅成为几何设计的主要工具，已被作为工业产品数据交换的STEP(Standard for The Exchange of Product Model Data)标准，也作为描述工业产品几何形状的唯一数学方法．参数曲线曲面造型按用户提供的初始信息不同可分为两类：一类是自由设计方法，它只要求设计者根据构思给出一些控制点和控制参数来定义曲线和曲面，然后在设计过程中允许改变这些控制点和参数来调整曲线和曲面的形状，直至它们符合设计要求为止．另一类是插值或逼近法(工程上统称为拟合法)，其特点是给定一组离散点，要求生成的曲线或曲面要么通过所有这些点(成为插值曲线或曲面)，要么以一定的精度贴近这些点(称为逼近曲线和曲面)．这两类方法生成的曲线曲面的形状都受参数化的影响．参数化既决定了所表示曲线曲面的形状，也决定了该曲线曲面上的点与其参数域内的点(即参数值)之间的一种对应关系．由此可见，参数化和插值与逼近技术是曲线曲面造型的基础问题，具有重要的理论价值和实际意义．围绕这两个问题，本文研究了参数曲线的最优多边形逼近、参数曲线的最优参数化和高密度的海量数据点拟合等一类关键问题．本文的主要研究工作如下：1．研究了参数曲线的最优多边形逼近对传统的逼近算法——参数逼近算法和几何逼近算法进行了讨论，找出了传统算法的不足，并在几何逼近算法的基础上提出了多边形逼近新算法．该算法采用贪心技术，从端点开始，逐步定位逼近点．除最后一段外，参数曲线与逼近线段的最大偏移量总是等于给定的逼近精度，而传统算法不能确保这一点，导致传统算法得到的逼近线段数目偏多．对于凸参数曲线，给定逼近精度，证明了该算法得到逼近线段的数目最少．如果以生成的逼近线段的数目越少则算法越优为标准，则该算法是最优的．算法包含求解一个非线性方程．对于Bézier曲线，提出了一种技术把算法涉及的非线性方程的次数降低两次，使得算法能够精确处理二次曲线．文中用三个实例来对比该算法与传统子分算法的效果，验证了在同一逼近公差下，该算法所需的逼近多边形的顶点最少．算法直观可行，具有一定的实用价值．该算法的不足之处在于，对于非凸参数曲线，不能保证得到最优解，不过得到逼近线段的数目与最优逼近的差额，不超过该曲线中拐点的数目，由于生产实践中，常用的参数曲线含有拐点的数目有限，该算法能够得到近似最优解．2．研究了参数曲线的最优参数化问题讨论了参数曲线的弧长参数化，分析了有理重新参数化对参数曲线产生的影响．研究了利用有理重新参数化的自由度，求解参数曲线最优逼近弧长参数化的问题．提出了一种新的度量曲线的参数速度与弧长参数化接近程度的方法，基于该方法求出了参数曲线的最优参数化．最优参数化的参数速度偏离单位速度的最大值达到最小．与国外著名学者Farouki的算法相比，该算法取得的最优参数化的参数速度偏离单位速度的最大值较小．本文用三个实例来对比该算法与Farouki算法的效果，实例表明该算法比Farouki的算法效果好．该算法的不足之处在于，由于有理重新参数化调整参数速度的能力有限，对于参数速度存在多次波动的曲线，最优参数化的参数速度不能保证处处逼近单位速度．3．研究了数据点的曲线重建问题．对曲线重建进行了讨论，研究了有序数据点的曲线重建问题．对样条插值曲线进行了分析，找出了样条插值曲线拟合高密度数据点的不足．基于二次样条函数，给出了一个拟合高密度的海量数据点的算法．对于给定的一组有序数据点，算法利用多边形逼近，将该组数据点分成一个个子集，在误差允许的范围内，每个子集内的数据点近似在一条直线上．由一段二次曲线拟合每个子集的数据点，全部数据点由在连接处C~1连续的分段二次样条曲线拟合．该算法保持了样条函数结构简单，易于计算的优点，并在保持逼近精度的前提下，大大减少了插值曲线的段数，提高了效率．文中给出实例来对比该算法与传统样条插值算法的效果，验证了该算法所需的插值曲线的段数远远少于传统算法．论文的主要创新点如下：1)提出了多边形逼近参数曲线的新算法．对于凸参数曲线，在同样的逼近精度下，该算法逼近得到逼近线段的数目最少，因而逼近满足最优条件；除了最后一条边以外，多边形的每一条边到被逼近曲线的最大距离都恰好等于给定的逼近误差，而传统算法不能确保这一点，导致传统算法得到的逼近线段较多；当被逼近曲线为Bezier曲线时，有一种技术来降低本算法的计算复杂度，使得对2次Bezier曲线的逼近有精确解．2)对于有理重新参数化，提出了一种度量曲线的参数速度与弧长参数化接近程度的方法．基于该方法求出了参数曲线的最优参数化．最优参数化的参数速度偏离单位速度的最大值达到最小．3)基于二次样条函数，给出了一个拟合海量数据点算法．算法保持了样条函数结构简单，易于计算的优点，并在保持逼近精度的前提下，大大减少了插值曲线的段数，提高了效率．本文的主要贡献在于为解决几何造型中的上述关键问题，提供了新的方法．所提出的参数曲线的最佳多边形逼近算法，大大提高了计算机数控的工作效率；所提出的最优逼近弧长参数化的方法，对于参数曲线的理论研究和生产实践都有较好的意义；所提出的有序数据点的曲线重建，减少了组合曲线的段数，获得了较好的效果．'

【英文摘要】： 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 below1) 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.