二维填充与多边形扫描转化

二维填充与多边形扫描转化第1页，共59页，2023年，2月20日，星期三关于光栅图形本质：点阵表示特点：面着色，画面明暗自然、色彩丰富与线框图相比：更加生动、直观、真实感强线框平面多边形着色的平面多边形第2页，共59页，2023年，2月20日，星期三线框多边形物体填充多边形物体第3页，共59页，2023年，2月20日，星期三5.1.1概念多边形分为凸多边形、凹多边形、含内环的多边形。5.1多边形的扫描转换第4页，共59页，2023年，2月20日，星期三多边形的表示方法顶点表示点阵表示顶点表示：用多边形顶点的序列来刻划多边形。优点:直观、几何意义强、占内存少；

缺点:难以判断哪些像素位于多边形内部,不能直接用于面着色。第5页，共59页，2023年，2月20日，星期三点阵表示：用位于多边形内的象素的集合来刻划多边形。缺点:失去了许多重要的几何信息；优点:便于运用帧缓冲存储器表示图形，易于面着色。第6页，共59页，2023年，2月20日，星期三多边形的扫描转换：

把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。两种方法：扫描线算法；边界标志法。第7页，共59页，2023年，2月20日，星期三多边形的顶点表示多边形的点阵表示第8页，共59页，2023年，2月20日，星期三5.1.2扫描线算法扫描线算法目标：利用相邻像素之间的连贯性，提高算法效率处理对象：非自交多边形（边与边之间除了顶点外无其它交点）第9页，共59页，2023年，2月20日，星期三交点的取整规则要求：使生成的像素全部位于多边形之内用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用假定非水平边与扫描线y=e相交，交点的横坐标为x,规则如下第10页，共59页，2023年，2月20日，星期三●规则1：

X为小数，即交点落于扫描线上两个相邻像素之间

(a)交点位于左边之上，向右取整

(b)交点位于右边之上，向左取整第11页，共59页，2023年，2月20日，星期三●规则2： 边界上象素的取舍问题，避免填充扩大化。●解决方法： 边界象素：规定落在右上边界的象素不予填充。 具体实现时，只要对扫描线与多边形的相交区间左闭右开第12页，共59页，2023年，2月20日，星期三●规则3： 扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。●解决方法： 检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。

第13页，共59页，2023年，2月20日，星期三

y=yiky=yik+1一、Ｘ－扫描线算法基本思想：按扫描线顺序，计算扫描线与多边形的相交区间（像素），再用相应的颜色（或图案）显示这些像素。第14页，共59页，2023年，2月20日，星期三算法步骤：(1)确定多边形所占有的最大扫描线数。即得到多边形顶点的最小和最大y值。（Ymin和Ymax)(2)从y=ymin到y=ymax:每次用一条扫描线填充。(3)填充步骤：求交：计算扫描线与多边形各边的交点。排序：所有交点按递增的顺序排序。交点配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边行的一个相交区间。区间填色：把这些相交区间内的像素置成不同于背景的填充色。

第15页，共59页，2023年，2月20日，星期三存在的问题：当扫描线与多边形顶点相交时，交点的取舍问题．解决的方法：共享顶点的两条边分别落在扫描线的两边，则交点只算一个．共享顶点的两条边在扫描线的一侧，则交点算０或者２个．第16页，共59页，2023年，2月20日，星期三

二、改进的有效边表算法（Y-连贯性算法）（１）有效边（ActiveEdge):与该扫描线相关的多边形的边。边的相关性：若pi(xi,yi),则有

扫描线Yi+1扫描线YiPiPi+1pi+1(xi+1,yi+1),其中xi+1=xi+1/k,yi+1=yi+1第17页，共59页，2023年，2月20日，星期三两边的相关性为每条边建立一个边记录，其结点内容为：X|yminymax1/knext第18页，共59页，2023年，2月20日，星期三(2)边表（ＥＴ：EdgeTable):是一个包含多边形全部边记录的表。

第19页，共59页，2023年，2月20日，星期三边表2７4^P5P1８７-1^P2P1２６0^P4P5６３-2P3P4６５0.5^P3P2^^^第20页，共59页，2023年，2月20日，星期三纵向链表的构造：长度为最大扫描线数。将相关边（该扫描线）的记录接点链入。一个结点（纵向链）有多个相关边时，按x|ymin由小到大的顺序；如果x|ymin相等，则按１／k由小到大的顺序。在ET表中：与X轴平行的边不计入顶点：如前法则相同。第21页，共59页，2023年，2月20日，星期三（３）有效边表（活动边表）：AET(ActiveEdgeTable)

将有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为AET。结点内容为：X

ymax1/knext其中x为当前扫描线与边的交点第22页，共59页，2023年，2月20日，星期三活动边表的例子43-2P3P46.550.5^P3P2扫描线2AET指针260P4P5750.5^P3P2扫描线3AET指针(x,ymax,Δx,next)63-2P3P4650.5^P3P2扫描线1AET指针第23页，共59页，2023年，2月20日，星期三活动边表的例子２６0P4P57.550.5^P3P2扫描线4AET指针260P4P587-1^P2P1扫描线5AET指针274P5P187-1^P2P1扫描线6AET指针第24页，共59页，2023年，2月20日，星期三(4)算法实现步骤这样，当建立了边的分类表ET后，扫描线算法可按下列步骤进行：（1）取扫描线纵坐标y的初始值为ET中非空元素的最小序号。（2）将边的活化链表AEL设置为空。（3）按从下到上的顺序对纵坐标值为y的扫描线（当前扫描线）执行下列步骤，直到边的分类表ET和边的活化链表都变成空为止。

第25页，共59页，2023年，2月20日，星期三A）如边分类表ET中的第y类元素非空，则将属于该类的所有边从ET中取出并插入边的活化链表中，AEL中的各边按照x值（当x值相等时，按Δx值）递增方向排序。B）若相对于当前扫描线，边的活化链表AEL非空，则将AEL中的边两两依次配对，即1，2边为一对，3，4边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。C）将边的活化链表AEL中满足y=ymax的边删去。D）将边的活化链表AEL剩下的每一条边的x域累加Δx，即x:=x+Δx。(Δx=1/k)E）将当前的扫描线的纵坐标值y累加1，即y=y+1。第26页，共59页，2023年，2月20日，星期三多边形边表实例第27页，共59页，2023年，2月20日，星期三多边形扫描转换实例第28页，共59页，2023年，2月20日，星期三多边形扫描转换实例第29页，共59页，2023年，2月20日，星期三多边形扫描转换实例第30页，共59页，2023年，2月20日，星期三多边形扫描转换实例第31页，共59页，2023年，2月20日，星期三多边形扫描转换实例第32页，共59页，2023年，2月20日，星期三多边形扫描转换实例第33页，共59页，2023年，2月20日，星期三多边形扫描转换实例第34页，共59页，2023年，2月20日，星期三多边形扫描转换实例第35页，共59页，2023年，2月20日，星期三多边形扫描转换实例第36页，共59页，2023年，2月20日，星期三多边形扫描转换实例第37页，共59页，2023年，2月20日，星期三多边形扫描转换实例第38页，共59页，2023年，2月20日，星期三扫描线算法特点：算法效率较高。缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。第39页，共59页，2023年，2月20日，星期三扫描线算法问题：如何处理多边形的水平边？如何修改扫描线算法，使它能处理边自交的多边形？第40页，共59页，2023年，2月20日，星期三1.对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。2.填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。取一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。Inside的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，inside不变。5.1.3边界标志算法第41页，共59页，2023年，2月20日，星期三边界标志算法:算法过程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); }}第42页，共59页，2023年，2月20日，星期三边界标志算法用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。第43页，共59页，2023年，2月20日，星期三边界标志算法思考：如何处理边界的交点个数使其成为偶数？第44页，共59页，2023年，2月20日，星期三5.2区域填充算法区域指已经表示成点阵形式的填充图形，它是象素的集合。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的第45页，共59页，2023年，2月20日，星期三表示方法：内点表示、边界表示内点表示枚举出区域内部的所有像素内部的所有像素着同一个颜色边界像素不能着上述颜色第46页，共59页，2023年，2月20日，星期三边界表示:枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色第47页，共59页，2023年，2月20日，星期三区域填充要求区域是连通的连通性

4连通、8连通4连通：8连通第48页，共59页，2023年，2月20日，星期三4连通与8连通区域的区别连通性：4连通可看作8连通区域，但对边界有要求对边界的要求第49页，共59页，2023年，2月20日，星期三适合于内点表示区域的填充算法设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成多边形色；（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。5.2.1种子填充算法第50页，共59页，2023年，2月20日，星期三例：多边形由P0P1P2P3P4构成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)设种子点为（3，2），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示

s123498765111213141510(210812)(371310812)(461471310812)……第51页，共59页，2023年，2月20日，星期三递归算法可实现如下:voidFloodFill4(intx,inty,intoldColor,intnewColor){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);}}/*endofFloodFill4() */第52页，共59页，2023年，2月20日，星期三边界表示的4连通区域voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){ intcolor; 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); }}/*endofBoundaryFill4() */第53页，共59页，2023年，2月20日，星期三该算法也可以填充有孔区域。

缺点：(1)有些象素会入栈多次，降低算法效率；栈结构占空间。(2)递归执行，算法简单