第四讲-改进的Bresanham算法圆的扫描转换课件

2024/8/4济南大学信息学院 1第第4讲 改改进的的Brensemham算法算法 圆的的扫描描转换2023/8/19济济南大学信息学院南大学信息学院 1第第4讲讲 改改进进的的Bre12024/8/4济南大学信息学院 25.1.2 中点中点Bresenham算法算法设两端点为P0(x0,y0)和P1(x1,y1)，则直线的方程该直线方程将平面分为三个区域：对于直线上的点，F(x,y)=0；对于直线上方的点，F(x,y)0；对于直线下方的点，F(x,y)0。2023/8/19济济南大学信息学院南大学信息学院 25.1.2 中点中点B22024/8/4济南大学信息学院 3F(x,y)=y-2x-1=0F(x,y)=y-2x-1=02023/8/19济济南大学信息学院南大学信息学院 3F(x,y)=y-232024/8/4济南大学信息学院 4Bresenham算算法法的的基基本本原原理理：在最大位移方向上走一步时，在另一个方向上是否走步取决于误差项的判断。假定0k1，x是最大位移方向2023/8/19济济南大学信息学院南大学信息学院 4Bresenham算算42024/8/4济南大学信息学院 5判别式判别式：则有：00k1k12023/8/19济济南大学信息学院南大学信息学院 5判判别别式：式：则则有：有：0k52024/8/4济南大学信息学院 6误差项的递推误差项的递推d0：取点(xi+1,yi+1)下一个中点(xi+2,yi+1.5)00k1k12023/8/19济济南大学信息学院南大学信息学院 6误误差差项项的的递递推推0k62024/8/4济南大学信息学院 7误差项的递推误差项的递推d0：取点(xi+1,yi)下一个中点(xi+2,yi+0.5)00k1k12023/8/19济济南大学信息学院南大学信息学院 7误误差差项项的的递递推推0k72024/8/4济南大学信息学院 8初始值初始值d的计算的计算00k1k12023/8/19济济南大学信息学院南大学信息学院 8初始初始值值d的的计计算算0k82024/8/4济南大学信息学院 9用2dx代替d1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=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。否则结束。2023/8/19济济南大学信息学院南大学信息学院 12算法步算法步骤骤：（0122024/8/4济南大学信息学院 13改进改进1：为计算方便，令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e0)thene=e-12023/8/19济济南大学信息学院南大学信息学院 13改改进进1：为计为计算方便算方便132024/8/4济南大学信息学院 14算法步骤算法步骤为：（0k1）1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-0.5、x=x0、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.c2023/8/19济济南大学信息学院南大学信息学院 14算法步算法步骤为骤为：（142024/8/4济南大学信息学院 15改改进进2：为方便硬件实现，作以下改进摆脱小数、除法运算。用2ex来替换ee初=-x，每走一步有e=e+2y。if(e0)thene=e-2x2023/8/19济济南大学信息学院南大学信息学院 15改改进进2：为为方便硬件方便硬件152024/8/4济南大学信息学院 16算法步骤算法步骤：（0k1）1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-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。否则结束。2023/8/19济济南大学信息学院南大学信息学院 16算法步算法步骤骤：（0162024/8/4济南大学信息学院 17xy ee+2dy00-5-110-1321-7-331-3142-9-552-5-1例例：画直线段P0(0,0)-P1(5,2)斜率0k1e的的初始值-x=-5 2y4 -2x-10相应坐标值和判别式如下：相应坐标值和判别式如下：2023/8/19济济南大学信息学院南大学信息学院 17x y 172024/8/4济南大学信息学院 18以上算法仅考虑，0k1时的情况，对于其它情况依此类推。以1k为例说明2023/8/19济济南大学信息学院南大学信息学院 18以上算法以上算法仅仅考考虑虑，0182024/8/4济南大学信息学院 191kdkkd2023/8/19济济南大学信息学院南大学信息学院 191kdkkd192024/8/4济南大学信息学院 20对于点Pi(xi,yi)令e=d-0.5K1K12023/8/19济济南大学信息学院南大学信息学院 20对对于点于点Pi(xi,202024/8/4济南大学信息学院 21再再用2ey来替换ee初=-y，每走一步有e=e+1/k=e+2x。if(e0)thene=e-2yK1K12023/8/19济济南大学信息学院南大学信息学院 21再用再用2e y来替来替换换212024/8/4济南大学信息学院 22算法步骤算法步骤：（k1）1.输入直线的两端点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。否则结束。2023/8/19济济南大学信息学院南大学信息学院 22算法步算法步骤骤：（k222024/8/4信息科学与工程学院信息科学与工程学院 23圆的扫描转换圆的扫描转换解决的问题：解决的问题：绘出圆心在原点，半径为整数R的圆x2+y2=R2圆心不在原点的圆，先平移至原点，扫描转换后再平移回原位置2023/8/19信息科学与工程学院信息科学与工程学院 23圆圆的的扫扫描描转换转换解决解决232024/8/4信息科学与工程学院信息科学与工程学院 24B(y,x)C(-y,x)D(-x,y)E(-x,-y)F(-y,-x)G(y,-x)H(x,-y)A A5.2.15.2.1八分法画八分法画圆2023/8/19信息科学与工程学院信息科学与工程学院 24B(y,x)C(242024/8/4信息科学与工程学院信息科学与工程学院 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.cCir8f0.c(0,0)0,0)为圆心，为圆心，(x,y)x,y)为圆上的点为圆上的点2023/8/19信息科学与工程学院信息科学与工程学院 25程序段程序段为为：程序：程序C252024/8/4信息科学与工程学院信息科学与工程学院 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.cCir8f.c(x0,y0)x0,y0)为圆心，为圆心，(x,y)x,y)为以为以(x0,y0)x0,y0)为圆心的圆上的点为圆心的圆上的点2023/8/19信息科学与工程学院信息科学与工程学院 26程序段程序段为为：程序：程序C262024/8/4信息科学与工程学院信息科学与工程学院 27解决问题解决问题：要得到整个圆的扫描像素集，要得到整个圆的扫描像素集，只要扫描转换只要扫描转换1/81/8圆弧即可圆弧即可2023/8/19信息科学与工程学院信息科学与工程学院 27解决解决问题问题：要得到：要得到272024/8/4信息科学与工程学院信息科学与工程学院 285.2.25.2.2简单方程方程产生生圆弧弧算法原理算法原理：利用其函数方程，直接离散计算1/81/8圆弧圆弧方法方法1 1笛卡尔方程直接计算笛卡尔方程直接计算2023/8/19信息科学与工程学院信息科学与工程学院 285.2.2 简单简单282024/8/4信息科学与工程学院信息科学与工程学院 29圆的方程绘制方法圆的方程绘制方法C+实现实现void圆的方程绘制()doublexc=300,yc=200,R=150;doublexr=300+150/1.414;doublex,y;for(x=xc;x=xr;x+)y=sqrt(R*R-(x-xc)*(x-xc)+yc;SetPixel(x,y,RGB(0,0,0);这一方法包括乘法和平方根运算，计算量较大，所画象素位置间的间距也是不一致的。2023/8/19信息科学与工程学院信息科学与工程学院 29圆圆的方程的方程绘绘制方法制方法292024/8/4信息科学与工程学院信息科学与工程学院 30圆的极坐标方程为：方法方法2 2圆的极坐标方程圆的极坐标方程将离散化0kn2023/8/19信息科学与工程学院信息科学与工程学院 30圆圆的极坐的极坐标标方程方程为为302024/8/4信息科学与工程学院信息科学与工程学院 31使用上述离散化方程，可以得到如下算法：begin for k0 to n xxcRcos(2.k/n)yycRsin(2.k/n)putpixel(x,y)next k endfor end 使用上述方法可沿圆周等距点绘制出圆来。算法中，n取的值越大，计算的点越多，但执行时间越长。此算法的缺点是含有三角函数，计算量大。2023/8/19信息科学与工程学院信息科学与工程学院 31使用上述离散化方使用上述离散化方312024/8/4信息科学与工程学院信息科学与工程学院 32为了避免三角函数运算，考虑下图,如果已经计算出圆上一点（xk,yk）,则增加一个角度 后，下一点（xk+1,yk+1）的坐标值可以用上一个点表示出。xk+1Rcos()R(coscos sinsin)R.coscosRsinsin xkcosyksin yk+1Rsin()R(sincoscossin)RcoscosRsinsin ykcosxksin5.2.3 DDA圆的生成算法2023/8/19信息科学与工程学院信息科学与工程学院 32为为了避免三角函数了避免三角函数322024/8/4信息科学与工程学院信息科学与工程学院 33当 足够小时有：cos1 sin这样，方程式 xk+1xkcosyksin yk+1ykcosxksin可以改写为：xk+1=xkyk yk+1=ykxk习惯上用 表示一个较小的量，用它替代,式子改写为：xk+1=xkyk yk+1=ykxk2023/8/19信息科学与工程学院信息科学与工程学院 33当当 足足够够小小时时有有332024/8/4信息科学与工程学院信息科学与工程学院 34利用前式，圆的参数方程生成算法可以描述如下：begin xxcR yyc 0 for 2 putpixel(x,y)xxy yyx endforend上述算法中，选取的值越小，计算的点越多，但执行时间越长。为了在光栅系统上得到连续的边界，可选取1R，这样绘制的象素位置大约为一个单位间隔。此算法也被称为DDA圆的生成算法。此圆的生成算法中仍包含浮点数和乘法运算，影响速度。2023/8/19信息科学与工程学院信息科学与工程学院 34利用前式，利用前式，圆圆的参的参342024/8/4信息科学与工程学院信息科学与工程学院 35圆的参数绘制方法圆的参数绘制方法C+实现实现voidApplicationProceesing()doublexc=300,yc=200,R=150;doublex,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。构造判别式构造判别式：2023/8/19信息科学与工程学院信息科学与工程学院 39当当d0时时，下一，下一392024/8/4信息科学与工程学院信息科学与工程学院 40误差项的递推误差项的递推d0：下一个中点下一个中点(xi+2,yi-0.5)增量为增量为2xi+32023/8/19信息科学与工程学院信息科学与工程学院 40误误差差项项的的递递推增量推增量402024/8/4信息科学与工程学院信息科学与工程学院 41误差项的递推误差项的递推d0：下一个中点下一个中点(xi+2,yi-1.5)增量为增量为2(xi-yi)+52023/8/19信息科学与工程学院信息科学与工程学院 41误误差差项项的的递递推增量推增量412024/8/4信息科学与工程学院信息科学与工程学院 42判别式判别式d的初始值的初始值2023/8/19信息科学与工程学院信息科学与工程学院 42判判别别式式d的初始的初始值值422024/8/4信息科学与工程学院信息科学与工程学院 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.当xy时，重复步骤3和4。否则结束。2023/8/19信息科学与工程学院信息科学与工程学院 43算法步算法步骤骤：432024/8/4信息科学与工程学院信息科学与工程学院 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+;2023/8/19信息科学与工程学院信息科学与工程学院 44程序段程序段为为：程序段：程序段442024/8/4信息科学与工程学院信息科学与工程学院 45用用d-0.25代替代替d摆脱小数运算，得：摆脱小数运算，得：d0=1-R误差判别项误差判别项d0对应于d0.25，由于始终为整数，故d0.25等价于d0其余增量保持不变。2023/8/19信息科学与工程学院信息科学与工程学院 45用用d-0.25代代452024/8/4信息科学与工程学院信息科学与工程学院 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.当xy时，重复步骤3和4。否则结束。2023/8/19信息科学与工程学院信息科学与工程学院 46改改进进：用：用d-0.46