规则曲线生成算法的研究

规则曲线的研究2012 年 1 月 规则曲线的研究摘要本文首先讨论规则曲线及几类规则曲线的投影及图示方法。其次从规则曲线入手, 通过比较、论证, 确定出以参数形式作为曲线的标准模型。最后针对机器人末端执行器在笛卡尔空间中的轨迹规划方法，研究了空间直线、平面圆弧、空间圆弧等三种基本规则曲线的插补算法。此算法在理论上可使所有插补点均落在所要求的曲线上，算法精简且无累积误差。研究成果已在实际机器人中得到实现。关键词：曲线的投影 曲线的数学建模 机器人的三种规则曲线引言曲线可分为规则曲线和不规则曲线。所谓规则曲线就是一条曲线可以用标准代数方程来描述。曲线可看作是一个点在空间连续运动的轨迹。按点的运动轨迹是否在同一平面，曲线可分为平面曲线和空间曲线。按点的运动有无一定规律，曲线又可分为规则曲线和不规则曲线。随着图形技术的日益广泛应用, 计算机绘图方法的研究也就显得愈来愈重要.可以说, 在当今计算机的应用中, 绝大多数都不同程度地使用了图形技术. 曲线绘制是计算机图形学的一个基础内容. 由于其基础性和在实用中被大量地使用, 因此其任何进步都具有很重要的意义.一、曲线概述曲线可看作是一个点在空间连续运动的轨迹。按点的运动轨迹是否在同一平面，曲线可分为平面曲线和空间曲线。按点的运动有无一定规律，曲线又可分为规则曲线和不规则曲线。所谓规则曲线就是一条曲线可以用标准代数方程来描述。解析几何已经把几何问题和代g数问题紧密地结合了起来，例如，在平面直角坐标系内，如果一条曲线上的点都能满足符合某种条件，而满足该条件的点又均位于这条曲线上，那么我们就可以把这种对应关系写成一个确定的函数式：y=f(x)这个函数式就称为曲线的方程；同样，该曲线即为这个方程的曲线。例如，圆的方程可写成 ，椭圆的方程可以写成 ,同样，还可以写出比如双曲线、抛物线等方程。在绘制这些曲线的时候，我们可以借助各种标准工具，比如画圆可以用圆规，画椭圆也可以用椭圆规。但对于非圆曲线，绘制时的更一般方法是借助曲线板。我们先在平面上确定一些满足条件的、位于曲线上的坐标点，然后借用曲线板把这些点分段光滑地连接成曲线。绘出的曲线的精确程度，则取决于我们所选择的数据点的精度和数量。坐标点的精度高，点的数量取得多，则连成的曲线愈接近于理想曲线。其实，以上所说的方法就是用计算机来绘制各类曲线的基本原理。由于图形输出设备的基本动作是显示像素点或者是画以步长为单位的直线段，所以，从图形显示器和绘图仪上输出的图形，一般除了水平线和垂直线以外，其他的各种线条，包括直线和曲线，都是由很多的短直线构成的锯齿形线条组成的。从理论上讲，绝对光滑的理想曲线是绘不出来的。这就告诉了我们一个绘制任何曲线的基本原理，就是要把曲线离散化，把它们分割成很多短直线段，用这些短直线段组成的拆线来逼近曲线?至于这些短直线段取多长，则取决于图形输出设备的精度和我们绘制的曲线所要求的精度，但我们所要求达到的精度不能逾越图形设备所实际具有的精度。随着图形技术的日益广泛应用, 计算机绘图方法的研究也就显得愈来愈重要.可以说, 在当今计算机的应用中, 绝大多数都不同程度地使用了图形技术. 曲线绘制是计算机图形学的一个基础内容. 由于其基础性和在实用中被大量地使用, 因此其任何进步都具有很重要的意义. 以往人们使用的图形显示器主要是随机扫描显示器, 所以人们对绘图算法的研究也是从基于几何的算法( 即线式生成算法) 开始的. 对于绘制工程制图中常用的自由曲线, 这类算法目前在有些场合仍在使用, 它的基本思想比较简单, 即在曲线上均匀地取一些点, 然后将这些点用小直线段相连而生成曲线. 在这类算法中曾出现了一些比较有效的算法, 如我国学者提出的T -N方法等, 但是由于此类算法使用小折线段来逼近曲线, 因此所绘制的曲线不够光滑且误差较大.目前广泛使用的图形显示器是光栅扫描显示器. 随之出现了另一类图形算法 象素级的图形绘制算法( 或称点式生成算法) . 这类算法一般只使用整数运算来逐点计算曲线上的象素, 因此由其生成的曲线是很细致的, 并且误差小( 最大偏差不大于半个象素单位) . 可以说这类算法充分利用了光栅显示器的特点. 目前这类算法中已经出现了一些有效的算法, 如绘制直线的Br esenham 算, 绘制圆的Br esenham 算法、中点法、正负法以及绘制椭圆及抛物线的Pitterway 算法等. 开发自由曲线的绘制算法比研制圆及椭圆等曲线的绘制算法更困难一些, 因为圆及椭圆被分成8 段之后, 每一段的走向都是确定的; 而自由曲线则是不确定的, 也就是说曲线上每一段的走向是没有规律的. 所以,研制生成自由曲线的算法就要更多地依靠计算机自动判断方向, 以确定生成曲线下一点的位置. 在自由曲线的逐点绘制算法中主要有非参数曲线的生成算法和参数曲线的生成算法. 对于非参数曲线, 1998 年, 提出了一个有效的算法, 它能够逐点地绘制任何方向和任何变化的非参数曲线且只用整数运算. Hobby曾于1990 年提出过另一个逐点绘制非参数曲线的算法, 但是该算法只能绘制其方向变化在45之内( 一个象限内) 的曲线. 对于参数曲线, 也出现了一些比较有效的逐点绘制算法.这类算法目前存在的公认的问题是由于步长太小导致取点过密, 造成算法中大量的无效计算, 并且重复绘制了许多象素点.二、曲线的投影因为曲线是点的集合，所以画出曲线上的一系列点的投影，并将各点的同面投影依次光滑连接，就得到该曲线的投影，这是绘制曲线投影的一般方法。曲线上过一点的切线，其投影仍与曲线的投影相切于该点的同面投影。图一平面曲线的投影根据平面对投影面的倾斜状态而有三种情形：1. 曲线平面平行于投影面，投影反映实形；2. 曲线平面垂直于投影面，投影是一直线；3. 曲线平面倾斜于投影面，投影是相仿形。 图二所谓规则曲线就是一条曲线可以用标准代数方程来描述。平面规则曲线即凡曲线上所有的点都属于同一平面，则该曲线称为平面曲线。常见的圆、椭圆、抛物线和双曲线等可以用二次方程描述，不能用二次方程描述的曲线为不规则曲线，亦称为自由曲线。1.圆的投影 圆的投影根据圆平面对投影面的倾斜状态而有三种情形：等大的圆、长度等于直径的线段、长轴长度等于直径的椭圆。图三例1 圆位于铅垂面内，圆心为O(o,o)，直径长度为D，画出该圆的两投影。图四解：圆的水平投影为直线段，正面投影为椭圆，利用辅助投影求出椭圆上的点。图五2.圆柱螺旋线的投影2.1形成图六2.2投影的画法图七三、曲线的数学建模曲线建模的基本要求：1.几何形状的稳定性曲线的数学描述有三种基本形式：显函数表示y=f(x) (1)隐函数表示 (2)参数表示 (3)在这三种基本形式中适于计算机绘制和表示的是参数形式，其理由是, 显函数和隐函数表示曲线对坐标的依赖性大, 当曲线有垂直切线时, 不便于计算机表示, 在进行几何变换时曲线形状不稳定,编程不方便。而参数形式可弥补这些缺点。例如, 当用有限个点确定一条曲线时, 设三个点为，这三个点确定一条抛物线，用显函数描述为：，当把这三个点绕原点旋转时，三个点的坐标有了改变：经旋转变换后, 曲线发生了变化, 见图1,图2。 图八同样这三个点用矢参数形式描述为 参数.为三点的位置矢量。在进行旋转时，三点的相对位置保持不变，所以其形状也保持不变。1. 易于界定，能处理无穷大斜率在平面直角坐标系，一条曲线若用或形式描述时，能出现一值对多值现象，不利于界定。再如，当曲线的切线斜率为无穷大时，计算机产生溢出错误。2. 方便编程和变换例如，圆曲线，当用描述时，编程和绘制都不方便。而用参数式给出时，参数与坐标单值对应，这样既方便编程，又便于变换。建模方法及表达式：通过前面的讨论, 用参数形式进行曲线, 曲面的计算机描述是合适的, 将函数方程转换成参数方程, 一般的方法是利用直角坐标与极坐标的转化, 或空间直角坐标与球坐标的转化, 公式如下：平面曲线 (4) (5) (6)空间曲线： (7) (8)四、机器人的三种规则曲线插补算法机器人的轨迹规划，在机器人控制中具有重要的作用，直接影响着控制的准确性和快速性。我们希望只示教机器人运动路径上的某些关键点，然后根据轨迹特征算出这些示教点之间必须到达的中间位置点，通过插补进行控制，从而实现高效高精的运动控制。运动路径一般由一些基本曲线组成，本文研究的是空间直线、平面圆弧、空间圆弧等三种规则曲线的插补算法。1.轨迹规划算法传统的轨迹规划分为两种，一种是关节空间的规划，另一种是笛卡尔空间的规划。这两种方式各有其优缺点：关节空间的轨迹规划相对简单，计算量小，且不会出现奇异位形，但是其末端的运动轨迹不直观；笛卡尔空间的轨迹规划则比较直观，但在规划过程中容易进入机器人的奇异位形2。本文采用笛卡尔空间轨迹规划方法，但由于大部分机器人是关节机器人系统控制的是关节坐标轴，该轨迹规划方法生成的值是机器人末端执行器的位姿，必须反复求解逆运动学方程来计算关节角，具体规划步骤如下：（1）由示教得到几个关键路径点（对六自由度机器人而言，得到的是6 个关节角度值），通过机器人正运动学正解得出其在笛卡尔空间中所表示的位置和姿态值；（2）根据关键点的位置和姿态值以及轨迹要求，按照一定算法进行插补，从而形成一系列笛卡尔空间里的路径点；（3）将规划好的一系列路径点，通过机器人逆运动学反解得出机器人能识别的关节空间表示量。插补算法在以上步骤中，占据着举足轻重的地位，是整个机器人轨迹规划控制过程的精华所在，因此研究它具有十分重要的意义。2.规则直线插补算法机器人终端执行器在笛卡尔空间中的描述，包括位置描述与姿态描述，因此其插补算法中也包括位置插补与姿态插补。其中，姿态插补一般采取线性方式，即把终端执行器在曲线上的终点和起点的方位差均匀地分配到插补的每一步，算法简单，在此不作讨论。位置插补方式，包括直线插补，圆弧插补，抛物线插补，样条线插补等。本文只研究最基础的直线和圆弧插补算法。2.1空间直线插补已知空间直线的起点坐标、终点坐标和插补次数N，则 (9)对于该直线上任一点有 (10) 平面圆弧插补原理图九2.2平面圆弧插补已知标准平面（如X- Y 平面、Y-Z 平面或Z- X 平面）上的圆心坐标、半径R、圆弧方向（顺时针或逆时针）、起始角、圆弧圆心角，以及插补次数N，求此平面圆弧上的点坐标。以X- Y 平面上的圆弧为例，如图2 所示，圆AC 为顺时针方向，起始角是指圆弧起始点与Y 轴之间的夹角与 均用弧度制表示，则 (11) (12) 对于圆弧上任一点有 (13)2.3 空间圆弧插补 已知空间任意三点为圆弧起点、中间点和终点，A、B、C 三点不在同一直线上，以及插补次数N（不包括A、C 点），求此三点所在空间圆弧上的系列点坐标。步骤如下：（1）求圆弧圆心和半径R。由 (14)由得(15)由不共线的三点确定的平面方程，有 (16)联立式（1）式（2）式（3），即可求出圆心；半径R= (17)（2）求圆弧所在平面的法矢量n。在数控机床中，平行于坐标平面的圆弧编程，一般只给出起点、终点和圆心，因而需要用G02 和G03 区分为顺时针圆弧和逆时针圆弧。给定了起点、终点和一个中间点的空间三点圆弧的走向是确定的，用表示空间三点圆弧所在平面的法矢量n，则从n 的正方向看, 从A 到B 到C 的圆弧始终是逆时针圆弧。设,则 (18)（3）求圆心角。如图3 所示，有两种情况：当（圆弧ABC）时，;(19)当时， 图十、圆心角的计算而如何判断与的关系呢？我们设矢量在各坐标轴方向上的分量为 (20)并设，则当H0 时，矢量与圆弧所在平面的法矢量方向相同，此时；当H 0 时，矢量与圆弧所在平面的法矢量方向相反，此时。（4）求步距角。每次插补走过的步距角是不变的，有。（5）求插补递推公式5。如图4所示，圆弧上任一点处沿前进方向的切矢量 图十一、空间圆弧插补原理 (21)可得 (22)设经过一个插补周期后，机器人终端执行器从点Pi (xi ,yi , zi)沿圆弧切向移动距离后，到达点P i+1(xi+1，yi+1，zi+1)，则有 (23)其中。又(24)故,为一常量。从图4可看出，点并不在圆弧上，为使所有插补点都落在圆弧上，需对式（4）进行修正。连接 交圆弧于点，以代替作为实际插补点，则可保证插补点始终落在所求圆弧上。在直角三角形中，有即，则有 (25)令（为一常量），同时把式（4）代入式（5），得插补递推公式 (26)另设i = 0 时，插补起点为点A，即 (27)综上由式（6）可递推得到空间圆弧上的一系列插补点的坐标值，并能保证插补点总在圆弧上，此算法没有累积误差。五、总结插补算法独立于机器人结构6，直线和圆弧插补是机器人系统中不可缺少的插补算法，对于非直线、非圆弧的轨迹，都可以采用直线、圆弧来逼近，以实现这些轨迹。本文研究了机器人轨迹规划中的空间直线、平面圆弧、空间圆弧等三种规则曲线的插补算法，理论上可使所有插补点均落在要求曲线上，在空间圆弧插补中还采用了矢量算法，避免了插补方向和过象限的判断，算法精简且没有累积误差。这些算法已经编写成计算机语言，结合机器人正逆运动学算法，在本实验室中的一台六自由度机器人的控制中得到实现。本研究成果也可适用于高性能要求的机床数控系统。六、参考文献1 孙家广，杨长贵. 计算机图形学. 北京：清华大学出版社,1995.2 唐泽圣,周嘉玉，李新友. 北京：清华大学出版社 ,1995.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吴红斌，石续年. 三次均匀B样条曲线和双三次均匀B样条曲面的边界控制. 北京农业工程大学学报.1993:13-4.11 胡钢,刘哲,徐华楠. 三次均匀B样条曲线的新扩展及应用. 计算机工程与应用.2008:44-32.12 张棋,田森平. 双三次B样条曲面的生成方法. 郑阳师范高等专科学校学报.2001(6):21-3.13 Securing E-passports with Elliptic Curves.14 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.15 Foley J, Dam A V etc., Computer Graphics: Principle and Practice, 2nd Edition, Addison-Wesley, 1990.计算机图形学课程设计由：天空乐园网郑州大学生兼职收集由开封市同力基础工程有限公司整理出版！14