规则曲线生成算法的研究

规则曲线生成算法的研究摘要 截止目前为止,规则曲线生成算法的研究可谓涉及到了这块研究领域的方方面面，故本文在此研究的基础上对此做一总结,从而方便大家在整体上更好的把握和解这一领域的研究范围和进程。本文主要涉及规则曲线生成算法的方面有:规则曲插补算法，B样条曲线的快速实时插补算法，CB样条,TB样条曲线及其应用,三次均匀B样条等算法的一些研究，C-B样条曲线的广顺逼近算法研究，均匀T-B样条曲线的研究等。希望通过对此方面知识的学习，让我们了解更多关于规则曲线的知识。关键词：规则曲线插补算法，CB样条,TB样条,三次均匀B样,算法研究1规则曲线插补算法基于机器人的应用13机器人终端执行器在笛卡尔空间中的描述，包括位置描述与姿态描述，因此其插补算法中也包括位置插补与姿态插补。其中，姿态插补一般采取线性方式，即把终端执行器在曲线上的终点和起点的方位差均匀地分配到插补的每一步，算法简单，在此不作讨论。位置插补方式，包括直线插补，圆弧插补，抛物线插补，样条线插补等。本文只研究最基础的直线和圆弧插补算法。插补算法在以上步骤中，占据着举足轻重的地位，是整个机器人轨迹规划控制过程（图 1）的精华所在，因此研究它具有十分重要的意义。1.1空间直线插补已知空间直线的起点坐标、终点坐标和插补次数你N，则 (1)对于该直线上的任一点有 (2) 1.2 平面圆弧插补已知标准平面（如平面、平面或平面）上的圆心坐标、半径、圆弧方向（顺时针或逆时针）、起始角、圆弧圆心角，以及插补次数，求此平面圆弧上的点坐标。以平面上的圆弧为例，如下图2：圆弧为顺时针方向，起始角是指圆弧起始点与轴之间的夹角，与均为弧度制表示，则 (3) (4)对于圆弧上任一点有 (5)插补算法独立于机器人结构，直线和圆弧插补是机器人系统中不可缺少的插补算法，对于非直线、非圆弧的轨迹，都可以采用直线、圆弧来逼近，以实现这些轨迹。本文研究了机器人轨迹规划中的空间直线、平面圆弧、空间圆弧等三种规则曲线的插补算法，理论上可使所有插补点均落在要求曲线上，在空间圆弧插补中还采用了矢量算法，避免了插补方向和过象限的判断，算法精简且没有累积误差。这些算法已经编写成计算机语言，结合机器人正逆运动学算法，在本实验室中的一台六自由度机器人的控制中得到实现。本研究成果也可适用于高性能要求的机床数控系统。2 B样条曲线的快速实时插补算法17在众多的曲线曲面描述方法中, B样条曲线曲面由于其具有凸包性、局部修改性等一系列优良特性而在曲线曲面造型领域倍受青睐,但在数控加工领域, 目前很多CNC机床只能对直线和圆弧进行直接插补, 还不具备直接进行B样条曲线插补的功能。所以, 为了对B样条曲线进行插补, 一般采取的措施是先借助外部编程将B样条曲线离散成为微直线段再进行插补。由于精度和表面质量等要求的限制, 这些微线段一般取得很短, 这样势必增大加工的程序量, 而且对实时插补也极其不利。最近出现了一些关于B样条曲线曲面的直接插补算法, 但在算法中一般都需进行繁琐的计算, 需要较长的插补时间, 难以实现B样条曲线的快速实时插补。为了改善上述状况, 仔细研究了B样条曲线曲面直接插补的相关技术, 在分析和吸收别人成果的基础上, 提出了一种简单的三次B样条曲线的直接插补算法。该算法不需要通常B样条曲线实时插补算法中的繁琐计算, 而采取了一种科学合理的近似算法, 大大缩短了三次B样条曲线直接插补的时间, 显著提高了该曲线的实时插补速度。2.1曲线插补的基本原理当前数控加工系统的插补方法主要分为两大类: 一类为脉冲增量插补, 即行程标量插补； 另一类为数据采样插补, 即时间标量插补。脉冲增量插补是以步进器在每个脉冲时间内的进距作为插补单位进行插补, 此方法主要用于直线和圆弧的插补,而数据采样插补是以刀具在一个采样时间内所走距离进行插补, 该方法可用于较为复杂的曲线的插补。本文主要讨论三次B样条曲线的直接插补，考虑到三次B样条曲线不易用脉冲增量进行插补, 采用了数据采样方法对其进行插补。该方法的原理如下：设 表示一段参数曲线, 表示上沿该曲线方向的切向量, 由微分几何可得: 其中将CAD模型中的静态信息和CNC加工系统中需要的动态信息联系起来, 但现在的主要问题是怎样求出的表达式。为此对式两边取模, 为叙述方便, 假设沿参数的正向插补实际上沿参数反向插补时原理相同, 于是可得: 即 这时用采样时间对此微分方程进行离散得： 其中为采样时间，为了保证精度和表面质量， 取得很小，这样就可以略去式中的高次项，即得： (5) 式中表示刀具在曲线上处对应的速度，此值可通过合理选取得到，于是剩下就是的计算，根据微分几何可得： 目前，有关B样条曲线的插补算法中大都把B样条的具体表达式带入式求解，由于B样条曲线的具体表达式较为复杂，这样不可避免地造成了繁琐的计算，增加了插补计算量，不利于实时插补的实现。考虑到由于插补过程中采样时间取得很短,这样每个采样时间内的的变化量也很小，故将式的微分变为差分，即 且取上一个采样周期内已经得到的值, 这样就避免了繁琐的求解微分方程, 大大减少了插补中的计算量。2.2三次B样条曲线的实时插补三次B样条曲线的实时插补的步骤为：计算 (13) (14)判断的区间，将带入与之区间相应的系数计算式，计算 ， 并求出 (15)计算，用之近似代替，并代入 式求出以代替重复， 直到插补结束为止。 从以上实时插补过程可以看出，三次B样条曲线实时插补方法在计算中采用了近似方法，减少了插补计算时间，提高了插补速度。现在的问题是此方法是否可靠？我们认为这种方法完全可靠。其一，在采样插补中，为了保证精度和表面质量，采样时间一般取得很小，这样采用差分代替微分误差自然很小，实际上在此方法中用差分代替微分就是用曲线的弦方向代替切线方向。根据微分几何，在具有一阶导数连续的曲线中，当弦趋近零时, 弦的方向即为切线方向。其二，从该方法可以看出, 由该近似方法产生的插值点仍位于曲线上，所以该方法产生的误差不具有累积效应。因此本文提出的三次B样条曲线实时插补方法的近似算法具有坚实的理论基础，能够满足数控加工的精度要求。另外，尽管本文讨论的是三次B样条曲线的实时插补，其实该方法对于任何一阶导数连续的曲线皆具有实用意义。3 T-B样条曲线及其应用3在飞机外形设计与机械零件加工中经常遇到许多有二次曲线弧和二次曲面片表示的形状，如圆弧、椭圆弧、圆柱面、圆锥面、椭球面等，这些曲线曲面在设计中需要有明确的表现形式，在制造上又要求有较高的精确度。B样条方法在表示与设计曲线曲面形状时显示了强大的威力，然而在表示与设计这些由二次曲面与平面构成的初等曲面时却无能为力，只能给出近似表示，这就存在了设计误差问题，从而带来了问题的复杂化；现在流行的NURBS方法较好地解决了上述问题，然而其权因子与参数化问题至今仍没有完全解决。3.1 T-B 样条曲线定义 给定个控制顶点可以生成个曲线段连成一条曲线，其中第个曲线段定义为： （16） 其中为控制顶点。 当时，（17）当时， (18)当时, (19) 如下图：3.2 椭(圆)弧的T-B样条曲线精确表示当时，令有 (20)当时，令有 (21)当时，令有 (22)T-B样条曲线具有与同阶B样曲线完全类似的性质： 端点插值性质、导矢性质、凸包性、变差缩减性等，且表达式简单，特别是T-B样条曲线可以不需有理形式即可精确表示椭圆弧等，相应的张量积曲面可精确表示椭球面等， 同时还能与多项式或有理多项式参数曲线相互转化，在造型设计方面使用简便。4 均匀T - B 样条曲线的研究10在飞机外形设计与机械零件加工中经常遇到许多有二次曲线弧和二次曲面片表示的形状， 如圆弧、椭圆弧、椭球面、圆柱面等，这些曲线曲面在设计中需要有精确的表现形式，在制造上要求有较高的精确度。B样条方法在解决这类问题时无能为力，只能给出近似表示，这就存在了设计误差问题； NURBS 方法较好地解决了上述问题，然而其有理形式也带来了曲线曲面设计的复杂化，而且其权因子与参数化问题至今没有完全解决。4.1均匀T - B 样条基函数的定义若所构造的均匀T- B 样条曲线与均匀B 样条曲线具备类似的几何特性，则待构造的基函数必须具备正性和权性以及相应的端点性质。曲线表达式为： 其中，当时，取 (25) 结合式得到： (26) (27)建立方程组解得： 当时： 对于次曲线, 共有个基函数，由式可知每个基函数包括个未知系数，所以共有个未知数系数。根据得到个约束条件；根据得到个约束条件；根据；根据；根据因此，共有个约束条件。方程数目和未知系数数目相同，故可解。对均匀T- B 样条基函数式，令， 重新参数化使其参数的范围规范为。图1 给出了均匀T- B 样条关于参数的基函数。4.2 均匀T - B 样条基函数的性质由于均匀T- B 样条基函数与均匀B 样条基函数具有类似的性质，将均匀T- B 样条基函数也记作，结合上述T- B样条基函数的定义知，均匀T- B 样条基函数性质如下：（1） 正性 （2） 权性 （3） 连续性在整个参数空间上至少为阶连续 4.3 均匀T - B 样条曲线的定义定义1 给定个控制顶点可以生成个曲线段连接成一条曲线，其中第个曲线段，定义为： 其中为控制顶点，为基函数。图2 给出了由6 段三次T- B 样条曲线段组成的T- B 样条曲线。4.4 均匀T- B 样条曲线的性质( 1) 端点及其导矢的几何性质 (35) (36) (38) (39)根据取不同的值可得到相应的端点及导矢的几何性质。（2） 几何不变性: 由定义知：故T- B样条曲线具有几何不变性。（3）凸包性： 因为, ；在几何图形上， 这意味着T- B 曲线是相应控制点的凸线性组合，并且曲线上各点均落在特征多边形构成的凸包之中。(4) 连续性： T- B样条曲线有阶连续导数， 故其是连续的。特别的, 三次T- B 样条曲线比B 样条曲线具有更高的光滑度。(5) 变差缩减性： 设个控制点构成T- B 样条曲线的特征多边形， 在该平面内的任意一条直线与的交点个数不多于该直线和特征多边形的交点个数。本文将均匀T- B 样条基函数推广到次，并给出了次均匀T- B 样条基函数的求解方法。均匀T- B 样条曲线与同阶均匀B 样条曲线具有相类似的性质，且表达式简单，能精确表示圆弧、椭圆弧等二次曲线，在造型设计方面使用简便。依据其基函数和曲线的性质容易得到它的升阶公式和控制点反求公式以及T- 曲线间的拼接条件。理论推导表明三次均匀T- B 样条比三次均匀B 样条具有更好的光滑性。T- B 样条曲线的诸多良好性质也可以推广到T- B 样条曲面，下一步的工作就是研究T- B 样条曲面的性质。5 CB样条曲线的光顺逼近算法研究15Bezier曲线和均匀 样条曲线不能精确表示除抛物线之外的圆锥曲线，为此引入 曲线解决了表示和设计初等曲面时的构造问题，但方法的权因子参数化曲线曲面的几何连续性问题仍然没有完全解决B样条曲线不仅很好地克服上述弊端，更有着其特殊的性质，从而可以处理自由曲线曲面，精确表示圆弧和椭圆在构造工程曲面时，采用C-B样条方法，具有算法简单相对节省存储空间运算速度快等特点。目前，国内外的研究主要集中在C-B样条的性质、插值、分割、拼接及造型等方面，但关于样条的光顺问题却很少涉及因此，文章对C-B样条曲线的光顺问题进行了研究曲线光顺的方法之一是能量法：指弹性细梁所处的最自然状态，其物理上的意义为应力能达到极小文中的光顺准则定为将物理意义下的应力和应力能及动力学中的扰动能作加权线性组合，使其达到最小。首先考虑：问题1已知数据点列,求一条C-B样条曲线：使得矢径的终点求解方法如下。首先将型值点参数化，可采用规范累加弦长参数化： （40）则上述的问题归之为解非线性方程组： (41)如果写成矩阵形式则有：式中：分别为C-B样条曲线的4个控制顶点。 (42)其中，是C-B样条曲线基函数。一般情况下，上式是没有精确解的，即不存在严格通过这些数据点的插值曲线，但可以求这些型值点的最小二乘逼近解，即求参数多项式曲线： (43)使得 (44)因是列满秩，即,则上式对应的Gauss正交方程组为： (45)则有： (46)其中. (47)由方程求得C-B样条曲线的控制顶点 ，从而得到问题1的解。问题2 如何调整控制参数和控制顶点，使对应的C-B样条曲线光顺。根据上文提出的光顺准则，可建立光顺的约束方程为： (48)由上式有： 在进行光顺时，既要考虑曲线的偏差 ，同时又要考虑到光顺量达到最小，所以综合问题1和问题2，整个系统的能量可令：这样可求出光顺后的控制参数和控制顶点，但在设计中希望曲线通过首末控制顶点，所以令，这样只要对E求关于控制参数和控制顶点的偏导，从而达到光顺的目的。即由变分原理有： (49)综合问题1和问题2给出C-B样条曲线的光顺逼近算法如下：（1）采用累加弦长方法将数据点参数化；（2）给定 的初始值，由上述方程求得C-B样条曲线的控制顶点；（3）给定的值，令，由上式确定 ；（4）将的值代入上式，从而得相应的光顺逼近曲线：。 (50)文章提出的通过调整控制参数和控制顶点使得C-B样条曲线的能量最小，得到最优的光顺逼近曲线的方法具有简单直观和实用的特点，并可以进一步推广到高阶C-B样条曲线和曲面的光顺逼近。总结 本文主要涉及规则曲线生成算法的方面有:规则曲线插补算法，B样条曲线的快速实时插补算法，TB样条曲线及其应用,C-B样条曲线的广顺逼近算法研究，均匀T-B样条曲线的研究。插补算法独立于机器人结构，直线和圆弧插补是机器人系统中不可缺少的插补算法，对于非直线、非圆弧的轨迹，都可以采用直线、圆弧来逼近，以实现这些轨迹。三次B样条曲线实时插补方法在计算中采用了近似方法，减少了插补计算时间，提高了插补速度。T-B样条曲线具有与同阶B样曲线完全类似的性质： 端点插值性质、导矢性质、凸包性、变差缩减性等，且表达式简单，特别是T-B样条曲线可以不需有理形式即可精确表示椭圆弧等，相应的张量积曲面可精确表示椭球面等， 同时还能与多项式或有理多项式参数曲线相互转化，在造型设计方面使用简便。均匀T- B 样条曲线与同阶均匀B 样条曲线具有相类似的性质，且表达式简单，能精确表示圆弧、椭圆弧等二次曲线，在造型设计方面使用简便。依据其基函数和曲线的性质容易得到它的升阶公式和控制点反求公式以及T- 曲线间的拼接条件。理论推导表明三次均匀T- B 样条比三次均匀B 样条具有更好的光滑性。T- B 样条曲线的诸多良好性质也可以推广到T- B 样条曲面。目前，国内外的研究主要集中在C-B样条的性质、插值、分割、拼接及造型等方面，但关于样条的光顺问题却很少涉及因此，文章对C-B样条曲线的光顺问题进行了研究曲线光顺的方法之一是能量法：指弹性细梁所处的最自然状态，其物理上的意义为应力能达到极小文中的光顺准则定为将物理意义下的应力和应力能及动力学中的扰动能作加权线性组合，使其达到最小。参考文献1 袁奇荪.计算几何造型学基础.北京：航空工业出版社，1987.1461782常命，黄培宁.工程曲面差值设计方法及其应用.华中理工大学出版社3 单银根，李淑春. 计算机图形学基础. 北京学院出版社,1994.4 周玉良.曲线、曲面的数学建模与微机绘制.哈尔滨建筑大学学报.1996(2):29-1.5 卓扬娃，白晓灿，陈永明. 机器人的三种规则曲线插补算法. 装备制造技术2009 :11.6 刘永奎，周晓敏.逐点生成参数曲线的双步算法.计算机辅助设计与图形学学报.20029（7）：14-7.7 刘军强，高佳宏,李言. 规则曲线和曲面的NURBS 表示.西安工业学院学报.2004(12):24-4.8黄有度，朱功勤.有利参数曲线的快速逐点声称算法. 计算机学报.2001(8):24-8.9刘勇奎.曲线的整数型生成算法.计算机学报.1998(3):21-310孙家广，杨长贵. 计算机图形学. 北京：清华大学出版社,1995.11俞长高.计算机辅助几何设计.上海：上海交通大学出版社，1986.546712唐泽圣,周嘉玉，李新友. 北京：清华大学出版社 ,1995.13陈传波,陆枫. 计算机图形学基础M. 北京：电子工业出版社,2005：272-27414张全伙,张剑达. 计算机图形学M. 北京：机械工业出版社,2003：245-24715李东,孙长嵩,苏小红. 计算机图形学实用教程M .北京：人民邮电出版社,2004: 239-24116吴红斌，石续年. 三次均匀B样条曲线和双三次均匀B样条曲面的边界控制. 北京农业工程大学学报.1993:13-4.17 胡钢,刘哲,徐华楠. 三次均匀B样条曲线的新扩展及应用. 计算机工程与应用.2008:44-32.18 张棋,田森平. 双三次B样条曲面的生成方法. 郑阳师范高等专科学校学报.2001(6):21-3.19李鹏，李原，刘平，张开富.C-B样条曲线及曲面的光滑拼接与应用西北工业大学报，2007,25(6):890-89520 Foley J, Dam A V etc., Computer Graphics: Principle and Practice, 2nd Edition, Addison-Wesley, 1990.21 Securing E-passports with Elliptic Curves.22 Katja Schmidt-Samoa, Olivier Semay, and Tsuyoshi Takagi. Analysis of Fractional Window Recoding Methods and Their Application to Elliptic Curve Cryptosystems. IEEE TRANSACTIONS ON COMPUTERS, VOL. 55, NO. 1, JANUARY 2006.23Bresenham J E . Algorithm for computer control of a digital plotter J .IBM Systems Journal ,1965,4(1):25-3024Wu X. Anefficient anti aliasing technique J. Computer Graphics，1991，5(4)：143-152.计算机图形学课程设计由：天空乐园网郑州大学生兼职收集由开封市同力基础工程有限公司整理出版！14