1、2022-12-26济南大学信息学院 1第第4 4讲讲 改进的改进的BrensemhamBrensemham算法算法 圆的扫描转换圆的扫描转换2022-12-26济南大学信息学院 25.1.2 中点中点Bresenham算法算法设两端点为P0(x0,y0)和 P1(x1,y1)，则直线的方程该直线方程将平面分为三个区域：对于直线上的点，F(x,y)=0；对于直线上方的点，F(x,y)0；对于直线下方的点，F(x,y)0F(x,y)=0F(x,y)0F(x,y)=0F(x,y)0F(x,y)=y-2x-1=0F(x,y)=y-2x-1=02022-12-26济南大学信息学院 4Bresenham
2、算法的基本原理算法的基本原理：在最大位移方向上走一步时，在另一个方向上是否走步取决于误差项的判断。假定0k1，x是最大位移方向Pu(xi+1,yi+1)M(xi+1,yi+1/2)P(xi,yi)Pd(xi+1,yi)图5-5 Brensemham算法生成直线的原理Q2022-12-26济南大学信息学院 5判别式判别式：)1(5.0)5.0,1(),(bxkyyxFyxFdiiiiMM则有：)0()0(1dydyyPu(xi+1,yi+1)M(xi+1,yi+1/2)P(xi,yi)Pd(xi+1,yi)图5-5 Brensemham算法生成直线的原理Q00k1k1bkxyyxF),(2022
3、-12-26济南大学信息学院 6d0(xi,yi)(xi+1,yi+0.5)(xi+2,yi+1.5)误差项的递推误差项的递推d=0(xi,yi)(xi+1,yi+0.5)(xi+2,yi+0.5)1(5.0)5.0,1(),(bxkyyxFyxFdiiiiMM00k1k12022-12-26济南大学信息学院 8初始值初始值d的计算的计算kkbkxybxkyyxFd5.0 5.0 )1(5.0 )5.0,1(0000000 0),(bkxyyxF00k1k12022-12-26济南大学信息学院 9用2dx代替d1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d
4、=x-2y、x=x0、y=y0。3.绘制点(x,y)。判断d的符号。若d0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。2022-12-26济南大学信息学院 13改进改进1：为计算方便，令e=d-0.50)(e 0)(e 1111iiiiiyyyxx e初=-0.5，每走一步有e=e+k。if(e0)then e=e-12022-12-26济南大学信息学院 14算法步骤算法步骤为：（0k1）1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-0.5、x=x
5、0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。参见程序参见程序bmipv01.c2022-12-26济南大学信息学院 15改进改进2：为方便硬件实现，作以下改进摆脱小数、除法运算。用2ex来替换e e初=-x，每走一步有e=e+2y。if(e0)then e=e-2x2022-12-26济南大学信息学院 16算法步骤算法步骤：（0k1）1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=
6、-x、x=x0、y=y0。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。否则结束。2022-12-26济南大学信息学院 17x y e e+2dy00-5 -110-1 321-7 -331-3 142-9 -552-5 -1 例例：画直线段P0(0,0)-P1(5,2)斜率0k1 e的的初始值-x=-5 2y4 -2x-10相应坐标值和判别式如下：相应坐标值和判别式如下：0 1 2 3 4 5321Line:P0(0,0)-P1(5,2)
7、2022-12-26济南大学信息学院 18以上算法仅考虑，0k1时的情况，对于其它情况依此类推。以1k为例说明2022-12-26济南大学信息学院 191kdkkd2022-12-26济南大学信息学院 20对于点Pi(xi,yi)0.5)(d 0.5)(d 1111iiiiixxxyy令e=d-0.50)(e 0)(e 1111iiiiixxxyyK1K12022-12-26济南大学信息学院 21再再用2ey来替换e e初=-y，每走一步有e=e+1/k=e+2x。if(e0)then e=e-2yK1K12022-12-26济南大学信息学院 22算法步骤算法步骤：（k 1）1.输入直线的两端
8、点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-y、x=x0、y=y0。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。否则结束。2022-12-26信息科学与工程学院信息科学与工程学院 23圆的扫描转换圆的扫描转换解决的问题：解决的问题：绘出圆心在原点，半径为整数R的圆x2+y2=R2圆心不在原点的圆，先平移至原点，扫描转换后再平移回原位置2022-12-26信息科学与工程学院信息科学与工程学院 24(x,y)yy=-
9、xy=xB(y,x)C(-y,x)D(-x,y)E(-x,-y)F(-y,-x)G(y,-x)H(x,-y)A A5.2.1 5.2.1 八分法画圆八分法画圆2022-12-26信息科学与工程学院信息科学与工程学院 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);程序程序C
10、ir8f0.cCir8f0.c(0,0)0,0)为圆心，为圆心，(x,y)x,y)为圆上的点为圆上的点2022-12-26信息科学与工程学院信息科学与工程学院 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,1
11、4);putpixel(x+x0,-y+y0,14);程序程序Cir8f.cCir8f.c(x0,y0)x0,y0)为圆心，为圆心，(x,y)x,y)为以为以(x0,y0)x0,y0)为圆心的圆上的点为圆心的圆上的点2022-12-26信息科学与工程学院信息科学与工程学院 27解决问题解决问题：yy=x图5-10 1/8圆弧xR要得到整个圆的扫描像素集，要得到整个圆的扫描像素集，只要扫描转换只要扫描转换1/81/8圆弧即可圆弧即可2022-12-26信息科学与工程学院信息科学与工程学院 285.2.2 5.2.2 简单方程产生圆弧简单方程产生圆弧算法原理算法原理：利用其函数方程，直接离散计算
12、222Ryx7)-(5 )(2R0,x121211iiiixRroundyxx1/81/8圆弧圆弧方法方法1 1笛卡尔方程直接计算笛卡尔方程直接计算 2022-12-26信息科学与工程学院信息科学与工程学院 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);这一方法包括乘法和平方根运算，计算量较大，所画象素位置间
13、的间距也是不一致的。2022-12-26信息科学与工程学院信息科学与工程学院 30圆的极坐标方程为：sincosRyRx方法方法2 2圆的极坐标方程圆的极坐标方程 将 离散化)2sin()2cos(nkRyynkRxxckck0kn2022-12-26信息科学与工程学院信息科学与工程学院 31使用上述离散化方程，可以得到如下算法：begin for k0 to n xxcRcos(2.k/n)yycRsin(2.k/n)putpixel(x,y)next k endfor end 使用上述方法可沿圆周等距点绘制出圆来。算法中，n取的值越大，计算的点越多，但执行时间越长。此算法的缺点是含有三角函
14、数，计算量大。2022-12-26信息科学与工程学院信息科学与工程学院 32为了避免三角函数运算，考虑下图,如果已经计算出圆上一点（xk,yk）,则增加一个角度 后，下一点（xk+1,yk+1）的坐标值可以用上一个点表示出。xk+1Rcos()R(coscos sinsin)R.coscosRsinsin xkcosyksin yk+1Rsin()R(sincoscossin)RcoscosRsinsin ykcosxksin5.2.3 DDA圆的生成算法2022-12-26信息科学与工程学院信息科学与工程学院 33当 足够小时有：cos1 sin这样，方程式 xk+1xkcosyksin y
15、k+1ykcosxksin可以改写为：xk+1=xkyk yk+1=ykxk习惯上用 表示一个较小的量，用它替代,式子改写为：xk+1=xkyk yk+1=ykxk2022-12-26信息科学与工程学院信息科学与工程学院 34利用前式，圆的参数方程生成算法可以描述如下：begin xxcR yyc 0 for 2 putpixel(x,y)xxy yyx endforend上述算法中，选取的值越小，计算的点越多，但执行时间越长。为了在光栅系统上得到连续的边界，可选取1R，这样绘制的象素位置大约为一个单位间隔。此算法也被称为DDA圆的生成算法。此圆的生成算法中仍包含浮点数和乘法运算，影响速度。2
16、022-12-26信息科学与工程学院信息科学与工程学院 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时，下一点取Pd(xi+1,yi-1)。中点M的坐标为：M(xi+1,yi-0.5)当F(xM,yM)0时，取Pd(xi+1,yi-1)当F(xM,yM)=0时，约定取Pu。构造判别式构造判别式：222)5.0()1()5.
17、0,1(),(RyxyxFyxFdiiiiMM2022-12-26信息科学与工程学院信息科学与工程学院 40误差项的递推误差项的递推d0：下一个中点下一个中点(xi+2,yi-0.5)(a)d0：下一个中点下一个中点(xi+2,yi-1.5)5)(2 )22()32()5.0()1()5.1()2()5.1,2(222222iiiiiiiiiiyxdyxRyxRyxyxFd(b)d0的情况Pxixi+2xi+1yi-1yiyi-2增量为增量为2(xi-yi)+5222)5.0()1(Ryxdii2022-12-26信息科学与工程学院信息科学与工程学院 42判别式判别式d的初始值的初始值RRRR
18、Fd25.1 )5.0(1 )5.0,1(220 xy图5-11 中点Bresenham画圆的原理PPuPdM2022-12-26信息科学与工程学院信息科学与工程学院 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。否则结束。2022-12-26信息科学与工程学院信息科学与工程学院 44程序段为：程序段为
19、：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+;2022-12-26信息科学与工程学院信息科学与工程学院 45用用d-0.25代替代替d摆脱小数运算，得：摆脱小数运算，得：d0=1-R误差判别项误差判别项d0对应于d0.25，由于始终为整数，故d0.25等价于d0其余增量保持不变。2022-12-26信息科学与工程学院信息科学与工程学院 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。否则结束。
