第四章 区域填充_应用.ppt

第一章 计算机图形学概述,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,浙江大学工程及计算机图学所,工程及计算机图形学,#,SHU Graphics&Image Group,第一章 计算机图形学概述,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第四章,区域填充,4.1,图元的扫描转换,4.2,数学理论和准备,4.3,区域填充,主要内容,浙江大学工程及计算机图学所,问题：,1.,矩形是简单的多边形，那么为什么要单独处理矩形？,答：比一般多边形可简化计算。,应用非常多，窗口系统。,2.,共享边界如何处理？,答：原则：左闭右开，下闭上开,属于谁？,图,4-1-1,4.1,图元的扫描转换,浙江大学工程及计算机图学所,方法：,void,FillRectangle(Rectangle,*,rect,int,color),int,x,y,;,for(y,=,rect,-,ymin;y,ymax;y,+),for(x,=,rect,-,xmin;x,xmax;x,+),PutPixel(x,y,color,);,/*end of,FillRectangle,()*/,图,4-1-2,4.1.1,扫描转换矩形,浙江大学工程及计算机图学所,多边形分为凸多边形、凹多边形、含内环的多边形。,图,4-1-3,4.1.2,扫描转换多边形,浙江大学工程及计算机图学所,多边形的表示方法,顶点表示,用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。,点阵表示,用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。,图,4-1-4,图,4-1-5,4.1.2,扫描转换多边形,浙江大学工程及计算机图学所,多边形的扫描转换：,把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。,几种方法,：逐点判断法；扫描线算法；边缘填充法；栅栏填充法；边界标志法。,4.1.2,扫描转换多边形,浙江大学工程及计算机图学所,void,FillPolygonPbyP(Polygon,*,P,int,polygonColor,),int,x,y,;,for(y,=,ymin;y,=,ymax;y,+),for(x,=,xmin;x,e,dyik+1,成立时，则由区域的连贯性可知,d,的交点序列和,e,的交点序列之间有以下关系：,1,）两序列元素的个数相等，如上图所示。,2,）点,(,xeir,e,),与,(,xdjr,d,),位于多边形,P,的同一边上，于是,xeir,=,xdjr,+1/kjr (2),这样，运用递推关系式,(2),可直接由,d,的交点序列和,e,的获得,e,的交点序列。,以上性质称为边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。,4.2.3,边的连贯性,浙江大学工程及计算机图学所,当扫描线与多边形,P,的交点是,P,的顶点时，则称该交点为奇点。,以上所述多边形的三种形式的连贯性都基于这样的几何事实：每一条扫描线与多边形,P,的边界的交点个数都是偶数。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点，都可能出现奇数个交点。那么如果保证交点数为偶数呢？,4.2.4,奇点的处理,浙江大学工程及计算机图学所,若奇点做一个交点处理，则情况,A,，交点个数不是偶数。,若奇点做两个交点处理，则情况,B,，交点个数不是偶数。,图,4-2-14,4.2.4,奇点的处理,浙江大学工程及计算机图学所,多边形,P,的顶点可分为两类：极值奇点和非极值奇点。如果,(yi-1-yi)(yi+1-yi)0,，则称顶点,Pi,为极值点；否则称,Pi,为非极值点。,规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。,奇点的预处理：,图,4-2-15,4.2.4,奇点的处理,浙江大学工程及计算机图学所,算法基本思想：首先取,d=yin,。容易求得扫描线,y=d,上的交点序列为,xdj1,xdj2,xdjn,，这一序列由位于扫描线,y=d,上的多边形,P,的顶点组成。,由,yin,的交点序列开始，根据多边形的边的连贯性，按从上到下的顺序求得各条扫描线的交点序列；根据扫描线的连贯性，可确定各条扫描线上位于多边形,P,内的区段，并表示成点阵形式。,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。,如何判断多边形的一条边与扫描线是否相交？,与当前扫描线相交的边称为活性边（,active edge),，把它们按与扫描线交点,x,坐标递增的顺序存入一个链表中，边的活化链表（,AEL,Active edge table),。它记录了多边形边沿扫描线的交点序列。,只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,如何计算下一条扫描线与边的交点。,直线方程：,ax+by+c,=0,当前交点坐标：,(xi,yi,),下一交点坐标：,(xi+1,yi+1),xi+1=(-byi+1)-c)/a=,(-byi+1)-c)/a,=xi-b/a,活动边表中需要存放的信息：,x,：当前扫描线与边的交点,dx,-b/a,：从当前扫描线到下一条扫描线之间的,x,增量,ymax,：边所交的最高扫描线,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,增加哪一条边呢？,为了方便边的活化链表的更新，建立另一个表,-,边表，存放在该扫描线第一次出现的边,。,存放的信息：,x,：扫描线与该边的初始交点,dx,：,x,的增量,ymax,：该边的最大,y,值,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,即算法中采用较灵活的数据结构。它由边的分类表,ET,（,Edge Table,）和边的活化链表,AEL,（,Active Edge List,）两部分组成。,表结构,ET,和,AEL,中的基本元素为多边形的边。边的结构由以下四个域组成：,ymax,边的上端点的,y,坐标；,x,在,ET,中表示边的下端点的,x,坐标，在,AEL,中则表示边与扫描线的交点的坐标；,x,边的斜率的倒数；,next,指向下一条边的指针。,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,边的分类表,ET,是按边的下端点的,y,坐标对非水平边进行分类的指针数组。下端点的,y,坐标的值等于,i,的边归入第,i,类。有多少条扫描线，就设多少类。同一类中，各边按,x,值（,x,值相等时，按,x,的值）递增的顺序排列成行。,图,4-2-16,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,举例,已知多边形,P=(P0P1P2P3P4P5P6P0),；其各边坐标分别为,（,2,，,5,）（,2,，,10,）（,9,，,6,）（,16,，,11,）（,16,，,4,）（,12,，,2,）（,6,，,2,）,建立其边表和边的活化链表,图,4-2-17,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,边表,图,4-2-18,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,y=3,Y=8,活动边表,图,4-2-19,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,这样，当建立了边的分类表,ET,后，扫描线算法可按下列步骤进行：,（,1,）取扫描线纵坐标,y,的初始值为,ET,中非空元素的最小序号。,（,2,）将边的活化链表,AEL,设置为空。,（,3,）按从下到上的顺序对纵坐标值为,y,的扫描线（当前扫描线）执行下列步骤，直到边的分类表,ET,和边的活化链表都变成空为止,。,算法实现步骤,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,1,）,如边分类表,ET,中的第,y,类元素非空，则将属于该类的所有边从,ET,中取出并插入边的活化链表中，,AEL,中的各边按照,x,值（当,x,值相等时，按,x,值）递增方向排序。,2,）若相对于当前扫描线，边的活化链表,AEL,非空，则将,AEL,中的边两两依次配对，即,1,，,2,边为一对，,3,，,4,边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。,3,）将边的活化链表,AEL,中满足,y=,ymax,的边删去。,4,）将边的活化链表,AEL,剩下的每一条边的,x,域累加,x,，即,x:=,x+x,。,5,）将当前的扫描线的纵坐标值,y,累加,1,，即,y:=y+1,。,4.2.5,数据结构与实现步骤,浙江大学工程及计算机图学所,扫描线算法：,特点：算法效率比逐点填充法高很多。,缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。,问题：,如何处理多边形的水平边？,如何修改扫描线算法，使它能处理边自交的多边形？,扫描线算法总结,浙江大学工程及计算机图学所,4.2.6,边缘填充算法,求余运算,：假定,A,为一个正整数，则,M,的余定义为,A,M,记为 。计算机中取,A,为,n,位能表示的最大整数。即，,A=0 xFFFFFFFF,由来,：光栅图形中，如果某区域已着上值为,M,的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为,的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。,算法基本思想,：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。,浙江大学工程及计算机图学所,1,、将当前扫描线上的,所有象素着上 颜色；,2,、求余：,for(i,=0;i=m;i+),在当前扫描线上，,从横坐标为,Xi,的交,点向右求余；,算法,1,（以扫描线为中心的边缘填充算法）,4.2.6,边缘填充算法,图,4-2-20,浙江大学工程及计算机图学所,1,、将绘图窗口的背景色置 为 ；,2,、对多边形的每一条非水平边做：,从该边上的每个象素开始向右求余；,算法,2,（以边为中心的边缘填充算法）,4.2.6,边缘填充算法,图,4-2-21,浙江大学工程及计算机图学所,4.2.6,边缘填充算法,图,4-2-22,浙江大学工程及计算机图学所,适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。,优点：算法简单,缺点：对于复杂图形，每一象素可能被访问多次，输入,/,输出的量比有序边表算法大得多。,4.2.6,边缘填充算法,浙江大学工程及计算机图学所,引入栅栏，以减少填充算法访问象素的次数。,栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。,基本思想：扫描线与多边形的边求交，将交点与 栅栏之间的象素取补。,减少了象素重复访问数目，但不彻底。,图,4-2-23,4.2.7,栅栏填充算法,浙江大学工程及计算机图学所,1.,对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。,2.,填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。,取一个布尔变量,inside,来指示当前点的状态，若点在多边形内，则,inside,为真。若点在多边形外，则,inside,为假。,Inside,的初始值为假，每当当前访问象素为被打上标志的点，就把,inside,取反。对未打标志的点，,inside,不变。,4.2.8,边界标志算法,浙江大学工程及计算机图学所,算法程序：,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.2.8,边界标志算法,浙江大学工程及计算机图学所,用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，,但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。,4.2.8,边界标志算法,浙江大学工程及计算机图学所,思考：如何处理边界的交点个数使其成为偶数？,4.2.8,边界标志算法,浙江大学工程及计算机图学所,4.3,区域填充算法,区域,指已经表示成点阵形式的填充图形，它是象素的集合。,区域填充,指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的,浙江大学工程及计算机图学所,表示方法：,内点表示、边界表示,内点表示,枚举处区域内部的所有像素,内部的所有像素着同一个颜色,边界像素着与内部像素不同的,颜色,边界表示,枚举出边界上所有的像素,边界上的所有像素着同一颜色,内部像素着与边界像素不同的颜色,4.3,区域填充算法,图,4-3-1,浙江大学工程及计算机图学所,区域填充要求区域是连通的,连通性,4,连通、,8,连通,4,连通：,8,连通,4.3,区域填充算法,图,4-3-2,浙江大学工程及计算机图学所,4,连通与,8,连通区域的区别,连通性：,4,连通可看作,8,连通区域，但对边界有要求,对边界的要求,4.3,区域填充算法,图,4-3-3,浙江大学工程及计算机图学所,A,：适合于内点表示区域的填充算法,设,G,为一内点表示的区域，,(,x,y,),为区域内一点，,old,_,color,为,G,的原色。现取,(,x,y,),为种子点对区域,G,进行填充：即先置像素,(,x,y,),的颜色为,new,_,color,，然后逐步将整个区域,G,都置为同样的颜色。,步骤如下：,种子象素入栈，当栈非空时，执行如下三步操作：,（,1,）栈顶象素出栈；,（,2,）将出栈象素置成多边形色；,（,3,）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,4.3,种子填充算法,浙江大学工程及计算机图学所,例：多边形由,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,），搜索的方向是上、下、左、右。,依此类推，最后像素被选中并填充的次序如图中箭头所示,图,4-3-4,图,4-3-5,4.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.3,种子填充算法,浙江大学工程及计算机图学所,#include,stdafx.h,void,test(int,a),printf(%dn,a);,if(a=3&a 8),a+;,test(+a,);,int,main(int,argc,char*,argv,),printf(Hello,World!n);,test(0);,return 0;,递归调用,4.3,种子填充算法,浙江大学工程及计算机图学所,递归调用结果：,图,4-3-6,4.3,种子填充算法,浙江大学工程及计算机图学所,边界表示的,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()*/,4.3,种子填充算法,浙江大学工程及计算机图学所,该算法也可以填充有孔区域。,缺点,：,(1),有些象素会入栈多次，降低算法效率；栈结构占空间。,(2),递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进,/,出栈，费时费内存。,改进算法，减少递归次数，提高效率。,解决方法是用扫描线填充算法,4.3,种子填充算法,浙江大学工程及计算机图学所,扫描线算法,目标：减少递归层次,适用于边界表示的,4,连通区域,算法思想,：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的个区段都填充完毕。,4.3,种子填充算法,浙江大学工程及计算机图学所,(1),初始化：堆栈置空。将种子点（,x,，,y,）入栈。,(2),出栈：若栈空则结束。否则取栈顶元素（,x,，,y,），以,y,作为当前扫描线。,(3),填充并确定种子点所在区段：从种子点（,x,，,y,）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为,xl,和,xr,。,(4),并确定新的种子点：在区间,xl,，,xr,中检查与当前扫描线,y,上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（,2,）步。,上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。,4.3,种子填充算法,浙江大学工程及计算机图学所,该算法也可以填充有孔区域。,像素中的序号标指它所在区段位于堆栈中的位置,图,4-3-7,4.3,种子填充算法,浙江大学工程及计算机图学所,图,4-3-8,4.3,种子填充算法,浙江大学工程及计算机图学所,图,4-3-9,4.3,种子填充算法,浙江大学工程及计算机图学所,图,4-3-10,4.3,种子填充算法,浙江大学工程及计算机图学所,4.4,总结,联系：都是光栅图形面着色，用于真实感图形显示。可相互转换。,多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用,Bresenham,或,DDA,算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。,区域填充转化为多边形的扫描转换；若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。,多边形扫描转换与区域填充方法比较：,浙江大学工程及计算机图学所,不同点：,1.,基本思想不同：,前者是顶点表示转换成点阵表示，后者只改变区域内填充颜色，没有改变表示方法。,2.,对边界的要求不同,前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。,3.,基本的条件不同,前者：从边界顶点信息出发。,后者：区域内种子点。,4.4,总结,浙江大学工程及计算机图学所,