3-4多边形的转换与区域填充2

2020年1月12日计算机图形学13.4多边形的扫描转换与区域填充多边形扫描转换与区域填充可以统称区域填充，就是如何用颜色或图案来填充一个二维区域。填充主要做两件工作：一是确定需要填充的范围，二是确定填充的内容。一般区域填充指的是已知区域内一个种子，然后由种子向周围蔓延填充规定区域。方法：扫描线法：x-扫描线法-〉有序边表法，边填充算法种子填充算法（区域填充）2020年1月12日计算机图形学23.4.1扫描转换（扫描线）法多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。三种方法：扫描线算法边填充算法边界标志法2020年1月12日计算机图形学3多边形分类多边形分为凸多边形、凹多边形、含内环的多边形。2020年1月12日计算机图形学4多边形表示多边形的表示方法顶点表示点阵表示顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。2020年1月12日计算机图形学53.4.1.1扫描线算法-x扫描线法扫描线算法目标：利用相邻像素之间的连贯性，提高算法效率处理对象：非自交多边形（边与边之间除了顶点外无其它交点）2020年1月12日计算机图形学6步骤(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤：①计算扫描线与多边形各边的交点。②对求得的交点进行排序。③奇偶配对求出扫描线与多边形的相交区间。④对这些相交区间填充色。2020年1月12日计算机图形学7需要解决的几个问题扫描线与多边形顶点相交时交点的取舍问题多边形边界上像素点的取舍问题水平边的处理减少求交运算问题2020年1月12日计算机图形学8需要解决的几个问题（一）一、当扫描线与多边形顶点相交时，交点的取舍问题。解决：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。2020年1月12日计算机图形学9具体实现时只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。2020年1月12日计算机图形学10xy213456789111234567891011121012与多边形顶点相交的交点的处理2020年1月12日计算机图形学11011110222与扫描线相交的多边形顶点的交点数2020年1月12日计算机图形学12需要解决的几个问题（二）二、边界上象素的取舍问题，避免填充扩大化。解决方法：边界象素：规定落在右上边界的象素不予填充。具体实现时，只要对扫描线与多边形的相交区间实行：左闭右开（左边界像素填充，右边界像素不填充）下闭上开（下边界像素填充，上边界像素不填充）属于谁？2020年1月12日计算机图形学13需要解决的几个问题（三）三、水平边的处理（与扫描线重合）将水平边画出后删去，不参加求交，即求交后的操作（但是在计算交点个数时算作一个点）。2020年1月12日计算机图形学14需要解决的几个问题（四）减少求交算法：x-扫描线法在处理每条扫描线时需要与多边形的所有边求交，而实际上一条扫描线往往只与少数几条边相交，因此降低了效率，于是提出了改进算法—有序边表法，也称y连贯性算法。2020年1月12日计算机图形学153.4.1.2扫描转换法-有序边表法该法与x-扫描线法基本过程一样，只是在处理求交计算时作了改进。2020年1月12日计算机图形学16改进思路可以从以下方面考虑：1在处理一条扫描线时，仅对与它相交的边（有效边）进行求交运算，于是可以构造活性边表。2考虑扫描描线的连贯性，即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或者相似。3多边形边的连贯性，即当一条边与当前扫描线相交时，它可能也与下一条扫描线相交。2020年1月12日计算机图形学17所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。如何判断多边形的一条边与扫描线是否相交？有效边（ActiveEdge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（ActiveEdgeTable,AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效（活性）边表。2020年1月12日计算机图形学18数据结构与实现步骤只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。2020年1月12日计算机图形学19如何计算下一条扫描线与边的交点直线方程：ax+by+c=0当前交点坐标：(xi,yi)下一交点坐标：(xi+1,yi+1)xi+1=((-byi+1)-c)/a=((-byi+1)-c)/a=xi-b/a=xi-1/k活动边表中需要存放的信息：x：当前扫描线与边的交点dx＝-b/a：从当前扫描线到下一条扫描线之间的x增量△xymax：边所交的最高扫描线2020年1月12日计算机图形学20数据结构与实现步骤为了方便边的活化链表的更新，建立另一个表-新边表，存放在该扫描线第一次出现的边。存放的信息：x：扫描线与该边的初始交点dx：x的增量ymax：该边的最大y值2020年1月12日计算机图形学21数据结构与实现步骤即算法中采用较灵活的数据结构。它由边的新边表NET（newEdgeTable）和边的活性边表AET（ActiveEdgeTable）两部分组成。表结构NET和AET中的基本元素为多边形的边。边的结构由以下四个域组成：ymax：边的上端点的y坐标；x：在NET中表示边的最低点的x坐标，在AET中则表示边与扫描线的交点的坐标；Δx：边的斜率的倒数；（当前扫描线到下一条扫描线x的增量）next：指向下一条边的指针。2020年1月12日计算机图形学22ymaxx1/m(△x)nextymaxx1/m(△x)nextAET活性边表NET新边表X:边的下端点的x坐标X:边与扫描线的交点的坐标2020年1月12日计算机图形学232020年1月12日计算机图形学24活性边表的例子34-2P3P456.50.5^P3P2扫描线2AET指针620P4P5570.5^P3P2扫描线3AET指针(Ymax,x,Δx,next)36-2P3P4560.5^P3P2扫描线1AET指针2020年1月12日计算机图形学25活性边表的例子620P4P557.50.5^P3P2扫描线4AET指针620P4P578-1^P2P1扫描线5AET指针724P5P178-1^P2P1扫描线6AET指针2020年1月12日计算机图形学26新边表724^P5P178-1^P2P1620^P4P536-2P3P4560.5^P3P2^^^(Ymax,x,Δx,next)2020年1月12日计算机图形学27算法实现步骤这样，当建立了边的分类表NET后，扫描线算法可按下列步骤进行：（1）取扫描线纵坐标y的初始值为NET中非空元素的最小序号。（2）将边的活化链表AET设置为空。（3）按从下到上的顺序对纵坐标值为y的扫描线（当前扫描线）执行下列步骤，直到边的分类表ET和边的活化链表都变成空为止。2020年1月12日计算机图形学28算法实现步骤1）如边分类表NET中的第y类元素非空，则将属于该类的所有边从AET中取出并插入边的活化链表中，AET中的各边按照x值（当x值相等时，按Δx值）递增方向排序。2）若相对于当前扫描线，边的活化链表AEL非空，则将AET中的边两两依次配对，即1，2边为一对，3，4边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。3）将边的活化链表AET中满足y=ymax的边删去。4）将边的活化链表AET剩下的每一条边的x域累加Δx，即x:=x+Δx。5）将当前的扫描线的纵坐标值y累加1，即y:=y+1。2020年1月12日计算机图形学29扫描线算法特点：算法效率较高。缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。2020年1月12日计算机图形学30扫描线算法问题：如何处理多边形的水平边？如何修改扫描线算法，使它能处理边自交的多边形？2020年1月12日计算机图形学313.4.1.3边填充法算法简单，但对于复杂图型，每一象素可能被访问多次算法过程：对于每一条扫描线和每条多边形边的交点（x1,y1）,将该扫描线上交点右方的所有像素取补，对多边形的每条边做同样处理，多边形顺序随意，如下图：2020年1月12日计算机图形学322020年1月12日计算机图形学333.4.1.4栅栏填充算法为了减少重复计算，可采用栅栏算法，栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。2020年1月12日计算机图形学34算法过程对于每个扫描线与多边形的交点，将交点与栅栏之间的像素取补，若交点位于栅栏左边，则将交点之右，栅栏之作的所有像素取补，若交点位于栅栏右边，则将栅栏之左，交点之右的像素取补。2020年1月12日计算机图形学35栅栏算法图示2020年1月12日计算机图形学363.4.1.5边界标志算法1.对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。2.填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。取一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。Inside的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，inside不变。2020年1月12日计算机图形学37边界标志算法:算法过程voidedgemark_fill(polydef,color)多边形定义polydef；intcolor;{对多边形polydef每条边进行直线扫描转换；inside=FALSE;for(每条与多边形polydef相交的扫描线y)for(扫描线上每个象素x){if(象素x被打上边标志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background);}}2020年1月12日计算机图形学38边界标志算法用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。思考：如何处理边界的交点个数使其成为偶数？2020年1月12日计算机图形学393.4.2区域填充算法3.4.2.1种子填充法区域指已经表示成点阵形式的填充图形，它是象素的集合。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的2020年1月12日计算机图形学40区域填充表示方法：内点表示、边界表示内点表示枚举出区域内部的所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同的颜色边界表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色2020年1月12日计算机图形学41区域填充区域填充要求区域是连通的连通性：4连通、8连通4连通：8连通44p44(b)p的8-邻接点88888p888(a)p的4-邻接点邻接点的定义2020年1月12日计算机图形学42区域填充4连通与8连通区域的区别连通性：4连通可看作8连通区域，但对边界有要求2020年1月12