1、第二章第二章 图形基元的显示图形基元的显示 扫描转换扫描转换 将图形描述转换成用将图形描述转换成用象素矩阵表示的过程象素矩阵表示的过程 图形基元（输出图形元素）图形图形基元（输出图形元素）图形系统能产生的最基本图形系统能产生的最基本图形 线段、圆、多边形线段、圆、多边形 第一节第一节 直线扫描转换算法直线扫描转换算法 第二节第二节 圆的扫描转换算法圆的扫描转换算法 第三节第三节 区域填充区域填充 第一节第一节 直线扫描转换算法直线扫描转换算法 DDADDA直线扫描转换算法直线扫描转换算法 中点画线法中点画线法 BresenhamBresenham画线算法画线算法 设待画线段两端点的坐标值设待画
2、线段两端点的坐标值(x1,y1)和和(x2,y2)，假定，假定 x1fabs(dy)?fabs(dx):fabs(dy);dx/=e;dy/=e;x=x1;y=y1;for(int i=1;i0；直线下方的点，直线下方的点，F(x，y)0。将将M代入代入F(x，y)d=F(M)=F(xi+1，yi+0.5)=a(xi+1)+b(yi+0.5)+c当当 d 0，则取正右方的则取正右方的P1。当当d=0时，二者一样合适，取时，二者一样合适，取P1。对每一个象素计算判别式对每一个象素计算判别式d，根据，根据它的符号确定它的符号确定下一下一象素。象素。d0 时，取正右方象素时，取正右方象素P1，判断，
3、判断再再下一个下一个象素应取哪个，应计算象素应取哪个，应计算d1=F(xi+2，yi+0.5)=a(xi+2)+b(yi+0.5)+c =d+a故故d的增量为的增量为a。而若而若d0，则取右上方象素，则取右上方象素P2。要判。要判断再下一个象素，则要计算断再下一个象素，则要计算d2=F(xi+2，yi+1.5)=a(xi+2)+b(yi+1.5)+c=d+a+b 故在第二种情况故在第二种情况,d的增量为的增量为a+b 再看再看d的初始值。显然，第一个象的初始值。显然，第一个象素应取左端点素应取左端点(x0,y0)，相应的判别式，相应的判别式值为值为 d0=F(x0+1，y0+0.5)=a(x0
4、+1)+b(y0+0.5)+c=ax0+by0+c+a+0.5b=F(x0,y0)+a+0.5b 由于由于(x0，y0)在直线上，在直线上，故故F(x0，y0)=0。因此因此,d的初始值为的初始值为d0=a+0.5b 考虑用考虑用2d来代替来代替d的计算的计算void MidpointLine(int x0,int y0,int x1,int y1)int a,b,delta1,delta2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+b;delta1=2*a;delta2=2*(a+b);x=x0;y=y0;SetPixel(x,y);while(xx1 )if(d0)x+;y+
5、;d+=delta2;else x+;d+=delta1;SetPixel(x,y);/*while*/*MidpointLine*/xyd001(-4)10-3(+6)213(-4)31-1(+6)425(-4)521(x=x1=5)(0，0)、(5，2)a=y0-y1=-2，b=x1-x0=5 d d0 0 =2=2*a a+b b=1=1 斜率斜率m在在0到到1之间，并且之间，并且 设在第设在第i步已经确定步已经确定第第i个象素点是个象素点是 ，它是直线上点它是直线上点 的最接近位置的最接近位置()现在看第现在看第i+1步如步如何确定第何确定第i+1个象个象素点的位置。素点的位置。1 1
6、2 2x xx x)y y,x x(i ii i)y y,(x(xi ii ii ii ix xx x d1d21 12 2b by y2 21 1)x x2 2m m(d dd di ii i2 21 1b b1 1)x xm m(1 1)y y(y y1 1)y y(d dy yb b1 1)x xm m(y yy yd di ii i2 2i ii ii i1 12 21 1d dd d,下一个象素点取下一个象素点取 1 1)y y1 1,x x(i ii i 2 21 1d dd d，下一个象素点取，下一个象素点取 )y y1 1,x x(i ii i 2 21 1d dd d，取两象
7、素点中的任意一个，取两象素点中的任意一个 cyxxypiii11122cyxxyddxpiii22)(21)(2211iiiiyyxypp0ip,应取11iyiyx)x)-2(y2(yi ip p1 1i ip p0ip,应取应取 iyiy1yipip21确定确定P P1 1,bxxyyyxx111,11令令i i=1=1，可计算求出，可计算求出：xy21pvoid BresenhamLine(int x1,int y1,int x2,int y2)int x,y,dx,dy,p;x=x1;y=y1;dx=x2-x1;dy=y2-y1;p=2*dy-dx;for(;x=0)y+;p+=2*(d
8、y-dx);elsep+=2*dy;第二节第二节 圆的扫描转换算法圆的扫描转换算法 x2+y2=R2 2 2x x2 2R Ry yR Rs si in ny yR Rc co os sx x中点画圆法中点画圆法 讨论如何从点讨论如何从点(0(0，R R)至至 (，)的的1 18 8圆周圆周 2/R2/Rx x坐标为坐标为x xi i的的象素象素(x xi i,y yi i)下一个象素只下一个象素只能是能是(x xi i+1,+1,y yi i)的的P P1 1点或点或 (x xi i+1,+1,y yi i-1)-1)的的P P2 2点点M构造函数：构造函数：F(x,y)=x2+y2-R2圆
9、上的点，圆上的点，F(x,y)=0圆外的点，圆外的点，F(x,y)0圆内的点，圆内的点，F(x,y)0 P1和和P2的中点为的中点为 M=(xi+1,yi-0.5)F(M)0时，时，M在圆外，取在圆外，取P2F(M)=0时，时，P1或或P2随取一个即可，随取一个即可，取取P2 构造判别式构造判别式222)5.0()1()5.0,1()(RyxyxFMFdiiii 若若d d00，取，取P P1 1作为作为下一个象素下一个象素，而，而且且再下一个象素再下一个象素的判别式为的判别式为 32)5.0()2()5.0,2(222iiiiixdRyxyxFd 而若而若d d00，应取，应取P P2 2作
10、为作为下一个象素下一个象素，而且而且再下一个象素再下一个象素的判别式的判别式 522)5.1()2()5.1,2(222iiiiiiyxdRyxyxFd 第一个象素是第一个象素是(0,(0,R R)，判别式，判别式d d的初始值为的初始值为 d d0 0=F F(1,(1,R R-0.5)=1+(-0.5)=1+(R R-0.5)0.5)2 2-R R2 2=1.25-=1.25-R R。void MidpointCircle(int R)int x,y;double d;x=0;y=R;d=1.25-R;SetPixel(x,y);while(xy)if(d0)d+=2*x+3;x+;els
11、ed+=2*(x-y)+5;x+;y-;SetPixel(x,y);在上述算法中，使用了浮点数来表在上述算法中，使用了浮点数来表示判别式示判别式d。简化算法，在算法中全部使用整数，简化算法，在算法中全部使用整数，使用使用e=d-0.25代替代替d。显然，初始化运算显然，初始化运算d=1.25-R对应对应于于e=1-R。判别式判别式d0对应于对应于e-0.25。算法中可把算法中可把d直接换成直接换成e。又由于。又由于e的的初值为整数，且在运算过程中的增量也初值为整数，且在运算过程中的增量也是整数，故是整数，故e始终是整数，所以始终是整数，所以e-0.25等价于等价于e0。上述算法还可以进一步改进
12、。上述算法还可以进一步改进。以提高效率。注意到以提高效率。注意到d的增量是的增量是x、y的线性函数，每当的线性函数，每当x递增递增1，d递增递增x=2。每当。每当y递减递减1，d递增递增y=2。由于初始象素为。由于初始象素为(0,R)，所以，所以x的初值为的初值为3，y的初值为的初值为-2R+5。void MidpointCircle2(int R)int x,y,deltax,deltay,d;x=0;y=R;d=1-R;deltax=3;deltay=5-R-R;SetPixel(x,y);while(xy)if(d0和和dD0若若pi0，即，即dH 0，必有，必有pi0，dD0，必有，必
13、有pi0。得出结论：得出结论：pi做判别量，做判别量，pi0选选H点为点为下一个象素点，当下一个象素点，当pi0 0时，选时，选D点为下点为下一个象素点。一个象素点。从从 计算计算ip1222222)1(2Riyiyixip64)1221(21ixiyiyiyiyipip 当当p pi i00时，应选时，应选D D点，即选点，即选11iyiy10)(41iiiiyxpp1ip 当当p pi i00时，应选时，应选H H，即选，即选 iyiy1641iiixpp 画圆的起始点是画圆的起始点是(0(0，R R)，即即x x1 1=0=0，y y1 1=R R，代入前式，令，代入前式，令i i=1=
14、1，就得到：就得到：RP231void BresenhamCircle(int R)int x,y,p;x=0;y=R;p=3-2*R;for(;x=0)p+=4*(x-y)+10;y-;else p+=4*x+6;只需修改语句只需修改语句SetPixel(x,y)，画八个对称的点，就可以画出全部圆画八个对称的点，就可以画出全部圆周。若加一个平移，就可以画出圆心周。若加一个平移，就可以画出圆心在任意位置的圆周。在任意位置的圆周。区域填充区域填充 种子填充算法种子填充算法 区域是指光栅网格上的一组象素。区域是指光栅网格上的一组象素。区域填充是把某确定的象素值送入区域填充是把某确定的象素值送入 到
15、区域内部的所有象素中。到区域内部的所有象素中。区域填充方法分为两大类。区域填充方法分为两大类。区域由区域由多边形多边形围成，区域由多边形围成，区域由多边形的顶点序列来定义的顶点序列来定义;另一类方法是通另一类方法是通过过象素的值象素的值来定义区域的内部，相应来定义区域的内部，相应的技术称为是以象素为基础的的技术称为是以象素为基础的.内定义区域内定义区域，定义方法是指出区域内，定义方法是指出区域内部所具有的象素值部所具有的象素值,此时区域内部所有象此时区域内部所有象素有某个原值素有某个原值oldvalue;边界定义区域边界定义区域，定义方法是指出区域，定义方法是指出区域边界所具有的象素值。此时区
16、域边界上边界所具有的象素值。此时区域边界上所有象素具有某个边界所有象素具有某个边界boundaryvalue。区域的边界应该是。区域的边界应该是封闭的，并且应该指明区域的内部。封闭的，并且应该指明区域的内部。以象素为基础的区域填充主要是依据以象素为基础的区域填充主要是依据区域的连通性进行。区域的连通性进行。四连通四连通:从区域中的从区域中的一个象素出发，经连续一个象素出发，经连续地向上下左右四个相邻地向上下左右四个相邻象素的移动，就可以到象素的移动，就可以到达区域内的任意另一个达区域内的任意另一个象素象素.八连通八连通:如果除了要如果除了要经上下左右的移动，还经上下左右的移动，还要经左上、右上
17、、左下要经左上、右上、左下和右下的移动，才能由和右下的移动，才能由一个象素走到区域中另一个象素走到区域中另外任意一个象素外任意一个象素.利用区域的连通性进行区域填充，利用区域的连通性进行区域填充，除了需要区域应该明确定义外，还需要除了需要区域应该明确定义外，还需要事先给定一个事先给定一个区域内部象素区域内部象素，这个象素，这个象素称为称为种子种子。做区域填充时，要进行对光栅网格做区域填充时，要进行对光栅网格的的遍历遍历，找出由种子出发能达到而又不，找出由种子出发能达到而又不穿过边界的所有象素。穿过边界的所有象素。这种利用连通性的填充，其主要优这种利用连通性的填充，其主要优点是不受区域点是不受区
18、域不规则性不规则性的影响，主要缺的影响，主要缺点是需要事先知道一个内部象素。点是需要事先知道一个内部象素。void Floodfill(int x,int y,COLORREF oldvalue,COLORREF newvalue)/*(x，y)为种子为种子 oldvalue是原值是原值 newvalue是新值，应不等于原值。是新值，应不等于原值。*/if(GetPixel(x,y)=oldvalue)SetPixel(x,y,newvalue);/赋新值赋新值 Floodfill(x,y-1,oldvalue,newvalue);/四向扩散四向扩散 Floodfill(x,y+1,oldva
19、lue,newvalue);Floodfill(x-1,y,oldvalue,newvalue);Floodfill(x+1,y,oldvalue,newvalue);演示void Boundaryfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue)/*(x,y)为种子位置为种子位置boundaryvalue是边界象素值是边界象素值newvalue是区域内象素新值，未填充前区域内是区域内象素新值，未填充前区域内不应有值为不应有值为newvalue的象素。的象素。*/if(GetPixel(x,y)!=boundaryvalue&G
20、etPixel(x,y)!=newvalue)/未达边界且未访问过未达边界且未访问过 SetPixel(x,y,newvalue);/赋以新值赋以新值Boundaryfill(x,y-1,boundaryvalue,newvalue);/向四个方向扩散。向四个方向扩散。Boundaryfill(x,y+1,boundaryvalue,newvalue);Boundaryfill(x-1,y,boundaryvalue,newvalue);Boundaryfill(x+1,y,boundaryvalue,newvalue);扫描线种子填充算法扫描线种子填充算法 将区域内由边界点限定的同一行内相将
21、区域内由边界点限定的同一行内相连接的不具有新值连接的不具有新值newvalue的一组象的一组象素称为一个素称为一个象素段象素段，象素段用它最右边，象素段用它最右边的象素来标识。的象素来标识。算法的步骤如下：算法的步骤如下：1 1对种子所在象素段进行填充。对种子所在象素段进行填充。2 2从右至左检查种子所在行的上一从右至左检查种子所在行的上一横行，将查得的象素段依次编号存入堆横行，将查得的象素段依次编号存入堆栈。接着对种子所在行的下一横行同样栈。接着对种子所在行的下一横行同样处理。处理。3 3若堆栈为空则算法结束，否则从堆栈若堆栈为空则算法结束，否则从堆栈顶部取出一个象素段。就以这个象素为顶部取
22、出一个象素段。就以这个象素为新的种子，返回到新的种子，返回到1 1。下面我们用伪下面我们用伪C语言写出扫描线填充语言写出扫描线填充算法。算法。void ScanlineSeedfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue)int x0,xl,xr,y0,xid;int flag;Stack s;Point p;s.push(Point(x,y);/种子入栈种子入栈while(!s.isempty()p=s.pop();/栈顶象素出栈栈顶象素出栈x=p.x;y=p.y;SetPixel(x,y,newvalue);x0=x+1
23、;while(GetPixel(x0,y)!=boundaryvalue)/填充右方象素填充右方象素SetPixel(x0,y,newvalue);x0+;xr=x0-1;/最右象素最右象素x0=x-1;while(GetPixel(x0,y)!=boundaryvalue)/填充左方象素填充左方象素SetPixel(x0,y,newvalue);x0-;xl=x0+1;/最左象素最左象素/检查上一条扫描线和下一条扫描线检查上一条扫描线和下一条扫描线/若存在非边界且未填充的象素，若存在非边界且未填充的象素，/则选取代表各连续区间的种子象素则选取代表各连续区间的种子象素入栈。入栈。y0=y;fo
24、r(int i=1;i=-1;i-=2)x0=xr;y=y0+i;while(x0=xl)flag=0;while(GetPixel(x0,y)!=boundaryvalue)&(GetPixel(x0,y)!=newvalue)&(x0 xl)if(flag=0)flag=1;xid=x0;x0-;/将最右侧可填充象素压入栈中将最右侧可填充象素压入栈中if(flag=1)s.push(Point(xid,y);flag=0;/检查当前填充行是否被中断，若被中断，寻检查当前填充行是否被中断，若被中断，寻找左方第一个可填充象素找左方第一个可填充象素while(GetPixel(x0,y)=bou
25、ndaryvalue)/判断当前点是否为边界点判断当前点是否为边界点|(GetPixel(x0,y)=newvalue)/判断当前点是否为已填充点判断当前点是否为已填充点x0-;/若当前点为边界点或已填充点，若当前点为边界点或已填充点，根据前面的判断，当前点必然未超出左边界，则根据前面的判断，当前点必然未超出左边界，则当前点向左移动当前点向左移动/while(x0=xl)/for(int i=1;i=-1;i-=2)/while(!s.isempty()多边形的扫描转换算法多边形的扫描转换算法 多边形扫描转换产生多边形扫描转换产生面填充面填充的图形。多的图形。多边形扫描转换可以依据区域的一种边
26、形扫描转换可以依据区域的一种“奇偶奇偶”性质，即一条直线与任意封闭的曲线相交时，性质，即一条直线与任意封闭的曲线相交时，总是从第一个交点进入内部，再从第二个交总是从第一个交点进入内部，再从第二个交点退出，以下交替的进入退出，即奇数次进点退出，以下交替的进入退出，即奇数次进入，偶数次退出。当然可能有一些入，偶数次退出。当然可能有一些“相切相切”的点应特殊处理。的点应特殊处理。可以分如下三个步骤来做：可以分如下三个步骤来做：1 1找出扫描线与多边形边界线的所有交点；找出扫描线与多边形边界线的所有交点；2 2按按x x坐标增加顺序对交点排序；坐标增加顺序对交点排序；3 3在交点对之间进行填充。在交点
27、对之间进行填充。相切点的解决方法：当顶点表现为相切点的解决方法：当顶点表现为是是局部极大或局部极小局部极大或局部极小时，就看做是二时，就看做是二个，否则看做一个。局部极大，如果这个，否则看做一个。局部极大，如果这个顶点的前面和后面各有一些相邻顶点个顶点的前面和后面各有一些相邻顶点的的y y坐标，都小于该顶点的坐标，都小于该顶点的y y坐标。局部坐标。局部极小可类似地确定。极小可类似地确定。实际处理这个问题可以有一个简便实际处理这个问题可以有一个简便办法，那就是对应该看做是一个的顶点，办法，那就是对应该看做是一个的顶点，将其上面的边将其上面的边缩短缩短两条相邻扫描线对应两条相邻扫描线对应的一个单
28、位。的一个单位。计算扫描线与多边形边界线的交点：计算扫描线与多边形边界线的交点：注意到若扫描线注意到若扫描线yi与多边形边界线交点与多边形边界线交点x的坐标是的坐标是xi，则对下一条扫描线，则对下一条扫描线yi+l，它，它与那条边界线的交点的与那条边界线的交点的x坐标坐标xi+1，可如，可如下求出：下求出：mixix11 活跃边表活跃边表AET(ActiveEdgeTable)，用这个表存贮与当前扫描线，用这个表存贮与当前扫描线相交的各边。相交的各边。每次离开一条扫描线进入每次离开一条扫描线进入下一条之前，将表中有但与下一条扫描下一条之前，将表中有但与下一条扫描线不相交的边线不相交的边清除清除
29、出表，将与下一条扫出表，将与下一条扫描线相交而表中没有的边描线相交而表中没有的边加入加入表中。表中。边表边表ET(EdgeTable)，ET中中各登记项按各登记项按y坐标递增排序，每一登记坐标递增排序，每一登记项下的项下的“吊桶吊桶”按所记按所记x坐标递增排序，坐标递增排序，“吊桶吊桶”中各项的内容依次是：中各项的内容依次是：1.边的另边的另端点的较大的端点的较大的y坐标坐标ymax。2.与较小的与较小的y坐标对应的边的端点的坐标对应的边的端点的x坐坐 标标xmin。3.斜率的倒数，即斜率的倒数，即1/m。Void Polygonfill(EdgeTableET,COLORREF color)
30、y=边表边表ET中各登记项对应的中各登记项对应的y坐标中最坐标中最 小的值小的值;活跃边表活跃边表AET初始化为空表初始化为空表;while(ET表中仍有扫描线未被处理表中仍有扫描线未被处理)/处理处理ET表中的每一条扫描线表中的每一条扫描线 将将ET中登记项中登记项y对应的各对应的各“吊桶吊桶”合并到表合并到表AET中，将中，将AET中各吊桶按中各吊桶按x坐标递增排序；坐标递增排序；在扫描线在扫描线y上，按照上，按照AET表提供的表提供的x坐标对，用坐标对，用color实施填充；实施填充；将将AET表中有表中有y=ymax的各项清除出的各项清除出表；表；对对AET中留下的各项，分别将中留下的各项，分别将x换为换为x+1/m，这是求出，这是求出AET中各边与下一中各边与下一条扫描线交点的条扫描线交点的x坐标；坐标；y=y+1，去处理下一条扫描线。，去处理下一条扫描线。
