西安电子科技大学《计算机图像显示技术》第11讲 图形显示软件(2)1468603110

计算机图形显示技术主讲徐青西安电子科技大学雷达信号处理国防科技重点实验室2第十一讲图形软件Bresenham画线算法圆的生成算法•Bresenham画圆法•中点画圆法区域填充算法•扫描线填充算法•边界填充算法3图形软件——Bresenham画线算法AboutBresenham•E.JackBresenham——ProfessorofComputerScience•Ph.D.,StanfordUniversity,1964MSIE,StanfordUniversity,1960BSEE,UniversityofNewMexico,1959•Retiredfrom27yearsserviceatIBMasaSeniorTechnicalStaffMemberin1987.Havetaught10yearsatWinthrop.Holderoffivepatents.4图形软件——Bresenham画线算法Bresenham算法•该算法由Bresenham在1965年提出，是目前使用较为广泛的一种扫描转换算法，可用于直线、圆弧等图元的扫描转换。5图形软件——Bresenham画线算法Bresenham画线算法基本思想•过各行各列像素中心构造一组假象的栅格•按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素dddd6图形软件——Bresenham画线算法Bresenham画线算法•设直线从起点（x1,y1）到终点（x2,y2）•设直线方程为：y=kx+b其中b=y1-k*x1dxdyx1x2y1y2k7图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2x1的情况（1a象限）•根据•即DDA算法的讨论有：xi+1=xi+1(1)yi+1=yi+k(2)在1a象限里，当直线光栅化时，x每次都增加1个单元：xi+1=xi+18图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2x1的情况（1a象限）•由于k不一定是整数，因此由(2)式求出的y也不一定是整数。所以要用最靠近y的整数yi来代替y•假设直线上第i个像素坐标为(xi,yi)，那么，它的下一个点的像素点的可能位置为(xi+1,yi)或(xi+1,yi+1)。如图：9图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2x1的情况（1a象限）•如上图•该点•因此在x=xi+1处，直线上y的值y=k(xi+1)+b距离点(xi+1,yi)和点(xi+1,yi+1)的距离分别为d1和d2：d1=y-yi=k(xi+1)+b-yi(3)d2=(yi+1)-y=(yi+1)-k(xi+1)-b(4)，这两个距离的差为：d1-d2=2k(xi+1)-2yi+2b-1(5)10图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2x1的情况（1a象限）•根据（5）式，作如下讨论分析：当d1-d20时，说明直线上的理论点距离(xi+1,yi+1)较近，因此下一个直线像素点应取(xi+1,yi+1)•当d1-d20时，说明直线上的理论点距离(xi+1,yi)较近，因此下一个直线像素点应取(xi+1,yi)•当d1-d2=0时，说明直线上的理论点距离上、下两个像素点的距离相等，因此规定取(xi+1,yi+1)作为下一个直线像素点11图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2x1的情况（1a象限）•因此，利用（d1-d2）的符号就可以决定下一个像素点的选择•然而含有变量xi、yi，不利于计算。为此，我们构造一个新的判别式：pi=x*(d1-d2)=2xiy-2yix+c（6）其中：x=(x2-x1)0，因此pi与(d1-d2)符号相同；y=y2-y1；数c=2y+x(2b-1)12图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2x1的情况（1a象限）①以i+1代入式(6)中的i，得：pi+1=x*(d1-d2)=2xi+1y-2yi+1x+c（7）②将式(7)减去式(6)，并由xi+1=xi+1可得：pi+1=pi+2y-2x(yi+1-yi)（8）③假设直线上的初始端点恰好是其像素点的坐标，则将将x1,y1，和b代入式（6）中的xi,yi可到pi的初始值p1=2y-x（9）13图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2x1的情况（1a象限）•利用上面构造的误差判别变量，可得第1a象限内的直线Bresenham算法：p1=2y-xxi+1=xi+1yi+1=yi+1,pi+1=pi+2(y-x)当pi≥0时yi+1=yi,pi+1=pi+2y当pi0时14图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2x1的情况（1a象限）•从算法可以看出，第i+1步的判别变量pi+1仅与第i步的判别变量pi、直线的两个端点分量差x、y有关，•只用整数相加和乘2运算，没有四舍五入处理，而乘2可利用左移一位来实现•因此该算法速度快且易于硬件实现15图形软件——Bresenham画线算法Bresenham画线算法描述若直线斜率k∈[0,1]且x2x1的情况（1a象限）1、输入两端点(x1,y1),(x2,y2)，并以第一点作为起始点2、分别计算x=x2-x1;y=y2-y1；计算误差初值p1=2y-x；i=1；3、求直线的下一点位置：xi+1=xi+1；ifpi≥0则yi+1=yi+1；否则yi+1=yi；16图形软件——Bresenham画线算法Bresenham画线算法描述若直线斜率k∈[0,1]且x2x1的情况（1a象限）4、画点（xi+1,yi+1）；5、求下一个误差pi+1；ifpi≥0则pi+1=pi+2y-2x；否则pi+1=pi+2y；6、i=i+1；ifix+1则转3；否则end17图形软件——Bresenham画线算法Bresenham画线算法•现在讨论如何让该算法实现任何方向线段的绘制•如图所示，线段的方向可分为8种，从原点出发射向8个区•当直线斜率的绝对值大于1时，让y坐标每次增加1，再用Bresenham的误差判别式确定x坐标是否需要增加1。18图形软件——Bresenham画线算法Bresenham画线算法如果能充分利用x－y平面各种八分和四分区域间的对称性，就可减少运算量。象限取值1a、2ayi+1=yi或yi+13a、4ayi+1=yi或yi-11b、2bxi+1=xi或xi+13b、4bxi+1=xi或xi-119图形软件——Bresenham画线算法Bresenham画线算法•例:分析从(0,0)到(5,3)的直线段-10123456-1012345620图形软件——圆的生成算法•给出圆心坐标(xc,yc)和半径r，逐点画出一个圆周的公式有下列两种：⒈直角坐标法(xxc)2+(yyc)2=r2由上式导出：cc22()yyrxx21图形软件——圆的生成算法⒈直角坐标法•当•但•同时xxc从r到r作加1递增时，就可以求出对应的圆周点的y坐标由于有乘方和平方根运算，且都是浮点运算，算法效率不高。，这样求出的圆周上的点是不均匀的，xxc接近R时，由于圆的斜率趋向于无穷大，使得圆周上有较大的间隙22图形软件——圆的生成算法⒉极坐标法•假设•利用圆周上一点（x,y）处的半径与x轴的夹角为θ,则圆的极坐标方程为：x=xc+r·cosθ，y=yc+r·sinθ圆周上点的对称性，我们可求出圆上各点，此时自变量θ的取值范围是[0,45]度，以固定角度为步长来变化，可得到沿圆周等距离分布的一系列光点，但运算量大，也不被采用。23图形软件——圆的生成算法AB极坐标法对称性（x,y）（y,x）（y,-x）（x,-y）（-x,y）（-y,x）（-y,-x）（-x,-y）45°直角坐标法画圆24图形软件——圆的生成算法Bresenham画圆算法•与Bresenham直线生成算法一样，其基本思想：利用判别变量来判断选择最近的像素，判别变量仅用加减和移位就可计算出来•为讨论方便，仅考虑圆心在原点，半径为R的第一象限上的一段圆弧•取（0，R）为起点，按顺时针方向绘制该1/4圆弧25Bresenham画圆算法如图所示，从当前点亮像素出发，按顺时针方向生成圆时，最佳逼近该圆的下一个像素只可能为H、D、V三像素之一。H、D、V中距圆周边界距离最小者，即为所求的像素点。图形软件——圆的生成算法26Bresenham画圆算法H、D、V三点到圆心的距离平方与圆的半径平方差，即为H、D、V到圆弧距离的一种度量：H=(x+1)2+y2-R2；D=(x+1)2+(y-1)2-R2；（式1）V=x2+(y-1)2-R2；为了根据这些度量值可确定最佳像素点，首先，将H、D、V与理想圆弧的关系进行分类图形软件——圆的生成算法27Bresenham画圆算法如图存在以下五种情况：1）H、D、V全在圆内2）H在圆外，D、V在圆内3）D在圆上，H在圆外，V在圆内4）H、D在圆外，V在圆内5）H、D、V全在圆外图形软件——圆的生成算法28Bresenham画圆算法与Bresenham画线算法一样，按照上述不同类型，找出误差度量的递推公式，然后判别它的正、负性即可确定最佳逼近的像素点当D0,只可能为1或2种情况。为了确定是H还是D，可用如下判别式：δHD=|H|-|D|δHD≤0则应选H，否则选D图形软件——圆的生成算法29Bresenham画圆算法对于第2种情况：δHD=H+D=(x+1)2+y2-R2+(x+1)2+(y-1)2-R2=2D+2y-1对于第1种情况：∵y是x的单调递减函数∴H为下一点亮像素。（如图）另，此时H0和D0H+D=2D+2y-10综上两种情况可得如下结论：在D＜0时，若2（D+y)-1≤0，则取H，否则取D图形软件——圆的生成算法30Bresenham画圆算法当D＞0,只可能有4、5两种情况。且最佳像素点为D或V，可用如下判别式：δDV=|D|-|V|δDV≤0则应选D，否则选V。（如图）对于第4种情况：δDV=D+V（D＞0，V＜0）=(x+1)2+(y-1)2-R2+(x)2+(y-1)2-R2=2(D-x)-1图形软件——圆的生成算法31Bresenham画圆算法对于第5种情况：D，V都在圆外，显然V为所选像素。注意：∵D＞0，V＞0∴D+V=2(D-x)-1＞0综上两种情况可得如下结论：在D＞0时，若2（D-x)-1≤0，则取D，否则取V当D=0此时D是最佳像素图形软件——圆的生成算法32Bresenham画圆算法总结上述分析结果：（如图）当D＞0，若2(D-x)-1＞0，取D，否则取V当D＜0，若2(D+y)-1≤0，取H，否则取D当D=0，取D关键的问题就是计算D（见D的计算公式）采用增量法，获得D的计算公式图形软件——圆的生成算法33Bresenham画圆算法分三种情况：（如图）•下一像素为H时H=(x’,y’)=(x+1,y)Dk+1=((x+1)+1)2+(y-1)2-R2=(x+1)2+(y-1)2-R2+2(x+1)+1=Dk+2(x+1)+1图形软件——圆的生成算法34Bresenham画圆算法•下一像素为D时（如图）D=(x’,y’)=(x+1,y-1)Dk+1=((x+1)+1)2+((y-1)-1)2-R2=(x+1)2+(y-1)2-R2+2(x+1)-2(y-1)+1=Dk+2(x+1)-2(y-1)+2图形软件——圆的生成算法35Bresenham画圆算法•