计算机图形学彩版第四章多边形填充

孔令德

多边形填充第四章有效边表填充算法边缘填充算法四邻接点种子填充算法八邻接点种子填充算法扫描线种子填充算法本章学习目标4.1多边形的扫描转换4.2有效边表填充算法4.3边缘填充算法4.4区域填充算法4.5本章小结本章内容

在第3章中，讲解了直线段扫描转换的中点Bresenham算法。多段直线彼此连接并且闭合就构成了多边形。多面体的每个表面就是一个多边形，曲面体的连续表面一般被离散为三角形小面或四边形小面。每个表面（小面）均需要按照顶点颜色进行着色，而顶点颜色可以直接指定也可以是材质、纹理、光照等条件交互作用的结果。解决了多边形的填充问题就解决了物体的表面着色问题。多边形的边界线可根据需要选择绘制或者不绘制，如图4-1所示。真实感图形的绘制中，一般不绘制多边形的边界线。（a）无边界（b）绘制边界图4-1填充多边形本章基于图4-2所示的“示例多边形”讲解多边形填充算法。图4-2示例多边形4.1.1多边形的定义

多边形是由折线段组成的封闭图形。它由有序顶点的点集Pi（i＝0，…，n-1）及有向边的线集Ei（i＝0，…，n-1）定义，n为多边形的顶点数或边数，且Ei＝PiPi+1，i＝0，…，n-1。这里Pn＝P0，用以保证了多边形的封闭性。多边形可以分为凸、凹多边形以及环，如图4-3所示。4.1多边形的扫描转换

图4-3多边形的定义⑴顶点表示法

4.1.2多边形的表示

图4-4多边形表示法⑵点阵表示法⑶多边形的扫描转换将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出位于多边形内部及其边界上的各个像素点信息。

4.1.3多边形着色模式

多边形可以使用平面着色模式（flatshadingmode）或光滑着色模式（smoothshadingmode）填充。平面着色是指使用多边形第一个顶点的颜色填充，多边形内部具有单一颜色。光滑着色是指多边形内部像素点的颜色是由多边形各个顶点的颜色进行线性插值得到。图4-6所示为三角形的平面着色，三角形填充为三角形第一个顶点的颜色红色。图4-7所示为三角形的光滑着色，三角形上任一点的颜色为3个顶点颜色的光滑过渡。

图4-6三角形的平面着色图4-7三角形的光滑着色图4-8所示的图形是采用平面着色模式填充的不同灰度的矩形块，被称为马赫带（MachBand）。观察明暗变化的边界，可以看出边界处亮度对比度加强，使得边界表现得非常明显，称为马赫带效应。马赫带效应不是一种物理现象，而是一种心理现象，夸大了平面着色的渲染效果，使得人眼感到的亮度变化比实际的亮度变化要大，如图4-9所示。实际光强感知光强

图4-8马赫带图4-9边界位置的实际亮度与感知亮度

4.1.4多边形填充算法这里的多边形是用顶点法表示的多边形。多边形的填充是指从多边形的顶点信息出发，求出其覆盖的每个像素点，取为填充色，而将多边形外部的像素点保留为背景色。

多边形填充的主要工作是确定穿越多边形扫描线的覆盖区间，然后将其着色。

首先确定多边形覆盖的扫描线条数（ymin～ymax），对每一条扫描线，计算扫描线与多边形边界的交点区间（xmin～xmax），然后再将该区间内的像素赋予指定的颜色。在扫描线从多边形顶点的最小值ymin向多边形顶点的最大值ymax的移动过程中，重复上述工作，就可以完成多边形的填充任务。4.1.5区域填充算法区域是指一组相邻而又具有相同属性的像素，可以理解为图形的内部。区域一般由封闭边界定义。区域的边界色和填充色不一致，区域一般采用种子算法进行填充。种子填充算法是从区域内给定的种子位置开始，按填充颜色填充种子的相邻像素直到颜色不同的边界像素为止。种子填充算法主要有4邻接点算法和8邻接点算法。4.2有效边表填充算法

4.2.1填充原理

多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色着色填充区间内的每个像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸多边形、凹多边形和环，已成为目前最为有效的多边形填充算法。在图4-10中，多边形覆盖了12条扫描线。扫描线y＝3与多边形有4个交点，分别为（2.3,3），(4.5,3），（7,3）和（9,3）。对交点进行圆整处理后的结果为（2,3），(5,3），（7,3）和（9,3）。按x值递增的顺序对交点进行排序、配对后的填充区间为[2,5]和[7,9]，共有7个像素点需要着色。图4-10用一条扫描线填充多边形P44.2.2边界像素处理原则

实际填充过程中，需要考虑到边界像素的影响问题。图4-11中正方形P0P1P2P3被等分为4个小正方形。假定小正方形P0P5P8P6被填充为绿色，P5P1P7P8被填充为黄色，P8P7P2P4被填充为绿色，P6P8P4P3被填充为黄色。

P0P5P1P7P6P8P2P3

对于相邻多边形的公共边，如不做处理，可能公共边上的像素先设置为一个多边形的颜色，然后又设置为另一个多边形的颜色，一条边界绘制两次会导致混乱的视觉效果。图4-11边界像素的问题

在实际应用中，有时也需要考虑到像素面积大小的影响问题。对左下角为（1，1），右上角为（3，3）的正方形进行填充时，若边界上的所有像素全部填充，就得到图4-12所示的结果。所填像素覆盖的面积为3×3个单位，而正方形的面积实际只有2×2个单位。

图4-12面积为3×3P4为了解决这些问题，在多边形填充过程中，常采用“下闭上开”和“左闭右开”的原则对边界像素进行处理。图4-11的填充结果如图4-13所示，每个小正方形的右边界像素和上边界像素都没有填充，即P6P8和P5P8填充为黄色，P8P7和P8P4填充为绿色。图4-12的填充结果如图4-14所示，没有填充上面一行像素和右面一列像素，保证正方形的面积是2×2个单位。图4-13边界像素的处理P2P5P8P0P6P3P7P1

图4-14面积为2×2图4-2中的顶点可分为3类。共享顶点的两条边落在扫描线的下方。如P1、P6和P4。局部最高点普通连接点局部最低点共享顶点的两条边分别落在扫描线两侧。如P2

共享顶点的两条边落在扫描线的上方。如P0、P3和P5常根据共享顶点的两条边的另一端的y值大于扫描线y值的个数来将这3类顶点个数分别取为0、1和2。有效边表算法能自动处理这3类顶点。普通连接点的处理原则

图4-2中P2点是边P3P2的终点，也是边P2P1的起点，属于普通连接点的顶点个数计数为1。按照“下闭上开”的原则，P2点作为P3P2边的终点不填充，但作为P2P1的起点被填充。局部最低点的处理原则P0、P3和P5点是局部最低点，如果处理不当，扫描线y＝1会填充区间[3，8]，结果填充了P3点和P5点之间的像素，如图4-15所示。将局部最低点的顶点个数计数为2。y＝1的扫描线填充时，共享顶点P3的P3P2边与P3P4边加入有效边表，所以P3点被填充两次，同理，P4点也被填充两次。图4-15局部点的处理局部最高点的处理原则局部最高点的顶点个数计数为0，扫描线会自动填充P4点，根据“下闭上开”原则会自动放弃P1点、P4点和P6点。P1点与P6点将不再填充，P4点被扫描线y=5填充。如图4-15所示。4.2.3有效边与有效边表

有效边多边形内与当前扫描线相交的边称为有效边（activeedge，AE）。在处理一条扫描线时仅对有效边进行求交运算，可以避免与多边形的所有边求交。有效边交点之间具有相关性，知道当前扫描线与有效边的交点坐标，使用增量法可计算出下一条扫描线与有效边的交点坐标。交点的y坐标就是扫描线，执行的是加1操作，交点的x坐标可以按如下方法推导。设有效边的斜率为k假定有效边与当前扫描线yi的交点为（xi，yi），则有效边与下一条扫描线yi+1的交点为（xi+1，yi+1）。其中，，如图4-16所示，随着扫描线的移动，扫描线与有效边交点的x坐标是从边的起点坐标开始按增量1/k计算出来的。图4-16有效边交点之间的相关性2.有效边表将有效边按照与扫描线交点的x坐标递增的顺序存放在一个链表中，称为有效边表（activeedgetable，AET），有效边表的结点如图4-17所示。图4-17有效边表结点图4-17中，x是当前扫描线与有效边的交点；ymax是边所在的扫描线最大值，用于判断该边何时扫描完毕后，被抛弃而成为无效边。对于图4-2所示的多边形，顶点表示法为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）,P4（6，5）,P5（8，1）,P6（12，9）。扫描线的最大值为ymax＝12，最小值为ymin＝1。共有12条扫描线，扫描线之间间隔1个像素单位。每条扫描线的有效边表如图4～18～图4-22所示。图4-18扫描线y=1～y＝3的有效边表图4-19扫描线y=4～y＝5的有效边表y=4的扫描线处理完毕后对于P3P4和P4P5两条边，因为下一条扫描线y=5与ymax相等，根据“下闭上开”的原则予以删除，如图4-19所示。图4-20扫描线y=6～y＝7的有效边表y=6的扫描线处理完毕后，对于P2P3边，因为下一条扫描线y=7与ymax相等，根据“下闭上开”的原则予以删除。当y＝7时，添加上新边P1P2，如图4-20所示。当y＝8时，添加上新边P0P1和P0P6，如图4-21所示。这条扫描线处理完毕后对于P5P6边和P0P6边，因为下一条扫描线y=9与ymax相等，根据“下闭上开”的原则予以删除，如图4-22所示。图4-21扫描线y=8的有效边表y=11的扫描线处理完毕后对于P1P2边和P0P1边，因为下一条扫描线y=12与ymax相等，根据“下闭上开”的原则予以删除。图4-22扫描线y=9～y＝11的有效边表4.2.4桶表与边表

桶表和边表的表示法桶表是按照扫描线顺序管理边出现情况的一个数据结构。构造一个纵向扫描线链表，其长度为多边形所覆盖的最大扫描线数，链表的每个结点称为桶（Bucket）。将每边信息链到与该边最小y坐标（ymin）相对应的桶结点。对于一条扫描线，如果新增多条边，按x|ymin坐标递增的顺序存放在一个链表中，若x|ymin

相等，按照1/k由小到大排序，这样就形成边表，如图4-23所示。图4-23边表结点2.桶表与边表示例图4-24示例多边形的桶表与边表4.3边缘填充算法4.3.1填充原理

边缘填充算法是先求出多边形的每条边与扫描线的交点，然后将交点右侧的所有像素颜色全部取为补色。按任意顺序处理完多边形的所有边后，就完成了多边形的填充任务。边缘填充算法利用了图像处理中的求“补”的概念，对于黑白图像，求补是把颜色为RGB(255,255,255)（白色）的像素置为RGB(0,0,0)（黑色），反之亦然；对于彩色图像，求补是将背景色置为填充色，反之亦然。4.3.2填充过程

假定边的访问顺序为E0、E1、E2、E3、E4、E5和E6，如图4-25所示。图4-25边缘填充算法示例多边形示例多边形的填充过程如图4-26所示。

图4-26边缘填充算法示意图边缘填充算法的效率受到交点右侧像素的数量影响，右侧像素越多，需要取补的像素也就越多。为了提高填充效率，可以在图4-27所示多边形的包围盒内进行像素取补，或者如图4-28所示，在包围盒内再添加一条栅栏，处理每条边与扫描线的交点时，只将交点与栅栏之间的像素取补。

图4-27带包围盒的多边形图4-28带栅栏形的多边形4.4区域填充算法4.4.1填充原理

对于用点阵方法表示的区域，如果其内部像素具有同一种颜色，而边界像素具有另一种颜色，如图4-29所示，可以使用种子填充算法进行填充。种子填充算法是从区域内任一个种子像素位置开始，由内向外将种子像素的颜色扩展到整个区域内的填充过程。该算法基于连通域内像素的连贯性，以递归方式确定区域内部点与边界点，而不涉及区域外部的点，从而有效地提高了算法的效率。图4-29区域内部与边界表示

4.4.2四邻接点与八邻接点

（a）四邻接点（b）八邻接点图4-30邻接点定义区域内部任意一个种子像素，其左、上、右、下这4个像素称为四邻接点，如图4-30（a）所示。区域内部任意一个种子像素，其左、上、右、下以及左上、右上、右下、左下这8个像素称为八邻接点，如图4-30（b）所示。4.4.3四连通域与八连通域

种子填充算法要求区域内部必须是连通的，才能将种子像素的颜色扩展到区域内部的所有像素点，一般将区域划分为四连通域与八连通域两种。四连通域定义从区域内部任意一个种子像素点出发，通过访问其左、上、右、下这4个邻接点可以遍历区域内的所有像素点，该区域称为四连通域，如图4-31和图4-32所示。

八连通域定义从区域内部任意一个种子像素点出发，通过访问其左、左上、上、右上、右、右下、下、左下这8个邻接点可以遍历区域内的所有像素，该区域称为八连通域，如图4-33和图4-34所示。

图4-31四连通域及四连通约束边界图4-32四连通域及八连通约束边界

图4-33八连通域及四连通约束边界图4-34八连通域及八连通约束边界对于图4-34所示的八连通域，假定种子像素位于多边形区域的左下部区域内，则四邻接点算法只能填充其左下部区域，而不能进入其右上部区域，如图4-35所示。八邻接点算法则可以从其左下部区域进入右上部区域，填充完整个多边形区域，如图4-36所示。

图4-35四邻接点种子填充八连通域图4-36八邻接点种子填充八连通域4.4.4种子填充算法1.算法定义从种子像素点开始，使用四邻接点方式搜索下一像素点的填充算法称为四邻接点种子填充算法。从种子像素点开始，使用八邻接点方式搜索下一像素点的填充算法称为八邻接点种子填充算法。2.算法原理种子填充算法一般需要使用堆栈数据结构来实现。算法原理为：先将种子像素入栈，种子像素为栈底像素，如果栈不为空，执行如下3步操作：（1）栈顶像素出栈；（2）按填充色绘制出栈像素。（3）按左、上、右、下（或左、左上、上、右上、右、右下、下、左下）顺序搜索与出栈像素相邻的4（或8）个像素，若该