Computer Graphics 第四章 多边形填充

本章内容 4.1 实面积图形的概念 4.2 有效边表填充算法 4.3 边缘填充算法 4.4 区域填充算法

4.1　实面积图形的概念 实面积图形既能描述物体的几 何轮廓，又能表现物体的表面色彩， 与人们观察物体表面的习惯相一致， 同时，实面积图形也是描述三维物体、 绘制三维真实感图形的基础。

4.1.1 多边形的定义 多边形是由折线段组成的封闭图形。它由有序 顶点的点集Pi(i=0,1,…，n-1)及有向边Ei(i=0,…， n-1)定义，n为多边形的顶点数或边数，且 Ei=PiPi+1 ， i=0,…，n-1。 这里Pn=P0 ，用以保 证多边形的封闭性。

多边形上任意两顶点间的连线都在多边形之内，凸 点对应的内角小于180°,只具有凸点的多边形称为凸多 边形。 1 凸多边形 多边形上任意两顶点间的连线都在多边形之内，凸 点对应的内角小于180°,只具有凸点的多边形称为凸多 边形。 2 凹多边形 多边形上任意两顶点间的连线有不在多边形内部的 部分，凹点对应的内角大于180°,有一个凹点的多边形 称为凹多边形。 3 环 多边形内包含有另外的多边形。如果规定每条有向 边的左侧为其内部实面积区域，则当观察者沿着边界行 走时，内部区域总在其左侧，也就是说多边形外轮廓线 的环形方向为逆时针，内轮廓线的环形方向为顺时针。 这种定义了环形方向的多边形称为环。

4.1.2 多边形的表示 在计算机图形学中，多边形有两种示方法：顶点表示法和点阵表示法。 图 4-4 多边形的点阵表示法 P1 P0 P5 P2 P3 P4 图 4-3 多边形的顶点表示法 图 4-4 多边形的点阵表示法

⑴顶点表示法 多边形的顶点表示法是用多边形的顶点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换，顶点表示法如图4-3所示。 ⑵点阵表示法 多边形的点阵表示法是用多边形覆盖的像素点集来描述。 特点是便于直接确定实面积图形覆盖的像素点，是多边形填充所需要的表示形式，但是缺少了多边形顶点的几何信息，如图4-4所示。

⑶多边形的扫描转换 将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出多边形内部的各个像素点信息。

4.1.3 多边形的填充 这里的多边形是使用顶点表示法表示的多边形。 多边形的填充是指从多边形的顶点信息出发，求出 其覆盖的每个像素点，取为填充色，而将多边形外 部的像素点保留为背景色。多边形填充的主要工作 是确定穿越多边形内部的扫描线的覆盖区间。首先 确定多边形覆盖的扫描线条数(y=ymin~ymax),对每一 条扫描线，计算扫描线与多边形边界的交点区间 (xmin~xmax),然后再将该区间内的像素赋予指定的颜 色。在扫描线从多边形顶点的最小值ymin到多边形 顶点的最大值ymax移动的过程中，重复上述工作， 就可以完成多边形的填充。

4.1.4 区域填充 区域是指一组具有相同属性的像素，可以理 解为多边形的内部。区域的边界色和填充色不一 致，填充算法只对区域内部进行填充。种子填充 算法是从给定的种子位置开始，按填充颜色点亮 种子的相邻像素直到颜色不同的边界像素为止、 种子填充法主要有4邻接算法和8邻接算法。

4.2 有效边表填充算法 4.2.1 填充原理 4.2.2 边界像素的处理原则 4.2.3 有效边和有效边表 4.2.4 边表

4.2.1 填充原理 多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间内的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。

在图4-5中，多边形覆盖了12条扫描线。扫描线y＝3与多边形有4个交点（2. 3，3），(4 在图4-5中，多边形覆盖了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个像素点需要填充为指定颜色。 P1 P0 P6 P2 P4 P3 P5 图 4-5 用一条扫描线填充多边形

4.2.2 边界像素的处理原则 在实际填充过程中，需要考虑到边界像素影响问题： 图4-6中正方形P0P2P4P6被等分为四个小正方形。假定小正方形P0P1P8P7被填充为绿色，P1P2P3P8被填充为橙色，P8P3P4P5被填充为绿色，P7P8P5P6被填充为橙色。四个小正方形的公共边为：P1P8、P8P5、P7P8和P8P3。考虑到公共边P1P8既是正方形P0P1P8P7的右边界，又是正方形P1P2P3P8的左边界；考虑到P7P8既是是正方形P0P1P8P7的上边界，又是正方形P7P8P5P6的下边界，那么P1P8和P7P8应该填充为哪一个小正方形的颜色？同理，P8P5 和P8P3应该填充为哪一个小正方形的颜色？

P5 P5 P6 P6 P4 P4 P7 P8 P3 P7 P3 P8 P0 P2 P1 P2 P0 P1 图 4-7 边界像素的处理 图 4-6 边界像素的问题 在实际填充过程中，也需要考虑到像素面积大小的影响问题：对左下角为（1，1），右上角为（3，3）的正方形进行填充时，若边界上的所有像素全部填充，就得到图4-8所示的结果。所填像素覆盖的面积为3×3个单位，而正方形的面积实际只有2×2个单位。

图 4-8 面积3×3 图 4-9 面积2×2 为了保解决这些问题，在多边形填充过程中，常采用“下闭上开”和“左闭右开”的原则对边界像素进行处理。图4-6的处理结果如图4-7所示，每个小正方形的右边界像素和上边界像素都没有填充。图4-8的处理结果如图4-9所示，上面一行像素和右面一列像素没有填充。

按照以上原则对图4-5中的一些特殊点进行处理： 1.P2点的处理原则 图4-5中P2是边P3P2的终点，同时也是边P2P1的起点。按照“下闭上开”的原则，可以自动处理。 P1 P6 P0 P2 P4 P3 P5 图4-10 局部点的处理

2.P0、P3、P5点和P4点的处理原则 对局部最高点P4，根据“下闭上开”的原则，P4点不予填充，y＝5扫描线会自动填充P4点，如图4-10所示。 对局部最低点P0、P3和P5的处理方法为，填充时设置一个逻辑变量（初始值为假），每访问一个结点，逻辑变量值取反一次，若逻辑变量值为真，则填充该区间，这样可以保证局部最低点处理正确。

设多边形P的顶点为Pi=（xi,yi）,i=0,1,…，n-1, 这些顶点可以分为两类：极值点和非极值点。如 果(yi-1-yi)(yi+1-yi) ≥0，则称顶点Pi为极值点 （如P0、P3、P5和P4点）；否则称为非极值点（如 P2点）。 为使每一条扫描线与多边形P的边界的交点个数始 终为偶数，规定当点是多边形P的极值点时，该点 按两个交点计算，否则按一个交点计算。

对于每一条扫描线，多边形的填充步骤为： 计算扫描线与多边形各边的交点，设交点 个数为n。 把所有的交点按x值递增的顺序进行排列。 将排序后的第1个和第2个交点，第3个和第 4个交点，…，第n-1个和第n个交点配对， 每对交点就代表扫描线与多边形的一个相 交区间。 把相交区间内的像素置成多边形的颜色， 相交区间外的像素设置成背景色。

4.2.3 有效边和有效边表 1.有效边（Active Edge，AE） 多边形内与当前扫描线相交的边称为有效边。在处理一条扫描线时仅对有效边进行求交运算，可以避免与多边形的所有边求交，提高了算法效率。有效边上的扫描线由起点到终点每次加1，即像素点的y坐标为：y＝y+1，x坐标的变化可以按如下方法推导。

设有效边的斜率为k。假定有效边与当前扫描线yi的交点为（xi，yi），则有效边与下一条扫描线yi+1的交点为（xi+1，yi+1）。其中, xi+1= xi +1/k= xi +⊿x/⊿y， yi+1 = yi+1。如图4-11所示。这说明随着扫描线的移动，扫描线与有效边交点的x坐标从起点开始可以按增量1/k计算出来。 （xi+1，yi+1） 1/k （xi，yi） 图4-11 有效边交点相关性

2.有效边表（Active Edge Table，AET） 把有效边按照与扫描线交点x坐标递增的顺序存放在一个链表中，称为有效边表，有效边表的结点如下： x:当前扫描线与有效边的交点 ymax：边所在的扫描线最大值 1/k：斜率的倒数 Next：指向下一条边的指针

有效边表的数据结构： class CAET //有效边表类 { public: CAET(); //构造函数 virtual ~CAET(); //析构函数 double x; int yMax; double k; //程序中令k=⊿x/⊿y CAET *next; }

图 4-13 示例多边形 P1 P6 P0 P2 P4 P3 P5 对于图4-13所示的多边形，顶点表示法为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）, P4（6，5）, P5（8，1）, P6（12，9）。

扫描线的最大值为Smax＝12，最小值为Smin＝1，共有12条扫描线，每条扫描线之间间隔1个像素单位。每条扫描线的有效边表为如图4～18所示。

这条扫描线处理完毕后 对于P3、P4和P4、P5两条边，因为下一条扫描线S=5和ymax相等，根据“下闭上开”的原则予以删除。

这条扫描线处理完毕后 对于P2、P3边，因为下一条扫描线S=7和ymax相等，根据“下闭上开”的原则予以删除。当S＝7时，添加上新边P1、P2。

当S＝8时，添加上新边P0、P1和P0、P6。 这条扫描线处理完毕后 对于P5P6边和P0P6边，因为下一条扫描线S=9和ymax相等，根据“下闭上开”的原则予以删除。

S=11的扫描线处理完毕后 对于P1P2边和P0、P1边，因为下一条扫描线S=12和ymax相等，根据“下闭上开”的原则予以删除。至此，全部有效边表已经给出。

4.2.4 边表 从有效边表的建立过程可以看出，有效边表给出了扫描线和有效边交点坐标的计算方法，但是没有给出新边出现的位置坐标。为了确定在哪条扫描线上插入了新边，就需要构造一个边表（Edge Table，ET），用以存放扫描线上多边形各条边出现的信息。因为水平边的1/k为∞，并且水平边本身就是扫描线，在建立边表时可以不予考虑。

1.边表的表示法 (1)边表是按照扫描线顺序管理边的出现情况的一个数据结构。首先，构造一个纵向扫描线链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点称为桶，对应多边形覆盖的每一条扫描线。 将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就存放在相应的扫描线桶中。

对于每一条扫描线，如果新增多条边，则按x|ymin坐标递增的顺序存放在一个链表中，若x|ymin 相等，则按照1/k由小到大排序，这样就形成边表，如图4-14所示。 图 4-14 边表结点 其中，x为新增边低端的x|ymin值，用于判断边表在桶中的排序；ymax是该边所在的最大扫描线值，用于判断该边何时成为无效边。1/k是边在x方向的变化量和在y方向的变化量的比值，即△x/△y。从图4-14可以看出边表是有效边表的特例，即该边的最低点处的有效边表，有效边表和边表可以使用同一个数据结构来表示。

2.边表示例 对于图 4-13示例多边形。边表结构如图4-15所示。 图 4-15 边表