多边形的转换及区域填充.ppt
,第五章,多边形的扫描转换及区域填充,多边形的扫描转换及区域填充,第五章-2,内容,基本概念 扫描转换矩形 扫描转换多边形 区域填充 光栅图形的反走样,多边形的扫描转换及区域填充,第五章-3,基本概念,多边形有两种重要的表示方法顶点表示 用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内，故不能直接用于面着色 点阵表示 用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。,多边形的扫描转换及区域填充,第五章-4,基本概念,多边形的扫描转换把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应象素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。区域填充（演示）是指先将在点阵表示的多边形区域内的一点（称为种子点）赋予指定的颜色和灰度，然后将这种颜色和灰度扩展到整个区域内的过程。,多边形的扫描转换及区域填充,第五章-5,扫描转换矩形,问题：矩形是简单的多边形，那么为什么要单独处理矩形？应用非常多，特别是窗口系统比一般多边形可简化计算共享边界如何处理？左闭右开下闭上开,属于谁？,多边形的扫描转换及区域填充,第五章-6,扫描转换矩形,方法,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()*/,多边形的扫描转换及区域填充,第五章-7,扫描转换多边形,凸多边形任意两顶点间的连线均在多边形内凹多边形任意两顶点间的连线有不在多边形内的部分 含内环的多边形多边形内再套有多边形，多边形内的多边形也叫内环，内环之间不能相交,多边形的扫描转换及区域填充,第五章-8,扫描转换多边形,几种方法逐点判断算法逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。扫描线算法（要求重点掌握）利用相邻像素之间的连贯性，避免逐点判断和反复求交运算。边缘填充算法利用求余运算，来达到填充的目的。,多边形的扫描转换及区域填充,第五章-9,逐点判断算法,多边形的扫描转换及区域填充,第五章-10,逐点判断算法,逐个判断绘图窗口内的像素如何判断点在多边形的内外关系？射线法弧长法,多边形的扫描转换及区域填充,第五章-11,点关于多边形内外关系的判断,射线法（演示）如果从一点发出的射线与多边形边界的交点个数为奇数，则该点位于多边形之内，否则位于多边形之外。,p0,p1,p2,p3,p4,U0,U1,U2,U3,多边形的扫描转换及区域填充,第五章-12,点关于多边形内外关系的判断,弧长法（累计角度法)步骤从v点向多边形P各顶点发出射线，形成有向角计算有向角的和，得出结论,（演示）,多边形的扫描转换及区域填充,第五章-13,逐点判断算法-小结,逐点判断的算法虽然程序简单，但不可取。原因是速度太慢，效率低。主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。,多边形的扫描转换及区域填充,第五章-14,扫描线算法,处理对象非自交多边形（边与边之间除了顶点外无其它交点）,多边形的扫描转换及区域填充,第五章-15,扫描线算法,扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比，扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算，达到了减少计算量和提高速度的目的。开发和利用相邻象素之间的连贯性是光栅图形算法研究的重要内容。扫描转换算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。,多边形的扫描转换及区域填充,第五章-16,扫描线算法,基本思想对于一个给定的多边形，用一组水平或垂直的扫描线进行扫描，分别求出每条扫描线与多边形的交点，这些交点将扫描线分割为相间排列的落在多边形内和多边形外的线段，将落在多边形内的所有线段上的每个像素点赋以给定的多边形填充色。利用相邻象素之间的连贯性填充每一条扫描线位于多边形内部的区段。,多边形的扫描转换及区域填充,第五章-17,区域的连贯性,设多边形P的顶点Pi=(xi,yi),i=0,1,n，又设yi0,yi1,yin是各顶点Pi的坐标yi的递减数列，即yikyik+1,0kn-1。屏幕上位于y=yik和y=yik+1两条扫描线之间的长方形区域被多边形P的边分割成若干梯形（三角形可看作其中一底边长为零的梯形），它们具有下列性质：,多边形的扫描转换及区域填充,第五章-18,区域的连贯性,梯形的两底边分别在y=yik和y=yik+1（yikyik+1)两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。这些梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。两类梯形在长方形区域yik,yik+1内相间的排列，即相邻的两梯形必有一个在多边形P内，另一个在P外。,多边形的扫描转换及区域填充,第五章-19,区域的连贯性,结论：根据这些性质，实际上只需知道该长方形区域内任一梯形内一点关于多边形P的内外关系后，即可确定区域内所有梯形关于P的内外关系。,多边形的扫描转换及区域填充,第五章-20,扫描线的连贯性,设e为一整数，yi0eyin。若扫描线y=e与多边形P的Pi-1Pi相交，则记其交点的横坐标为xei。以上交点的横坐标递增排序得到的序列称为交点序列。交点序列具有如下性质：,多边形的扫描转换及区域填充,第五章-21,扫描线的连贯性,（1）交点个数为偶数。（2）交点之间的区段按交替的顺序依次出现在多边形内部和外部。以上性质称为扫描线的连贯性，它是多边形区域连贯性在一条扫描线上的反映。,多边形的扫描转换及区域填充,第五章-22,边的连贯性,由扫描线y=e和多边形的所有交点递推出扫描线y=d=e+1与多边形各边的交点。边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。,x,y,多边形的扫描转换及区域填充,第五章-23,奇点的处理,当扫描线与多边形P的交点是P的顶点时，则称该交点为奇点。以上所述多边形的连贯性都基于这样的几何事实：每一条扫描线与多边形P的边界的交点个数都是偶数。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点，都可能出现奇数个交点。那么如何保证交点数为偶数呢？,y=e,q0,q3,多边形的扫描转换及区域填充,第五章-24,奇点的处理,若奇点做一个交点处理，则情况A，交点个数不是偶数。若奇点做两个交点处理，则情况B，交点个数不是偶数。,多边形的扫描转换及区域填充,第五章-25,奇点的处理,多边形P的顶点可分为两类：极值奇点和非极值奇点。如果(yi-1-yi)(yi+1-yi)0，则称顶点Pi为极值点；否则称Pi为非极值点。规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。奇点的预处理：,多边形的扫描转换及区域填充,第五章-26,交点取整规则,要求：使生成的像素全部位于多边形之内由直线的扫描转换算法（如中点算法或DDA算法）求出的表示边的像素虽然和交点最靠近，却无法保证这些像素都落在多边形区域的内部,多边形的扫描转换及区域填充,第五章-27,交点取整规则,假设某非水平边与扫描线ye相交，交点的横坐标记为x，则有如下几种规则：（1）x为小数，即交点(x，e)落于扫描线ye 上两个相邻像素之间,多边形的扫描转换及区域填充,第五章-28,交点取整规则,（2）交点(x，e)正好落于像素点上 边界上象素的取舍问题，避免填充扩大化。按照前面所介绍的对多边形区域边界的处理方法，若(x，e)位于多边形左边上，见图(a)，则将它看作属于多边形；若(x，e)在多边形右边上，见图(b)则它不属于多边形。左闭右开的原则,多边形的扫描转换及区域填充,第五章-29,交点取整规则,（3）落在像素点上交点(x，e)为多边形的顶点扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。处理方法：将多边形的每条边看成是下端闭上端开,多边形的扫描转换及区域填充,第五章-30,扫描线算法-数据结构,为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。活性边（active edge)与当前扫描线相交的边；活性边表（AET-Active edge table)将活性边按与扫描线交点x坐标递增的顺序存入一个链表中，它记录了多边形边沿扫描线的交点序列。每条扫描线对应一个活性边表。只需对当前扫描线的活性边表作更新，即可得到下一条扫描线的活性边表。,多边形的扫描转换及区域填充,第五章-31,扫描线算法-数据结构,(扫描线6的活性边表),AET,(扫描线7的活性边表),AET,多边形的扫描转换及区域填充,第五章-32,扫描线算法-数据结构,如何计算下一条扫描线与边的交点？直线方程：ax+by+c=0当前交点坐标：(xi,yi)下一交点坐标：(xi+1,yi+1)xi+1=(-byi+1)-c)/a=(-b(yi+1)-c)/a=xi-b/axi+1=xi+x（x=-b/a为常数)活动边表中需要存放的信息x：当前扫描线与边的交点x-b/a：从当前扫描线到下一条扫描线之间的x增量ymax：边所交的最高扫描线，即边的上端点的y坐标；,多边形的扫描转换及区域填充,第五章-33,扫描线算法-数据结构,为了方便边的活性边表（AET）的更新，建立另一个表，即边表（ET-Edge Table）边表中需要存放的信息x：扫描线与该边的初始交点，即边的下端点的x坐标x：x的增量ymax：该边的最大y值，即边的上端点的y坐标；边表ET是按边的下端点的y坐标对非水平边进行分类的指针数组。下端点的y坐标的值等于i的边归入第i类。同一类中，各边按x值（x值相等时，按x的值）递增的顺序排列成行。,多边形的扫描转换及区域填充,第五章-34,扫描线算法-数据结构,P6P1,ET,多边形的扫描转换及区域填充,第五章-35,扫描线算法-数据结构,小结：算法中采用较灵活的数据结构。它由边表ET（Edge Table）和活性边表AET（Active Edge List）两部分组成。边表ET和活性边表AET中的基本元素为多边形的边。边的结构由以下四个域组成：ymax：边的上端点的y坐标；x：在ET中表示边的下端点的x坐标，在AET中则表示边与扫描线的交点的坐标；x：边的斜率的倒数；next：指向下一条边的指针。,多边形的扫描转换及区域填充,第五章-36,扫描线算法-算法实现步骤,1.建立ET；2.将扫描线纵坐标y的初值置为ET中非空元素 的最小序号（如前图所示，y=1）；3.置AET为空；4.执行下列步骤直至ET和AET都为空：如果ET中的第y类非空，则将其中的所有边取出并插入AET中；如果有新的边插入AET，则对AET中各边排序；对AET中的边两两配对，将每对边中x坐标按规则取整，获得有效的填充区段，再填充；将当前扫描线纵坐标y值递增1，即y=y+1；对AET中满足y=ymax边删去（因为每条边被看作下闭上开的）；对AET中剩下的每一条边的x递增x，即x=x+x。,多边形的扫描转换及区域填充,第五章-37,扫描线算法-算法实现步骤,void polyfill(polygon,color)int color;多边形 polygon;for(各条扫描线i)初始化边表头指针ET i；把y min=i 的边放进边表ET i;y=最低扫描线号；初始化活性边表AET为空；for(各条扫描线i)把边表ETi中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；遍历AET表，把配对交点区间(左闭右开)上的象素(x,y)，用putpixel(x,y,color)改写象素颜色值；遍历AET表，把ymax=i 的结点从AET表中删除，并把ymax i结点的x值递增 x；/*polyfill*/,多边形的扫描转换及区域填充,第五章-38,多边形扫描线算法分析,10,0,2,4,6,8,10,12,2,4,6,8,P3,P2,P1,P4,P5,P6,e3,e4,e2,e1,e5,e6,多边形的扫描转换及区域填充,第五章-40,扫描线算法与逐点判断法的比较,扫描线算法的数据结构和算法本身都比逐点判断法复杂得多。扫描线算法利用边的连贯性以加速交点的计算，利用ET以排除盲目求交。扫描线算法利用扫描线的连贯性以避免逐点判别，所以速度要比逐点判断算法快得多。,多边形的扫描转换及区域填充,第五章-41,区域填充,区域指已经表示成点阵形式的填充图形,它是相互连通的一组像素的集合。区域填充 是对区域重新着色的过程。是指先将区域的一点（称为种子点）赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。,多边形的扫描转换及区域填充,第五章-42,区域填充,区域的表示形式1.内点表示枚举出给定区域内所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同的颜色2.边界表示枚举出给定区域所有边界上像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色,区域的内点表示和边界表示,多边形的扫描转换及区域填充,第五章-43,区域填充,区域填充要求区域是连通的区域的连通形式4连通8连通,多边形的扫描转换及区域填充,第五章-44,区域填充,4连通与8连通区域的区别连通性：4连通可看作8连通区域，但对边界有要求对边界的要求,多边形的扫描转换及区域填充,第五章-45,种子填充算法-内点表示区域,设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤：种子象素入栈，当栈非空时，执行如下三步操作（1）栈顶象素出栈（2）将出栈象素置成多边形色（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,多边形的扫描转换及区域填充,第五章-46,种子填充算法-内点表示区域,例：多边形由P0P1P2P3P4构成：P0(1,5)、P1(5,5)、P2(7,3)、P3(7,1)、P4(1,1)设种子点为（3，3），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示,P0(1,5),P1(5,5),P2(7,3),P3(7,1),P4(1,1),多边形的扫描转换及区域填充,第五章-47,种子填充算法-内点表示区域,递归算法可实现如下,void FloodFill4(int x,int y,int oldColor,int newColor)int color;color=GetPixel（x，y）;if（color=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);,多边形的扫描转换及区域填充,第五章-48,种子填充算法-边界表示区域,步骤：种子象素入栈，当栈非空时，执行如下三步操作（1）栈顶象素出栈（2）将出栈象素置成多边形色（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,多边形的扫描转换及区域填充,第五章-49,种子填充算法-边界表示区域,void BoundaryFill4(int x,int y,int boundaryColor,int newColor)int color;color=GetPixel(x,y);if(color!=boundaryColor),递归算法可实现如下,多边形的扫描转换及区域填充,第五章-50,种子填充算法-边界表示区域,(3,2),(2,2),(3,3),(4,2),(3,1),(2,1),(4,1),(4,2),(2,2),(1,2),(2,3),(3,3),多边形的扫描转换及区域填充,第五章-51,种子填充算法,该算法也可以填充有孔区域。缺点有些像素会入栈多次，降低算法效率；栈结构占空间。递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。改进算法:减少递归次数，提高效率。解决方法：用扫描线填充算法,多边形的扫描转换及区域填充,第五章-52,扫描线填充算法,目标减少递归层次适用范围内点表示的4连通区域算法思想在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的个区段都填充完毕。,多边形的扫描转换及区域填充,第五章-53,扫描线填充算法,步骤：(1)初始化：堆栈置空。将种子点（x，y）入栈。(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。(4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。,多边形的扫描转换及区域填充,第五章-54,扫描线填充算法-举例分析1,多边形的扫描转换及区域填充,第五章-55,扫描线填充算法-举例分析2,多边形的扫描转换及区域填充,第五章-56,扫描线填充算法-举例分析2,多边形的扫描转换及区域填充,第五章-57,扫描线填充算法-举例分析2,多边形的扫描转换及区域填充,第五章-58,扫描线填充算法-举例分析2,多边形的扫描转换及区域填充,第五章-59,扫描线填充算法-举例分析2,多边形的扫描转换及区域填充,第五章-60,以图像填充区域,均匀着色方式位图不透明填充方式位图透明填充方式像素图填充方式,多边形的扫描转换及区域填充,第五章-61,多边形扫描转化与区域填充的比较,联系都是光栅图形面着色，用于真实感图形显示。可相互转换。多边形的扫描转换转化为区域填充当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。区域填充转化为多边形的扫描转换若已知给定多边形区域是多边形区域，并且通过一定的方法求出它的顶点坐标，则区域填充问题转化为多边形的扫描转换。差别基本思想不同对边界的要求不同基于的条件不同,多边形的扫描转换及区域填充,第五章-62,光栅图形的反走样,走样(aliasing)用离散量表示连续量引起的失真现象反走样(antialiasing)用于减少或消除这种效果的技术反走样技术提高分辨率区域采样加权区域取样,多边形的扫描转换及区域填充,第五章-63,光栅图形的反走样,FSAA Disabled-640 x480,多边形的扫描转换及区域填充,第五章-64,光栅图形的反走样,1.5 x 1.5 FSAA-640 x480,多边形的扫描转换及区域填充,第五章-65,光栅图形的反走样,2 x 2 FSAA-640 x480,
