实验报告(Bresenham画线算法)

实验报告（Bresenham画线算法）一、实验目的根据Bresenham画线算法，掌握绘制直线的程序设计方法。二、实验原理为了说明算法原理，我们首先考虑斜率非负且不超过1的直线的光栅化过程。设直线的起点坐标为(xs,ys)，终点坐标为(xe,ye)，则直线的方程为：dyyxBdx因此，其隐函数表示为：(,)0FxydyxdxyBdxaxbyc其中：,,adybdxcBdx显然，对于直线上的点，F(x,y)等于零；对于直线下方的点，F(x,y)大于零；而对直线上方的点，F(x,y)小于零。假设当前选择的像素点是(xi,yi)，那么下一步要选择的像素点可能是NE(xi+1,yi+1)，也可能是E(xi+1,yi)。选择的原则是看哪一个离直线与x=xi+1的交点最近。运用中点法则，我们只需考察中点M在直线的哪一侧，即计算：F(M)=F(xi+1,yi+1/2)=a(xi+1)+b(yi+0.5)+c并确定其正负号。由于根据函数值F(xi+1,yi+1/2)进行判定，所以我们定义一个判定函数如下：di=2F(xi+1,yi+1/2)根据定义：di=2a(xi+1)+2byi+b+2c当di0时，M在直线的上方，取E为下一个像素点；当d0时，M在直线的下方，取NE为下一个像素点；当d=0时，两者都可以选，我们约定选E。di的计算需要做4次加法和两次乘法。因此，为了有效地计算判定函数，我们需要建立关于di的递推公式。显然，di的变化依赖于下一个像素点选的是NE还是E。当di0时，下一个像素点是E，那么：di+1=2F(xi+2,yi+1/2)=2a(xi+2)+2byi+b+2c=di+2a当di0时，下一个像素点是NE，则：di+1=2F(xi+2,yi+1+1/2)=2a(xi+2)+2b(yi+1)+b+2c=di+2a+2b由此，得到计算判定函数di的递推公式：12,022,0iiiiiddyddddydxd因为直线上的第一个像素点就是直线的起点(xs,ys)，所以判定函数di的初值为：d0=2a(xs+1)+2bys+b+2c=2dy-dx故满足条件的直线的Bresnham算法的步骤如下：Step1.初始化dx=xe－xs,dy=ye－ys,x=xs,y=ys,d=2dy－dx；Step2.当xxe时，执行下述操作：（1）画像素点(x,y)；（2）求下一个像素点：x=x+1；if(d0)theny=y+1；（3）计算判定函数d：if(d0)thend=d+2dy－2dx；elsed=d＋2dy；Step3.算法结束。三、实验程序#includestdio.h#includegraphics.h#includemath.h#includeconio.h#includeeasyx.hvoidBresenham_line(intxs,intys,intxe,intye,intc){intdx=abs(xe-xs),dy=abs(ye-ys),i,x=xs,y=ys;inttwoDX=2*dx,twoDY=2*dy,p=2*dy-dx;ints1,s2,interchange=0,temp;if(xe-xs=0)s1=1;elses1=-1;if(ye-ys=0)s2=1;elses2=-1;if(dydx){temp=dx;dx=dy;dy=temp;interchange=1;}for(i=0;i=dx;i++){putpixel(x,y,c);if(p0){if(interchange)x+=s1;else{y+=s2;p-=twoDX;}}if(interchange)y+=s2;elsex+=s1;p+=twoDY;}}voidmain(){intx1=60,y1=88,x2=345,y2=789,c=GREEN;intdx,dy,n,k,f;intx,y;intgdriver,gmode;gdriver=DETECT;initgraph(&gdriver,&gmode,);Bresenham_line(x1,y1,x2,y2,c);getch();closegraph();}四、测试结果x1=60,y1=88,x2=345,y2=789,c=GREEN，则得图如下示：五、实验总结本次实验，让我了解到Bresenham算法实现的具体过程，对此算法生成线的过程和特点也有了进一步的了解。Bresenham算法生成直线的速度很快，由于光栅化的影响，直线的亮度明显不均匀。