02-1 第二章 基本图形的生成与计算-区域填充算法.pptx

第1页：区域填充算法

计算机图形学讲义 第2章 基本图形的生成与计算—区域填充算法

第2页：本章主要内容

主要内容

1. 逐点判断填充算法
2. 种子填充算法
   • 2.1 深度递归的种子填充算法
   • 2.2 扫描线种子填充算法
3. 扫描线多边形填充算法

第3页：逐点判断填充算法

１. 逐点判断填充算法：区域填充的基本（初级）方法

• 逐点判断绘图窗口内的每一个像素；
• 若在区域的内部：用指定的属性设置该点；
• 否则不予处理。

设有如下函数：Inside(D, x, y) = True when x∈D；False when x∉D

第4页：逐点判断算法伪代码

取矩形 R（x1≤x≤x2，y1≤y≤y2），使 R 包围 D，则逐点判断填充算法如下：

for (y = y1; y <= y2; y++) for (x = x1; x <= x2; x++) if (inside(D, x, y)) drawpixel(x, y, color);

上述算法原理简单、实用，但效率低；原因是没有考虑各象素之间的联系，孤立地考察象素与区域的关系，几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算。

第5页：点在多边形内外的判断

如何判断点在多边形的内或外？即包含性检查。具体计算方法如何？图形求交中再仔细讲解。

第6页：种子填充算法

2. 种子填充算法

• 2.1 深度递归的种子填充算法
• 2.2 扫描线种子填充算法

种子填充算法假设在多边形内有一象素已知，由此出发利用连通性找到区域内的所有象素，并进行填充。

第7页：种子填色与边界填色

种子填色又称边界填色（Boundary Filling）。它的功能是，给出多边形光栅化后的边界位置及边界色代码 boundary_color，以及多边形内的一点 (x, y) 位置，要求将颜色 fill_color 填满多边形。

第8页：填充条件与连通方式

1. 填充条件

区域内一点的坐标即种子坐标、边界色、填充色。

2. 连通方式

区域是互相连通着的象素的集合，连通方式可分为四连通和八连通。

• 四连通：从区域内一点出发，可通过上、下、左、右四个方向到达该区域内部的任意象素。
• 八连通：除上、下、左、右四个方向外，还允许沿着对角线方向移动。

第9页：内点检测条件

3、内点 (x, y) 的检测条件

• (1) if (getpixel(x,y) != 边界色 && getpixel(x,y) != 填充色)
• (2) if (getpixel(x,y) == 背景色)

这两个条件任何一个都可以用来检测象素点 (x, y) 是不是尚未填充。推荐使用条件 (1) 进行象素点检测。

第10页：区域边界的连通性要求

注意：

• （1）八连通区域中，区域内的两个象素可以通过对角线相通，区域边界上的象素则不能通过对角线相连，否则填充会溢出到区域外，因此八连通区域的边界线必须是四连通的（图 a）。
• （2）四连通区域，其边界象素是四连通和八连通的都可以（图 b）。

(a) 八连通区域四连通边界　(b) 四连通区域八连通（或四连通）边界

第11页：深度递归种子填色算法

void seed_filling (x, y, fcolor, bcolor) int x, y, fcolor, bcolor; { int c; c = getpixel (x, y); if (c != fcolor && c != bcolor) { putpixel (x, y, fcolor); seed_filling (x+1, y, fcolor, bcolor); seed_filling (x-1, y, fcolor, bcolor); seed_filling (x, y+1, fcolor, bcolor); seed_filling (x, y-1, fcolor, bcolor); } }

第12页：深度递归算法的优缺点

• 种子填充的递归算法原理和程序都很简单，容易理解。
• 但由于多次递归，费时、费内存，效率不高。太大的区域会由于递归太深而不能运行。虽然也可利用栈非递归实现，但也有同样的问题。
• 可以考虑利用队列进行广度优先填色，但是也是逐点判断，而且要重复判断一个点很多次，效率也不高。
• 为了减少递归次数，提高效率可以采用扫描线种子算法。

第13页：扫描线种子填充算法

2.2 扫描线种子填充算法

算法的基本过程：当给定种子点 (x, y) 时，首先填充种子点所在扫描线上位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，确定新种子点，并依次保存下来。反复这个过程，直到填充结束。

对于每一个待填充区段，只需压栈一次；而在递归算法中，每个象素都需要压栈。因此扫描线填充算法提高了区域填充的效率。

第14页：扫描线种子填充的步骤

1. 初始化：堆栈置空。将种子点（x，y）入栈。
2. 出栈：若栈空则结束。否则取栈顶元素（x，y），以 y 作为当前扫描线。
3. 填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到非内部。分别标记区段的左、右端点坐标为 xl 和 xr。
4. 确定新的种子点：在区间 [xl，xr] 中检查与当前扫描线 y 上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。

第15页：扫描线种子填充动画演示

动画演示

第16页：扫描线种子填充算法特点

1. 该算法考虑了扫描线上象素的相关性，种子象素不再代表一个孤立的象素，而是代表一个尚未填充的区段。
2. 进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象素），这样解决了堆栈溢出的问题。
3. 种子出栈时，则填充整个区段。
4. 一边对尚未填充象素的登记（象素进栈），一边进行填充（象素出栈），既可以节省堆栈空间，又可以实施快速填充。

第17页：扫描线多边形填充算法

3. 扫描线多边形填充算法：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，填充过程分为四个步骤：

1. 求交：计算扫描线与多边形各边的交点；
2. 排序：把所有交点按 x 值递增顺序排序；
3. 配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间；
4. 填色：把相交区间内的象素置成多边形颜色。

第18页：

第19页：重合点与水平边的处理

• 重合点的处理：当扫描线和边界相交于左顶点或右顶点时，同时产生两个交点，通常采用“起闭终开”或“起开终闭”。
• 水平边处理：水平边不参加求交计算，跳过。

P1 P2 P3 P4 P5：[P1,p2) [P4，P5) [P2,p3) [P5,p1)

第20页：活性边表AET

把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点 x 坐标递增的顺序存放在一个链表中，称此链表为活性边表（AET）。活性边表的每个节点的内容：

1. 当前扫描线与边的交点坐标 x 值；
2. 从当前扫描线到下一条扫描线间 x 的增量 Dx；
3. 该边所交的最高扫描线号 ymax；
4. 指向下一条边的指针。

X　ΔX　Ymax

第21页：交点增量的连贯性计算

假定当前扫描线与多边形某一条边的交点的 x 坐标为 x，则下一条扫描线与该边的交点不必重算，只要加一个增量 △x（连贯性）。设该边的直线方程为：ax + by + c = 0；若 y＝yi，x = xi；则当 y = yi+1 时，xi+1 = xi - b/a，其中 ΔX = -b/a 为常数。

使用增量法计算时，需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表中删除。

第22页：相邻扫描线的活性边表

扫描线6的活性边表 AET

扫描线7的活性边表 AET

第23页：新边表NET

为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表（NET），存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为 ymin，则该边就放在扫描线 ymin 的新边表中。

第24页：扫描线多边形填充主要步骤

扫描线多边形填充算法的主要步骤

• 建立 NET（NewEdgeList）
• 从最低扫描线开始到最高扫描线循环：
  • 建立或调整 AET（ActiveEdgeList）；
  • 按照 AET 中的接点顺序填充。

第25页：polyfill程序实现

void polyfill (多边形 polygon, 颜色 color) { for (各条扫描线 i) { 初始化新边表头指针 NET[i]； 把 ymin = i 的边放进边表 NET[i]; } y = 最低扫描线号； 初始化活性边表 AET 为空； for (各条扫描线 i) { 把新边表 NET[i] 中的边结点用插入排序法插入 AET 表，使之按 x 坐标递增顺序排列； 遍历 AET 表，把 ymax = i 的结点从 AET 表中删除，并把 ymax > i 结点的 x 值递增 Dx； 若允许多边形的边自相交，则用冒泡排序法对 AET 表重新排序； 遍历 AET 表，把配对交点区间（左闭右开）上的象素 (x, y)，用 drawpixel (x, y, color) 改写象素颜色值； } }

第26页：扫描线多边形填充动画演示

动画演示

第27页：扫描线多边形填充算法特点

• 该算法充分利用多边形的边相关性和扫描线的相关性，使用 ET 表对多边形的非水平边进行登记；
• 用 AET 表的建立和更新来支持填充，大大地减少了求交点的计算量，有效地提高了填充速度。

第28页：本章作业

作业

1. 当用深度递归的种子填色算法并选用编号为6的点作为种子填充如图所示区域时，写出区域内被填色的点先后顺序。其中采用四连通算法，填色顺序为右左上下。
2. 已知有一个5边形如下。建立新边表 NET，并写出每一条扫描线经过时活性边表 AET 中的数据状态。