几何造型研究三维几何信息如何在计算机内表示、分析和综合．几何造型是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)基于二次样条函数，给出了一个拟合海量数据点算法．算法保持了样条函数结构简单，易于计算的优点，并在保持逼近精度的前提下，大大减少了插值曲线的段数，提高了效率．本文的主要贡献在于为解决几何造型中的上述关键问题，提供了新的方法．所提出的参数曲线的最佳多边形逼近算法，大大提高了计算机数控的工作效率；所提出的最优逼近弧长参数化的方法，对于参数曲线的理论研究和生产实践都有较好的意义；所提出的有序数据点的曲线重建，减少了组合曲线的段数，获得了较好的效果．