图元属性多边形填充.ppt

        多边形的填充•1：多边形的扫描转换•2：多边形的区域填充•3：光栅图形的反走样算法1•讨论二二维区域的填充区域的填充问题，即面着色的，即面着色的问题，也，也就是就是为指定的平面区域填上所需要的指定的平面区域填上所需要的颜色￿ ￿3.4 多多边形的形的扫描描转换与填充与填充窗口23.4.1 基本概念基本概念•多边形：（定义）限定为有封闭折线边界且无交叉边的平面图形•多边形分类：凸多边形、凹多边形•判别凸凹多边形的方法1、凸多边形所有向量叉积均同号若有些叉积取正而有些为负，则是凹多边形2、观察多边形顶点位置与每条延长线的关系，若有些顶点在某一延长线的一侧而其他一些顶点在另一侧，则是凹多边形•分割凹多边形：向量方法、旋转方法3分割凹多边形分割凹多边形xy向量方法旋转方法E1E2E3E4E5E6V2V1V3V44内内-外外测试•不自交的多边形、自相交的多边形•常用解决方法: 奇-偶规则、非零环绕数规则1) 奇-偶规则（Odd-even Rule）–从任意位置p作一条射线，若与该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点5图例例113316图例例P’222472) 非零环绕数规则（Nonzero Winding Number Rule）•首先使多边形的边变为矢量。

•将环绕数初始化为零•再从任意位置p作一条射线(不经过多边形顶点)当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形的边从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1•处理完多边形的所有相关边之后，若环绕数为非零，则p为内部点，否则，p是外部点8内内-外外测试奇- -偶规则非零环绕数规则9多边形的表示方法1、表示方法：定点表示和点、表示方法：定点表示和点阵表示表示1））顶点表示点表示是用多是用多边形的形的顶点的序列点的序列来描述多来描述多边形，形，该表示几何意表示几何意义强、占、占内存少，但它不能直内存少，但它不能直观地地说明哪些像素明哪些像素在多在多边形内2）点）点阵表示表示是用位于多是用位于多边形内的象素形内的象素的集合来刻划多的集合来刻划多边形，形，该方法方法虽然没有然没有多多边形的几何信息，是面着色所需要的形的几何信息，是面着色所需要的图像表示形式像表示形式 多多边形填充就是把多形填充就是把多边形的形的顶点表示点表示转换为点点阵表示，即从多表示，即从多边形的形的给定定边界出界出发，求出位于其内部的各个像素，并将，求出位于其内部的各个像素，并将帧缓冲冲器内的各个器内的各个对应元素元素设置相置相应的灰度或的灰度或颜色。

色实际上，也就是多上，也就是多边形内的区域的着色形内的区域的着色过程图3.15多多边形形顶点表示点表示图3.16多多边形点形点阵表示表示  103.4.2 扫描描转换的常用算法的常用算法Ø逐点判断算法Ø扫描线算法Ø边缘填充算法Ø边界标志算法113.4.2.1 逐点判断算法•思想：逐个象素判别，确定它们是否在多边形内部，从而给出位于多边形内的点（象素）的集合•难点：如何确定一个点是否在多边形内部？12需要注意的需要注意的问题 在计算交点时，如果交点恰恰就是多边形的顶点，必须小心处理，即要观察在此顶点相遇的两条边，如果这两条边的其余两个顶点在新构成线段的同一侧，应认为此线段与多边形相交二次；若多边形两条边的其余两个顶点在新线段的异侧，则认为此线段与多边形相交一次（奇点的处理）13算法的算法的实现•现设P=P0P1…PnP0为一给定的多边形Framebuffer(x,y)是与点(x,y)相对应的帧缓冲器中的元素则逐点判断的算法可以表示成为如下的程序：          for y:= screen-ymin to screen-ymax do         for x:= screen-xmin to screen-xmax do               if inside(p, x, y)                     then setpixel(framebuffer, x, y, polygon-color)                     else  setpixel(framebuffer, x, y, back-color);14 逐点判断的算法虽然程序简单，但是不可取。

原因是速度太慢，该算法割断了各个象素之间的联系，孤立的考察各个象素和多边形P的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别都要多次求交点，需要做大量的乘除运算，花费大量的时间153.4.2.2 多边形填充的扫描线算法1、、特点特点：充分利用了相：充分利用了相邻象素之象素之间的的连续性，避免性，避免对象素的逐象素的逐点判断和反复求交运算，减少了点判断和反复求交运算，减少了计算量，提高了算法速度算量，提高了算法速度.基本概念：基本概念：1））扫描描线的的连续性性：：扫描描线即即电子子枪由左向右由左向右扫过的一行，的一行，或用座或用座标的的观点来点来说即即y=i这样的一条的一条线2））边的的连续性性3））奇点奇点￿ ￿：：扫描描线与多与多边形形P的交点是的交点是P的的顶点，点，该交点称交点称为奇点16 设多边形设多边形P的顶点的顶点, 又设又设 是各顶是各顶点点Pi的纵坐标的纵坐标yi的递减数列的递减数列, ,当当 时时, ,屏幕上位屏幕上位于于和和 两条扫描线之间的长方形区域被多边形两条扫描线之间的长方形区域被多边形P的边分割成若干梯形。

的边分割成若干梯形171）扫描线的连续性设设e为一整数为一整数 ≥e ≥ 若扫描线若扫描线y=e与多边形与多边形P的边的边Pi-1Pi相交，则记其交相交，则记其交点的横点的横坐标为坐标为 令： 是该扫描线与是该扫描线与P的边界各的边界各交点横坐标的递增序列，记为交点横坐标的递增序列，记为序列序列1由区域的连贯性可知，此交点序列具有以下由区域的连贯性可知，此交点序列具有以下性质：性质：(1) l是偶数2) 在该扫描线上，只有区段在该扫描线上，只有区段 位于多边形位于多边形P内内. . P内内P内内P内内182）边的连续性若若d为为一一整整数数，，d=e–1，，且且yi0≥y≥yin；；设设位位于于扫扫描描线线y=d上上的的交交点点序序列列为为 ，，记为序列记为序列2若若多边形多边形P的边的边Pi-1Pi与扫描线与扫描线y=e, y=d都相交，即：都相交，即：则序列则序列1和和 序列序列2有以下关系：有以下关系：a：两个序列元素个数相等，即：两个序列元素个数相等，即l=hb：点：点 和和 位于多边形的同一个边上，于是有位于多边形的同一个边上，于是有 其中其中mr为边为边Pr-1Pr的斜率的斜率 递推式递推式1edy63y24193）奇点的处理a: 多多边形形P的的顶点可分点可分为两两类：：极极值点和非极点和非极值点点。

如果如果 ，称，称顶点点Pi为极极值点点(P1,P2,P3,P5, P6,P8)；否；否则称称Pi为非极非极值点点(P0,P4,P7)若若扫描描线与多与多边形相交于多形相交于多边形的形的顶点，点，则该交点交点(顶点点)称称为奇点 b: 处理理时遇到的遇到的问题如果把每一奇点如果把每一奇点简单地地计为一个交点，一个交点，则交点个数可能出交点个数可能出现奇奇数，如上数，如上图中的中的 扫描描线的情况；但若将每一奇点都的情况；但若将每一奇点都简单地地计为两个交点，同两个交点，同样会会导致反常的致反常的结果，如上果，如上图中中 扫描描线的情况 203）奇点的处理 c: 奇点的奇点的处理理 为了使交点个数保持了使交点个数保持为偶数，偶数，规定当奇点是定当奇点是P的极的极值点点时，，该点按两个交点点按两个交点计算；否算；否则按一个交点按一个交点计算 d: 实际算法算法预处理理: 若若Pi是非极是非极值点，点，则将将 两两边中位于中位于扫描描线y=yi上方的那条上方的那条边在在Pi点点处截去一截去一单位位长 21扫描描线算法算法—奇点的奇点的处理理•p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。

 如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)p2，p6为非极值点，则不用如上处理0246810122468101234024681012246810123p1p2p3p4p5p6p1p2p3p4p5p6222、扫描线算法的实现•对于于每一条每一条扫描描线，，多多边形的填充形的填充过程可分程可分为以以下下4步：步：1423把所有的交点按把所有的交点按x值递增的增的顺序序进行排列；行排列；计算算扫描描线与多与多边形各形各边的交点，的交点，设交点个数交点个数为n；； 将排序后的第将排序后的第1个与第个与第2个交点，第个交点，第3个与第个与第4个交点，个交点，……第第n-1个与第个与第n个交点配个交点配对，每，每对交点就代表交点就代表扫描描线与多与多边形的一个相交区形的一个相交区间；； 4把相交区把相交区间内的像素置成多内的像素置成多边形的形的颜色，相交区色，相交区间外外的像素置成背景色的像素置成背景色23扫描描线算法的算法的实现步步骤–对于一条扫描线填充过程可以分为四个步骤：•求交•排序•配对•填色242、扫描线算法的实现253、扫描线算法的数据结构a：数据：数据结构构边的的分分类表表ET和和边的的活活化化链表表AEL。

ET和和AEL中中的的多多边形形的的边由四个域由四个域组成：成： ymax 边的上端点的的上端点的y坐坐标；； x ET中中为边的的下下端端点点的的x坐坐标，，在在AEL中中是是边与与扫描描线交交点点的的x坐坐标 Δx 边的斜率的倒数的斜率的倒数 next 指向下一条指向下一条边的指的指针告告诉处理到哪条理到哪条扫描描线时，就，就可以可以结束束这条条边了了记录了初始了初始扫描描线与与这条条边的的初始初始x值记录当前当前扫描描线与某条与某条边的交的交点点x值dy/dx，，扫描描线加加1时，即，即y=y+1时x=x+1/m相交的相交的边对在哪，即要填充哪在哪，即要填充哪两条两条边之之间的区域263、扫描线算法的数据结构AEL 边的的活活化化链表表AEL由由与与当当前前扫描描线相相交交的的所所有有多多边形形的的边组成成它它记录了了多多边形形边沿沿扫描描线的的交交点点序序列列.当当前前扫描描线与与该边的的交交点点坐坐标为(xi,yi)，，则下下一一条条扫描描线与与该边的的交交点点(xi+1,yi+1)不不需需要要重重新新计算算，，只只要要加加一一个个增增量量即可。

即可 边的的活活化化链表表-5/357AELe0e54212AEL在在y=2扫描描线上的状上的状态-5/355AELe0e54214AEL在在y=3扫描描线上的状上的状态2ymaxx1/mAEL中的各中的各边按照按照x值(当当x的的值相等相等时，按，按Δx值)递增方向排序增方向排序273、扫描线算法的数据结构ET分分类表表ET按按边下下端端点点的的纵坐坐标y对边进行行分分类也也就就是是说，，如如果果某某边的的较低低端端点点为ymin，，则该边就就放放在在扫描描线ymin的的新新边表表中中同同一一类中中，，各各边按按x值递增增的的顺序序排排列列成成行行对于于图3.20的的多多边形：形：[P0P1P2P3P4P5 P6]=[(2,5) (2,10) (9,6) (16,11) (16,4) (12,2) (7,2)] 多多边形的形的边y筒筒注意：注意：其中其中P0和和P4点是非极点是非极值点，我点，我们在做在做y边的分的分类之前已之前已经做做过对边e1和和e4的的预处理理：分：分别在在P0和和P4处截掉一个截掉一个单位以保位以保证扫描描线y=yi只与只与Pi-1Pi、、PiPi+1两两边的一的一边相交，只求得一个交点。

同相交，只求得一个交点同时由于由于e6是水平是水平边，不参加分，不参加分类y1256284、扫描线算法的步骤：Ø步步骤1:(AEL初始化初始化)将将边的活化的活化链表表AEL设置置为空空Ø步步骤2:(y初始化初始化)取取扫描描线纵坐坐标y的初始的初始值为ET中非空元中非空元素的素的最小序号最小序号Ø步步骤3：按：按从下到上的从下到上的顺序序对纵坐坐标值为y的的扫描描线(当前当前扫描描线)执行行下列步下列步骤，直到，直到边的分的分类表表ET和和边的活化的活化链表表AEL都都变成空成空为止止295、扫描线算法的具体步骤：•①①如如边分分类表表ET中的第中的第y类元素非空，元素非空，则将将属于属于该类的所的所有有边从从ET中取出并插入中取出并插入边的活化的活化链表表AEL中中，，AEL中的中的各各边按照按照x值(当当x的的值相等相等时，按，按Δx值)递增方向排序增方向排序5/357AELe0e54212AEL在在y=2扫描描线上的状上的状态2v从从ET中中选择当前当前扫描描线的的边表，方便活表，方便活性性边表的建立和更新表的建立和更新305、扫描线算法的具体步骤：•②②若相若相对于当前于当前扫描描线，，边的活化的活化链表表AEL非空，非空，则将将AEL中的中的边两两依次配两两依次配对，即第，即第1，，2边为一一对，第，第3，，4边为一一对，依此，依此类推。

推￿￿￿￿￿￿￿￿￿￿￿￿每一每一对边与当前与当前扫描描线的交点所构成的区段位于多的交点所构成的区段位于多边形内，依次形内，依次对这些区段上的点些区段上的点(象素象素)按多按多边形属性着色形属性着色利用了利用了扫描描线的的连续性性-5/357AELe0e54212AEL在在y=2扫描描线上的状上的状态315、扫描线算法的具体步骤：•③③将将边的活化的活化链表表AEL中中满足足y=ymax的的边删去 (表明一条表明一条边已已经结束束)•④④将将边的活化的活化链表表AEL剩下的每一条剩下的每一条边的的x域累加域累加Δx，即，即x:=x+Δx (下一条下一条扫描描线与与边的交点的交点x，利用了，利用了边的的连续性性)•⑤⑤将当前的将当前的扫描描线的的纵坐坐标值y累加，即累加，即y:=y+1 ( 求下一条求下一条扫描描线)-5/357AELe0e54212AEL在在y=2扫描描线上的状上的状态-5/355AELe0e54214AEL在在y=3扫描描线上的状上的状态e0:m=-5/3,所以所以x变为7－－5/3＝＝5e5:m=2,所以所以x变为12+2＝＝14y=y+1,即即y=2+1=332-5/355AELe0e54214AEL在在y=3扫描描线上的状上的状态-5/353AELe0e54216AEL在在y=4扫描描线上的状上的状态-5/352AELe0e49216AEL在在y=5扫描描线上的状上的状态…54因因为对于于e5,y的的max已已经到了，到了，故去掉故去掉e5，而，而从从ET表中加入表中加入e433扫描描线算法描述算法描述1.建立ET表，置y为ET表中非空的最小y坐标值2.置AEL表为空，且按照y值将ET表的边加入AEL表中3.while  AEL表非空并且ET表中非空   do     begin4.      对AEL表中的xmin值按升序排列5.      按照AEL表中交点前后次序，在每对奇偶交点间的x段予以填充6.      if 扫描线 y=ymax  then 从AEL表中删除这些边7.      对在AEL表中的其他边，计算与下一条扫描线的交点：x=x+1/m8.      计算下一条扫描线：y=y+19.      按照扫描线y值把ET表中相应的边加入AEL表中end10.end of algorithm34扫描描线算法性能分析算法性能分析 扫描线算法的数据结构和程序结构都远比逐点判断算法复杂，对各种表的维护和排序的耗费很大。

但是由于它充分利用的多边形的区域、扫描线和边的三种形式的连贯性，从而避免了反复求交点的大量运算，因此速度比逐点判断法快的多353.4.2.3 边缘填充算法1、特点：、特点：采用采用对图像像进行逐位求反的方法，免去行逐位求反的方法，免去对边排序排序￿￿￿￿￿￿的工作量的工作量2、、预备知知识：：对颜色色M作偶数次求反运算，其作偶数次求反运算，其结果果还是是M，而，而对M作奇数次作奇数次求反运算的求反运算的结果是果是M的反的反M 在光在光栅图形中，如某区域已着形中，如某区域已着上上值为M的某种的某种颜色，色，则上述求反运算得到的上述求反运算得到的结果是：果是：对区区域作偶数次求反运算后，域作偶数次求反运算后，该区域的区域的颜色不色不变；作奇数次求反；作奇数次求反运算后，运算后，该区域的区域的颜色色则变成成值为M的的颜色363、边缘填充算法的实现 实现：：对多多边形形P的每一非水平的每一非水平边上的各像素做向右求反运算上的各像素做向右求反运算￿￿￿￿即可，即可，见下下图，其中，其中(a)为给定的多定的多边形；形；(b)为对区域区域赋初初值；；(c)，，(d)，，(e)和和(f)表示逐表示逐边向右求反。

向右求反￿ ￿373.4.2.4 边界标志算法1、基本原理：首先、基本原理：首先用一种用一种特殊的特殊的颜色色在在帧缓冲器中将多冲器中将多边形形的的边界界（水平（水平边的部分的部分边界除外）界除外）勾画勾画出来然后然后再把位于再把位于多多边形内形内的各个的各个像素着上所需的像素着上所需的颜色￿ ￿2、、算法具体算法具体实现步步骤：：Ø步步骤1：：以以值为boundary-color 的特殊的特殊颜色色勾画勾画多多边形形P的的边界界设多多边形形顶点点为Pi= (xi, yi),0≤i≤n，， xi, yi均均为整数；置整数；置Pn+1=P0每一条每一条扫描描线上着上上着上这种特殊种特殊颜色的点的个数必定色的点的个数必定是偶数是偶数(包括零包括零)Ø步步骤2：：设interior_point 是一布是一布尔变量对每一条每一条扫描描线从从左到右左到右进行搜索，如果当前是行搜索，如果当前是像素像素位于位于多多边形形P内内，，则interior_point=true，，需要需要填上填上值为polygon_color的的颜色；否色；否则该像素像素在在多多边形形P外外，需要填上，需要填上值为background_color的的颜色。

色￿ ￿383、边界标志算法实例标志志边界并界并处理奇点理奇点P2(9,6)P0(2,5)P1(2,11)P3(15,9)P4(15,3)P5(12,1)P6(7,1) for(i=0;i<=n;i++){v dy=p[i+1].y-p[i].y;v dx=(p[i+1].x-p[i].x)/dy;v if(dy>0)x=p[i].x;else x=p[i+1].x;v ymax=(Math.max(p[i].y,p[i+1].y));v ymin=(Math.min(p[i].y,p[i+1].y)); vfor (y=ymin+1;y<=ymax ;y++ )v { x=(int)(x+dx+.5);v if(pixels(x, y)==blue)v pixels(x+1, y)=blue;v else pixels(x, y)=blue;v }} // for(i=0;i<=n;i++)v确定某条确定某条边的的上下上下端点端点v水平水平边不考不考虑v多多边形的形的边数数v边界界颜色－色－蓝色色vP0P1的底端点的底端点yminvP0P1的上端点的上端点ymaxXXXXXXvP1P2的底端点的底端点yminXXXXXXXXXXXXXXXXXXXX393、边界标志算法实例P2(9,6)P0(2,5)P1(2,11)P3(15,9)P4(15,3)P5(12,1)P6(7,1)XXXXXXXXXXXXXXXXXXXXXXXXXX//maxx、、maxy、、minx、、miny是是获得得的的多多边//形最小矩形包形最小矩形包围盒盒边界界值for(y1 = miny - 1 ; y1<= maxy ;y1++) { in_flag = 0; //多多边形内部形内部标志志变量量 for( x1 = minx - 1; x1<=maxx - 1; x1++) { l = pixels(x, y); //多多边形形边界界颜色色blue if (l == blue) { if (in_flag == 0) in_flag = 1; else in_flag = 0; } if (in_flag) pixels(x, y)=blue; //在多在多边形内部填充色形内部填充色蓝色色 else pixels(x, y)=white; } } vminy,minxvmaxxvmaxyv获得当前象素得当前象素颜色以判断是否色以判断是否是是边界色界色v如果是如果是边界，且第一界，且第一/三次碰到三次碰到边界，就置界，就置flag为1，表明其后的，表明其后的象素要置成多象素要置成多边形的形的颜色色v如果是第二如果是第二/四次遇四次遇到到边界，就置界，就置flag为0，，对其后的元素置背景其后的元素置背景色色为白色。

白色403、边界标志算法实例P2(9,6)P0(2,5)P1(2,11)P3(15,9)P4(15,3)P5(12,1)P6(7,1)XXXXXXXXXXXXXXXXXXXXXXXXXXP2(9,6)P0(2,5)P1(2,11)P3(15,9)P4(15,3)P5(12,1)P6(7,1)XXXXXXXXXXXXXXXXXXXX413.3.2.5 区域填充一、区域的基本概念1、区域、区域是指已是指已经表示成点表示成点阵形式的像素集合形式的像素集合在光在光栅图形形￿￿￿￿￿￿中，区域可采用内点表示和中，区域可采用内点表示和边界表示两种形式界表示两种形式进行描述￿ ￿Ø内点表示法：内点表示法：把位于把位于给定区定区域域内内的所有的所有像素像素一一一一列列举出来出来的方法称的方法称为内点表示法内点表示法图3.25内点表示的区域图3.26边界表示的区域Ø边界表示法：界表示法：把位于把位于给定区定区域域边界界上的上的像素像素一一一一列列举出来出来的方法称的方法称为边界表示法界表示法421））4连通的区域通的区域: 取区域内任意两取区域内任意两点，在点，在该区域内若从其中一点出区域内若从其中一点出发通通过上、下、左、右四种运上、下、左、右四种运动可到可到达另一点。

达另一点图3.24四个方向的运四个方向的运动2））8连通的区域通的区域: 取区域内任意两取区域内任意两￿ ￿点，若从其中任一点出点，若从其中任一点出发，在，在该区域内通区域内通过沿水平方向、垂直方向沿水平方向、垂直方向和和对角角线方向的八种运方向的八种运动可到达另可到达另一点图3.25八个方向的运八个方向的运动2、区域的、区域的连通性通性43 3））￿ ￿4连通区域也可理解成通区域也可理解成8连通区域，即通区域，即4连通能达到的通能达到的8连通通肯定能达到，肯定能达到，4连通只是通只是8连通的一种特殊情况通的一种特殊情况图3.26内点表示的八内点表示的八连通区域通区域图3.27边界表示的八界表示的八连通区域通区域8连通而通而非非4连通通的地方的地方连通不是指通不是指边界而是界而是边界内的区域界内的区域这里是里是X围起来的区域起来的区域·号是区域号是区域X是是边界界44 但是两者的但是两者的边界界不尽相同不尽相同如果图中中标有有·号的象素号的象素组成成的区域作的区域作为4连通区域，通区域，则其其边界由界由图中的中的标有有△△号的象号的象素素组成如果将成如果将该区域作区域作为8连通的区域，通的区域，则其其边界由界由图中中标有有△△号和号和×号的两种象素号的两种象素组成。

成￿￿￿￿￿￿￿￿因因为如果区域是如果区域是8连通的，通的，△￿△￿边界不能将区域有效封堵，界不能将区域有效封堵，X的位置和区域又是的位置和区域又是连通的了￿ ￿图3.28四四连通区域与八通区域与八连通区域的不同通区域的不同边界界45二、简单的种子填充算法基本思想：基本思想：给定区域定区域G一种子点一种子点（（x, y））,首先首先判断判断该点点是否是是否是区域内区域内的一点，如果是，的一点，如果是，则将将该点点填充填充为新的新的颜色色，然后将，然后将该点周点周围的四个点的四个点（四（四连通）或通）或八八个点个点（八（八连通）作通）作为新的新的种子点种子点进行同行同样的的处理，通理，通过这种种扩散散完成完成对整个区域的填充整个区域的填充46算法描述如下：算法描述如下：1．将种子象素入栈；2．当栈非空时，重复：     ①栈顶象素出栈；     ②若该象素未填充，则将出栈象素置成填充色     ③以该象素为中心，检查出栈象素的4-邻接点，依“左上右下”顺序将非边界象素和未填充象素压入堆栈若其中某个象素点不是边界色且未置成填充色，则把该象素入栈47简单的种子填充算法void flood_fill_8(int[] pixels, int x, int y, int old_color, int new_color){ if(x0&&y0) { if (pixels[y*w+x]==old_color){ pixels[y*w+x]== new_color); flood_fill_8(pixels, x,y+1,old_color,new_color); flood_fill_8(pixels, x,y-1,old_color,new_color); flood_fill_8(pixels, x-1,y,old_color,new_color); flood_fill_8(pixels, x+1,y,old_color,new_color); flood_fill_8(pixels, x+1,y+1,old_color,new_color); flood_fill_8(pixels, x+1,y-1,old_color,new_color); flood_fill_8(pixels, x-1,y+1,old_color,new_color); flood_fill_8(pixels, x-1,y-1,old_color,new_color); } } } 48堆栈变化步骤例子：49•种子象素为（3，2）•填充（3，2），入栈（3，2）•出栈（3，2），填充并入栈（2，2），（3，3），（4，2），（3，1）•出栈（3，1），填充并入栈（2，1），（4，1）•出栈（4，1），出栈（2，1），出栈（4，2），•出栈（3，3），填充并入栈（2，3）•出栈（2，3），出栈（2，2），填充并入栈（1，2），出栈（1，2）50递归算法的性能分析算法的性能分析   区域填充的递归算法程序简单，表达清楚。

但由于多层递归，系统堆栈反复进出，费时费内存51三、扫描线种子填充算法1、基本思想：、基本思想：￿￿￿￿￿￿￿￿￿￿￿￿从从给定的定的种子点开始，种子点开始，填充填充当前当前扫描描线上上种子种子点所在点所在的一的一区段区段，然后确定与，然后确定与这一段相一段相邻的的上下两条上下两条扫描描线上位于区域内的区段（需要填充的区上位于区域内的区段（需要填充的区间），从），从这些区些区间上上各取一个种子点各取一个种子点依次把它依次把它们存起来，存起来，作作为下次填充的种子点下次填充的种子点反复进行行这过程，直到所保存的程，直到所保存的各区段都填充完各区段都填充完毕522、算法步、算法步骤：：步步骤￿ ￿1：：（初始化）（初始化）将算法将算法设置的堆置的堆栈置置为空将给定的定的￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿种子点种子点（（x, y））压入堆入堆栈步步骤￿ ￿2：：（出（出栈））如果堆如果堆栈为空，算法空，算法结束；否束；否则取取栈顶￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿元素（元素（x, y）作）作为种子点种子点12栈种子种子53步步骤￿ ￿3：：（区段填充）（区段填充）从种子点从种子点（（x, y））开始，沿开始，沿纵坐坐标为y的当前的当前扫描描线向左右两个方向逐个像素用新的向左右两个方向逐个像素用新的颜色色值进行行填充，直到填充，直到边界界为止即象素止即象素颜色等于色等于边界色。

界色设区区间两两边界的横坐界的横坐标分分别为xleft 和和xright步步骤4：：在与当前在与当前扫描描线相相邻的上下两条的上下两条扫描描线上，上，以区以区间[xleft, xright]为搜索搜索范范围，求出需要填充的，求出需要填充的各各小区小区间，把，把各小区各小区间中最中最右右边的点并作的点并作为种子点种子点压入堆入堆栈，，转到步到步骤2￿ ￿12种子点种子点xleft xright54区域填充的区域填充的扫描描线算法描述算法描述1.将种子象素点压入堆栈2.while 堆栈非空   do  begin3.     从堆栈中弹出一个种子象素4.     沿着扫描线对种子象素的左右象素进行填充，直至遇到边界  象素为止5.     标志区间内最左和最右象素为xleft 和xright6.     if在xleft≤x≤xright中检查与当前扫描线相邻的上下两条扫描线全为边界象素或全为已填充过的象素  then goto 27.     在xleft≤x≤xright中标记每一个既不包含边界象素又不包含已 填充过的象素的区间8.     将每一区间的最右象素作为种子象素压入堆栈end9.end of algorithm553、算法的关、算法的关键原原则：：1）搜索原）搜索原则：：从前一个填充的区从前一个填充的区间（（边界之界之间的的范范围xleft, xright）作）作为后一条后一条扫描描线种子点种子点寻找的范找的范围。

2）填充原）填充原则：：从种子点往从种子点往左，右左，右填，填到填，填到边界界1212如果种子如果种子点在点在这里里xleftxright搜索确定种子点搜索确定种子点种子点填充种子点填充5612121022223322222v4、、实例例57Stack stack=new Stack();//堆堆栈￿ ￿pixel_stack初始化初始化Stack.push (point)；；￿￿￿￿￿￿￿￿//(x,y)是是给定的种子像素定的种子像素while (!stack.empty()){p=(Point)(stack.pop())；；//出出栈，从堆，从堆栈中取一像素作种子像素中取一像素作种子像素x=p.x; y=p.y;savex=x；；//保存种子点的横坐保存种子点的横坐标x的的值while (dc.GetPixel(x,y)!= boundary_color){dc.SetPixel(x,y,new_color); x++;} //从种子像素开始向右填充到从种子像素开始向右填充到边界界xright=x–1; //保存保存线段的右端点段的右端点x=savex–1; //设定种子点往左填充的起点定种子点往左填充的起点x-1填充填充过程程xxrv5、程序、程序实现58while (dc.GetPixel(x,y)!= boundary_color){dc.SetPixel(x,y,new_color);x=x–1;}//从种子像素开始向左填充到从种子像素开始向左填充到边界，以上两步完成区界，以上两步完成区间填充。

填充    xleft=x+1；； //保存保存线段的左端点，加段的左端点，加1是因是因为前面前面                       // 循循环时多减一次多减一次x=xleft;     //起点是上次的左端点起点是上次的左端点y=y+1;     //开始开始处理上一条理上一条扫描描线填充填充过程程xx-1xleft59while(x<=xright) { //在上一条在上一条扫描描线上上检查是否需要填充是否需要填充span_need_fill=false; //先先设定定为不需要填充不需要填充while (dc.GetPixel(x,y)==old_color&&x<=xright ) { //待填充的待填充的线段段 span_need_fill=true; //发现有旧象素，需要填充有旧象素，需要填充 x=x+1;} //待填充的待填充的线段段处理完，即遇到理完，即遇到边界色，界色，!=old_color跳出跳出if (span_need_fill) { //如果区如果区间需要填充，需要填充，则将其右端点作将其右端点作￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿为种子点种子点压进堆堆栈 p=new Point(x-1,y); stack.push (p); //进栈 span_need_fill=false;}60//继续向右向右检查以防有以防有遗漏漏while (dc.GetPixel(x,y)!=old_color &&x<=xright ) x=x+1;} //在上一条在上一条扫描描线上上检查完完x＝＝xleft；；y=y–2; //形成下一条形成下一条扫描描线的的y值//在下一条在下一条扫描描线上从左向右上从左向右检查位于区位于区间[xleft，，xright]上的像素，上的像素，其方法与在上一条其方法与在上一条扫描描线上上检查的情况完全一的情况完全一样。

}//出出栈完完如果种子点在这里12123xleftxright61扫描描转换和区域填充的比和区域填充的比较多边形的扫描转换和区域填充是两类典型的面着色问题，在一定条件下两者可以相互转换但二者的基本思想是不同的ü多边形的扫描转换是指将多边形的顶点表示转换成点阵表示，在扫描转换过程中利用了多边形各种形式的连贯性；ü区域填充只改变区域的颜色，不改变区域的表示方法在填充过程中应用了区域的连通性623.4 字符的生成 •3.4.1 点点阵式字符式字符 •在点在点阵字符字符库中，每个字符由一个位中，每个字符由一个位图表示该位位为1表表示字符的笔画示字符的笔画经过此位，此位，对应于此位的象素于此位的象素应置置为字符字符颜色该位位为0表示字符的笔画不表示字符的笔画不经过此位，此位，对应于此位的于此位的象素象素应置置为背景背景颜色在实际应用中，有多种字体（如宋用中，有多种字体（如宋体、楷体等），每种字体又有多种大小型号，因此字体、楷体等），每种字体又有多种大小型号，因此字库的的存存储空空间是很是很庞大的 63•常用的点常用的点阵大小有大小有7×9、、8×8、、16×16等下图所所示的是字母示的是字母“P”的点的点阵式表示。

式表示显示点示点阵式字符式字符时，只需将字，只需将字库中的矩形点中的矩形点阵映射到映射到帧缓冲器中冲器中的的单元即可643.4.2 轮廓式字符•轮廓式字符是将每个字符定廓式字符是将每个字符定义为一条曲一条曲线或多或多边形的形的轮廓，廓，显示示时需要需要进行行扫描描转换如下图所所示示为字母字母“B”的的轮廓表示，廓表示，轮廓廓线构成了一个或构成了一个或若干个封若干个封闭的平面区域，的平面区域，显示示时字符字符轮廓的内部廓的内部需用需用扫描描线填充程序来填充填充程序来填充 653.5 光栅图形的反走样算法 a:图形的形的边界一般都呈界一般都呈阶梯形梯形￿ ￿￿ ￿b:图形的形的细节失真、狭小失真、狭小图形形遗失失￿ ￿（（a））￿ ￿待待显示的示的细小小图形形（（b））￿ ￿显示示结果果细节失真失真（（a）待）待显示的狭小矩形示的狭小矩形（（b））￿ ￿显示示结果果狭小狭小图形的形的遗失失阶梯形梯形边界界阶梯形梯形线段段v3.5.1 光光栅图形的走形的走样现象象663.5.2 提高分辨率的反走样方法Ø采用采用硬件硬件: 采用高分辨率的光采用高分辨率的光栅图形形显示器，花示器，花费的代价大。

的代价大Ø采用采用软件件: 花花费的代价小，也容易的代价小，也容易实现•高分辨率高分辨率计算算：将低分辨的：将低分辨的图形形显示象示象￿ ￿￿ ￿￿ ￿素素划划分分为许多多子子象象素素，，如如2×2划划分分，，￿ ￿￿ ￿￿ ￿3×3划划分分等等，，然然后后按按通通常常的的算算法法计算算￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿出各个子象素的出各个子象素的颜色色值或灰度或灰度值•低分辨率低分辨率显示示：将一象素内的各个子象：将一象素内的各个子象￿￿￿￿￿￿素的素的颜色色值或灰度或灰度值的平均的平均值作作为该￿￿￿￿￿￿象素的象素的颜色色值或灰度或灰度值求平均值时￿￿￿￿￿￿可取算可取算术平均，也可取加平均，也可取加权平均￿ ￿加加权表表1、用、用软件件提高分辨率的方法是：提高分辨率的方法是：￿￿￿￿￿￿高分辨率高分辨率计算，低分辨率算，低分辨率显示￿ ￿673.5.3  区域采样的反走样算法￿1、、线段的反混淆算法的段的反混淆算法的基本思想基本思想可可归纳如下：如下：(1)把把线段段看看作作是是有有宽度度的的狭狭长的的矩矩形形(因因为线段段是是有有宽度度的的)，，所以所以(2)线段段具具有有一一定定的的面面积，，当当线段段通通过某某象象素素时，，可可以以求求出出线段与像素的面段与像素的面积的交，的交，然后然后(3)根根据据每每一一象象素素与与线段段相相交交部部分分的的面面积值决决定定该象象素素的的颜色色值或灰度或灰度值。

有有宽度的度的线段段反走反走样后后线段的段的显示示683.5.3   区域采样的反走样算法￿设一条直一条直线的斜率的斜率为m，其，其宽度度为一个像素一个像素单位，位，则直直线与像与像素相交的情况共有素相交的情况共有5种￿ ￿v(a)v(b)v(c)v(d)v(e)•在在计算阴影面算阴影面积时，（，（a）与（）与（e）、（）、（b）与（）与（d））类似，（似，（c）可用）可用正方形的面正方形的面积减去减去2个三角形的面个三角形的面积因此只讨论（（a）和（）和（b）的情）的情况如下图，情况（，情况（a）的阴影面）的阴影面积为D2/2m；情况（；情况（b）的阴影面）的阴影面积为D-m/2vDvD/mvDvmv(a)v(b)v阴影面积的计算693.5.3   区域采样的反走样算法￿•上述阴影面上述阴影面积是介于是介于0～～1之之间的正数，用它乘以像素的最的正数，用它乘以像素的最大灰度大灰度值，再取整，就可得到像素的，再取整，就可得到像素的显示灰度示灰度值将这种种区域采区域采样的反走的反走样算法用于直算法用于直线段段时，就相当于将，就相当于将线段上段上位于原相位于原相邻阶梯之梯之间的像素置的像素置为了了过渡渡颜色或灰度，从而色或灰度，从而使得使得颜色或者灰度色或者灰度过渡自然，渡自然，变化柔和。

化柔和阶梯被淡化后，梯被淡化后，线形自然就形自然就显得平直了得平直了•为了了简化运算，有化运算，有时候候还可以采用离散可以采用离散的方法即将屏幕像素均分成的方法即将屏幕像素均分成n个子像个子像素，素，计算中心点落在直算中心点落在直线段内的子像素段内的子像素的个数的个数k，那么，那么该像素的亮度就是最大像素的亮度就是最大灰度灰度值乘以相交区域面乘以相交区域面积的近似的近似值k/n左左图所示是所示是n=9，，k=3，近似面，近似面积为1/3的情况 703.5.4 加权区域采样的反走样算法￿ 将像素均分成将像素均分成n个子像素，每个子像素的面个子像素，每个子像素的面积为1/n，，计算每个子像素算每个子像素对原像素的原像素的贡献，并保存献，并保存在一在一张二二维的加的加权表中（表中（3.5.2节的的图中的（中的（a）、）、（（b）就是将一个像素分）就是将一个像素分别均分均分为3×3个子像素和个子像素和7×7个子像素个子像素时所所对应的加的加权表）；求出所有中心表）；求出所有中心落在直落在直线段内的子像素段内的子像素组成的集合，并成的集合，并计算算这些些子像素子像素对原像素的亮度原像素的亮度贡献之和的献之和的值，，该值乘以乘以像素的最大灰度像素的最大灰度值就得到就得到该像素最像素最终要要显示的亮示的亮度。

度 71•课件等相关资料下载：•E-Mail：•密码：geoscience200872。