第四章多边形的扫描转换.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章多边形的扫描转换与区域填充,4.1,多边形扫描转换,4.2,区域填充,多边形分为凸多边形、凹多边形、含内环的多边形。,4.1,多边形的扫描转换,4.1,多边形的扫描转换,多边形的表示方法,顶点表示,点阵表示,顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。,点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。,4.1,多边形的扫描转换,多边形的扫描转换：,把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。,两种方法：,扫描线算法；边界标志法,。,扫描线算法,扫描线算法,目标：利用相邻像素之间的连贯性，提高算法效率,处理对象：非自交多边形（边与边之间除了顶点外无其它交点）,扫描线算法,交点的取整规则,要求：使生成的像素全部位于多边形之内,用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用,假定非水平边与扫描,线,y=e,相交，交点的横坐标为,x,规则如下,扫描线算法,规则,1,：,X,为小数，即交点落于扫描线上两个相邻像素之间,(,a),交点位于左边之上，向右取整,(,b),交点位于右边之上，向左取整,规则,2,：,边界上象素的取舍问题，避免填充扩大化。,解决方法：,边界象素：规定落在右上边界的象素不予填充。,具体实现时，只要对扫描线与多边形的相交区间左闭右开,扫描线算法,规则,3,：,扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。,解决方法：,检查两相邻边在扫描线的哪一侧。,只要检查顶点的两条边的另外两个端点的,Y,值，,两个,Y,值中大于交点,Y,值的个数是,0，1，2,，来决定取,0，1，2,个交点。,扫描线算法,扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比，扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算，达到了减少了计算量和提高速度的目的。,开发和利用相邻象素之间的连贯性是光栅图形算法研究的重要内容。扫描转换算法综合利用了区域的连贯性、扫描线连贯性和边的连贯性等三种形式的连贯性。,扫描线算法,设多边形,P,的顶点,P,i,=(x,i,y,i,),i=0,1,n，,又设,y,i0,y,i1,y,in,是各顶点,P,i,的坐标y,i,的递减数列，即,y,ik,y,ik+1,0kn-1,这样，当,y,ik,y,ik+1,0kn-1,时，屏幕上位于,y=y,ik,和,y=y,ik+1,两条扫描线之间的长方形区域,被多边形,P,的边分割成若干梯形（三角形可看作其中一底边长为零的梯形），它们具有下列性质：,区域的连贯性,y=y,ik,y=y,ik+1,区域的连贯性,1,）梯形的两底边分别在,y=y,ik,和,y=y,ik+1,两条扫描线上，腰在多边形,P,的边上或在显示屏幕的边界上。,2,）这些梯形可分为两类：一类位于多边形,P,的内部；另一类在多边形,P,的外部。,3,）两类梯形在长方形区域,y,ik,y,ik+1,内相间的排列，即相邻的两梯形必有一个在多边形,P,内，另一个在,P,外。,y=y,ik+1,y=y,ik,区域的连贯性,根据这些性质，实际上只需知道该长方形区域内任一梯形内一点关于多边形,P,的内外关系后，即可确定区域内所有梯形关于,P,的内外关系,。,设,e,为一整数，,y,i0,ey,in,。,若扫描线,y=e,与多边形,P,的,P,i-1,P,i,相交，则记其交点的横坐标为,x,ei,。,现设x,ei1,x,ei2,x,ei3,x,eil,是该扫描线与,P,的边界各交点横坐标的递增序列，称此序列为交点序列。由区域的连贯性可知，此交点序列具有以下性质：,扫描线的连贯性,扫描线的连贯性,1）设,L,是偶数。,2）在该扫描线上，只有区段,(,x,eik,x,eik+1,）,k=1,3,5,L,-1位于多边形,P,内，其余区段都在,P,外。,以上性质称为扫描线的连贯性，它是多边形区域连贯性在一条扫描线上的反映。,设,d,为一整数，并且,d=e-1,并且,y,i0,dy,in,。,设位于扫描线,y=d,上的交点序列为,x,dj1,x,dj2,x,dj3,x,djk,现在来讨论扫描线,d，e,交点序列之间的关系。若多边形,P,的边,P,r-1,P,r,与扫描线,y=e,y=d,都相交，则交点序列中对应元素,x,er,x,dr,满足下列关系：,x,er,=,x,dr,+1/m,r,(1),其中,m,r,为边,P,r-1,P,r,的斜率。,边的连贯性,y=e,y=d,边的连贯性,于是，可利用,d,的交点序列计算,e,的交点序列，即先运用递推关系式,(1),求得与扫描线,y=e,和,y=d,都相交的所有多边形上的交点,x,er,再求得与扫描线,y=d,不相交但与扫描线,y=e,相交的所有边,P,q,P,q+1,上的交点,x,eq,。,如果,P,的顶点的坐标是整数，那么,x,eq,=,x,q,或,x,eq,=x,q+1,然后把这两部分按递增的顺序排列，即可得,e,的交点序列。,y=e,y=d,边的连贯性,特别是当存在某一个整数,k,0,kn-1,使得,y,ik,e,dy,ik+1,成立时，则由区域的连贯性可知,d,的交点序列和,e,的交点序列之间有以下关系：,1,）两序列元素的个数相等，如上图所示。,2,）点,(,x,eir,e,),与(x,djr,d)位于多边形,P,的同一边上，于是,x,eir,=,x,djr,+1/k,j,r,(2),这样，运用递推关系式,(2),可直接由,d,的交点序列和,e,的获得,e,的交点序列。,以上性质称为边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。,当扫描线与多边形,P,的交点是,P,的顶点时，则称该交点为奇点。,以上所述多边形的三种形式的连贯性都基于这样的几何事实：每一条扫描线与多边形,P,的边界的交点个数都是偶数。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点，都可能出现奇数个交点。那么如果保证交点数为偶数呢？,奇点的处理,奇点的处理,若奇点做一个交点处理，则情况,A，,交点个数不是偶数。,若奇点做两个交点处理，则情况,B，,交点个数不是偶数。,奇点的处理,多边形,P,的顶点可分为两类：极值奇点和非极值奇点。如果,(,y,i-1,-y,i,)(y,i+1,-y,i,)0，,则称顶点,P,i,为极值点；否则称,P,i,为非极值点。,规定：奇点是非极值点时，该点按两个交点计算，否则按一个交点计算。,数据结构与实现步骤,算法基本思想：首先取,d=y,in,。,容易求得扫描线,y=d,上的交点序列为,x,dj1,x,dj2,x,djn,，,这一序列由位于扫描线,y=d,上的多边形,P,的顶点组成。,由,y,in,的交点序列,开始，根据多边形的边的连贯性，按从上到下的顺序求得各条扫描线的交点序列；根据扫描线的连贯性，可确定各条扫描线上位于多边形,P,内的区段，并表示成点阵形式。,数据结构与实现步骤,所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。,如何判断多边形的一条边与扫描线是否相交？,与当前扫描线相交的边称为活性边（,active edge)，,把它们按与扫描线交点,x,坐标递增的顺序存入一个链表中，边的活化链表（,AEL,Active edge table)。,它记录了多边形边沿扫描线的交点序列。,只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。,数据结构与实现步骤,如何计算下一条扫描线与边的交点。,直线方程：,ax+by+c=0,当前交点坐标：,(,x,i,y,i,),下一交点坐标：,(,x,i+1,y,i+1,),x,i+1,=,(-by,i+1,)-c)/a=,(-by,i,+1)-c)/a,=x,i,-b/a=x,i,+1/m,i,活动边表中需要存放的信息：,x：,当前扫描线与边的交点,dx,-b/a：,从当前扫描线到下一条扫描线之间的,x,增量,ymax,：,边所交的最高扫描线,数据结构与实现步骤,为了方便边的活化链表的更新，建立另一个表,-,边表，存放在该扫描线第一次出现的边。,存放的信息：,x：,扫描线与该边的初始交点,dx,：x,的增量,ymax,：,该边的最大,y,值,即算法中采用较灵活的数据结构。它由边的分类表,ET（Edge Table）,和边的活化链表,AEL,（Active Edge List）,两部分组成。,表结构,ET,和,AEL,中的基本元素为多边形的边。边的结构由以下四个域组成：,y,max,边的上端点的,y,坐标；,x,在,ET,中表示边的下端点的,x,坐标，在,AEL,中则表示边与扫描线的交点的坐标；,x,边的斜率的倒数；,next,指向下一条边的指针。,数据结构与实现步骤,数据结构与实现步骤,边的分类表,ET,是按边的下端点的,y,坐标对非水平边进行分类的指针数组。下端点的,y,坐标的值等于,i,的边归入第,i,类。有多少条扫描线，就设多少类。同一类中，各边按,x,值（,x,值相等时，按,x,的值）递增的顺序排列成行。,边表,7,2,4,P,5,P,1,7,8,-1,P,2,P,1,6,2,0,P,4,P,5,3,6,-2,P,3,P,4,5,6,0.5,P,3,P,2,(,Y,max,x,x,next),活动边表的例子,3,4,-2,P,3,P,4,5,6.5,0.5,P,3,P,2,扫描线,2,AET,指针,6,2,0,P,4,P,5,5,7,0.5,P,3,P,2,扫描线,3,AET,指针,(,Y,max,x,x,next),3,6,-2,P,3,P,4,5,6,0.5,P,3,P,2,扫描线,2,AET,指针,活动边表的例子,6,2,0,P,4,P,5,5,7.5,0.5,P,3,P,2,扫描线,4,AET,指针,6,2,0,P,4,P,5,7,8,-1,P,2,P,1,扫描线,5,AET,指针,7,2,4,P,5,P,1,7,8,-1,P,2,P,1,扫描线,6,AET,指针,算法实现步骤,这样，当建立了边的分类表,ET,后，扫描线算法可按下列步骤进行：,（,1,）取扫描线纵坐标,y,的初始值为,ET,中非空元素的最小序号。,（,2,）将边的活化链表,AEL,设置为空。,（,3,）按从下到上的顺序对纵坐标值为,y,的扫描线（当前扫描线）执行下列步骤，直到边的分类表,ET,和边的活化链表都变成空为止。,算法实现步骤,1,）如边分类表,ET,中的第,y,类元素非空，则将属于该类的所有边从,ET,中取出并插入边的活化链表中，,AEL,中的各边按照,x,值（当,x,值相等时，按,x,值）递增方向排序。,2,）若相对于当前扫描线，边的活化链表,AEL,非空，则将,AEL,中的边两两依次配对，即,1，2,边为一对，,3，4,边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。,3,）将边的活化链表,AEL,中满足,y=y,max,的边删去。,4,）将边的活化链表,AEL,剩下的每一条边的,x,域累加,x，,即,x:=x+,x。,5）,将当前的扫描线的纵坐标值,y,累加,1,，即,y:=y+1,。,扫描线算法,特点：算法效率较高。,缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。,扫描线算法,问题：,如何处理多边形的水平边？,如何修改扫描线算法，使它能处理边自交的多边形？,1.,对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。,2.,填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。,取一个布尔变量,inside,来指示当前点的状态，若点在多边形内，则,inside,为真。若点在多边形外，则,inside,为假。,Inside,的初始值为假，每当当前访问象素为被打上标志的点，就把,inside,取反。对未打标志的点，,inside,不变。,边界标志算法,边界标志算法,:,算法过程,void,edgemark_fill(polydef,color),多边形定义,polydef,；,int,color;,对多边形,polydef,每条边进行直线扫描转换；,inside=FALSE;,for(,每条与多边形,polydef,相交的扫描线,y),for(,扫描线上每个象素,x),if(,象素,x,被打上边标志,),inside=!(inside);,if(inside！=FALSE),drawpixel,(x,y,color);,else,drawpixel,(x,y,background);,边界标志算法,用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，,但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。,边界标志算法,思考：如何处理边界的交点个数使其成为偶数？,第四章多边形的扫描转换与区域填充,4.1,多边形扫描转换,4.2,区域填充,4.2,区域填充算法,区域,指已经表示成点阵形式的填充图形，它是象素的集合。,区域填充,指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的,4.2,区域填充,表示方法：,内点表示、边界表示,内点表示,枚举出区域内部的所有像素,内部的所有像素着同一个颜色,边界像素着与内部像素不同的,颜色,边界表示,枚举出边界上所有的像素,边界上的所有像素着同一颜色,内部像素着与边界像素不同的颜色,4.2,区域填充,区域填充要求区域是连通的,连通性,4,连通、,8,连通,4,连通：,8,连通,4.2,区域填充,4,连通与,8,连通区域的区别,连通性：,4,连通可看作,8,连通区域，但对边界有要求,对边界的要求,适合于内点表示区域的填充算法,设,G,为一内点表示的区域，,(,x,y,),为区域内一点，,old,_,color,为,G,的原色。现取,(,x,y,),为种子点对区域,G,进行填充：即先置像素,(,x,y,),的颜色为,new,_,color,，,然后逐步将整个区域,G,都置为同样的颜色。,步骤如下：,种子象素入栈，当栈非空时，执行如下三步操作：,（,1,）栈顶象素出栈；,（,2,）将出栈象素置成多边形色；,（,3,）按上,、,下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,种子填充算法,种子填充算法,s1,2 3 4,9 8 7 6 5,11 12 13 14,10,(2 10 8 13),(3 7 13 10 8 13),(4 6 14 7 13 10 8 13),(5 6 14 7 13 10 8 13),例：多边形由,P,0,P,1,P,2,P,3,P,4,构成，,P,0(1,5),P,1(5,5),P,2(7,3),P,3(7,1),P,4(1,1),设种子点为（,3，3,），搜索的方向是上、下、左、右。,依此类推，最后像素被选中并填充的次序如图中箭头所示,种子填充算法,递归算法可实现如下,void FloodFill4(int,x,int,y,int,oldColor,int,newColor,),if(GetPixel(x,y,)=,oldColor,),PutPixel(x,y,newColor,);,FloodFill4(x,y+1,oldColor,newColor);,FloodFill4(x,y-1,oldColor,newColor);,FloodFill4(x-1,y,oldColor,newColor);,FloodFill4(x+1,y,oldColor,newColor);,/*end of FloodFill4()*/,种子填充算法,边界表示的,4,连通区域,void BoundaryFill4(int,x,int,y,int,boundaryColor,int,newColor,),int,color;,color=,GetPixel(x,y,);,if(color!=,boundaryColor,)&(color!=,newColor,),PutPixel(x,y,newColor,);,BoundaryFill4(x,y+1,oldColor,newColor);,BoundaryFill4(x,y-1,oldColor,newColor);,BoundaryFill4(x-1,y,oldColor,newColor);,BoundaryFill4(x+1,y,oldColor,newColor);,/*end of BoundaryFill4()*/,该算法也可以填充有孔区域。,缺点,：,(1),有些象素会入栈多次，降低算法效率；栈结构占空间。,(2),递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进,/,出栈，费时费内存。,改进算法，减少递归次数，提高效率。,解决方法是用扫描线填充算法,种子填充算法,扫描线算法,目标：减少递归层次,适用于边界表示的,4,连通区域,算法思想,：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的个区段都填充完毕。,扫描线填充算法,(1),初始化：堆栈置空。将种子点（,x，y）,入栈。,(2),出栈：若栈空则结束。否则取栈顶元素（,x，y），,以,y,作为当前扫描线。,(3),填充并确定种子点所在区段：从种子点（,x，y）,出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为,xl,和,xr,。,(4),并确定新的种子点：在区间,xl，,xr,中检查与当前扫描线,y,上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（,2,）步。,上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。,扫描线算法分析（举例分析）,该算法也可以填充有孔区域。,像素中的序号标指它所在区段位于堆栈中的位置,扫描线算法分析（举例分析）,扫描线算法分析（举例分析）,扫描线算法分析（举例分析）,多边形扫描转换与区域填充方法比较,联系：都是光栅图形面着色，用于真实感图形显示。可相互转换。,多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用,Bresenham,或,DDA,算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。,区域填充转化为多边形的扫描转换；若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。,多边形扫描转换与区域填充方法比较,不同点：,1.,基本思想不同；前者是,顶点表示转换成点阵表示，后者只改变区域内填充颜色，没有改变表示方法。,2.,对边界的要求不同,前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。,3.,基本的条件不同,前者：从边界顶点信息出发。,后者：区域内种子点。,