资源描述
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
展开阅读全文