资源描述：
《计算机图形学作业样本》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、长春大学计算机图形作业作业名称直线和圆中点Bresenham算法小组成员九位学号姓名院系计算机科学与技术系专业指导教师冯萍目录1.直线的Bresenham算法原理…………………………………………………11.1中点Bresenham算法……………………………………………………21.2改进的Bresenham算法…………………………………………………32.程序运行结果…………………………………………………………………93.总结…………………………………………………………………………114.参考资料……………………………………………………………………125.附录…………………………………………
2、………………………………131.直线的Bresenham算法原理1.1中点Bresenham算法给定直线的两个端点，可得到直线方程F(x,y)=y-kx-b=0且这时直线将平面分为三个区域：对于直线上的点，F(x,y)=0；对于直线上方的点，F(x,y)>0；对于直线下方的点，F(x,y)<0。由Bresenham提出的直线生成算法的基本原理是，每次在最大位移方向上走一步，而另一个方向是走步还是不走步取决于误差项的判别，如下图所示。Q假定0≤k≤1，由于x是最大位移方向，因此每次在x方向上加1，y方向上或加1，或加0.假设当前点是P，则下一个点在与中选一。以M表示与的中点，即。又设Q是理
3、想直线与垂直直线x=+1的交点；显然，若M在Q的下方，则离直线近，应取为下一个像素；否则取。如前所述，直线方程为F(x,y)=y-kx-b。欲判断Q在M上方还是下方，只要把M代入F(x,y)，并判断它的符号即可。构造判别式如下：当<0时，M在直线下方，故应取。当>0时，则应取正右方的。当=0时，二者一样合适，可以随便取一个。我们约定取，即-12-当<0时，取右上方像素，欲判断再下一个像素应取哪一个，应计算此时，的增量为1-k。当≥0时，取正右方像素，要判断再下一个像素应取哪一个，应计算此时，的增量为-k。下面计算的初值。显然，直线的第一个像素在直线上，因此相应的的初始值计算如下：由于我们
4、使用的只是的符号，因此可以用2代替来摆脱小数。此时算法只涉及整数运算。这样，0≤k≤1时，Bresenham算法的绘图过程如下：①输入直线的两端点；②计算初始值，，；③绘制点(x,y)。判断d的符号，若d<0，则(x,y)更新为（x+1，y+1），d更新为d+2-2；否则(x,y)更新为（x+1，y），d更新为d-2；④当直线没有画完时，重复步骤③，否则结束。0≤k≤1时Bresenham算法绘制直线的程序（仅包含整数运算）如下：voidMidBresenhamLine(intx0,inty0,intx1,inty1,intcolor){intdx,dy,UpIncre,DownIncr
5、e,x,y;if(x0>x1)-12-{x=x1;x1=x0;x0=x;y=y1;y1=y0;y0=y;}x=x0;y=y0;dx=x1-x0;dy=y1-y0;d=dx-2*dy;UpIncre=2*dx-2*dy;DownIncre=-2*dy;while(x<=x1){putpixel(x,y,color);x++;if(d<0){y++;d+=UpIncre;}elsed+=DownIncre;}}1.2改进Bresenham算法虽然中点Bresenham算法是一种效率很高的算法，但也还有改进的余地。当然，其基本原理仍然是每次在最大位移方向上走一步，二另一个方向上走步是不走步取决
6、于误差项的判别。为叙述简单，同样定0≤k≤1的直线段（k=/），其端点为。于是这样考虑该直线段的绘制：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，交点与网格线之间的误差为，根据确定该列网格中与此交点最近的像素点。当>0.5时，直线更接近于像素点；当<0.5时，更接近于像素点；当=0.5时，与上述两像素点一样接近，约定取，即-12-其中的关键在于误差项，它的初始值为0，每走一步有一旦y方向上走了一步，就把它减去1（此时可能出现负误差，这表明交点在所取网格点之下）。为方便计算，令。则当>0时，下一像素的y坐标增加1；否则，下一像素的y坐标不增
7、，即有此时，的初值为-0.5，每走一步有。当>0时，将减1.改进的Bresenham算法还有一个缺点：在计算直线斜率与误差时，要用到小数与除法，不利于硬件实现。因此改进如下：由于算法中只用到误差项的符号，于是可以用2e来替换e。这样就能获得整数Bresenham算法且可避免除法。其算法步骤如下：①输入直线的两端点；②计算初始值，，e=，③绘制点(x,y)。④e更新为e+2。判断e的符号，若e>0，则(x,y)更新为（x+1，y+1）
