(1)直线生成算法.doc

直线生成算法——Bresenham法最近的研究涉及在像素图上作直线，自己也不想花时间摸索，于是在网上找到了Bresenham的直线生成算法，有一篇博客讲得清晰明了，但是算法上有些问题，我进行了改进和移植，下面讲解Bresenham的直线生成算法时也是参考这篇博文。

1.算法简介图1算法思想：图1中，连接M点和N点的直线经过点B，由于是像素图，所以实际上B 点应该由A点或者C点代替。

当B点更靠近A点时，选择点A（x+1,y+1）；当B点更靠近C点时，选择点C（x+1,y）。

因此，当ε+m < 0.5时，绘制(x + 1, y)点，否则绘制(x + 1, y + 1)点，这里ε为累加误差，表达式为：式中：表示在第n次计算时的值，表示在第n+1次计算时的值；m就是直线的斜率。

由于斜率m的值有正有负，有可能为0，也可能为∞，为了避免分别讨论这些情况，将上述公式两边都乘以dx, 并将ε*dx用ξ表示，则有式中：表示在第n次计算时的值，表示在第n+1次计算时的值；dx为起点和终点横坐标之差，dy为起点和终点纵坐标之差。

还需说明一点，由直线斜率的定义故值得注意的是，现在我们只考虑dx > dy，且x，y的增量均为正的情况，但实际上有8种不同的情况（但是算法思想不变），如图2所示如图22.算法程序前文提到的那篇博文提出了一种方法，能将这8种情况都考虑，很巧妙。

但是实际应用时发现程序运行结果不是完全对，多次检查之后将程序进行了修改。

修改后的算法VB程序如下‘**************************************************************************** Type mypos '自定义数据类型x As Integery As IntegerEnd Type‘**************************************************************************** Function Bresenham(arr() As mypos, x1, y1, x2, y2)Dim x!, y!, dx!, dy!, ux%, uy%, eps!Dim cnt%ReDim arr(100)dx = x2 - x1dy = y2 - y1If dx >= 0 Then ux = 1If dx < 0 Then ux = -1If dy >= 0 Then uy = 1If dy < 0 Then uy = -1x = x1y = y1eps = 0dx = Abs(dx): dy = Abs(dy)cnt = 0If dx >= dy ThenFor x = x1 To x2 Step uxcnt = cnt + 1If 2 * (eps + dy) < dx Theneps = eps + dyarr(cnt).x = xarr(cnt).y = yElseeps = eps + dy - dxIf cnt >= 2 Then y = y + uy 'cnt大于2才执行y = y + uy，即排除起始坐标点，否则造成错误结果arr(cnt).x = xarr(cnt).y = yEnd IfNext xElseFor y = y1 To y2 Step uycnt = cnt + 1If 2 * (eps + dx) < dy Theneps = eps + dxarr(cnt).x = xarr(cnt).y = yElseeps = eps + dx - dyIf cnt >= 2 Then x = x + ux 'cnt大于2才执行x = x + ux，即排除起始坐标点，否则造成错误结果arr(cnt).x = xarr(cnt).y = yEnd IfNext yEnd Ifarr(0).x = cnt’记录元素个数End Function如果大家有不同看法，还希望共同讨论3.程序运行结果（VB+ OpenGL）图3图4绘制y=x，0≤x≤10，图3是原程序运行结果，图4时修改后的程序运行结果，原程序运行得到的起点是（0,1），但实际应该是（0,0）图5图6绘制直线[第1个坐标为起点，第2个坐标为终点]（5,5）-（15,15）、（5,10）-（15,15）、（5,15）-（15,15）、（5,20）-（15,15）、（5,25）-（15,15）；（25,5）-（15,15）、（25,10）-（15,15）、（25,15）-（15,15）、（25,20）-（15,15）、（25,25）-（15,15）；（5,5）-（15,15）、（10,5）-（15,15）、（15,5）-（15,15）、（20,5）-（15,15）、（25,5）-（15,15）；（5,25）-（15,15）、（10,25）-（15,15）、（15,25）-（15,15）、（20,25）-（15,15）、（25,25）-（15,15）；图5是原程序运行结果，图6是修改后的程序运行结果。

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）。

实验一基本图形元素生成算法1．实验目的：1）熟练掌握基本图形元素生成算法。

2）对高级语言的图形模式的设定有比较详细的了解。

3）对基本图形类（或函数）的调用方法有一个比较详细的了解。

2．实验内容：该学生自己选定一种基本图形（直线段），编写生成该基本图形的源程序，并能在计算机上编译运行，画出正确的图形。

3．实验步骤：1）DDA算法、Bresenham算法进行比较，选定比较合适的算法。

2）画出程序流程图；3）编写程序的源程序；4）编辑源程序并进行调试；5）进行特殊模式的运行测试，并结合情况进行调整。

6）打印源程序或把源程序以文件的形式提交。

4．实验报告：源代码：main.cpp#include <iostream>#include <cmath>using namespace std;class Point{protected:int xx,yy;public:Point(int a=0,int b=0):xx(a),yy(b){}Point(const Point& p):xx(p.xx),yy(p.yy){}void setPos(int x,int y){xx=x,yy=y;}int getX(){return xx;}int getY(){return yy;}~Point(){}};class Line{protected:Point p1,p2;public:Line(Point p,Point q):p1(p),p2(q){}void DDAline(){//数值微分法绘制直线int dx,dy,epsl,k;float x,y,xIncre,yIncre;dx=p2.getX()-p1.getX();dy=p2.getY()-p1.getY();x=p1.getX(),y=p1.getY();if(fabs(dx)>fabs(dy))epsl=fabs(dx);else epsl=fabs(dy);xIncre=(float)dx/(float)epsl;yIncre=(float)dy/(float)epsl;for(k=0;k<=epsl;k++){cout<<"("<<(int)(x+0.5)<<","<<(int)(y+0.5)<<")"<<endl; x+=xIncre;y+=yIncre;}}void MidBresenhamline(){//k>=0&&k<=1中点Bresenham算法int dx,dy,d,UpIncre,DownIncre,x,y;int m=p1.getX(),n=p2.getX();if(m>n){p1.setPos(p2.getX(),p2.getY());p2.setPos(p1.getX(),p1.getY());}x=p1.getX();y=p1.getY();dx=p2.getX()-p1.getX();dy=p2.getY()-p1.getY();d=dx-2*dy;UpIncre=2*dx-2*dy;DownIncre=-2*dy;while(x<=p2.getX()){cout<<"("<<x<<","<<y<<")"<<" "<<"d="<<d<<endl;x++;if(d<0){y++;d+=UpIncre;}else d+=DownIncre;}}~Line(){}};int main(){int x0,y0,x1,y1;int flag;cout<<"Please enter the value of vairable x0,y0,x1,y1in order:"; cin>>x0>>y0>>x1>>y1;Point pa(x0,y0),pb(x1,y1);//创建两个点对象Line line(pa,pb);//由两个点对象组合成一个线对象cout<<"Please enter the identifier of algorithms:"<<endl;cout<<"1.DDAline"<<endl<<"2.MidBresenhamline"<<endl;cin>>flag;if(1==flag)line.DDAline();else if(2==flag)line.MidBresenhamline();else cout<<"Run Failed!"<<endl;return 0;}流程图：DDA算法绘制直线流程中点Bresenham算法图形：。

实验一: 直线数学上，理想的直线是由无数个点构成的集合，没有宽度。

计算机绘制直线是在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，实现显示器绘制直线，即通常所说的直线的扫描转换，或称直线光栅化。

由于一图形中可能包含成千上万条直线，所以要求绘制直线的算法应尽可能地快。

本节介绍一个像素宽直线的常用算法：数值微分法（DDA）、中点画线法、Bresenham 算法。

一. DDA（数值微分）算法DDA算法原理：如图1-1所示，已知过端点的直线段；直线斜率为，从的左端点开始，向右端点步进画线，步长=1（个像素），计算相应的坐标；取像素点[ , round（y）] 作为当前点的坐标。

计算，当，即当x每递增1，y递增k（即直线斜率）。

1的情形。

在这种情况下，x每增加1, y最多增加1。

当时，必须把x，y地位互换，y每增加1，x相应增加1/k（请参阅后面的Visual C++程序）。

注意：上述分析的算法仅适用于k二. 生成直线的中点画线法中点画线法的基本原理如图1-2所示。

在画直线段的过程中，当前像素点为P，下一个像素点有两种选择，点P1或P2。

M为P1与P2中点，Q为理想直线与X=Xp+1垂线的交点。

当M在Q的下方时，则P2应为下一个像素点；当M在Q的上方时，应取P1为下一点。

中点画线法的实现：令直线段为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。

把M代入F（x, y），判断F的符号，可知Q点在中点M的上方还是下方。

为此构造判别式d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c。

南昌大学学生姓名：陈凯学号：405906111033学院：机电工程学院专业：机械设计及理论论文题目：直线生成算法文献综述2012年9月14日1直线生成算法综述陈凯（南昌大学机电工程学院江西南昌 330031 ）摘要：本文对现有的直线生成算法进行综述，介绍了各种算法的原理、优缺点、算法基础等。

详细说明了基于并行填充模式的直线生成算法，并以此为例子比较了其与Bresenham算法的效率和误差大小，综述了各种算法的适用条件。

关键字：直线算法并行填充模式 Bresenham算法引言直线是光栅图形学中最基本的元素之一, 直线生成算法的效率和质量直接影响着图形应用系统的效率和质量。

直到最近几年,为了提高直线的绘制速度, 仍然有大量的研究工作出现。

这些工作集中在如何一次生成位于直线上尽可能多的像素，在计算机中生成直线的常用算法有数值微分法（DDA）、中点画线法和1965年出现的Bresenham算法。

其中Bresenham算法是依据直线的斜率，快速生成直线，这种算法在直线段接近坐标的时候有很高的效率，但是随着斜率的增大, 其效率会显著下降。

以上所说的各种直线生成算法的特点都是一次生成尽可能的像素的数目。

但是, 若增加每次生成像素的数量, 则会由于pattern数量过多, 造成对误差值判断操作次数增加, 致使直线生成的效率反而会下降。

因此本文查看了大量的文献，找出了生成直线的其余常用算法，对常用的直线生成算法进行综述，并评价其各自的优缺点。

正文1、对称式八步直线生成算法由Bresenham 直线生成算法的基本思想可知, 生成的下一个像素与当前像素之间存在两种关系——沿轴向或沿斜向。

如当前像素点为P, 则下一个像素点12只能选择轴向或者斜向的下一个邻近像素点。

若使用4个像素的生成模式来生成直线, 即当n= 4时, 可以将直线依据其斜率划分为六类, 那么通过研究可供选择的生成模式集，每一种被选取的生成模式与这些直线的斜率范围的关系我们发现，直线的斜率不同, 其可选模式构成的模式集也不同；每类直线可供选择的生成模式集中均包含五种生成模式；直线的斜率决定了生成该直线时可供选择的生成模式集。

第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) y0 0 01 02 13 14 2图3 直线段的扫描转换注意：上述分析的算法仅适用于|k| ≤1的情形。

计算机图形学直线段⽣成绘制的实现算法实验⼆直线段⽣成绘制的实现算法班级 10信计专接本学号 20100504008 姓名吴晓楠分数⼀、实验⽬的和要求：1.了解计算机图形学的原理、⽅法和应⽤。

2.熟悉直线的⽣成算法，掌握直线的绘制3.实现C语⾔编写图形程序。

学会了解VC++的基本应⽤同时了解TC图形环境配置，学习简单的图形画法，并⽐较画法的优劣，尝试在计算机实现，得到图形，验证⽐较图形。

⼆、实验内容：1、掌握直线段的⽣成算法，并⽤C/WIN-TC/VC++实现算法，包括中点法⽣成直线，微分数值法⽣成直线段等。

2、编程实现DDA算法、Bresenham算法、中点画线法绘制直线段三、实验结果分析1、⽣成直线的DDA算法算法思想：⼀个坐标轴上以单位间隔增量，决定另⼀个坐标轴上最靠近线段路径的对应整数值。

假定x2﹣x1的绝对值⼤于y2﹣y1的绝对值，取x为⼀个象素单位长，即x 每次递增⼀个象素，然后利⽤下式计算相应的y值：yk+1﹦yk﹢△y﹦yk﹢m·△x 对于|m|＞1的线段，可通过计算由Y⽅向的增量△y引起的改变来⽣成直线：xk+1﹦xk﹢△x﹦xk﹢m·△y⽣成直线的DDA算法思想是源⽤初中直线的⽅程得出来的，⽽⽣成直线的中点算法是通过将DDA算法的⽅程式改为隐函数形式，然后通过与中点的⽐较确定该取的像素，绘制图线。

/* DDA */#includevoid 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;}}main(){int a,b,c,d,e;int graphdriver=DETECT;int graphmode=0;initgraph(&graphdriver,&graphmode,""); cleardevice();a=0;b=100;c=200;d=300;e=200;linedda(a,b,c,d,e);getch();closegraph();}运⾏结果：VC++环境：#include#include// 四舍五⼊int Round(float x){return (int)(x < 0 ? x - 0.5 : x + 0.5); }// 使⽤ DDA 算法画任意斜率的直线（包括起始点，不包括终⽌点）void Line_DDA(int x1, int y1, int x2, int y2, int color){float x, y; // 当前坐标点float cx, cy; // x、y ⽅向上的增量int steps = abs(x2 - x1) > abs(y2 - y1) ? abs(x2 - x1) : abs(y2 - y1); x = (float)x1;y = (float)y1;cx = (float)(x2 - x1) / steps;cy = (float)(y2 - y1) / steps;for(int i = 0; i < steps; i++){putpixel(Round(x), Round(y), color); // 在坐标 (x, y) 处画⼀个 color 颜⾊的点x += cx;y += cy;}}// 主函数void main(){initgraph(640, 480);// 测试画线Line_DDA(100, 100, 100, 478, RED);// 按任意键退出getch();}2、Bresenham直线算法是⽤来描绘由两点所决定的直线的算法，它会算出⼀条线段在 n 维光栅上最接近的点。

《计算机图形学》实验报告一、实验目的计算机图形学是一门研究如何利用计算机生成、处理和显示图形的学科。

通过本次实验，旨在深入理解计算机图形学的基本原理和算法，掌握图形的生成、变换、渲染等技术，并能够运用所学知识解决实际问题，提高对图形学的应用能力和编程实践能力。

二、实验环境本次实验使用的编程语言为 Python，使用的图形库为 Pygame。

开发环境为 PyCharm。

三、实验内容1、直线的生成算法DDA 算法（Digital Differential Analyzer）Bresenham 算法DDA 算法是通过计算直线的斜率来确定每个像素点的位置。

它的基本思想是根据直线的斜率和起始点的坐标，逐步计算出直线上的每个像素点的坐标。

Bresenham 算法则是一种基于误差的直线生成算法。

它通过比较误差值来决定下一个像素点的位置，从而减少了计算量，提高了效率。

在实验中，我们分别实现了这两种算法，并比较了它们的性能和效果。

2、圆的生成算法中点画圆算法中点画圆算法的核心思想是通过判断中点的位置来确定圆上的像素点。

通过不断迭代计算中点的位置，逐步生成整个圆。

在实现过程中，需要注意边界条件的处理和误差的计算。

3、图形的变换平移变换旋转变换缩放变换平移变换是将图形在平面上沿着指定的方向移动一定的距离。

旋转变换是围绕一个中心点将图形旋转一定的角度。

缩放变换则是改变图形的大小。

通过矩阵运算来实现这些变换，可以方便地对图形进行各种操作。

4、图形的填充种子填充算法扫描线填充算法种子填充算法是从指定的种子点开始，将相邻的具有相同颜色或属性的像素点填充为指定的颜色。

扫描线填充算法则是通过扫描图形的每一行，确定需要填充的区间，然后进行填充。

在实验中，我们对不同形状的图形进行了填充，并比较了两种算法的适用情况。

四、实验步骤1、直线生成算法的实现定义直线的起点和终点坐标。

根据所选的算法（DDA 或Bresenham）计算直线上的像素点坐标。