《图形显示软件》PPT课件.ppt

《《图形显示软件》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图形显示软件》PPT课件.ppt（50页珍藏版）》请在三一办公上搜索。

1、计算机图形显示技术,2,第十一讲 图形软件,Bresenham画线算法圆的生成算法Bresenham画圆法中点画圆法区域填充算法扫描线填充算法边界填充算法,3,图形软件 Bresenham画线算法,About BresenhamE.Jack Bresenham Professor of Computer SciencePh.D.,Stanford University,1964 MSIE,Stanford University,1960 BSEE,University of New Mexico,1959Retired from 27 years service at IBM as a Sen

2、ior Technical Staff Member in 1987.Have taught 10 years at Winthrop.Holder of five patents.,4,图形软件 Bresenham画线算法,Bresenham算法该算法由Bresenham在1965年提出，是目前使用较为广泛的一种扫描转换算法，可用于直线、圆弧等图元的扫描转换。,5,图形软件 Bresenham画线算法,Bresenham画线算法基本思想过各行各列像素中心构造一组假想的栅格按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素,6,图形软件

3、Bresenham画线算法,Bresenham画线算法设直线从起点（x1,y1）到终点（x2,y2）设直线方程为：y=kx+b 其中b=y1-k*x1,7,图形软件 Bresenham画线算法,Bresenham画线算法若直线斜率k0,1且x2x1的情况（1a象限）根据即,DDA算法的讨论有：xi+1=xi+1(1)yi+1=yi+k(2)在1a象限里，当直线光栅化时，x每次都增加1个单元：xi+1=xi+1,8,图形软件 Bresenham画线算法,Bresenham画线算法由于k不一定是整数，因此由(2)式求出的y也不一定是整数。所以要用最靠近y的整数yi来代替y假设直线上第i个像素坐标为

4、(xi,yi)，那么，它的下一个点的像素点的可能位置为(xi+1,yi)或(xi+1,yi+1)。如图：,9,图形软件 Bresenham画线算法,Bresenham画线算法若直线斜率k0,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 d2=yi+1-y=yi+1-k(xi+1)-b 因此，这两个距离的差为：d1-d2=2k(xi+1)-2yi+2b-1(1),10,图形软件 Bresenham画线算法,Bresenham画线算法根据

5、（1）式，作如下讨论分析：当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画线算法若直线斜率k0,1且x2x1的情况（1a象限）因此，利用（d1-d2）的符号就可以决定下一个像素点的选择然而含有,变量xi、yi，不利于计算。为此，我们构造

6、一个新的判别式：pi=x*(d1-d2)=2 xiy-2yix+c（2）其中：x=(x2-x1)0，因此pi与(d1-d2)符号相同；y=y2-y1；c=2y+x(2b-1),12,图形软件 Bresenham画线算法,Bresenham画线算法若直线斜率k0,1且x2x1的情况（1a象限）,以i+1代 入 式(2)中的i，得：pi+1=x*(d1-d2)=2 xi+1y-2yi+1x+c（3）将式(3)减去式(2)，并由xi+1=xi+1可得：pi+1=pi+2y-2x(yi+1-yi)（4）假设直线上的初始端点恰好是其像素点的坐标，则将x1,y1和b代 入 式（2）中的xi,yi可 到 p

7、i的初始值p1=2x1y-2y1x+2y+x2(y1-kx1)-1=2y-x（5）,13,图形软件 Bresenham画线算法,Bresenham画线算法若直线斜率k0,1且x2x1的情况（1a象限）利用上面构造的误差判别变量，可得第1a象限内的直线Bresenham算法：,p1=2y-x xi+1=xi+1 yi+1=yi+1,pi+1=pi+2(y-x)当pi 0时 yi+1=yi,pi+1=pi+2y 当pi 0时,14,图形软件 Bresenham画线算法,Bresenham画线算法若直线斜率k0,1且x2x1的情况（1a象限）从算法可以看出，第i+1步的判别变量pi+1仅与第i步的判

8、别变量pi、直线的两个端点分量差x、y有关，只用整数相加和乘2运算，没有四舍五 入处理，而乘2可利用左移一位来实现因此该算法速度快且易于硬件实现,15,图形软件 Bresenham画线算法,Bresenham画线算法描述若直线斜率k0,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；if pi 0 则 yi+1=yi+1；否则 yi+1=yi；,16,图形软件 Bresenham画线算法,Bresenham画线算法描述

9、若直线斜率k0,1且x2x1的情况（1a象限）,4、画点（xi+1,yi+1）；5、求下一个误差pi+1；if pi 0 则 pi+1=pi+2y-2x；否则 pi+1=pi+2y；6、i=i+1；if ix+1则转3；否则end,17,图形软件 Bresenham画线算法,Bresenham画线算法现在讨论如何让该算法实现任何方向线段的绘制如图所示，线段的方向可分为8种，从原点出发射向8个区当直线斜率的绝对值大于1时，让y坐标每次增加1，再用 Bresenham的误差判别式确定 x坐标是否需要增加1。,18,图形软件 Bresenham画线算法,Bresenham画线算法 如果能充分利用xy

10、 平面各种八分和四分区域间的对称性就可减少运算量。,19,图形软件 Bresenham画线算法,Bresenham画线算法（FLASH演示）例:分析从(0,0)到(5,2)的直线段,原始直线,Bresenham画出直线,20,图形软件 圆的生成算法,给出圆心坐标(xc,yc)和半径r，逐点画出一个圆周的公式有下列两种：1.直角坐标法由上式导出：,直角坐标法当xxc从r到r作加1递增时，就可以求出对应的圆周点的y坐标 但由于有乘方和平方根运算，且都是浮点运算，算法效率不高。同时，这样求出的圆周上的点是不均匀的xxc接近R时，由于圆的斜率趋向于无穷大，使得圆周上有较大的间隙,21,图形软件 圆的生

11、成算法,22,图形软件 圆的生成算法,极坐标法假设圆周上一点(x,y)处的半径与x轴的夹角为,则圆的极坐标方程为：x=xc+r cos y=yc+r sin利用圆周上点的对称性，我们可求出圆上各点，此时自变量的取值范围是0,45度，以固定角度为步长来变化，可得到沿圆周等距离分布的一系列光点，但运算量大，也不被采用。,A,B,极坐标法对称性,（x,y）,（y,x）,（y,-x）,（x,-y）,（-x,y）,（-y,x）,（-y,-x）,（-x,-y）,45,23,图形软件 圆的生成算法,Bresenham画圆算法与Bresenham直线生成算法一样，其基本思想：利用判别变量来判断选择最近的像素，

12、判别变量仅用加减和移位就可计算出来 为讨论方便，仅考虑圆心在原点，半径为R的第一象限上的一段圆弧取（0，R）为起点，按顺时针方向绘制该1/4圆弧,24,Bresenham画圆算法如图所示，从当前点亮像素出发，按顺时针方向生成圆时，最佳逼近该圆的下一个像素只可能为H、D、V三像素之一。H、D、V中距圆周边界距离最小者，即为所求的像素点。,图形软件 圆的生成算法,25,Bresenham画圆算法H、D、V三点到圆心的距离平方与圆的半径平方差，即为H、D、V到圆弧距离的一种度量：H=(x+1)2+y2-R2；D=(x+1)2+(y-1)2-R2；V=x2+(y-1)2-R2；为了根据这些度量值可确定

13、最佳像素点，首先，将H、D、V与理想圆弧的关系进行分类,图形软件 圆的生成算法,26,Bresenham画圆算法如图存在以下五种情况：1）H、D、V全在圆内2）H在圆外，D、V在圆内3）D在圆上，H在圆外，V在圆内4）H、D在圆外，V在圆内5）H、D、V全在圆外,图形软件 圆的生成算法,27,Bresenham画圆算法 与Bresenham画线算法一样，按照上述不同类型，找出误差度量的递推公式，然后判别它的正、负性即可确定最佳逼近的像素点 当D 0,只可能为1或2的情况。为了 确定是H还是D，可用如下判别式：HD=|H|-|D|HD 0 则应选H，否则选D,图形软件 圆的生成算法,28,Bre

14、senham画圆算法 对于第2种情况：HD=H+D=(x+1)2+y2-R2+(x+1)2+(y-1)2-R2=2 D+2y-1因为H 0，D 0，否则2 D+2y-1 0。对于第1种情况：y是x的单调递减函数 H为下一点亮像素。另，此时H 0 和 D 0 H+D=2 D+2y-1 0 综上两种情况可得如下结论：在 D 0时，若2（D+y)-1 0，则取H，否则取D,图形软件 圆的生成算法,29,Bresenham画圆算法当D 0,只可能有4、5两种情况。且最佳像素点为D或V，可用如下判别式：DV=|D|-|V|当DV 0 则应选D，否则选V。对于第4种情况：DV=D+V（D 0，V 0）=(

15、x+1)2+(y-1)2-R2+(x)2+(y-1)2-R2=2(D-x)1 若2(D-x)1 0，则选V，否则选D。,图形软件 圆的生成算法,30,Bresenham画圆算法对于第5种情况：D，V都在圆外，显然V为所选像素。注意：D 0，V0 D+V=2(D-x)-1 0 综上两种情况可得如下结论：在 D 0时，若2（D-x)-1 0，则取D，否则取V 当D=0 此时D是最佳像素,图形软件 圆的生成算法,Bresenham画圆算法总结上述分析结果：当D 0，若 2(D-x)-1 0，取D，否则取V 当D 0，若 2(D+y)-1 0，取H，否则取D 当D=0，取D关键的问题就是计算 DD=(

16、x+1)2+(y-1)2-R2；采用增量法，获得D的计算公式,图形软件 圆的生成算法,32,Bresenham画圆算法分三种情况：下一像素为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=D k+2(x+1)+1,图形软件 圆的生成算法,33,Bresenham画圆算法下一像素为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=D k+2(x+1)-2(y-1)+2,图形软件 圆的生成算法,34

17、,Bresenham画圆算法下一像素为V时 V=(x,y)=(x,y-1)Dk+1=(x+1)2+(y-1)-1)2-R2=(x+1)2+(y-1)2-R2-2(y-1)+1=D k-2(y-1)+1,图形软件 圆的生成算法,35,Bresenham画圆算法有了上述 D的递推计算公式，还需计算出D的初值 圆弧的起点为（0，R）D的初值为：D=(0+1)2+(R-1)2-R2=2(1-R),图形软件 圆的生成算法,36,图形软件 圆的生成算法,中点画圆算法与Bresenham画圆算法一样，以单位间隔取样并在每个步长中确定离指定圆最近的像素位置对于给定半径r和圆心（xc，yc），可先给出计算中心在

18、原点（0,0）的像素位置的算法，然后通过平移使每个计算出的（x，y）移动到其适当的屏幕位置利用圆的对称性，只须讨论1/8圆,37,图形软件 圆的生成算法,中点画圆算法为了应用中点圆算法，定义一个圆函数：fcircle(x,y)=x2+y2-r2则任何点(x,y)的相对位置可由对圆函数符合的检测来决定:0(x,y)位于圆边界外,38,图形软件 圆的生成算法,中点画圆算法假设用该算法计算出第k个点P(xk,yk)，下一步需要决定像素位置是A(xk+1,yk)，B(xk+1,yk-1)其中xk+1=xk+1A，B的中点 M(xk+1,yk-0.5),M,A,B,P（Xk，Yk）,39,图形软件 圆的

19、生成算法,中点画圆算法在M处决策参数：pk=fcircle(xk+1,yk-0.5)=xk+12+(yk-0.5)2-r2则:当pk 0，这个中点M在圆内，扫描线yk上的像素(xk+1,yk)更接近于圆边界，则下一点应取右边的点A(xk+1,yk)否则，中点M位于圆外或在边界上，我们选择扫描线yk-1上的像素B(xk+1,yk-1)pk+1=(xk+1+1)2+(yk+1-0.5)2-r2,40,图形软件 圆的生成算法,中点画圆算法递归表达式：pk+1=pk+2xk+1+(y2k+1-y2k)-(yk+1-yk)+1 其中:yk+1是yk(pk 0)或是yk-1(pk 0)，这取决于pk的符号

20、圆在起始位置(x0,y0)=(0,r)处求值就可得到初始决策参数：p0=fcircle(1,r-0.5)=5/4 r,41,图形软件 圆的生成算法,中点画圆算法中点圆算法的算法表示：p0=5/4 r xk+1=xk+1 yk+1=yk，pk+1=pk+2xk+1+1 当pk0 yk+1=yk-1，pk+1=pk+2xk+1+1-2yk+1 当pk0,42,图形软件 圆的生成算法,中点画圆算法对于2xk+1和2yk+1本身又是一个增量表达式2xk+1增量始终为2而2yk+1增量为0(当pk0)或-2(当pk0)，在起始位置(x0,y0)=(0,r)，2xk+1和2yk+1的初始值分别为0和2r,

21、43,图形软件 圆的生成算法,中点画圆算法步骤 1.输入圆半径r和圆心(xc,yc),并得到圆心在原点的圆周上的第一点为:(x0,y0)=(0,r)2.计算决策参数的初始值：p0=5/4 r 3.在每个xk位置处，从k=0开始，完成下列检测：假如pk 0，中心在(0,0)的圆的下一个点为(xk+1,yk)，且 pk+1=pk+2xk+1+1否则，圆的下一个点为(xk+1,yk-1)，且 pk+1=pk+2xk+1+1-2yk+1其中：2xk+1=2xk+1，2yk+1=2yk-2,44,图形软件 圆的生成算法,中点画圆算法(FLASH演示）4.确定在其它7个8分圆中的对称点 5.将每个计算出的

22、像素位置(x,y)移动到中心在(xc,yc)的圆路径上，并画坐标值：x=xc+x y=yc+y 6.重复步骤3到5，直至xy,45,图形软件 区域填充算法,区域填充是指在一个有界区域内填充某些颜色或图案该区域的边界可以是圆、多边形甚至任意曲线，区域内所有像素的颜色相同（称为实心区域），或呈现一定的规律（图案）我们后面讨论的都是实心区域的填充算法,46,图形软件 区域填充算法,扫描线填充算法扫描线算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，完成转换工作 区间的端点可以通过计算扫描线与多边形边界线的交点获得,47,图形软件 区域填充算法,扫描线填充算法对于一

23、条扫描线，多边形的扫描转换过程可以分为四个步骤（1）求交：计算扫描线与多边形各边的交点；（2）排序：把所有交点按x值递增顺序排序；（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间，（4）着色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色,48,图形软件 区域填充算法,扫描线填充算法为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算我们把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活化边表(AET),49,图形软件 区域填充算法,扫描线填充算法活化边表(AET)结点内容 x：当前扫描线与边的交点坐标x：从当前扫描线到下一条扫描线间x的增量ymax：该边所交的最高扫描线号ymax,扫描线7的活化边表,50,图形软件 区域填充算法,扫描线填充算法,扫描线6的活化边表,