第四讲 改进的Bresanham算法圆的扫描转换.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,济南大学信息学院,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息科学与工程学院,*,2026/6/9 周二,济南大学信息学院,1,第,4,讲 改进的,Brensemham,算法,圆的扫描转换,2026/6/9 周二,济南大学信息学院,2,5,.1.2 中点,Bresenham,算法,设两端点为,P,0,(x,0,y,0,),和,P,1,(x,1,y,1,)，,则直线的方程,该直线方程将平面分为三个区域：,对于直线上的点，,F(x,y)=0；,对于直线上方的点，,F(x,y)0；,对于直线下方的点，,F(x,y)0。,2026/6/9 周二,济南大学信息学院,3,F(x,y)=y-2x-1=0,2026/6/9 周二,济南大学信息学院,4,Bresenham,算法的基本原理,：在最大位移方向上走一步时，在另一个方向上是否走步取决于误差项的判断。,假定0,k1，x,是最大位移方向,2026/6/9 周二,济南大学信息学院,5,判别式,：,则有：,0,k1,2026/6/9 周二,济南大学信息学院,6,误差项的递推,d0：,取点(,x,i,+1,y,i,+1),下一个中点,(x,i,+2,y,i,+1.5,),0,k1,2026/6/9 周二,济南大学信息学院,7,误差项的递推,d0：,取点(,x,i,+1,y,i,),下一个中点,(x,i,+2,y,i,+0.5,),0,k1,2026/6/9 周二,济南大学信息学院,8,初始值,d,的计算,0,k1,2026/6/9 周二,济南大学信息学院,9,用2,dx,代替,d,1.,输入直线的两端点,P,0,(x,0,y,0,),和,P,1,(x,1,y,1,)。,2.,计算初始值,x、y、,d=x-2y,、x=x,0,、y=y,0,。,3.,绘制点(,x,y)。,判断,d,的符号。,若,d0.5，,则(,x,y),更新为(,x+1,y+1)，,同时将,d,更新为,d-1；,否则(,x,y),更新为(,x+1,y)。,5.,当直线没有画完时，重复步骤3和4。否则结束。,2026/6/9 周二,济南大学信息学院,13,改进1,：为计算方便，令,e=d-0.5,e,初=-0.5，,每走一步有,e=e+k。,if(e0)then e=e-1,2026/6/9 周二,济南大学信息学院,14,算法步骤,为：（,0,k1,）,1.输入直线的两端点,P,0,(x,0,y,0,),和,P,1,(x,1,y,1,)。,2.,计算初始值,x、y、,e=-0.5,、x=x,0,、y=y,0,。,3.,绘制点(,x,y)。,4.,e,更新为,e+k,，,判断,e,的符号。若,e,0，,则(,x,y),更新为(,x+1,y+1)，,同时将,e,更新为,e-1,；,否则(,x,y),更新为(,x+1,y)。,5.,当直线没有画完时，重复步骤3和4。否则结束。,参见程序,bmipv01.c,2026/6/9 周二,济南大学信息学院,15,改进2,：为方便硬件实现，作以下改进摆脱小数、除法运算。,用2,ex,来替换,e,e,初=-,x，,每走一步有,e=e+2y。,if(e0)then e=e-2x,2026/6/9 周二,济南大学信息学院,16,算法步骤,：（,0,k1,）,1.输入直线的两端点,P,0,(x,0,y,0,),和,P,1,(x,1,y,1,)。,2.,计算初始值,x、y、,e=-x,、x=x,0,、y=y,0,。,3.,绘制点(,x,y)。,4.e,更新为,e+2y,，,判断,e,的符号。若,e0，,则(,x,y),更新为(,x+1,y+1)，,同时将,e,更新为,e-2x,；,否则(,x,y),更新为(,x+1,y)。,5.,当直线没有画完时，重复步骤3和4。否则结束。,2026/6/9 周二,济南大学信息学院,17,x y e e+2dy,00-5 -1,10-1 3,21-7 -3,31-3 1,42-9 -5,52-5 -1,例,：画直线段,P0(0,0)-P1(5,2),斜率,0,k1,e,的,初始值-,x=-5 2y4 -2x-10,相应坐标值和判别式如下：,2026/6/9 周二,济南大学信息学院,18,以上算法仅考虑，0,k1,时的情况，对于其它情况依此类推。,以1,k,为例说明,2026/6/9 周二,济南大学信息学院,19,1,k,d,k,k,d,2026/6/9 周二,济南大学信息学院,20,对于点,P,i,(x,i,y,i,),令,e=d-0.5,K1,2026/6/9 周二,济南大学信息学院,21,再,用2,ey,来替换,e,e,初=-,y，,每走一步有,e=e+1/k=e+2x。,if(e0)then e=e-2y,K1,2026/6/9 周二,济南大学信息学院,22,算法步骤,：（,k,1,）,1.输入直线的两端点,P,0,(x,0,y,0,),和,P,1,(x,1,y,1,)。,2.,计算初始值,x、y、,e=-y,、x=x,0,、y=y,0,。,3.,绘制点(,x,y)。,4.e,更新为,e+2x,，,判断,e,的符号。若,e0，,则(,x,y),更新为(,x+1,y+1)，,同时将,e,更新为,e-2y,；,否则(,x,y),更新为(,x+1,y)。,5.,当直线没有画完时，重复步骤3和4。否则结束。,2026/6/9 周二,信息科学与工程学院,23,圆的扫描转换,解决的问题：,绘出圆心在原点，半径为整数,R,的圆,x,2,+y,2,=R,2,圆心不在原点的圆，先平移至原点，扫描转换后再平移回原位置,2026/6/9 周二,信息科学与工程学院,24,B(y,x),C(-y,x),D(-x,y),E(-x,-y),F(-y,-x),G(y,-x),H(x,-y),A,5.2.1 八分法画圆,2026/6/9 周二,信息科学与工程学院,25,程序段为：,void circlepoint(int x,int y),putpixel(x,y,14);,putpixel(y,x,14);,putpixel(-y,x,14);,putpixel(-x,y0,14);,putpixel(-x,-y,14);,putpixel(-y,-x0,14);,putpixel(y,-x,14);,putpixel(x,-y,14);,程序,Cir8f0.c,(,0,0),为圆心，(,x,y),为圆上的点,2026/6/9 周二,信息科学与工程学院,26,程序段为：,void circlepoint(int x,int y,int x0,int y0),putpixel(x+x0,y+y0,14);,putpixel(y+x0,x+y0,14);,putpixel(-y+x0,x+y0,14);,putpixel(-x+x0,y+y0,14);,putpixel(-x+x0,-y+y0,14);,putpixel(-y+x0,-x+y0,14);,putpixel(y+x0,-x+y0,14);,putpixel(x+x0,-y+y0,14);,程序,Cir8f.c,(,x0,y0),为圆心，(,x,y),为以(,x0,y0),为圆心的圆上的点,2026/6/9 周二,信息科学与工程学院,27,解决问题,：,要得到整个圆的扫描像素集，只要扫描转换,1/8,圆弧即可,2026/6/9 周二,信息科学与工程学院,28,5.2.2 简单方程产生圆弧,算法原理,：利用其函数方程，直接离散计算,1/8圆弧,方法,1,笛卡尔方程直接计算,2026/6/9 周二,信息科学与工程学院,29,圆的方程绘制方法,C+,实现,void,圆的方程绘制,(),double xc=300,yc=200,R=150;,double xr=300+150/1.414;,double x,y;,for(x=xc;x=xr;x+),y=sqrt(R*R-(x-xc)*(x-xc)+yc;,SetPixel(x,y,RGB(0,0,0);,这一方法包括乘法和平方根运算，计算量较大，所画象素位置间的间距也是不一致的。,2026/6/9 周二,信息科学与工程学院,30,圆的极坐标方程为：,方法2,圆的极坐标方程,将,离散化,0,k,n,2026/6/9 周二,信息科学与工程学院,31,使用上述离散化方程，可以得到如下算法：,begin,for k0 to n,xx,c,Rcos(2,.k/n),yy,c,Rsin(2,.k/n),putpixel(x,y),next k,endfor,end,使用上述方法可沿圆周等距点绘制出圆来。算法中，,n,取的值越大，计算的点越多，但执行时间越长。此算法的缺点是含有三角函数，计算量大。,2026/6/9 周二,信息科学与工程学院,32,为了,避免三角函数运算，考虑下图,如果已经计算出圆上一点（,x,k,y,k,）,则增加一个角度,后，下一点（,x,k+1,y,k+1,）的坐标值可以用上一个点表示出。,x,k+1,Rcos(,),R(cos,cos,sin,sin,),R.cos,cos,Rsin,sin,x,k,cos,y,k,sin,y,k+1,Rsin(,),R(sin,cos,cos,sin,),Rcos,cos,Rsin,sin,y,k,cos,x,k,sin,5.2.3 DDA,圆的生成算法,2026/6/9 周二,信息科学与工程学院,33,当,足够小时有：,cos,1,sin,这样，方程式,x,k+1,x,k,cos,y,k,sin,y,k+1,y,k,cos,x,k,sin,可以改写为：,x,k+1,=x,k,y,k,y,k+1,=y,k,x,k,习惯上用,表示一个较小的量，用它替代,式子改写为：,x,k+1,=x,k,y,k,y,k+1,=y,k,x,k,2026/6/9 周二,信息科学与工程学院,34,利用前式，圆的参数方程生成算法可以描述如下：,begin,xx,c,R,yy,c,0,for,2,putpixel(x,y),xxy,yyx,endfor,end,上述算法中，,选取的值越小，计算的点越多，但执行时间越长。为了在光栅系统上得到连续的边界，可选取,1,R,，这样绘制的象素位置大约为一个单位间隔。此算法也被称为,DDA,圆的生成算法。,此圆的生成算法中仍包含浮点数和乘法运算，影响速度。,2026/6/9 周二,信息科学与工程学院,35,圆的参数绘制方法,C+,实现,void ApplicationProceesing(),double xc=300,yc=200,R=150;,double x,y,theta,delta;,x=xc+R;y=yc;,delta=1.0/R;,for(theta=0;theta0；,而对于圆内的点，,F(x,y)0,时，下一点取,P,d,(x,i,+1,y,i,-1)。,中点,M,的坐标为：,M(x,i,+1,y,i,-0.5),当,F(x,M,y,M,)0,时，取,P,d,(x,i,+1,y,i,-1),当,F(x,M,y,M,)=0,时，约定取,P,u,。,构造判别式,：,2026/6/9 周二,信息科学与工程学院,40,误差项的递推,d0：,下一个中点,(x,i,+2,y,i,-0.5,),增量为,2x,i,+3,2026/6/9 周二,信息科学与工程学院,41,误差项的递推,d0：,下一个中点,(x,i,+2,y,i,-1.5,),增量为,2(x,i,-y,i,)+5,2026/6/9 周二,信息科学与工程学院,42,判别式,d,的初始值,2026/6/9 周二,信息科学与工程学院,43,算法步骤,：,1.输入圆的半径,R。,2.,计算初始值,d=1.25-R、x=0、y=R。,3.,绘制点(,x,y),及其在八分圆中的另外七个对称点。,4.判断,d,的符号。若,d0，,则先将,d,更新为,d+2x+3，,再将(,x,y),更新为(,x+1,y)；,否则先将,d,更新为,d+2(x-y)+5，,再将(,x,y),更新为(,x+1,y-1)。,5.,当,x y,时，重复步骤3和4。否则结束。,2026/6/9 周二,信息科学与工程学院,44,程序段为：,void midb(int r,int x0,int y0),int x,y,d;,x=0;y=r;d=,;,while(),circlepoint(x,y,x0,y0);,if()d=,;,else d=,;,;,;,程序段为：,void midb(int r,int x0,int y0),int x,y,d;,x=0;y=r;d=,1.25-r,;,while(,x=y,),circlepoint(x,y,x0,y0);,if(,d=0,),d+=2*x+3,;,else ,d+=2*(x-y)+5;y-,;,x+;,2026/6/9 周二,信息科学与工程学院,45,用,d-0.25,代替,d,摆脱小数运算，得：,d,0,=1-R,误差判别项,d,0,对应于,d,0.25,，由于始终为整数，故,d,0.25,等价于,d,0,其余增量保持不变。,2026/6/9 周二,信息科学与工程学院,46,改进：,用,d-0.25,代替,d,算法步骤,：,1.输入圆的半径,R。,2.,计算初始值,d=1-R,、x=0、y=R。,3.,绘制点(,x,y),及其在八分圆中的另外七个对称点。,4.判断,d,的符号。若,d0,，,则先将,d,更新为,d+2x+3，,再将(,x,y),更新为(,x+1,y)；,否则先将,d,更新为,d+2(x-y)+5，,再将(,x,y),更新为(,x+1,y-1)。,5.,当,x,y,时，重复步骤3和4。否则结束。,