下载文档原格式
实验二: 直线的生成算法的实现班级 08信计2班学号 20080502055 姓名分数一、实验目的和要求:1.理解直线生成的原理；2.掌握几种常用的直线生成算法；3.利用C实现直线生成的DDA算法。
二、实验内容:1.了解直线的生成原理2、掌握几种基本的直线生成算法: DDA画线法、中点画线法、Bresenham画线法。
3、仿照教材关于直线生成的DDA算法, 编译程序。
4.调试、编译、运行程序。
三、实验过程及结果分析1.直线DDA算法:算法原理：已知过端点P0（x0,y0）, P1（x1,y1）的直线段L(P0,P1), 斜率为k=(y1-y0)/(x1-x0), 画线过程从x的左端点x0开始, 向x右端点步进, 步长为1个像素, 计算相应的y坐标为y=kx+B。
计算y i+1 = kx i+B=kx i +B+kx=y i +kx当x=1,yi+1=yi+k, 即当x每递增1, y递增k。
由计算过程可知, y与k可能为浮点数, 需要取y整数, 源程序中round(y）=(int)(y+0.5)表示y四舍五入所得的整数值。
（1）程序代码:#include"stdio.h"#include"graphics.h"void linedda(int x0,int y0,int x1,int y1,int color){int x,dy,dx,y;float m;dx=x1-x0;dy=y1-y0;m=dy/dx;y=y0;for(x=x0;x<=x1;x++){putpixel(x,(int)(y+0.5),color);y+=m;setbkcolor(7);}}main(){int a,b,c,d,e;int graphdriver=DETECT;int graphmode=0;initgraph(&graphdriver,&graphmode,"");a=100;b=100;c=200;d=300;e=5;linedda(a,b,c,d,e);getch();closegraph();}运行结果:2.中点画线算法:假定所画直线的斜率为k∈[0,1], 如果在x方向上增量为1, 则y方向上的增量只能在0~1之间。
分别解释直线生成算法dda法,中点画线法和
bresenham法的基本原理
直线生成算法DDA法、中点画线法和Bresenham法的基本原理如下：
1. DDA直线生成算法：基于差分运算的直线生成算法。
通过将直线分割成
若干个相邻的像素点，并按照一定的步长进行逐点绘制，实现直线的绘制。
算法主要涉及到线性插值的思想，即根据已知的两点坐标，通过计算它们之间的差值，然后根据这个差值和步长来确定新的像素点的位置。
2. 中点画线法：一种线段绘制算法，从线段的起点和终点出发，按照一定的规则向终点逐步逼近，并在途中以控制变量的方式得出每个像素点的坐标，从而绘制出所需的线条。
具体实现中，通过计算线段斜率的变化情况，分为斜率小于1和大于等于1两种情况，并采用Bresenham的对称性原理，以中点的颜色来控制每个像素点的生长方向，从而获得较高的绘制效率和图像质量表现。
3. Bresenham算法：通过一系列的迭代来确定一个像素点是否应该被绘制。
对于一条从点(x1,y1)到点(x2,y2)的直线，首先计算出斜率k。
然后，通过比较每个像素点的y值到直线上的y值，来决定哪些像素点应该被绘制。
当斜率k大于等于1时，在x方向上迭代，而对于每个x值，计算出y值，并将像素点(x,y)绘制。
当斜率k小于1时，在y方向上迭代，而对于每个y值，计算出x值，并将像素点(x,y)绘制。
以上内容仅供参考，如需更多信息，建议查阅相关文献或咨询数学专业人士。
1、直线生成算法1.算法分析1)DDA设直线两端点:P1(x1,y1)及 P0(x0,y0),dx=x1-x0,dy=y1-y0直线斜率:k=dy/dx直线方程: y=k*x+b有：y1=k*x1+b=k*x0+k*dx+b=y0+k*dx当dx=1时，有y1=y0+k算法复杂度：加法+取整优点：避免了y=k*x+b 方程中的浮点乘法,比直接用点斜式画线快 缺点：需浮点数加法及取整运算,不利于硬件实现.2)Midpoint当前像素点为P(xP,yP),下一个像素点有两种可选择点P1(xP+1,yP),P2(xP+1,yP+1)。
若M=(xP+1,yP+0.5)为P1与P2的中点，Q 为理想直线与x=xP+1垂线的交点。
x Pi=(xi, yi ) M Q P1 p2y当M 在Q 的上方时，应取P1为下一点；当M 在Q 的下方时，应取P2为下一点；直线段L （P0(x0,y0),P1(x1,y1)),用方程F （x,y ）=ax+by+c=0表示 a=y0-y1,b=x1-x0,c=x0y1-x1y0有点与L 的关系：线上：F （x,y ）=0上方：F （x,y ）>0下方：F （x,y ）<0判别式：d=F(M)=F(xP+1,yP+0.5)=a(xP+1)+b(yP+0.5)+cD 是xP,yP 的线性函数，可采用增量计算，提高运算效率：1）若d>=0,取P1，d1=d+a,增量为a2）若d<=,取P2,d2=d+a+b,增量为a+b可用2d 代替d 来摆脱浮点运算，写出仅含整数运算的算法3）Bresenhamy x F(x,y)=0 F(x,y)>0 F(x,y)<0 (x1,y1)(x0,y0)设直线方程为y=kx+b,有y1=y0+k(x-x0)=y0+k是否增1取决于误差项d的值，初始值d0=0X每增加1，有d=d+k令e=d-0.5,e0=-0.5,增量为k当e>=0时，取当前像素（xi,yi）的右上方像素（xi+1,yi+1）,e 减小1；当e<0时，更接近于右方像素（xi+1,yi）。
计算机图形学实验指导书袁科计算机技术实验中心目录实验一实现DDA、中点画线算法和Bresenham画线算法 (24)实验二实现Bezier曲线 (25)实验三实现B样条曲线 (26)实验四实现多边形填充的边界标志算法 (27)实验五实现裁剪多边形的Cohen-Sutherland算法 (28)实验六二维图形的基本几何变换 (30)实验七画图软件的编制 (31)实验一实现DDA、中点画线算法和Bresenham画线算法【实验目的】1、掌握直线的多种生成算法；2、掌握二维图形显示原理。
【实验环境】VC++6.0/ BC【实验性质及学时】验证性实验，2学时，必做实验【实验内容】利用任意的一个实验环境，编制源程序，分别实现直线的三种生成算法，即数字微分法(DDA)、中点画线法以及Bresenham画线算法。
【实验原理】1、数字微分法(Digital Differential Analyzer，DDA)算法思想：基于直线的微分方程来生成直线。
ε=1/max(|△x|,|△y|)max(|△x|,|△y|)=|△x|，即|k|≤1 的情况：max(|△x|,|△y|)=|△y|，此时|k|≥1：2、中点画线法算法思想：每次在最大位移方向上走一步，另一方向是否走步取决于误差项的判断。
3、Bresenham画线算法算法思想：其基本思想同中点算法一样，即每次在最大位移方向上走一步，而另一个方向是否走步取决于误差项的判断。
【实验要求】1．上交源程序；2．上交实验报告，实验报告内容如下：(1) 实验名称(2) 实验目的(3) 算法实现的设计方法及程序流程图(4) 程序结果分析【分析与思考】(1) 上述所阐述的三个算法，其基本算法只能适用于直线的斜率(|K|<=1) 的情形，如何将上述算法进行推广，使其能够处理任意斜率的直线？(2) 计算机显示屏幕的坐标圆心在哪里，与我们平时的习惯有什么差异，如何协调二者？实验二 实现Bezier 曲线【实验目的】1、掌握Bezier 曲线的定义；2、能编程实现N 次Bezier 曲线的绘制与显示。
2.1.1 生成直线的DDA算法数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法。
一、直线DDA算法描述：设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得= m =直线的斜率(2－1) 可通过计算由x方向的增量△x引起y的改变来生成直线：x i+1=x i+△x (2－2)y i+1=y i+△y=y i+△x·m (2－3) 也可通过计算由y方向的增量△y引起x的改变来生成直线：y i+1=y i+△y (2－4)x i+1=x i+△x=x i+△y/m (2－5) 式(2－2)至(2－5)是递推的。
二、直线DDA算法思想：选定x2－x1和y2－y1中较大者作为步进方向(假设x2－x1较大)，取该方向上的增量为一个象素单位(△x=1)，然后利用式(2－1)计算另一个方向的增量(△y=△x·m=m)。
通过递推公式(2－2)至(2－5)，把每次计算出的(x i+1，y i+1)经取整后送到显示器输出，则得到扫描转换后的直线。
之所以取x2－x1和y2－y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。
另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。
三、直线DDA算法实现：1、已知直线的两端点坐标：(x1，y1)，(x2，y2)2、已知画线的颜色：color3、计算两个方向的变化量：dx=x2－x1dy=y2－y14、求出两个方向最大变化量的绝对值：steps=max(|dx|，|dy|)5、计算两个方向的增量(考虑了生成方向)：xin=dx/stepsyin=dy/steps6、设置初始象素坐标：x=x1,y=y17、用循环实现直线的绘制：for(i=1；i<=steps；i++){ putpixel(x，y，color)；/*在(x，y)处，以color色画点*/ x=x+xin；y=y+yin；}四、直线DDA算法演示：五、直线DDA算法特点：该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。
dda算法生成两点之间的线段DDA算法是一种数字微分算法，可以通过计算直线两个端点的坐标来生成两点之间的线段。
在计算机图形学中，生成线段是非常重要的，因此DDA算法在该领域有着广泛的应用。
这里我们将分步骤阐述DDA算法生成两点之间的线段的过程：1. 计算线段的斜率：通过计算两个端点的坐标差值和斜率来确定线段的方向。
斜率可以使用下面的公式来计算：slope = (y2 - y1) / (x2 - x1)，其中(x1, y1)和(x2, y2)表示线段的两个端点。
2. 确定像素数量：为了生成线段，我们需要知道需要绘制多少个像素。
如果线段是水平的，则需要计算x轴上像素的数量；如果线段是垂直的，则需要计算y轴上像素的数量。
可以使用下面的公式来计算数量：pixels = max(abs(x2 - x1), abs(y2 - y1))3. 计算增量：增量是每个像素步长的大小，我们可以使用斜率来计算它。
如果线段的斜率小于1，则x方向的增量为1，并且y方向的增量为斜率。
如果线段的斜率大于1，则y方向的增量为1，并且x 方向的增量为1/斜率。
可以使用下面的公式来计算增量：xincr = sign(x2 - x1), yincr = sign(y2 - y1), xdelta = abs(x2 - x1), ydelta = abs(y2 - y1), slope = ydelta / xdelta, x = x1, y = y1。
4. 绘制像素：现在我们有了每个像素步长的大小和像素数量，我们可以使用DDA算法来绘制像素。
在每个步骤中，我们先绘制一个像素，并更新当前位置(x, y)。
增量的值可以用于计算下一个点的位置，如x += xincr和y += yincr。
在绘制过程中，我们可以使用Bresenham算法进行像素的绘制。
5. 更新位置：在每次绘制后，我们需要更新当前位置(x, y)。
如果线段的斜率小于1，则需要更新x的值，如果线段的斜率大于1，则需要更新y的值。
dda算法生成两点之间的线段DDA算法是一种用于生成两点之间线段的计算机图形学算法。
它是一种比较简单而又常用的算法，可以在计算机屏幕上绘制出直线。
DDA算法的核心思想是通过计算斜率来确定每个像素点的位置，从而形成一条连续的直线。
该算法的优点在于简单易懂，计算速度快，能够满足常见的直线绘制需求。
我们需要确定两个点的坐标。
假设点A的坐标为(x1, y1)，点B的坐标为(x2, y2)。
然后，我们需要计算出直线的斜率k，即k = (y2 - y1) / (x2 - x1)。
接下来，我们需要根据斜率k的绝对值来判断直线是近似为水平线还是垂直线。
如果|k| ≤ 1，则直线近似为水平线，我们选择以x 为基准，逐个计算每个像素点的y坐标。
如果|k| > 1，则直线近似为垂直线，我们选择以y为基准，逐个计算每个像素点的x坐标。
对于水平线的情况，我们从x1到x2依次计算每个像素点的y坐标。
假设当前正在计算第i个像素点，那么其坐标为(xi, yi)，其中xi = x1 + i，而yi可以通过以下公式计算得出：yi = y1 + k * i。
对于垂直线的情况，我们从y1到y2依次计算每个像素点的x坐标。
假设当前正在计算第i个像素点，那么其坐标为(xi, yi)，其中yi = y1 + i，而xi可以通过以下公式计算得出：xi = x1 + i / k。
在计算过程中，我们需要对坐标进行取整操作，以获取最接近的整数坐标。
这是因为计算机屏幕上的像素点是离散的，无法表示小数坐标。
通过以上步骤，我们可以得到直线上的所有像素点的坐标。
然后，我们可以使用绘图函数将这些像素点连接起来，形成一条连续的直线。
需要注意的是，DDA算法存在一些问题。
首先，由于使用了浮点数计算，可能会产生误差。
其次，如果斜率k过大或过小，可能会导致直线显示不完整或过于密集。
为了解决这些问题，可以进行取整操作或者进行优化算法。
DDA算法是一种简单而有效的直线生成算法。
盐城师范学院数学科学学院实验报告课程名称计算机图形学班级08（6）学号15号姓名陈叶玲实验地点主楼B408 实验日期4月21日实验学时2课时实验名称DDA算法生成直线实验类型 基础性 综合性 设计性实验目的：理解基本图形元素光栅化的基本原理，掌握一种基本图形元素光栅化算法，利用OpenGL实现直线光栅化的DDA算法。
实验环境：(包括软件平台和硬件平台)工具：VC++6.0操作系统版本：WINGDOWS-XP2，主要硬件：CPU 2.4GHz，内存 512M，显示器：三星SyncMaster793DF实验内容及步骤 (含源程序)：直线是图形中最基本的元素，DDA算法是基于数字微分思想的直线声成算法，而Bresenham算法是比较常用和效果良好的直线算法。
通过本次试验学生对比学习直线的生成算法和图形效果的优良评价。
近一步巩固学生的程序设计能力和图形库使用的能力，以及图形算法的理解和掌握。
源程序：#include <GL/glut.h>void LineDDA(int x0,int y0,int x1,int y1/*,int color*/){int x, dy, dx, y;float m;dx=x1-x0;dy=y1-y0;m=dy/dx;y=y0;glColor3f (1.0f, 1.0f, 0.0f);glPointSize(1);for(x=x0;x<=x1; x++){glBegin (GL_POINTS);glVertex2i (x, (int)(y+0.5));glEnd ();y+=m;}}void myDisplay(void){glClear(GL_COLOR_BUFFER_BIT);glColor3f (1.0f, 0.0f, 0.0f);glRectf(25.0, 25.0, 75.0, 75.0);glPointSize(5);glBegin (GL_POINTS);glColor3f (0.0f, 1.0f, 0.0f); glVertex2f (0.0f, 0.0f);glEnd ();LineDDA(0, 0, 200, 300);glBegin (GL_LINES);glColor3f (1.0f, 0.0f, 0.0f); glVertex2f (100.0f, 0.0f);glColor3f (0.0f, 1.0f, 0.0f); glVertex2f (180.0f, 240.0f); glEnd ();glFlush();}void Init(){glClearColor(0.0, 0.0, 0.0, 0.0);glShadeModel(GL_FLAT);}void Reshape(int w, int h){glViewport(0, 0, (GLsizei) w, (GLsizei) h);glMatrixMode(GL_PROJECTION);glLoadIdentity();gluOrtho2D(0.0, (GLdouble) w, 0.0, (GLdouble) h);}int main(int argc, char *argv[]){glutInit(&argc, argv);glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);glutInitWindowPosition(100, 100);glutInitWindowSize(400, 400);glutCreateWindow("Hello World!");Init();glutDisplayFunc(myDisplay);glutReshapeFunc(Reshape);glutMainLoop();return 0;}实验结果及分析：通过本次实验，初步了解了计算机图形学在计算机图像处理，工程制作，平面设计上的应用，掌握了计算机绘制圆和直线的几种算法，DDA直线和圆的生成算法，并且理解和掌握了他们的优缺点，在以后的实验中会努力学习，争取把这门计算机图形学课学好。
dda数字积分插补算法DDA（Digital Differential Analyzer）数字积分插补算法是计算机图形学中常用的一种直线段插值算法。
它的主要作用是根据给定的两个端点坐标，通过在直线上等间距采样的方式，计算出直线上各个点的坐标值，从而实现直线的平滑插值。
DDA算法的基本思想是利用直线的斜率来逐步逼近直线的路径，从而计算出直线上各个点的坐标。
具体步骤如下：1. 计算出直线的斜率k，即直线在x轴上的单位增量Δx与在y轴上的单位增量Δy的比例：k = Δy / Δx。
2. 选择直线上两个端点中x值较小的一个作为起始点，并以其坐标值（x0，y0）作为起始值。
3. 将起始点的坐标值作为当前点的坐标值，并将其绘制到屏幕上。
4. 通过递增x坐标值的方式，计算出下一个点的y坐标值，即y = y0 + k。
5. 将下一个点的坐标值（x0+1，y）作为当前点的坐标值，并将其绘制到屏幕上。
6. 重复步骤4和步骤5，直到达到直线的结束点。
通过以上步骤，可以得到直线上各个点的坐标值，从而实现直线的平滑插值。
DDA算法的优点是计算简单、速度快，适用于直线斜率变化不大的情况。
但由于采用等间距采样的方式，可能导致插值结果与实际直线存在误差。
为了更好地理解DDA算法的原理，下面以一个具体的例子来说明。
假设有两个端点坐标分别为（2，2）和（8，5），我们来计算出直线上各个点的坐标。
计算出直线的斜率k = (5-2) / (8-2) = 3/6 = 1/2。
然后，选择起始点（2，2）作为起始值，并将其绘制到屏幕上。
接下来，通过递增x坐标值的方式，依次计算出下一个点的y坐标值。
根据步骤4，我们可以得到以下结果：x | y--------2 | 23 | 2 + 1/2 = 2.54 | 2.5 + 1/2 = 35 | 3 + 1/2 = 3.56 | 3.5 + 1/2 = 47 | 4 + 1/2 = 4.58 | 4.5 + 1/2 = 5我们得到直线上各个点的坐标值为（2，2）、（3，2.5）、（4，3）、（5，3.5）、（6，4）、（7，4.5）和（8，5）。
