多边形填充 计算机科学与技术系

多边形的扫描转换的目的 使图形表现更为直观、生动 使图形表现更为明暗自然、色彩丰富、真实感

多边形的定义 多边形是由折线段组成的封闭图形。 它由有序顶点的点集Pi（i＝0，…，n-1）及有向边的线集Ei（i＝0，…，n-1）定义，n为多边形的顶点数或边数，且Ei＝PiPi+1，i＝0，…，n-1。这里Pn＝P0，保证了多边形的闭合。 P0 P1 P2 P3 P4 P5 E0 E1 E2 E3 E4 E5

多边形的定义 多边形可以分为凸、凹多边形以及环。 凸多边形：多边形上任意两点连线在多边形边上或在其内部。 凹多边形：多边形上任意两点连线有不在多边形其内部的部分。凹点对应的内角大于180°，至少有一个凹点的多边形为凹多边形。 环：多边形内部包含另外的多边形边。如规定每条有向边的左侧为内部区域，则观察者沿边界行走，多边形的外轮廓为逆时针，内轮廓为顺时针。这样有环行方向的多边形称为环。 逆时针 顺时针

多边形的表示方法 有两种重要的表示方法 顶点表示:是用多边形的顶点的序列来描述多边形 优点：表示几何意义强、占内存少 缺点：不能直观地说明哪些像素在多边形内 所以不能直接填充，需要进行扫描转换后填充 多边形顶点表示 点阵表示:是用位于多边形内的象素的集合来描述多边形 优点：便于运用帧缓存来表示图形，直接读取像素来改变多边形的颜色 缺点：没有多边形的几何信息 多边形点阵表示

多边形着色模式 多边形可以使用两种方式填充： 平面着色模式（flat shading mode） 指多边形所有顶点的颜色都相同，多边形内部具有同顶点一样的颜色。 光滑着色模式（smooth shading mode） 指多边形各个顶点的颜色不同，多边形边的颜色是由这条边的两个顶点的颜色插值得到，多边形内部的颜色是由扫描线上共享同一顶点的相邻两条边上的颜色插值得到。

多边形着色模式 马赫带（Mach Band）是由灰度接近的矩形块组成。在观察明暗变化的边界时，边界处亮度对比度加强，常常在光强阶梯变化的一侧感知到亮度的正向尖峰效果，而在另一侧感知到亮度的负向尖峰效果，使得边界表现得非常明显，这种现象称为马赫带效应。马赫带效应不是一种物理现象，而使一种心理现象，夸大了平面着色的渲染效果，使得人眼感觉到的亮度变化比实际的亮度变化要大。绘制真实感图形的过程中应尽量避免出现马赫带效应。 感知光强 实际光强

多边形填充 多边形填充就是检查光栅上的每个像素点是否位于多边形内。 1.填充多边形 多边形的扫描转换是将多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。 2.填充区域 只对区域内部进行填充，区域内的所有像素着同一填充色，区域的边界着不同的颜色。

多边形的扫描转换算法 扫描转换填充算法- 利用扫描线的特点，计算多边形区域内的像素 扫描线算法 简单边填充算法 栅栏填充算法 边界标志算法

扫描转换填充算法-基本思想 求交：按扫描线顺序，计算扫描线与多边形各边的交点； 排序：将扫描线上交点按递增顺序排序； 配对：交点之间两两配对，构成一个交点相交区间； 着色：将这些区间的像素置为填充色。

像素编址和物体的几何表示 物体描述为一系列几何点，而屏幕像素有一定面积。因此要进行数学描述到有限区域的映射。 屏幕网格坐标的规定: 定义由像素边界线组成屏幕网格，左下角的整数网格坐标用来指定像素位置。 1 2 3 4 5 6 7 (3,3) 优点： － 避免半整数像素边界 －实现精确对象描述 －简化扫描转换和其它光柵程序的处理

边界像素的处理 填充扩大化问题 红色区域的四个顶点坐标： (3,2) -> (6,2) -> (6,5) -> (3,5) 4个3X3区域

边界像素的处理原则 左闭右开 下闭上开 原则： 屏幕坐标顶点在(0,0),(4,0),(4,3),(0,3)的矩型 20 21 22 23 24 25 26 27 28 29 10 14 13 12 11 17 16 15 端点坐标为(20,10)和(28,16)的线段 3 2 1 4 5 3 2 1 4 屏幕坐标顶点在(0,0),(4,0),(4,3),(0,3)的矩型 14 6 7 8 9 10 11 13 12 15 5 16 (10,10) 16 14 6 7 8 9 10 11 13 12 15 5 (10,10) 圆： (x-10)2+(y-10)2 = 52 原则： 左闭右开 下闭上开

扫描转换填充算法-重交点的取舍问题 扫描线与多边形的顶点或边界相交时，必须正确的交点的取舍。只需检查顶点的两条边的另外两个端点的y值。按“上开下闭，左闭右开”原则,将交点的个数是0,1,2. 0个交点 1个交点 2个交点 重合则计数为1，如右图p3p4

扫描线填充的步骤 对于一条扫描线填充过程可以分为四个步骤： （1）求交点，舍去重点 （2）排序，按x值由小到大 （3）配对，两两配对 （4）填色，配对区间添色 所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。 问题： 大量求交点计算，影响算法效率。

扫描线填充算法效率的考虑 如何算法提高效率？ 区域的连续性 扫描线的连续性 边的连续性 充分利用了相邻象素之间的连续性，避免对象素的逐点判断和反复求交运算，减少了计算量，提高了算法速度。

只需计算多边形边界与扫描线的交点,就可确定扫描线在多边形内外的区间 扫描转换填充算法-扫描线的连续性 一条扫描线与多边形相交，得到交点序列，且以x坐标值递增。 交点具有下列性质： 交点的个数为偶数； 交点对构成数个区间，一部分区间在多边形内，而一部分在多边形外，各区间相间排列； 这样的性质称为扫描线的连续性。 只需计算多边形边界与扫描线的交点,就可确定扫描线在多边形内外的区间

扫描转换填充算法-边的连续性 相邻两条扫描线与多边形相交，分别得到两组交点序列。 若两组交点序列的个数相同，且 Xi+1 = Xi + 1/k，k为直线的斜率。 则此性质为边的连续性。

扫描转换填充算法 目标是简化交点计算 根据扫描线和边的连续性，通过增量法 增量如何获得？ 确立每条扫描线的有效边(AE- Active Edge) ，（多边形与扫描线相交的边称为有效边） 有效边表（AET）是什么？ 一种数据结构，即链表，按照顺序记录所有的有效边（AE）。 3 7 -1/3 5 3/4

有效边表（AET） 有效边表 与当前扫描线相交的边称为有效边（active edge)。 有效边表：记录了多边形边与扫描线的交点序列，序列是以x坐标递增的顺序的。 有效边结点表 x ymax 1/k next 0 1 2 3 4 5 6 7 8 9 10 11 12 13 13 12 11 10 9 8 7 6 5 4 3 2 1 P0 P1 P2 P3 P4 P5 P6 x：当前扫描线与边的交点坐标 △x=1/k：从当前扫描线到下一条扫描线间x的增量 ymax：该边所交的最高扫描线号ymax next:指向下一条边的指针。

简化交点的计算—计算下一条扫描线与边的交点 假定当前扫描线与多边形某一条边的交点的x坐标为x，则下 一条扫描线与该边的交点不要计算，只要加一个增量△x。 设多边形某一边的直线方程为：ax+by+c=0； 若y＝yi，x=x i；则当y = y i+1时， 其中 为常数, 相当于直线的斜率k的倒数 y=yi+1 y=yi Pj Pj+1 (xi,yi) (xi+1,yi+1)

建立有效边表 例:扫描线1 有效边结点表 P0 P1 P2 P3 P4 P5 P6 x ymax 1/k next 3 7 -1/3 8 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 13 12 11 10 9 8 7 6 5 4 3 2 1 P0 P1 P2 P3 P4 P5 P6 例:扫描线1 有效边结点表 x ymax 1/k next 3 7 -1/3 8 5 -1/2 3/4 9 1/2 P2P3 P3P4 P4P5 P5P6

下闭上开 P0 P1 P2 P3 P4 P5 P6 3 7 -1/3 8 5 -1/2 3/4 9 1/2 1 8/3 7 -1/3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 13 12 11 10 9 8 7 6 5 4 3 2 1 P0 P1 P2 P3 P4 P5 P6 3 7 -1/3 8 5 -1/2 3/4 9 1/2 1 8/3 7 -1/3 15/2 5 -1/2 15/4 3/4 17/2 9 1/2 2 5/3 7 -1/3 10 9 1/2 5 P2P3 P5P6 下闭上开

扫描线算法 新边表 有效边表的更新 新边插入、旧边删除 为了方便有效边表的更新，建立另一个表——新边表（ET），即桶表，存放在该扫描线第一次出现的边。 新边表存放的信息： x：扫描线与该边的初始交点 △x：x的增量，即1/k ymax：该边的最大y值

新边表(桶表)建立 构造一个纵向扫描链表,链表的长度为多边形所占的最大扫描线数，存放在该扫描线第一次出现的边。 P0 P1 P2 P3 P4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 13 12 11 10 9 8 7 6 5 4 3 2 1 P0 P1 P2 P3 P4 P5 P6 构造一个纵向扫描链表,链表的长度为多边形所占的最大扫描线数，存放在该扫描线第一次出现的边。 x/ymin ymax 1/k 11 10 9 8 7 6 5 4 3 2 1 12 -1/3 3/4 -1/2 1/2 2/5 -1 P0P1 P6P0 P1P2 P2P3 P3P4 P4P5 P5P6

算法总结 扫描线与多边形的顶点相交： 计算交点个数时，仅对边的ymin顶点计数，其ymax顶点不计。 边界象素的取舍： 左端点填充，右端点不填充 下端点填充，上端点不填充 水平边不考虑交点 增量法取代求交点－效率优化

算法伪码 { int color; 多边形 polygon; void polyfill (polygon, color) class CAET { public: CAET(); ~CAET(); double x; int ymax; CAET* next; }; void polyfill (polygon, color) { int color; 多边形 polygon; for (各条扫描线i ) { 初始化新边表头指针ET [i]； 把y min = i 的边放进新边表ET [i]; } y = 最低扫描线号； 初始化活性边表AET为空；

算法过程(续) for (各条扫描线i ){ 把新边表ET [i] 中的边结点用插入排序法插 入AET表，使之按x坐标递增顺序排列； 的象素(x, y)，用setpixel (x, y, color) 改写象 素颜色值； 遍历AET表，把y max= i 的结点从AET表中删 除，并把y max > i 结点的x值递增x； 若允许多边形的边自相交，则用冒泡排序法 对AET表重新排序；} //结束j扫描线 } /* polyfill */

扫描线算法的优缺点 优点： 对每个像素只访问一次 与设备无关 缺点： 数据结构复杂 只适合软件实现

简单边缘填充算法 每边与扫描线交点右方的所有像素取“补”, 多边形边的顺序可任意。

简单边缘填充算法 最适合于有帧缓存的显示器 可按任意顺序处理多边形的边 优点： 最适合于有帧缓存的显示器 可按任意顺序处理多边形的边 仅访问与该边有交点的扫描线上右方的像素，算法简单，实现容易。既不需要求交点、交点排序、边的登记，也不需要使用链表、堆栈等数据结构。 缺点： 对复杂图形，每一像素可能被访问多次，输入/输出量大 图形输出不能与扫描同步进行，只有全部画完才能打印 改进办法:通过多边形设一栅栏，每次只对交点与栅栏之间的象素点取补，可使访问象素的次数减少。

栅栏填充算法 栅栏：与扫描线垂直的直线，通常过多边形顶点，且将多边形分成两半 方法：对每个扫描线与多边形的交点，将交点与栅栏间的像素取 “补” 引入栅栏的目的: 减少了被重复访问的像素，特别是有多个填充对象时，效果显著,但不彻底