第四讲：二维图形填充,内容摘要,区域填充有序边表算法边填充算法边标志算法种子填充算法圆域的填充线宽与线型的处理直线线宽的处理（笔型：线、方形）圆弧线宽的处理（笔型：线、方形）线型的处理,,,内容摘要,字符矢量字符点阵字符字型技术字符裁剪反走样基础提高分辩率简单的区域反走样算法卷积积分与反走样算法半色调技术,,有序边表算法,一般多边形的填充过程，对于一条扫描线Y值，可以分为四个步骤：求交点X：计算扫描线与多边形各边的交点X的值；排序：把所有相交点x按递增顺序进行排序；交点配对：第一个与第二个，第三个与第四个等等每对交点就代表扫描线与多边形的一个相交区间；区间填色：把这些相交区间内的象素置成多边形色，把相交区间外的象素置成背景色特殊顶点处理:P1、P3情况:相同交点取1个;P2、P5情况:相同交点取2个;P4、P6情况:相同交点取0个;(下闭上开原则，防止填充扩大化),,,,,,,,,填充扩大化问题的解决,采用下闭上开、左闭右开原则，防止填充扩大化例如填充左下角为（1，1），右上角为（3，3）的区域，得到的图形如图所示九个象素被点亮，而实际区域应是黄区所示采取的措施：在具体实现时，只要对扫描线与多边形的相交区间取“左闭右开”。
在上述讨论中，当扫描线与多边形顶点相交时，所使用的交点取舍的方法，保证了多边形的“下闭上开”，丢弃上方水平边以及上方非水平边上作为局部最高点的顶点如左图,活性边与活性边表处理方法,一个多边形与若干扫描线为了计算每条扫描线与多边形各边的交点，最简单的方法是把多边形的所有边放在一个表中在处理每条扫描线时，按顺序从表中取出所有的边，分别与扫描线求交点这样处理效率很低这是因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交若在处理每条扫描线时，不分青红皂白地把所有边都拿来与扫描线求交点，则其中绝大多数都是徒劳无用的如果采用活性边表，则可减少许多计算扫描线依次变化为1,2,3,4,5,6,7,8,…...x是边与当前扫描线的交点；x是该边从当前扫描线到下一扫描线之间x增量；ymax是边所交的最高扫描线号在上述的交点x坐标更新和新边插入之前，必须把那些与当前扫描线相交，而与下一条扫描线不再相交的边，从活性边表(AET)中删除出去新边表处理方法,为了方便活性边表的建立与更新，为每一条扫描线建立一个新边表，在该扫描线第一次出现的边保留与此也就是说,若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。
这样，当按扫描线号从小到大顺序处理扫描线时，该边在该扫描线第一次出现新边表的每个结点存放对应边的初始信息，比如该扫描线与该边的初始交点x（即较低端点的x值），x的增量x，以及该边的最大y值ymax图3-18所示，为左图中各扫描线的新边表区间填充需设置一个布尔变量b, 在多边形内b为真,, 在多边形外b为假,,b的初值为假当指针从活性边表中第一个结点（交点）到最后一个结点遍历一次时，每访问一个结点，把b取反一次若b为真，则把从当前结点的x值开始到下一结点的x值结束的左闭右开区间，用多边形色填充利用区间连贯性，即同一区间上的象素取同一颜色属性多边形外的点用背景色填充边填充算法,基本思想：对于每一条扫描线和每一条多边形边的交点(xi，yi)，将该扫描线上交点右方的所有象素取补对多边形的每条边均作此处理，多边形的顺序随意右图为采用最简单的边填充算法填充一个多边形的示意图边填充算法最适用于具有帧缓冲存储器的图形系统，按任意顺序处理的边在处理每条边时，仅访问与该边相交的扫描线上交点右方的象素当所有的边都被处理之后，按扫描线顺序读出帧缓冲存储器的内容，送入显示设备可见本算法的优点是简单，缺点是对于复杂图形，每一象素可能被访问多次，输入／输出的量比有序边表算法大得多。
为了减少边填充算法访问象素的次数，可引入栅栏所谓栅栏指的是一条与扫描线垂直的直线，栅栏位置通常取过多边形顶点、且把多边形分为左右两半栅栏填充算法,基本思想是：当扫描线与多边形边有交点，就将交点与栅栏之间的象素取补若交点位于栅栏左边，则将交点之右，栅栏之左的所有象素取补；若交点位于栅栏右边，则将栅栏之右，交点之左的象素取补如图所示，为采用栅栏填充算法填充多边形的示意图栅栏填充算法只是减少了被重复访问的象素的数目，但仍有一些象素会被重复访问从图中很容易看出这一点下面介绍的边标志算法进一步改进了栅栏填充算法，使得算法对每个象素仅访问一次算法示意图如下页所示边标志算法,基本思想是：分为两步骤，第一步，对多边形的每条边进行直线扫描变换，亦即对多边形边界所经过的象素打上标志；第二步，填充对每条与多边形相交的扫描线，依从左到右顺序，逐个访问该扫描线上象素使用一个布尔量inside来指示当前点的状态，若点在多边形内，则inside为真若点在多边形外，则inside为假inside的初始值为假，每当访问到象素为被打上边标志的点时，就把inside取反对未打标志的象素，inside不变若访问象素时，inside为真，则把该象素置为多边形色。
用软件实现时，有序边表算法与边标志算法的执行速度几乎相同，但由于在帧缓冲存储器中应用边标志算法时，不必建立、维护边表以及对它进行排序，所以边标志算法更适合于硬件实现，这时它的执行速度比有序边表算法快到一至两个数量级种子填充算法的连通区域,基本思想是前面讨论的填充算法都是按扫描线的顺序进行象素点的填充的，种子填充算法是根据已知的一个多边形区域内部的一个象素点来找到区域内其它的象素点进行填充的前面讨论的填充算法都是按扫描线的顺序进行象素点的填充的，种子填充算法是根据已知的一个多边形区域内部的一个象素点来找到区域内其它的象素点进行填充的一般都采用边界定义区域，即边界区域上所有象素被置为特定值，而区域内部所有的象素均不取这个值区域可以分为四连通或八连通两种，如果区域是四连通的，那么区域内每一个象素可以通过四个方向（上、下、左、右）组合到达，而对八连通区域，区域内的每个象素可通过上、下、左、右以及四个对角线方向的移动组合到达八连通算法可以填充四连通区域，而四连通算法不能填充八连通区域两类连通区域如图所示图 (b)中八连通区域的子区域是四连通的，然而从一个子区域到另一个子区域需用八连通算法，若每个子区域看成是分离的二个四连通区域，并且每个区域填上不同的色彩值，如果用八连通算法会让两个区域均被错误地填上同样的色彩。
下面仅讨论四向连通算法,只要把搜索方向从四个该为八个,即可得到八向算法简单种子填充算法,简单的种子填充算法如下：(1) 将种子象素压入栈中；(2)当栈非空时从栈中弹出一个象素；将该象素置成所要求的色彩值；检查每个与当前象素邻接的四连通象素是否是边界色或已置成所要求的色彩值，若是则返回(2)，否则将该象素压入栈中回到(2)[例] 简单的种子填充算法多边形由顶点P0、P1、P2、P3、P4构成，见图3-23P0（1，5）、P1(5，5) 、P2(7，3) 、P3(7，1) 、P4(1，1)，可设种子点为(3，3)；四连通的组合方向是上、下、左、,右初始时栈中只有(3，3)象素；弹出(3，3)，由于该象素未置成色彩值且也不是边界色，故填色彩值；同时将(3，4) (3，2) (2，3) 及(4，3)压入栈中；栈中有四个元素；弹出(4，3)并置上要求的色彩值，再将(4，4) (4，2) (5，3)压入栈中；栈中有6个元素；依次类推，象素被选中并填充的次序如图中箭头所示当栈为空时，算法终止分析该算法不难发现，在进行填充过程中堆栈会变得很大，而且在堆栈中还常常包含有一些重复的和不必要的信息为此提出了扫描线种子填充算法。
3,3),弹出(3,3),(4,3)(2,3)(3,2)(3,4),弹出(4,3)(2,3)(3,2)(3,4),(5,3)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(5,3)(4,2)(4,4)(2,3)(3,2)(3,4),(6,3)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(6,3)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),(6,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(6,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),(5,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),,,,,,,,,,,,,,,,,,,,弹出(5,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),(4,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(4,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),(3,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(3,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),(2,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(2,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),(2,3)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(2,3)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),(2,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(2,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),(3,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(3,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),(4,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(4,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),(5,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),弹出(5,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4),,扫描线种子填充算法,所谓扫描线种子填充算法，是在任意不间断扫描线区间中只取一个种子象素。
不间断区间即指在一条扫描线上一组相邻的元素算法可分为以下几步：1） 从包含种子象素的栈中弹出种子象素；2）沿着扫描线对种子象素进行填充，直到遇到边界象素为止，这样就填充了种子所在的扫描线中的元素；3）区间内最左、最右元素为Xleft，Xright;则在Xleft X Xright区间中检查与当前扫描线相邻的上、下两条扫描线是否全为边界象素或已填充过的象素若不是，则对于Xleft X Xrigh，把与当前扫描线相邻的上、下两条扫描线中该区间的最右象素作为种子压入栈中算法结束条件为栈空此算法适用于用边界定义的区域圆域的填充,,上面所讨论的多边形区域的填充原理也可以推广到圆域的填充对每条扫描线，先计算它与圆域的相交区间，再把区间内象素用指定颜色填充在实际应用中，除了使用单象素宽的线条，还经常使用指定线宽和线型的直线与弧线欲产生具有宽度的线，可以顺着扫描所生成的单象素线条轨迹，移动一把具有一定宽度的“刷子”来获得刷子”的形状可以是一条线段或一个正方形也可以采用区域填充的办法间接地产生有宽度的线假设直线斜率在[－1，1]之间，这里可以把刷子置成垂直方向，刷子的中点对准直线一端点，然后让刷子中心往直线的另一端移动，即可“刷出“具有一定宽度的线。
当直线斜率不在[－1，1]之间时，把刷子置成水平方向具体实现线刷子时，只要对直线扫描变换算法的内循环稍作修改即可例如，当直线斜率在[－1，1]之间时，把每步迭代所得的点的上下方半线宽之内的象素全部置成直线颜色如右上图所示为线宽是5个象素的情形线刷子的优点是算法简单、效率高但是，线的始末端总是水平或垂直的因此，当线宽较大时，看起来很不自然当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口,如左上图所示斜线与水平（或垂直）线不一样粗对于水平线或垂直线，刷子与线条垂直，因而最粗其粗细与指定线宽相等而对于45斜线，刷子与线条成45角，粗细仅为指定线宽的1/ 2 0.7倍。