第3章直线和圆弧的生成算法
3.1直线图形的生成算法
数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。
由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法（DDA）、中点画线法和Bresenham算法。
3.1.1逐点比较法
3.1.2数值微分(DDA)法
设过端点P0(x0 ,y0)、P1(x1 ,y1)的直线段为L(P0 ,P1)，则直线段L的斜率
L的起点P
的横坐标x0向L的终点P1的横坐标x1步进，取步长=1(个像素)，用L
的直线方程y=kx+b计算相应的y坐标，并取像素点(x,round(y))作为当前点的坐标。因为：
y
= kx i+1+b
i+1
= k1x i+b+k x
= y i+k x
所以，当x =1; y i+1 = y i+k。也就是说，当x每递增1，y递增k(即直线斜率)。根据这个原理，我们可以写出DDA（Digital Differential Analyzer）画线算法程序。
DDA画线算法程序：
void DDALine(int x0,int y0,int x1,int y1,int color)
{ int x；
float dx, dy, y, k；
dx = x1-x0； dy=y1-y0；
k=dy/dx,；y=y0；
for (x=x0；x< x1；x++)
{ drawpixel (x, int(y+0.5), color);
y=y+k;
}
}
注意：我们这里用整型变量color表示像素的颜色和灰度。
举例：用DDA方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
图3.1.1 直线段的扫描转换
注意：上述分析的算法仅适用于|k| ≤1的情形。在这种情况下，x每增加1,y最多增加1。当|k| 1时，必须把x，y地位互换，y每增加1，x相应增加1/k。在这个算法中，y与k必须用浮点数表示，而且每一步都要对y 进行四舍五入后取整，这使得它不利于硬件实现。
动画演示：数值微分画线算法（DDA）
3.1.3中点画线法
假定直线斜率k在0~1之间，当前像素点为（x p,y p），则下一个像素点有两种可选择点P1（x p+1,y p）或P2（x p+1,y p+1）。若P1与P2的中点（x p+1,y p+0.5）称为M，Q为理想直线与x=x p+1垂线的交点。当M在Q的下方时，则取P2应为下一个像素点；当M在Q的上方时，则取P1为下一个像素点。这就是中点画线法的基本原理。
图3.1.2 中点画线法每步迭代涉及的像素和中点示意图
下面讨论中点画线法的实现。过点(x0,y0)、(x1, y1)的直线段L的方程式为F(x, y)=ax+by+c=0，其中，a=y0-y1, b=x1-x0, c=x0y1-x1y0，欲判断中点M在Q点的上方还是下方，只要把M代入F（x，y），并判断它的符号即可。为此，我们构造判别式：
d=F(M)=F(x
+1, y p+0.5)=a(x p+1)+b(y p+0.5)+c
p
当d<0时，M在L(Q点)下方，取P2为下一个像素；
当d>0时，M在L(Q点)上方，取P1为下一个像素；
当d=0时，选P1或P2均可，约定取P1为下一个像素；
注意到d是x p, y p的线性函数，可采用增量计算，提高运算效率。
若当前像素处于d0情况，则取正右方像素P1(x p+1, y p),要判下一个像素位置，应计算d1=F(x p+2, y p+0.5)=a(x p+2)+b(y p+0.5)=d+a，增量为a。
若d<0时，则取右上方像素P2(x p+1, y p+1)。要判断再下一像素，则要计算d2= F(x p+2, y p+1.5)=a(x p+2)+b(y p+1.5)+c=d+a+b ，增量为a＋b。画线从(x0, y0)开始，d的初值d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b，
因 F(x0, y0)=0，所以d0=a+0.5b。
由于我们使用的只是d的符号，而且d的增量都是整数，只是初始值包含小数。因此，我们可以用2d代替d来摆脱小数，写出仅包含整数运算的算法程序。
中点画线算法程序：
void Midpoint Line (int x0,int y0,int x1, int y1,int color)
{ int a, b, d1, d2, d, x, y；
a=y0-y1； b=x1-x0；d=2*a+b；
d1=2*a；d2=2* (a+b)；
x=x0；y=y0；
drawpixel(x, y, color);
while (x { if (d<0) {x++；y++； d+=d2; } else {x++； d+=d1;} drawpixel (x, y, color); } /* while */ } /* mid PointLine */ 举例：用中点画线方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-4;d2=2*(a+b)=6 , x y d 0 0 1 1 0 -3 2 1 3 3 1 -1 4 2 5 5 2 15 图3.1.3 中点画线法 问题1：若上述算法往下取二步(i=2)，则算法和像素的取法将变成怎样？问题2：与DDA法相比，中点法的优点是什么？ 动画演示：中点画线算法 3.1.4 Bresenham算法 Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。仍然假定直线斜率在0~1之间，该方法类似于中点法，由一个误差项符号决定下一个像素点。 算法原理如下：过各行各列像素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求像素。 如图2.1.4所示，设直线方程为y i+1=y i+k(x i+1-x i)+k。假设列坐标像素已经确定为x i，其行坐标为y i。那么下一个像素的列坐标为x i＋1，而行坐标要么为y i，要么递增1为y i＋1。是否增1取决于误差项d的值。误差项d的初值d0＝0，x坐标每增加1，d的值相应递增直线的斜率值k，即d＝d＋k。一旦d≥1，就把它减去1，这样保证d在0、1之间。当d≥0.5时，直线与垂线x=x i＋1交点最接近于当前像素(x i，y i)的右上方像素(x i＋1，y i＋1)；而当d<0.5时，更接近于右方像素(x i＋1，y i)。为方便计算，令e＝d－0.5，e的初值为－0.5，增量为k。当e≥0时，取当前像素(x i，y i)的右上方像素(x i＋1，y i＋1)；而当e<0时，取(x i，y i)右方像素(x i＋1，y i)。 图3.1.4 Bresenham算法所用误差项的几何含义 ○Bresenham画线算法程序： void Bresenhamline (int x0,int y0,int x1, int y1,int color) { int x, y, dx, dy； float k, e; dx = x1-x0；dy = y1- y0；k=dy/dx； e=-0.5； x=x0,；y=y0； for (i=0；i { drawpixel (x, y, color); x=x+1；e=e+k; if (e0) { y++； e=e-1;} } } 1、概述 在机床的实际加工中，被加工工件的轮廓形状千差万别，各式各样。严格说来，为了满足几何尺寸精度的要求，刀具中心轨迹应该准确地依照工件的轮廓形状来生成。然而，对于简单的曲线，数控装置易于实现，但对于较复杂的形状，若直接生成，势必会使算法变得很复杂，计算机的工作量也相应地大大增加。因此，在实际应用中，常常采用一小段直线或圆弧去进行逼近，有些场合也可以用抛物线、椭圆、双曲线和其他高次曲线去逼近（或称为拟合）。所谓插补是指数据密化的过程。在对数控系统输入有限坐标点（例如起点、终点）的情况下，计算机根据线段的特征（直线、圆弧、椭圆等），运用一定的算法，自动地在有限坐标点之间生成一系列的坐标数据，即所谓数据密化，从而自动地对各坐标轴进行脉冲分配，完成整个线段的轨迹运行，以满足加工精度的要求。 机床数控系统的轮廓控制主要问题就是怎样控制刀具或工件的运动轨迹。无论是硬件数控（NC）系统，还是计算机数控（CNC）系统或微机数控（MNC）系统，都必须有完成插补功能的部分，只是采取的方式不同而已。在CNC或MNC中，以软件（程序）完成插补或软、硬件结合实现插补，而在NC中有一个专门完成脉冲分配计算（即插补计算）的计算装置——插补器。无论是软件数控还是硬件数控，其插补的运算原理基本相同，其作用都是根据给定的信息进行数字计算，在计算过程中不断向各个坐标发出相互协调的进给脉冲，使被控机械部件按指定的路线移动。 有关插补算法问题，除了要保证插补计算的精度之外，还要求算法简单。这对于硬件数控来说，可以简化控制电路，采用较简单的运算器。而对于计算机数控系统来说，则能提高运算速度，使控制系统较快且均匀地输出进给脉冲。 经过多年的发展，插补原理不断成熟，类型众多。从产生的数学模型来分，有直线插补、二次曲线插补等；从插补计算输出的数值形式来分，有基准脉冲插补（又称脉冲增量插补）和数据采样插补。在基准脉冲插补中，按基本原理又分为以区域判别为特征的逐点比较法插补，以比例乘法为特征的数字脉冲乘法器插补，以数字积分法进行运算的数字积分插补，以矢量运算为基础的矢量判别法插补，兼备逐点比较和数字积分特征的比较积分法插补，等等。在CNC系统中，除了可采用上述基准脉冲插补法中的各种插补原理外，还可采用各种数据采样插补方法。 本文将介绍在数控系统中常用的逐点比较法、数字积分法、时间分割法等多种插补方法以及刀具半径补偿计算原理。 2、逐点比较法 逐点比较法是我国数控机床中广泛采用的一种插补方法，它能实现直线、圆弧和非圆二次曲线的插补，插补精度较高。 实验报告 课程名称计算机图形学 实验名称DDA直线生成算法编程的实现实验类型验证型 实验地点计通学院304实验日期2010-03-29指导教师 专业 班级 学号 姓名 成绩 辽宁石油化工大学计算机与通信工程学院 实验报告说明 1、封面内容 （1）课程名称：实验所属的课程的名称。 （2）实验名称：要用最简练的语言反映实验的内容。要求与实验指导书中相一致。 （3）实验类型：说明是验证型实验、设计型实验、创新型实验还是综合型实验。 2、正文内容 实验报告的正文内容须包括以下内容： （1）实验目的：目的要明确，要抓住重点，符合实验指导书中的要求。 （2）实验内容：说明本实验的主要内容。 （3）实验原理：简要说明本实验项目所涉及的理论知识。 （4）实验环境：实验用的软硬件环境（配置）。 （5）实验方案：对于验证性型实验，写明依据何种原理、操作方法进行实验；对于设计型和综合型实验，写明依据何种原理、操作方法进行实验，并画出硬件组成图、软件流程图、设计思路和设计方法，再配以相应的文字说明；对于创新型实验，除符合设计型和综合型实验要求外，还应注明其创新点、特色。（6）实验步骤：写明实验的实施步骤，包括实验过程中的记录、数据。 （7）实验结果与分析：写明实验的最终结果，并对结果进行分析，做出结论。（8）实验中遇到的问题及解决方法：写明实验过程中遇到的问题及所采取的解决方法。 （9）实验总结（在封底上）：写出对本次实验的心得体会、思考和建议。 实验原理：已知线段的起点坐标()11x y ，终点坐标()22x y ，直线的点斜 式方程为：y m x b =?+，斜率和截距分别为：2121y y m x x -= - ， 11b y m x =-? 。沿x 的增量为x ?，沿y 的增量为y ?，即： 1x y m ?= ??，y m x ?=??。当1m ≤时，取x 为一个像素单位长，即x 每次增加一个像素，然后利用公式计算相应的y 值：1k k k y y y y m x -=+?=+??，相反1m >时，可以通过质量y ?来计算相应的x 值：1k k k x x x x m y -=+?=+??。 实验内容：新建一个Win32 Application 的典型“Hello World ”程序，工程 命名为：DDA 直线生成算法，打开DDA 直线生成算法.cpp 文件， 在里面加入代码： void DDA_line(HDC hdc) { double x,y,dx,dy,L,x1=100,x2=400,y1=100,y2=400; if(abs(x2-x1)>=abs(y2-y1)) L=abs(x2-x1); else L=abs(y2-y1); dx=(x2-x1)/L; dy=(y2-y1)/L; x=x1,y=y1; for(int k=1;k<=L;k++) { SetPixel(hdc,x,y,RGB(255,0,255)); x=x+dx; y=y+dy; Sleep(10); } } 实验结果：调用程序运行得出一下结果： 以下是Bresenham的直线生成算法和整圆生成算法，已调试过，没有任何问题。Bresenham直线生成算法 #include "stdio.h" #include "graphics.h" Bresenham_line(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; { int x,y,dx,dy, i; float k,e; dx=x1-x0;dy=y1-y0; k=(dy*1.0)/dx; e=-0.5; x=x0; y=y0; for (x=x0; x<=x1; x++) { putpixel(x,y,color); e=e+k; if(e>=0) { y++;e=e-1;} } } int main() { int x0,y0,x1,y1,c; int driver=DETECT,mode=0; initgraph(&driver,&mode,"c:\\tc"); setbkcolor(BLUE); setcolor(YELLOW); printf("input x0,y0,x1,y1,c"); scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&c); Bresenham_line(x0,y0,x1,y1,c); getch(); closegraph(); } 当取e=2*dy-dx时，可以消除浮点和除法运算 #include "stdio.h" #include "graphics.h" Bresenham_line(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; { int x,y,dx,dy, i,e; float k; dx=x1-x0;dy=y1-y0; k=(dy*1.0)/dx; e=2*dy-dx; x=x0; y=y0; for (x=x0; x<=x1; x++) { putpixel(x,y,color); e=e+2*dy; if(e>=0) { y++;e=e-2*dx;} } } int main() { int x0,y0,x1,y1,c; int driver=DETECT,mode=0; initgraph(&driver,&mode,"c:\\tc"); setbkcolor(BLUE); setcolor(YELLOW); printf("input x0,y0,x1,y1,c"); scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&c); Bresenham_line(x0,y0,x1,y1,c); getch(); closegraph(); } 第3章直线和圆弧的生成算法 3.1直线图形的生成算法 数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。 由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法（DDA）、中点画线法和Bresenham算法。 3.1.1逐点比较法 3.1.2数值微分(DDA)法 设过端点P0(x0 ,y0)、P1(x1 ,y1)的直线段为L(P0 ,P1)，则直线段L的斜率 L的起点P 的横坐标x0向L的终点P1的横坐标x1步进，取步长=1(个像素)，用L 的直线方程y=kx+b计算相应的y坐标，并取像素点(x,round(y))作为当前点的坐标。因为： y = kx i+1+b i+1 = k1x i+b+k x = y i+k x 所以，当x =1; y i+1 = y i+k。也就是说，当x每递增1，y递增k(即直线斜率)。根据这个原理，我们可以写出DDA（Digital Differential Analyzer）画线算法程序。 DDA画线算法程序： void DDALine(int x0,int y0,int x1,int y1,int color) { int x； float dx, dy, y, k； dx = x1-x0； dy=y1-y0； k=dy/dx,；y=y0； for (x=x0；x< x1；x++) { drawpixel (x, int(y+0.5), color); y=y+k; } } 注意：我们这里用整型变量color表示像素的颜色和灰度。 举例：用DDA方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 图3.1.1 直线段的扫描转换 注意：上述分析的算法仅适用于|k| ≤1的情形。在这种情况下，x每增加1,y最多增加1。当|k| 1时，必须把x，y地位互换，y每增加1，x相应增加1/k。在这个算法中，y与k必须用浮点数表示，而且每一步都要对y 进行四舍五入后取整，这使得它不利于硬件实现。 实验二 直线的生成算法的实现 班级 08信计2班 学号 59 姓名 分数 一、实验目的和要求 1.理解直线生成的基本原理。 2.掌握几种常用的直线生成算法。 3.利用Visual C++实现直线生成的DDA 算法。 二、实验内容 1.了解直线的生成原理，尤其是Bresenham 画线法原理。 2.掌握几种基本的直线生成算法：DDA 画线法、Bresenham 画线法、中点画线法。 3.利用Visual C++实现直线生成的DDA 算法，在屏幕上任意生成一条直线。 三、实验步骤 1.直线的生成原理： （1）DDA 画线法也称数值微分法，是一种增量算法。是一种基于直线的微分方程来生成直线的方法。 （2）中点画线法原理 以下均假定所画直线的斜率[0,1]k ∈，如果在x 方向上的增量为1，则y 方向上的增量只能在01 之间。中点画线法的基本原理是：假设在x 坐标为p x 的各像素点中，与直线最近者已经确定为(,)p p P x y ，用小实心圆表示。那么，下一个与直线最近的像素只能是正右方的1(1,)p p P x y +，或右上方的2(1,1)p p P x y ++，用小空心圆表示。以M 为1P 和2P 的中点，则M 的坐标为(1,0.5)p p x y ++。又假设Q 是理想直线与垂直线1p x x =+的交点。显然，若M 在Q 的下方，则2P 离直线近，应取2P 为下一像素点；若M 在Q 的上方，则1P 离直线近，应取1P 为下一像素点。 （3）B resenham 画线法原理 直线的中点Bresenham 算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点偏差判别式的值。 给定理想直线的起点坐标为P0（x0，y0），终点坐标为P1（x1，y1），则直线的隐函数方程为： 0b kx y y)F(x,=--= （3-1） 构造中点偏差判别式d 。 b x k y y x F y x F d i i i i M M -+-+=++==)1(5.0)5.0,1(),( 数控技术课程设计说明书 设计题目：数字积分法圆弧插补计软件设计指导老师： 专业：机械设计制造及其自动化 班级：机 姓名： 学号： 目录 一、课程设计题目 (1) 二、课程设计的目的 (1) 三、课程设计使用的主要仪器设备 (1) 四、课程设计的任务题目描述和要求 (1) 五、数字积分法插补原理 (2) 5.1从几何角度来看积分运算 (2) 5.2数字积分圆弧插补 (3) 5.3数字积分法圆弧插补程序流程图 (5) 5.4插补实例 (6) 六、程序清单 (7) 七、软件运行效果仿真 (18) 八、课程小节 (21) 九、参考文献 (22) 一、课程设计题目 数字积分法第一、二、三、四象限顺、逆圆插补计算 二、课程设计的目的 《数控原理与系统》是自动化（数控）专业的一门主要专业课程，安排课程设计的目的是通过课程设计方式使学生进一步掌握和消化数控原理基本内容，了解数控系统的组成，掌握系统控制原理和方法，通过设计与调试，掌握各种功能实的现方法，为今后从事数控领域的工作打下扎实的基础。 1)了解连续轨迹控制数控系统的组成原理。 2) 掌握数字积分法（DDA）插补的基本原理。 3）掌握数字积分法（DDA）插补的软件实现方法。 三、课程设计使用的主要仪器设备 1、PC计算机一台 2、数控机床实验装置一台 3、支持软件若干（选用VB环境） 四、课程设计的任务题目描述和要求 数字积分法又称数字微分分析法DDA(Digital Differential Analyzer)。数字积分法具有运算速度快、脉冲分配均匀、易于实现多坐标联动及描绘平面各种函数曲线的特点，应用比较广泛。其缺点是速度调节不便，插补精度需要采取一定措施才能满足要求。由于计算机有较强的计算功能和灵活性，采用软件插补时，上述缺点易于克服。 本次课程设计具体要求如下： （1）掌握数字积分插补法基本原理 （2）设计出数字积分（DDA）插补法插补软件流程图 （3）编写出算法程序清单算法描述（数字积分法算法在VB中的具体实现）（4）要求软件能够实现第一、二、三、四象限顺、逆圆插补计算 （5）软件运行仿真效果插补结果要求能够以图形模式进行输出 课程名称：计算机图形学指导教师：罗晓辉 上机实践名称：基本图形（直线）生成算法 年级：2008 姓名：孔广波 学号：312008********* 上机实践成绩： 上机实践日期：2011-4-10 实验一: 直线生成算法 上机实践报告 一、实验目的 理解直线生成的基本原理，掌握儿种常见的直线生成算法，利用Microsoft Visual C++6.0实现直线生成的DDA算法。 二、实验内容： 1）了解直线的生成原理。 2）掌握儿种基本的直线生成算法：DDA画线法、Bresenham画线法、中点画线法。 3）利用Microsoft Visual C++6.0实现直线生成的DDA算法，在屏幕上任意生成一条直线。 三、实验步骤： 1）预习教材关于直线的生成原理。 2）仿照教材关于直线生成的DDA算法，使用Microsoft Visual C++6.0实现该算法。 3）调试、编译、运行程序。 四、实验分析、源程序和结果： （1.1）中点算法分析： 中点画线算法原理示意图 直线斜率：k属于[0, 1] 线段的隐式方程：F(x,y) = ax + by + c = 0 ((x0 , y0), ( xl , yl )为两端点，式中a = yO - yl , b = xl - xO , c = xO * yl - xl * yO) 直线上方的点：F(x , y) > 0 直线下方的点：F ( x , y ) < 0 构造判别式：d = F(M) = F(Xp+l,Yp + 0.5) 由d>0, V0 可判定下一个象素，d 的初始值：d0 = F( X0 + 1 , Y0 + 0.5 ) = F( X0 , Y0 ) + a + 0.5b 因(X0, YO)在直线上，F(X0 , YO ) = 0,所以，dO = a + 0.5b (1.2)具体实现代码： void CGView::Line_DDA(long plxjong ply,long p2x,long p2y,CDC *pDC)〃画直线算法实现 ( int a,b,del 1 ,del2,d,x,y; b=p2x-plx; a=ply-p2y; d=2*a+b; dell=2*a; del2=2*(a+b); x=plx; y=piy； pDC->SetFixel(x,y,mJPenColor)； while(x 机电工程学院 数控加工技术课程设计——插补算法实现 学号：S311077006 专业：机械工程 学生姓名：胡晓锋 任课教师：李霞副教授 2011年4月 基于PC的圆弧曲线加减速算法实现 插补算法一直以来就是数控系统中的核心技术。从数控系统的原理来说，插补的本质问题就是对任意曲线进行分解，成为若干段微小的曲线，当对曲线的分解达到无穷级时，每一段曲线便成为微小的直线段。然后利用与相应微小曲线相类似的直线段代替，通过控制刀具按直线段行走进行加工，完成为整个曲线的插补运算加工。实际问题中不可能对任意曲线的分解达到无穷，因此总是存在相应的误差。然而在实际运用中对误差的容忍度有限，因此只需在满足精度的情况下进行曲线的分解。对曲线的分解过程即是将其坐标点进行密化，不但要保证精度，还需要在极短的时间内完成。受现代技术的限制，这一过程目前还存在一定的问题。由此而产生的对插补算法的研究也一直没有停止过，从经典的逐点比较法到现在的自由曲面直接插补法，各种算法层出不穷。 本次对圆弧的插补算法是基于PC技术的算法，利用MATLAB软件编写相应的插补程序，实现对插补轨迹的模拟与分析。 一、问题描述 本次设计针对圆弧曲线进行插补，采用加减速的方式完成刀具的行走过程。根据数据采样插补原理，实现数控轨迹的密化。本次插补的难点在于对刀具行走轨迹的自动加减速进行控制，由控制器发出相应指令，当刀具以不同速度运行到不同位置时，能够根据当前的状态判断下一个插补周期需要的状态，从而连续平滑的完成插补过程。 二、速度曲线的数学表达式 刀具在进行插补时的速度应该是一个加速-匀速-减速的过程，各个过程与时间的关系应该由相应的加速度来控制。因此曲线的形状呈现一定的抛物线形。 另初始进给速度为F1，末端进给速度为F2，指令速度为F，当前速度为V，减速距离为S，当前距离为CS，n为插补周期个数，t为当前时刻。则速度的数学表达式如下： (F1 实验报告 实验内容：逐点比较法直线和圆弧插补2011年9月25日 院系:物科院班级：085 学号：07080518 姓名：陈实 实验目的： 利用逐点比较法的插补原理，编写直角坐标系下的直线、圆弧插补程序，观察屏幕上仿真的运动轨迹，掌握逐点比较法的插补原理。 实验原理： 逐点比较发是基于动点与理想曲线院函数的比较来实现插补的。逐点比较法的插补过程，每走一步要进行一下四个步骤： 偏差判别：根据偏差值确定刀具相对加工曲线的位置 坐标进给：根据偏差判别的结果，决定控制线沿哪个坐标进给一步以接近曲线 偏差计算：计算新加工店相对曲线的偏差，作为下一步偏差判别的依据 终点判别：判别是否到达终点，未到达终点则返回第一步继续插补，到终点则停止 1、逐点比较法直线插补原理： 逐点比较法在第一象限的直线插补原理如下图所示，其他象限情况可依次类推。 现加工OE直线，如果刀具动点在OE直线上方或在线上，则令刀具沿X正方向进给一步；若刀具动点在OE直线下方，则令刀具沿Y轴正方向进给一步，如此循环直到加工到E点。判别刀具动点的位置根据偏差函数判别公式： 根据这个公式可以推到出两种不同情况下的地推公式： 对于插补终点的判别，可以采用单向的计数长度法，即：取计数长度M等于Xe、Ye中的大者，并设该坐标方向为计数方向。插补时，仅在该方向上产生进给时，计数长度减一。图1的逐点比较法中，工作循环的结束条件就是M减为0. 2、逐点比较法圆弧插补原理： 逐点比较法在第一象限的圆弧插补原理如图所示，其他象限可一次类推： 对于第一象限的逆圆弧，如果动点在圆弧的外侧则令刀具动点沿X轴负方向进给一步。如果动点在圆弧的内侧则令刀具沿Y轴正方向进给一步。 圆弧的偏差计算公式为： 根据这个公式同样可推导出圆弧插补的两种不同情况下的递推公式： 对于插补终点的判别，同样可以采用单向的计数长度法，不过对于圆弧，计数的方向并不取决于终点坐标中的大者，而是取决于圆弧终点处。 逐点比较法插补中需要编写插入部分流程图： 直线和圆弧的生成算 法 第3章直线和圆弧的生成算法 3.1直线图形的生成算法 数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。 由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法（DDA）、中点画线法和Bresenham算法。 3.1.1逐点比较法 3.1.2数值微分(DDA)法 设过端点P0(x0,y0)、P1(x1,y1)的直线段为L(P0,P1)，则直线段L的斜率 L的起点P0的横坐标x0向L的终点P1的横坐标x1步进，取步长=1(个像素)，用L的直线方程y=kx+b计算相应的y坐标，并取像素点(x,round(y))作为当前点的坐标。因为： y i+1= kx i+1+b = k1x i+b+k?x = y i+k?x 所以，当 x =1; y i+1= y i+k。也就是说，当x每递增1，y递增k(即直线斜率)。根据这个原理，我们可以写出DDA（Digital Differential Analyzer）画线算法程序。 DDA画线算法程序： void DDALine(int x0,int y0,int x1,int y1,int color) { int x； float dx, dy, y, k； dx = x1-x0； dy=y1-y0； k=dy/dx,；y=y0； for (x=x0；x< x1；x++) { drawpixel (x, int(y+0.5), color); y=y+k; } } 注意：我们这里用整型变量color表示像素的颜色和灰度。 举例：用DDA方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 二○一三届毕业设计 基于FPGA逐点比较圆弧插补算法设计 学院：电子与控制工程学院 专业：电子科学与技术 姓名：…….. 学号：……… 指导教师：…….. 完成时间：2013年5月 二〇一三年五月 摘 要 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 摘 要 本课题主要是研究基于VHDL 实现数控系统中的逐点比较圆弧插补，要求圆弧运动过程平滑，在各象限能顺利过渡，并有较小的设计误差，能与运动控制部分很好的集成，实现较高的切割频率。 本课题采用QuartusII 软件来调试程序，并进行波形仿真。主要的工作如下： 1） 理解数控系统中逐点比较圆弧插补算法的原理及其实现方法； 2） 通过硬件描述语言VHDL 在FPGA 上实现上述算法； 3） 完成圆弧插补的仿真与测试。 关键词：VHDL ，FPGA ，逐点比较法，QuartusII ABSTRACT ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ABSTRACT This topic mainly studies based on VHDL realization of point by point comparison circular arc interpolation in nc system, the movement for arc process smooth, in each quadrant can smooth transition, and a relatively small design error, can very good integration with motion control part, realize the high frequency of cutting. This subject adopts software QuartusII to debug program and waveform simulation. The main work is as follows: 1. Understand CNC system the principle of point by point comparison in circular arc interpolation algorithm and its realization method 2. Through the hardware description language VHDL FPGA to realize the above algorithms. 3. Finish arc interpolation of simulation and test KEY WORDS : VHDL, FPGA, point-by-point comparison, QUARTUS II 逐点比较法直线插补 （1）偏差函数构造 对于第一象限直线OA上任一点(X,Y):X/Y = Xe/Ye 若刀具加工点为Pi（Xi，Yi），则该点的偏差函数Fi可表示为： 若Fi= 0，表示加工点位于直线上； 若Fi> 0，表示加工点位于直线上方； 若Fi< 0，表示加工点位于直线下方。 （2）偏差函数字的递推计算 采用偏差函数的递推式（迭代式）：既由前一点计算后一点 Fi =Yi Xe -XiYe 若Fi>=0，规定向+X 方向走一步 Xi+1 = Xi +1 Fi+1 = XeYi –Ye(Xi +1)=Fi –Ye 若Fi<0，规定+Y 方向走一步，则有 Yi+1 = Yi +1 Fi+1 = Xe(Yi +1)-YeXi =Fi +Xe （3）终点判别 直线插补的终点判别可采用三种方法。 1）判断插补或进给的总步数：2）分别判断各坐标轴的进给步数；3）仅判断进给步数较多的坐标轴的进给步数。 （4）例 对于第一象限直线OA，终点坐标Xe=6 ,Ye=4，插补从直线起点O开始，故F0=0 。终点判别是判断进给总步数N=6+4=10，将其存入终点判别计数器中，每进给一步减1，若N=0，则停止插补。 逐点比较法圆弧插补（1）偏差函数构造 任意加工点Pi（Xi，Yi），偏差函数Fi可表示为 若Fi=0，表示加工点位于圆上； 若Fi >0，表示加工点位于圆外； 若Fi <0，表示加工点位于圆内 （2）偏差函数的递推计算 1） 逆圆插补 若F ≥0，规定向-X 方向走一步 若Fi<0，规定向+Y 方向走一步 2） 顺圆插补 若Fi ≥0，规定向-Y 方向走一步 若Fi<0，规定向+y 方向走一步 （3）终点判别 1）判断插补或进给的总步数： 2）分别判断各坐标轴的进给步数： （4）例 对于第一象限圆弧AB ，起点A （4，0），终点B （0，4） ???+-=-+-=-=++12)1(122211i i i i i i i X F R Y X F X X ???++=-++=+=++12)1(122211i i i i i i i Y F R Y X F Y Y ???+-=--+=-=++12)1(122211i i i i i i i Y F R Y X F Y Y ???++=-++=+=++12)1(122211i i i i i i i X F R Y X F X X b a b a Y Y X X N -+-=b a x X X N -= b a y Y Y N -= 实验2 直线生成算法实现 1.实验目的 理解基本图形元素光栅化的基本原理, 掌握一种基本图形元素光栅化算法, 利用0penGL 实现直线光栅化的DDA算法。 2.实验内容 (1)根据所给的直线光栅化的示范源程序, 在计算机上编译运行, 输出正确结果。 (2)指出示范程序采用的算法, 以此为基础将其改造为中点线算法或Bresenham算法,写 入实验报告。 (3)根据示范代码,将其改造为圆的光栅化算法,写入实验报告。 (4)了解和使用OpenGL的生成直线的命令,来验证程序运行结果。 3.实验原理 示范代码原理DDA算法。下面介绍OpenGL画线的一些基础知识和glutReshapeFunc（）函数。 (1)数学上的直线没有宽度,但0penGL的直线则是有宽度的。同时, OpenGL的直线必须是有限长度,而不是像数学概念那样是无限的。可以认为, OpenGL的“直线”概念与数学上的“线段”接近,它可以由两个端点来确定。这里的线由一系列顶点顺次连接而成, 有闭合和不闭合两种。 前面的实验已经知道如何绘“点”,那么OpenGL是如何知道拿这些顶点来做什么呢? 是依次画出来,还是连成线? 或者构成一个多边形? 或是做其他事情? 为了解决这一问题, OpenGL要求:指定顶点的命令必须包含在glBegin函数之后, glEnd函数之前(否则指定的顶点将被忽略),并由glBegin来指明如何使用这些点。 例如: glBegin(GL P0INTS) , glVertex2f(0.0f, 0.0f); glVertex2f(0.5f, 0.0f); glEnd(); 则这两个点将分别被画出来。如果将GL_POINTS替换成GL_LINES,则两个点将被认为是直线的两个端点, OpenGL将会画出一条直线。还可以指定更多的顶点, 然后画出更复杂的图形。另一方面, glBegin支持的方式除了GL_POINTS和GL_LINES,还有GL LINE STRIP、GL LINE L0〇P、GL TRIANGLES、GL TRIANGLE STRIP、GL TRIANGLE_FAN等几何图元。 (2) 首次打开窗口、移动窗口和改变窗口大小时, 窗口系统都将发送一个事件, 以通知程序员。如果使用的是GLUT,通知将自动完成,并调用向glutReshapeFunc注册的函数。该函数必须完成下列工作: ①重新建立用作新渲染画布的矩形区域。 ②定义绘制物体时使用的坐标系。 如: void Reshape(int w, int h) { glViewport(0, 0, (GLsizei) w, (GLsizei) h); §3.2圆的生成——Bresenham算法 条件：给定圆心(x c,y c)和半径R 约定：只考虑圆心在原点，半径为整数R的圆x2+y2.=R2。对于圆心不在原点的圆，可先通过平移转换，化为圆心在原点的圆，再进行扫 描转换，把所得到的像素集合加上一个位移量，就可以把目标圆光 栅化。 在众多圆的生成算法，如逐点比较法、角度DDA法、Bresenham算法中，Bresenham画圆法是一种最简单有效的的方法。 首先注意到只要生成一个八分圆，那么，圆的其它部分就可以通过一系列的对成变换得到。 1 2 3 4 5 6 7 8 由算法生成 y=x 第一八分圆关于y=x对称变换 第一四分圆关于x=0对称变换 上半圆关于y=0对称变换 如果以点x=0，y=R为起点按顺时针方向生成圆，则在第一象限内y是x 的单调递减函数。 要在这三个像素中选择一个使其与理想圆的距离的平方达到最小，即下 列数值中的最小者。 R (0,R) (R,0) x y 这样，从圆上任一点出发，按顺时针方向生成圆时，为了最佳逼近该圆，对于下一像素的取法只有三种可能的选择，即正右方像素、正下方像素和右下角像素，分别记作：m H、m V、m D。 (x i，y i) (x i，y i-1) (x i+1，y i) (x i+1，y i-1) m H m D m V m H=|(x i+1)2+(y i)2-R2| m V=|(x i)2+(y i+1)2-R2| m D=|(x i+1)2+(y I-1)2-R2| m H (x i,y i) (x i+1,y i) (x i+1,y i+1) (x i+1,y i-1) (x i-1,y i-1) (x i,y i-1) m V m D 1 2 3 5 4 圆与点(x i，y i)附近光栅格网的相交关系只有五种可能。 实验二基本图形元素（直线）生成算法的实现 1．实验目的： 理解基本图形元素光栅化的基本原理，掌握一种基本图形元素光栅化算法，利用OpenGL实现直线光栅化的DDA算法。 2．实验内容： （1）根据所给的直线光栅化的示范源程序，在计算机上编译运行，输出正确结果； （2）指出示范程序采用的算法，以此为基础将其改造为中点线算法或Bresenham算法，写入实验报告； （3）根据示范代码，将其改造为圆的光栅化算法，写入实验报告； （4）了解和使用OpenGL的生成直线的命令，来验证程序运行结果。 3．实验原理： 示范代码原理参见教材直线光栅化一节中的DDA算法。下面介绍下OpenGL画线的一些基础知识和glutReshapeFunc()函数。 （1）数学上的直线没有宽度，但OpenGL的直线则是有宽度的。同时，OpenGL的直线必须是有限长度，而不是像数学概念那样是无限的。可以认为，OpenGL的“直线”概念与数学上的“线段”接近，它可以由两个端点来确定。这里的线由一系列顶点顺次连结而成，有闭合和不闭合两种。 前面的实验已经知道如何绘“点”，那么OpenGL是如何知道拿这些顶点来做什么呢？是一个一个的画出来，还是连成线？或者构成一个多边形？或是做其它事情呢？为了解决这一问题，OpenGL要求：指定顶点的命令必须包含在glBegin函数之后，glEnd函数之前（否则指定的顶点将被忽略），并由glBegin来指明如何使用这些点。 例如： glBegin(GL_POINTS); glVertex2f(0.0f, 0.0f); glVertex2f(0.5f, 0.0f); glEnd(); 则这两个点将分别被画出来。如果将GL_POINTS替换成GL_LINES，则两个点将被认为是直线的两个端点，OpenGL将会画出一条直线。还可以指定更多的顶点，然后画出更复杂的图形。另一方面，glBegin 支持的方式除了GL_POINTS和GL_LINES，还有GL_LINE_STRIP，GL_LINE_LOOP，GL_TRIANGLES，GL_TRIANGLE_STRIP， N=6+4=10,将其存入终点判别计数器中，每进给一步减 1，若N=0,则停止插补。 (1)偏差函数构造 对于第一象限直线 0A 上任一点(X,Y): X/Y = Xe/Ye Pi (Xi , Yi ),则该点的偏差函数 Fi 可表示为： (2 )偏差函数字的递推计算 采用偏差函数的递推式(迭代式)：既由前一点计算后一点 Fi =Yi Xe -XiYe 若Fi>=0，规定向 +X 方向走 Xi+1 = Xi +1 Fi+1 = XeYi 讦e(Xi +1)=Fi 讦e 若Fi<0，规定+Y 方向走一步，则有 Yi+1 = Yi +1 Fi+1 = Xe(Yi +1)-YeXi =Fi +Xe (3 )终点判别 直线插补的终点判别可采用三种方法。 逐点比较法直线插补 若刀具加工点为 若 Fi= 0， 表示加工点位于直线上; 若 Fi> 0， 表示加工点位于直线上方; 若 Fi< 0， 表示加工点位于直线下方。 1)判断插补或进给的总步数：2)分别判断各坐标轴的进给步数；3)仅判断进给步数较多的坐标轴的进给步数。 (4)例 对于第一象限直线0A终点坐标Xe=6 ,Ye=4，插补从直线起点0开始，故F0=0。终点判别是判断进给总步数 10 4 逐点比较法圆弧插补(1)偏差函数构造 任意加工点Pi (Xi , Yi),偏差函数Fi可表示为 若Fi=0,表示加工点位于圆上; 若Fi >0，表示加工点位于圆外; 2 若Fi<0,表示加工点位于圆内 （2）偏差函数的递推计 算 1）逆圆插补 若F> 0,规定向-X方向走一步X i 1 X i 若Fi<0，规定向+Y方向走一步 2）顺圆插补 若Fi > 0,规定向-Y方向走一步若Fi<0，规定向+y方向走一步 （3 ）终点判 别 1 ）判断插补或进给的总步数: 2）分别判断各坐标轴的进给步数: (4)例F i Y i F i Y i F i X i 1 F i 1 N x 对于第一象限圆弧AB,起点A（4，0）， (X i Y i X i2 Y i X i2 X i (X i X a X a 终点 1 1)2 (Y i (Y i 1 1)2 X b X b B （0， Y i2 1)2 1)2 Y i2 Y a R2 R2 R2 R2 Y b N y F i F i F i F i Y a 2X i 2Y i 2Y i 2X i Y b 圆的生成算法 利用直线坐标法和极坐标法生成圆周颇费时间，而圆的Bresenham算法则简捷很多。一．圆的Bresenham算法思想： 设圆的半径为r，先考虑圆心在（0,0），并从x=0、y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束。即有 X i+1=X i+1 相应地yi+1则在两种可能中选择： Y i+1=y i或者y i+1=y i-1 选择的原则是考虑精确值y是靠近yi还是靠近yi-1,计算公式为 Y2=r2-(x i+1)2 d1=y i2-y2=y i2-r2+(x i+1)2 d2=y2-(y i-1)2=r2-(x i+1)2-(y i-1)2 令pi=d1-d2,并代入d1、d2，则有 P i=2(x i+1)2+y i2+(y i-1)2-2r2(1) Pi称为误差。如果Pi<0,则yi+1=yi，否则yi+1=yi-1.pi的递归式为 P i+1=p i+4x i+6+2(y i+12-y i2)-2(y i+1-y i) (2) P i的初值由式（1）代入xi=0,yi=r,而得 P1=3-2r (3) 根据上面的推导，圆周生成算法思想如下： (1)求误差初值，p1=3-2r，i=1,画点（0，r）； (2)求下一个光栅位置，其中x i+1=x i+1,如果p i<0,则y i+1=y i,否则y i+1=y i-1； (3)画点（x i+1,y i+1）； (4)计算下一个误差，如果p i<0，则p i+1=p i+4x i+6，否则p i+1=p i+4(x i-y i)+10； (5)I=i+1,如果x=y，则结束，否则返回步骤2； 虽然（1）式表示p i+1的算法很复杂，但因为y i+1只能y i或y i-1，使得步骤（4）的算法变得简单，只需做加法和乘4的乘法。 圆的Bresenham算法的程序实现如下： #include 学院 毕业论文（设计） 2015 届机械设计制造及其自动化专业 13 班级 题目逐点比较插补算法设计 姓名学号 1 指导教师职称教授 二О一五年五月二十一日 摘要 逐点比较法是数控加工中常用的插补方法,通过控制刀具每次移动的位置与理想位置的误差函数进而实现零件加工,鉴于VB编程简单、直观,采用VB可以实现逐点比较插补原理的相关程序设计及加工过程虚拟化。插补技术是机床数控系统的核心技术,逐点比较法可以实现直线和圆弧插补算法,其算法的优劣直接影响零件直线和圆弧轮廓的加工精度和加工速度。文章在传统的逐点比较直线插补与圆弧插补算法的基础上,提出以八方向进给取代传统的四方向进给,研究了偏差最小的走步方向的实现方法,同时研究了保证数控机床坐标进给连续的偏差递推计算过程。结果表明,新算法可以提高零件轮廓的逼近精度且减少了插补计算次数,从而提高了零件直线和圆弧轮廓的加工精度和加工速度。 关键词 数控；插补；逐点比较；逼近；偏差函数 The algorithm design of point-to-point comparison Author: LI Zhiyuan Tutor: Chen Liangji Abstract Abstract: The algorithm of point-to-point comparison is a typical plugging method in processing of numerical control,manufacturing parts by controlling error function between the position the cutting tool moves to and the perfect program is simple and visual,which can visualize the programming and processing of The algorithm of point-to-point comparison. Interpolation technology is the core technology of machine tool’s CNC system. The algorithm of point-to-point comparison can achieve the algorithms of linear and circular algorithm of point-to-point comparison插补运动(逐点比较法)
DDA直线生成算法
Bresenham的直线生成算法和整圆生成算法完整代码
直线和圆弧的生成算法
计算机图形学 直线的生成算法的实现
数字积分圆弧第一二三四象限顺逆插补计算
(1)直线生成算法.doc
圆弧加减速插补算法
逐点比较法插补实验报告
直线和圆弧的生成算法讲课稿
基于FPGA的逐点比较圆弧插补算法设计
逐点比较法直线插补圆弧插补实例
OpenGL-实验2直线生成算法实现教学文案
§3.2圆、圆弧的生成—Bresenham算法
CG_实验2_基本图形元素(直线)生成算法的实现
逐点比较法直线插补圆弧插补实例
圆的生成算法
逐点比较插补算法设计
相关主题
文本预览