第3章 基本图形的生成(二).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,内蒙古大学计算机图形学,*,2026/5/27 周三,内蒙古大学计算机图形学,1,第三章基本图形的生成,光栅图形的扫描转换与区域填充,扫描转换矩形,扫描转换多边形,区域填充,扫描转换矩形,2026/5/27 周三,内蒙古大学计算机图形学,2,问题：,矩形是简单的多边形，那么为什么要单独处理矩形？,比一般多边形可简化计算。,应用非常多，窗口系统。,共享边界如何处理？,原则：左闭右开，下闭上开,属于谁？,扫描转换矩形,2026/5/27 周三,内蒙古大学计算机图形学,3,方法：,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()*/,扫描转换多边形,2026/5/27 周三,内蒙古大学计算机图形学,4,多边形分为凸多边形、凹多边形、含内环的多边形。,扫描转换多边形,2026/5/27 周三,内蒙古大学计算机图形学,5,多边形的表示方法,顶点表示,点阵表示,顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。,点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。,多边形的扫描转换,2026/5/27 周三,内蒙古大学计算机图形学,6,多边形的扫描转换：,把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。,几种方法：,逐点判断法；扫描线算法；边缘填充法；栅栏填充法；边界标志法,。,2026/5/27 周三,内蒙古大学计算机图形学,7,逐点判断法,void FillPolygonPbyP(Polygon*P,int polygonColor),int x,y;,for(y=ymin;y=ymax;y+),for(x=xmin;x 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,的交点序列。,以上性质称为边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。,2026/5/27 周三,内蒙古大学计算机图形学,26,奇点的处理,当扫描线与多边形,P,的交点是,P,的顶点时，则称该交点为奇点。,以上所述多边形的三种形式的连贯性都基于这样的几何事实：每一条扫描线与多边形,P,的边界的交点个数都是偶数。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点，都可能出现奇数个交点。那么如果保证交点数为偶数呢？,奇点的处理,2026/5/27 周三,内蒙古大学计算机图形学,27,若奇点做一个交点处理，则情况,A,，交点个数不是偶数。,若奇点做两个交点处理，则情况,B,，交点个数不是偶数。,奇点的处理,2026/5/27 周三,内蒙古大学计算机图形学,28,多边形,P,的顶点可分为两类：极值奇点和非极值奇点。如果,(,y,i-1,-y,i,)(y,i+1,-y,i,)0,，则称顶点,P,i,为极值点；否则称,P,i,为非极值点。,规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。,奇点的预处理：,数据结构与实现步骤,2026/5/27 周三,内蒙古大学计算机图形学,29,算法基本思想：,首先取,d=y,in,。,容易求得扫描线,y=d,上的交点序列为,x,dj1,x,dj2,x,djn,，,这一序列由位于扫描线,y=d,上的多边形,P,的顶点组成。,由,y,in,的交点序列,开始，根据多边形的边的连贯性，按从上到下的顺序求得各条扫描线的交点序列；根据扫描线的连贯性，可确定各条扫描线上位于多边形,P,内的区段，并表示成点阵形式。,2026/5/27 周三,内蒙古大学计算机图形学,30,数据结构与实现步骤,即算法中采用较灵活的数据结构。它由边的分类表,ET,（,Edge Table,）和边的活化链表,AEL,（,Active Edge List,）,两部分组成。,表结构,ET,和,AEL,中的基本元素为多边形的边。边的结构由以下四个域组成：,y,max,边的上端点的,y,坐标；,x,在,ET,中表示边的下端点的,x,坐标，在,AEL,中则表示边与扫描线的交点的坐标；,x,边的斜率的倒数；,next,指向下一条边的指针。,数据结构与实现步骤,2026/5/27 周三,内蒙古大学计算机图形学,31,边的分类表,ET,是按边的下端点的,y,坐标对非水平边进行分类的指针数组。下端点的,y,坐标的值等于,i,的边归入第,i,类。有多少条扫描线，就设多少类。同一类中，各边按,x,值（,x,值相等时，按,x,的值）递增的顺序排列成行。,数据结构与实现步骤,2026/5/27 周三,内蒙古大学计算机图形学,32,与当前扫描线相交的边称为活性边（,active edge),，把它们按与扫描线交点,x,坐标递增的顺序存入一个链表中，边的活化链表（,AEL,Active edge table),。它记录了多边形边沿扫描线的交点序列。,例子,2026/5/27 周三,内蒙古大学计算机图形学33,已知多边形,P=(P,0,P,1,P,2,P,3,P,4,P,5,P,6,P,0,),；其各边坐标分别为,（,2,，,5,）（,2,，,10,）（,9,，,6,）（,16,，,11,）（,16,，,4,）（,12,，,2,）（,7,，,2,）,建立其边表和边的活化链表,例子,2026/5/27 周三,内蒙古大学计算机图形学,34,边表,2026/5/27 周三,内蒙古大学计算机图形学,35,2026/5/27 周三,内蒙古大学计算机图形学,36,活动边表的例子,y=3,Y=8,算法实现步骤,2026/5/27 周三,内蒙古大学计算机图形学,37,这样，当建立了边的分类表,ET,后，扫描线算法可按下列步骤进行：,（,1,）取扫描线纵坐标,y,的初始值为,ET,中非空元素的最小序号。,（,2,）将边的活化链表,AEL,设置为空。,（,3,）按从下到上的顺序对纵坐标值为,y,的扫描线（当前扫描线）执行下列步骤，直到边的分类表,ET,和边的活化链表都变成空为止。,算法实现步骤,2026/5/27 周三,内蒙古大学计算机图形学,38,1,）如边分类表,ET,中的第,y,类元素非空，则将属于该类的所有边从,ET,中取出并插入边的活化链表中。递增方向排序。,2,）若相对于当前扫描线，边的活化链表,AEL,非空，则将,AEL,中的边两两依次配对，依此类推。并填色。,3,）将边的活化链表,AEL,中满足,y=y,max,的边删去。,4,）,x:=x+,x,。,5,）,y:=y+1,。,扫描线算法,2026/5/27 周三,内蒙古大学计算机图形学,39,特点：算法效率比逐点填充法高很多。,缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。,扫描线算法,2026/5/27 周三,内蒙古大学计算机图形学,40,问题：,如何处理多边形的水平边？,如何修改扫描线算法，使它能处理边自交的多边形？有孔的多边形如何处理？,如何处理圆、椭圆的扫描线算法？,边缘填充算法,2026/5/27 周三,内蒙古大学计算机图形学,41,求余运算,：假定,A,为一个正整数，则,M,的余定义为,AM,记为 。计算机中取,A,为,n,位能表示的最大整数。即，,A=0 xFFFFFFFF,由来,：光栅图形中，如果某区域已着上值为,M,的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为,的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。,算法基本思想,：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。,算法,1,（以扫描线为中心的边缘填充算法）,2026/5/27 周三,内蒙古大学计算机图形学,42,1,、将当前扫描线上的,所有象素着上 颜色；,2,、求余：,for(i=0;i=m;i+),在当前扫描线上，,从横坐标为,Xi,的交,点向右求余；,算法,2,（以边为中心的边缘填充算法）,2026/5/27 周三,内蒙古大学计算机图形学,43,1,、将绘图窗口的背景色置为 ；,2,、对多边形的每一条非水平边做：,从该边上的每个象素开始向右求余；,边缘填充算法,2026/5/27 周三,内蒙古大学计算机图形学,44,适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。,优点：算法简单,缺点：对于复杂图形，每一象素可能被访问多次，输入,/,输出的量比有序边表算法大得多。,栅栏填充算法,2026/5/27 周三,内蒙古大学计算机图形学,45,引入栅栏，以减少填充算法访问象素的次数。,栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。,基本思想：扫描线与多边形的边求交，将交点与栅栏之间的象素取补。,减少了象素重复访问数目，但不彻底。,2026/5/27 周三,内蒙古大学计算机图形学,46,边界标志算法,1.,对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。,2.,填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。,取一个布尔变量,inside,来指示当前点的状态，若点在多边形内，则,inside,为真。若点在多边形外，则,inside,为假。,Inside,的初始值为假，每当当前访问象素为被打上标志的点，就把,inside,取反。对未打标志的点，,inside,不变。,边界标志算法,:,算法过程,2026/5/27 周三,内蒙古大学计算机图形学,47,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);,边界标志算法,2026/5/27 周三,内蒙古大学计算机图形学,48,用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，,但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。,边界标志算法,2026/5/27 周三,内蒙古大学计算机图形学,49,思考：如何处理边界的交点个数使其成为偶数？,区域填充算法,2026/5/27 周三,内蒙古大学计算机图形学,50,区域,指已经表示成点阵形式的填充图形，它是象素的集合。,区域填充,指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的,区域填充,2026/5/27 周三,内蒙古大学计算机图形学,51,表示方法：,内点表示、边界表示,内点表示,枚举处区域内部的所有像素,内部的所有像素着同一个颜色,边界像素着与内部像素不同的,颜色,边界表示,枚举出边界上所有的像素,边界上的所有像素着同一颜色,内部像素着与边界像素不同的颜色,区域填充,2026/5/27 周三,内蒙古大学计算机图形学,52,区域填充要求区域是连通的,连通性,4,连通、,8,连通,4,连通：,8,连通,区域填充,2026/5/27 周三,内蒙古大学计算机图形学,53,4,连通与,8,连通区域的区别,连通性：4,连通可看作,8,连通区域，但对边界有要求,对边界的要求,2026/5/27 周三,内蒙古大学计算机图形学,54,种子填充算法,A,：适合于内点表示区域的填充算法,设,G,为一内点表示的区域，,(,x,y,),为区域内一点，,old,_,color,为,G,的原色。现取,(,x,y,),为种子点对区域,G,进行填充：即先置像素,(,x,y,),的颜色为,new,_,color,，然后逐步将整个区域,G,都置为同样的颜色。,步骤如下：,种子象素入栈，当栈非空时，执行如下三步操作：,（,1,）栈顶象素出栈；,（,2,）将出栈象素置成,new,_,color,；,（,3,）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素在边界内且未置成,new,_,color,，则把该象素入栈。,种子填充算法,2026/5/27 周三,内蒙古大学计算机图形学,55,例：多边形由,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,），搜索的方向是上、下、左、右。,依此类推，最后像素被选中并填充的次序如图中箭头所示,种子填充算法,2026/5/27 周三,内蒙古大学计算机图形学,56,递归算法可实现如下,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()*/,种子填充算法,2026/5/27 周三,内蒙古大学计算机图形学,57,边界表示的,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()*/,种子填充算法,2026/5/27 周三,内蒙古大学计算机图形学,58,该算法也可以填充有孔区域。,缺点,：,(1),有些象素会入栈多次，降低算法效率；,(2),递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进,/,出栈，费时费内存。,改进算法，减少递归次数，提高效率。,解决方法是用扫描线填充算法,扫描线填充算法,2026/5/27 周三,内蒙古大学计算机图形学,59,扫描线算法,目标：减少递归层次,适用于边界表示的,4,连通区域,算法思想,：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的个区段都填充完毕。,扫描线填充算法,2026/5/27 周三,内蒙古大学计算机图形学,60,(1),初始化：堆栈置空。将种子点（,x,，,y,）入栈。,(2),出栈：若栈空则结束。否则取栈顶元素（,x,，,y,），以,y,作为当前扫描线。,(3),填充并确定种子点所在区段：从种子点（,x,，,y,）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为,xl,和,xr,。,(4),并确定新的种子点：在区间,xl,，,xr,中检查与当前扫描线,y,上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（,2,）步。,上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。,扫描线算法分析（举例分析）,2026/5/27 周三,内蒙古大学计算机图形学,61,该算法也可以填充有孔区域。,像素中的序号标指它所在区段位于堆栈中的位置,扫描线算法分析（举例分析）,2026/5/27 周三,内蒙古大学计算机图形学,62,扫描线算法分析（举例分析）,2026/5/27 周三,内蒙古大学计算机图形学,63,扫描线算法分析（举例分析）,2026/5/27 周三,内蒙古大学计算机图形学,64,多边形扫描转换与区域填充方法比较,2026/5/27 周三,内蒙古大学计算机图形学,65,联系：都是光栅图形面着色，用于真实感图形显示。可相互转换。,多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用,Bresenham,或,DDA,算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。,区域填充转化为多边形的扫描转换；若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。,多边形扫描转换与区域填充方法比较,2026/5/27 周三,内蒙古大学计算机图形学,66,不同点：,1.,基本思想不同；,顶点表示转换成点陈表示后者只改变区域内填充颜色，没有改变表示方法。,2.,对边界的要求不同,前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。,3.,基本的条件不同,前者：从边界顶点信息出发。,后者：区域内种子点。,