第三章 基本图形生成算法
实区域填充算法
计算机学院
苏小红
实区域填充算法
确定待填充的象素，即检查光栅的每一像素是
否位于多边形区域内
解决的主要问题是什么？
图案填充还有一个什么象素填什么颜色的问题
曲线围成的区域，可用多边形逼近
点在多边形内的包含性检验
检验夹角之和
射线法检验交点数
检验夹角之和
若夹角和为 0，则点 p在多边形外 若夹角和为 360°,则点 p在多边形内
A
B
C
D
E
P
A
B
C
D
E
P
夹角如何计算？
大小：利用余弦定理
方向：令
))(())(( PAPBPBPA
PBPB
PAPA zzxxzzxx
zzxx
zzxxT ??????
??
???
当 T<0时,AP斜率 >BP斜率，为顺时针角 当 T>0时,AP斜率 <BP斜率，为逆时针角
z
x
A
B
P
z
x
B
A
P
射线法检验交点数
A
B
C
D
E
P
A
B
C
D
E
P
交点数 =偶数（包括 0）
点在多边形之外
交点数 =奇数
点在多边形之内
z
x
左闭右开
包围盒法
凸多边形 凹多边形
逐点测试效率低不实用怎么办？
实区域填充算法分类
扫描线填充算法
? 扫描线顺序
种子填充算法
? 内部一个点出发
扫描线填充算法
0 1 2 3 4 5 6 7
1
2
3
4
5
6
7
y
x
8
8 9 10
扫描线5
P 4
P 1 P 2
P 3
P 5
扫描线2
I 1 I 2 I 3 I 4
求交,I4,I3,I2,I1
排序,I1,I2,I3,I4
交点配对,(I1,I2),(I3,I4)
区间填色
利用图形的空间连贯性
和扫描线的连贯性
填充扩大化问题
解决方法：
? 取中心扫描线 y+0.5
? 检查交点右方像素的中心是否落在区间内
xl≤ x+0.5≤ xr
0 1 2 3 4 5 6 7
1
2
3
4
5
6
7
y
x0 1 2 3 4 5 6 7
1
2
3
4
5
6
7
y
x
P 1 P 2
P 3P 4
0 1 2 3 4 5 6 7
1
2
3
4
5
6
7
y
x0 1 2 3 4 5 6 7
1
2
3
4
5
6
7
y
x
P 1 P 2
P 3P 4
112011-3-30
顶点交点的计数问题
5
4
3
2
1
0 P
1 P2
P3
P4
I1 I2 I3
I4
P5
扫描线 5
扫描线 4
扫描线 3
扫描线 2
扫描线 1
I5
I6
检查交于该顶点的两条边的另外两个端点
的 y值大于该顶点 y值的个数
计数 0次
计数 1次
计数 2次
有序边表算法
影响一般扫描线填充算法效率的因素？
把多边形所有边放在一个表中，按顺序取出，
分别计算与每条扫描线的交点？
如何提高效率？
建立每条扫描线的活性边表
何谓活性边？
求交和排序
目标是简化交点计算
有序边表算法
活性边表的建立
结点信息
x：当前扫描线与边的交点
△ x：从当前扫描线到下一条扫描线之间的 x增量
ymax：边所交的最高扫描线号
活性边表的更新
新边插入
旧边删除
△ x =1/k
有序边表算法
对每条扫描线建立一个新边表
结点信息
x0：扫描线与边的初始交点
△ x：从当前扫描线到下一条扫描线之间的 x增量
ymax：边所交的最高扫描线号
边结点不必排序
y
x0 1 2 3 4 5 6 7 8 9 10111
2
3
4
5
67
8 P6 P4
P2
P5
P2
P3
新
边
表
8.5
7.5
6.5
5.5
4.5
3.5
2.5
1.5
0.5
∧
∧
∧
∧
∧
5 2 8, 5 -1.5 7 ∧
11 0 8 ∧
2 0 7 ∧
5 -3 2, 5 3 3 ∧
P4P5 P5P6
P3P4
P6P1
P1P2 P2P3活性边表
5 -3 2, 5 3 3 ∧
P1P2 P2P3
y=1.5
2 0 7, 8 3 3 ∧
P6P1 P2P3
y=2.5
2 0 7, 11 0 8 ∧
P6P1 P3P4
y=3.5
5 2 8,
P4P5
11 0 8 ∧
P3P4
5 -1.5 7
P5P6
2 0 7,
P6P1
y=5.5
7 2 8,
P4P5
11 0 8 ∧
P3P4
3.5 -1.5 7
P5P6
2 0 7,
P6P1
y=6.5
5 2 8,
P4P5
11 0 8 ∧
P3P4
y=7.5
step1：把新边表 NET［ i］中的边结点，用插入排序法
插入活性边表 AET，使之按 X坐标递增顺序排序；
step2：遍历 AET表，把配对交点之间的区间 (左闭右开 )上的各象
素 (X,Y)，用 drawpixel(x,y,color)改写象素颜色值；
step3：遍历 AET表，把 Ymax=i的结点从 AET表中删除，并把
Ymax＞ i的结果点的 X值递增 △ X；
step4：重复各扫描线
?算法,(对每一条扫描线 i)
有序边表算法
优点：
? 对每个像素只访问一次
? 与设备无关
缺点：
? 数据结构复杂
? 只适合软件实现
边填充算法
(Edge Fill Algorithm) P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
(a) (b) (c)
(d) (e)
边填充算法
(Edge Fill Algorithm)
优点：
? 最适合于有帧缓存的显示器
? 可按任意顺序处理多边形的边
? 仅访问与该边有交点的扫描线上右方的像素，
算法简单
缺点：
? 对复杂图形，每一像素可能被访问多次，输
入 /输出量大
? 图形输出不能与扫描同步进行，只有全部画
完才能打印
栅栏填充算法
(Fence Fill Algorithm)
引入栅栏的目的？
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
(a) (b) (c)
(d) (e)
P 4
栅栏线
212011-3-30
种子填充算法
假设多边形区域内至少有一个像素已知
区域定义法：
? Interior-defined
? Boundary-
defined
Flood-fill algorithm
Boundary-fill algorithm
区域连通方式：
? 4-connected
? 8-connected
区域连通方式对填充结果的影响
4连通区域边界填
充算法的填充结果
8连通区域边界填
充算法的填充结果
简单的种子填充算法
（ 4连通边界）
种子像素入栈
当栈非空时，重复以下步骤：
? 栈顶像素出栈
? 将出栈象素置成填充色
? 按左、上、右、下顺序检查与出栈象素相邻的
四象素，若其中某象素不在边界上且未被置成
填充色，则将其入栈
填充算法演示
6 7
5 4 S 9
3 2 8
S
2
4
7
9
3
8
4
7
9
4
8
4
7
9
5
6
8
4
7
9
6
8
4
7
9
7
8
4
7
9
8
4
7
9
9
4
7
9
4
7
9
S
7
9 9
缺点？
4-connected boundary-fill
void BoundaryFill4(int x,int y,int fill,int
boundary)
{
int current;
current = getpixel(x,y);
if ((current != boundary) && (current != fill))
{
putpixel(x,y,fill);
BoundaryFill4(x+1,y,fill,boundary);
BoundaryFill4(x-1,y,fill,boundary);
BoundaryFill4(x,y+1,fill,boundary);
BoundaryFill4(x,y-1,fill,boundary);
}
}
4-connected boundary-fill
void FloodFill4(int x,int y,int fillColor,int
oldColor)
{
int current;
current = getpixel(x,y);
if (current == oldColor)
{
putpixel(x,y,fillColor);
BoundaryFill4(x+1,y,fillColor,oldColor);
BoundaryFill4(x-1,y,fillColor,oldColor);
BoundaryFill4(x,y+1,fillColor,oldColor);
BoundaryFill4(x,y-1,fillColor,oldColor);
}
}
扫描线种子填充算法
利用扫描线的连贯性
减少递归次数
扫描线种子填充算法
种子像素入栈
当栈非空时，重复以下步骤：
? 栈顶像素出栈
? 沿扫描线对出栈像素的左右像素进行填充，
直到遇到边界像素为止
? 将上述区间内最左、最右像素记为 xl和 xr
? 在区间 [xl,xr]中 检查与当前扫描线相邻的上
下两条扫描线 是否全为边界像素、或已填充
的像素，若为非边界、未填充的像素，则 把
每一区间的最右像素取为种子像素入栈
二维光栅图形的混淆与反混淆
混淆现象
反混淆方法
混淆 (antialiasing)
图形的锯齿状：图形信号连续，光栅显示系统中，离散
表示。
用离散量 (像素 )表示连续的量 (图形 )而引起的失真，叫
混淆或叫 走样 (aliasing)
光栅图形混淆：
阶梯状边界；
图形细节失真；
狭小图形遗失：动画序列中时隐时现，产生闪烁。
图形反走样技术（ antialiasing）
1.从硬件角度提高分辨率
? 高分辨率显示器
显示器点距减少一倍
帧缓存容量增加到原来的 4倍
输带宽提高 4倍
扫描转换花 4倍时间
代价高
图形反走样技术（ antialiasing）
2.从软件角度替高分辨率
? 高分辨率计算，低分辨率显示
? 像素细分技术，相当于后置滤波
1
1
1
1
算术
平均
1 2
2
1
4
2
1
2
1
加权
平均
只能减轻，不能消除
322011-3-30
图形反走样技术（ antialiasing）
3.区域采样技术
? 改变边或直线的外观，模糊淡化阶梯
? 相当于图像的前置滤波
点 有限
区域
直线有宽度
332011-3-30
图形反走样技术（ antialiasing）
8级灰度
0≤ 面积 ≤1/8 7/8≤ 面积 ≤1
根据相交的面积值决定像素显示的亮度级别
实区域填充算法
计算机学院
苏小红
实区域填充算法
确定待填充的象素，即检查光栅的每一像素是
否位于多边形区域内
解决的主要问题是什么？
图案填充还有一个什么象素填什么颜色的问题
曲线围成的区域，可用多边形逼近
点在多边形内的包含性检验
检验夹角之和
射线法检验交点数
检验夹角之和
若夹角和为 0，则点 p在多边形外 若夹角和为 360°,则点 p在多边形内
A
B
C
D
E
P
A
B
C
D
E
P
夹角如何计算？
大小：利用余弦定理
方向：令
))(())(( PAPBPBPA
PBPB
PAPA zzxxzzxx
zzxx
zzxxT ??????
??
???
当 T<0时,AP斜率 >BP斜率，为顺时针角 当 T>0时,AP斜率 <BP斜率，为逆时针角
z
x
A
B
P
z
x
B
A
P
射线法检验交点数
A
B
C
D
E
P
A
B
C
D
E
P
交点数 =偶数（包括 0）
点在多边形之外
交点数 =奇数
点在多边形之内
z
x
左闭右开
包围盒法
凸多边形 凹多边形
逐点测试效率低不实用怎么办？
实区域填充算法分类
扫描线填充算法
? 扫描线顺序
种子填充算法
? 内部一个点出发
扫描线填充算法
0 1 2 3 4 5 6 7
1
2
3
4
5
6
7
y
x
8
8 9 10
扫描线5
P 4
P 1 P 2
P 3
P 5
扫描线2
I 1 I 2 I 3 I 4
求交,I4,I3,I2,I1
排序,I1,I2,I3,I4
交点配对,(I1,I2),(I3,I4)
区间填色
利用图形的空间连贯性
和扫描线的连贯性
填充扩大化问题
解决方法：
? 取中心扫描线 y+0.5
? 检查交点右方像素的中心是否落在区间内
xl≤ x+0.5≤ xr
0 1 2 3 4 5 6 7
1
2
3
4
5
6
7
y
x0 1 2 3 4 5 6 7
1
2
3
4
5
6
7
y
x
P 1 P 2
P 3P 4
0 1 2 3 4 5 6 7
1
2
3
4
5
6
7
y
x0 1 2 3 4 5 6 7
1
2
3
4
5
6
7
y
x
P 1 P 2
P 3P 4
112011-3-30
顶点交点的计数问题
5
4
3
2
1
0 P
1 P2
P3
P4
I1 I2 I3
I4
P5
扫描线 5
扫描线 4
扫描线 3
扫描线 2
扫描线 1
I5
I6
检查交于该顶点的两条边的另外两个端点
的 y值大于该顶点 y值的个数
计数 0次
计数 1次
计数 2次
有序边表算法
影响一般扫描线填充算法效率的因素？
把多边形所有边放在一个表中，按顺序取出，
分别计算与每条扫描线的交点？
如何提高效率？
建立每条扫描线的活性边表
何谓活性边？
求交和排序
目标是简化交点计算
有序边表算法
活性边表的建立
结点信息
x：当前扫描线与边的交点
△ x：从当前扫描线到下一条扫描线之间的 x增量
ymax：边所交的最高扫描线号
活性边表的更新
新边插入
旧边删除
△ x =1/k
有序边表算法
对每条扫描线建立一个新边表
结点信息
x0：扫描线与边的初始交点
△ x：从当前扫描线到下一条扫描线之间的 x增量
ymax：边所交的最高扫描线号
边结点不必排序
y
x0 1 2 3 4 5 6 7 8 9 10111
2
3
4
5
67
8 P6 P4
P2
P5
P2
P3
新
边
表
8.5
7.5
6.5
5.5
4.5
3.5
2.5
1.5
0.5
∧
∧
∧
∧
∧
5 2 8, 5 -1.5 7 ∧
11 0 8 ∧
2 0 7 ∧
5 -3 2, 5 3 3 ∧
P4P5 P5P6
P3P4
P6P1
P1P2 P2P3活性边表
5 -3 2, 5 3 3 ∧
P1P2 P2P3
y=1.5
2 0 7, 8 3 3 ∧
P6P1 P2P3
y=2.5
2 0 7, 11 0 8 ∧
P6P1 P3P4
y=3.5
5 2 8,
P4P5
11 0 8 ∧
P3P4
5 -1.5 7
P5P6
2 0 7,
P6P1
y=5.5
7 2 8,
P4P5
11 0 8 ∧
P3P4
3.5 -1.5 7
P5P6
2 0 7,
P6P1
y=6.5
5 2 8,
P4P5
11 0 8 ∧
P3P4
y=7.5
step1：把新边表 NET［ i］中的边结点，用插入排序法
插入活性边表 AET，使之按 X坐标递增顺序排序；
step2：遍历 AET表，把配对交点之间的区间 (左闭右开 )上的各象
素 (X,Y)，用 drawpixel(x,y,color)改写象素颜色值；
step3：遍历 AET表，把 Ymax=i的结点从 AET表中删除，并把
Ymax＞ i的结果点的 X值递增 △ X；
step4：重复各扫描线
?算法,(对每一条扫描线 i)
有序边表算法
优点：
? 对每个像素只访问一次
? 与设备无关
缺点：
? 数据结构复杂
? 只适合软件实现
边填充算法
(Edge Fill Algorithm) P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
(a) (b) (c)
(d) (e)
边填充算法
(Edge Fill Algorithm)
优点：
? 最适合于有帧缓存的显示器
? 可按任意顺序处理多边形的边
? 仅访问与该边有交点的扫描线上右方的像素，
算法简单
缺点：
? 对复杂图形，每一像素可能被访问多次，输
入 /输出量大
? 图形输出不能与扫描同步进行，只有全部画
完才能打印
栅栏填充算法
(Fence Fill Algorithm)
引入栅栏的目的？
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
P 5
P 1 P 2
P 3
P 4
(a) (b) (c)
(d) (e)
P 4
栅栏线
212011-3-30
种子填充算法
假设多边形区域内至少有一个像素已知
区域定义法：
? Interior-defined
? Boundary-
defined
Flood-fill algorithm
Boundary-fill algorithm
区域连通方式：
? 4-connected
? 8-connected
区域连通方式对填充结果的影响
4连通区域边界填
充算法的填充结果
8连通区域边界填
充算法的填充结果
简单的种子填充算法
（ 4连通边界）
种子像素入栈
当栈非空时，重复以下步骤：
? 栈顶像素出栈
? 将出栈象素置成填充色
? 按左、上、右、下顺序检查与出栈象素相邻的
四象素，若其中某象素不在边界上且未被置成
填充色，则将其入栈
填充算法演示
6 7
5 4 S 9
3 2 8
S
2
4
7
9
3
8
4
7
9
4
8
4
7
9
5
6
8
4
7
9
6
8
4
7
9
7
8
4
7
9
8
4
7
9
9
4
7
9
4
7
9
S
7
9 9
缺点？
4-connected boundary-fill
void BoundaryFill4(int x,int y,int fill,int
boundary)
{
int current;
current = getpixel(x,y);
if ((current != boundary) && (current != fill))
{
putpixel(x,y,fill);
BoundaryFill4(x+1,y,fill,boundary);
BoundaryFill4(x-1,y,fill,boundary);
BoundaryFill4(x,y+1,fill,boundary);
BoundaryFill4(x,y-1,fill,boundary);
}
}
4-connected boundary-fill
void FloodFill4(int x,int y,int fillColor,int
oldColor)
{
int current;
current = getpixel(x,y);
if (current == oldColor)
{
putpixel(x,y,fillColor);
BoundaryFill4(x+1,y,fillColor,oldColor);
BoundaryFill4(x-1,y,fillColor,oldColor);
BoundaryFill4(x,y+1,fillColor,oldColor);
BoundaryFill4(x,y-1,fillColor,oldColor);
}
}
扫描线种子填充算法
利用扫描线的连贯性
减少递归次数
扫描线种子填充算法
种子像素入栈
当栈非空时，重复以下步骤：
? 栈顶像素出栈
? 沿扫描线对出栈像素的左右像素进行填充，
直到遇到边界像素为止
? 将上述区间内最左、最右像素记为 xl和 xr
? 在区间 [xl,xr]中 检查与当前扫描线相邻的上
下两条扫描线 是否全为边界像素、或已填充
的像素，若为非边界、未填充的像素，则 把
每一区间的最右像素取为种子像素入栈
二维光栅图形的混淆与反混淆
混淆现象
反混淆方法
混淆 (antialiasing)
图形的锯齿状：图形信号连续，光栅显示系统中，离散
表示。
用离散量 (像素 )表示连续的量 (图形 )而引起的失真，叫
混淆或叫 走样 (aliasing)
光栅图形混淆：
阶梯状边界；
图形细节失真；
狭小图形遗失：动画序列中时隐时现，产生闪烁。
图形反走样技术（ antialiasing）
1.从硬件角度提高分辨率
? 高分辨率显示器
显示器点距减少一倍
帧缓存容量增加到原来的 4倍
输带宽提高 4倍
扫描转换花 4倍时间
代价高
图形反走样技术（ antialiasing）
2.从软件角度替高分辨率
? 高分辨率计算，低分辨率显示
? 像素细分技术，相当于后置滤波
1
1
1
1
算术
平均
1 2
2
1
4
2
1
2
1
加权
平均
只能减轻，不能消除
322011-3-30
图形反走样技术（ antialiasing）
3.区域采样技术
? 改变边或直线的外观，模糊淡化阶梯
? 相当于图像的前置滤波
点 有限
区域
直线有宽度
332011-3-30
图形反走样技术（ antialiasing）
8级灰度
0≤ 面积 ≤1/8 7/8≤ 面积 ≤1
根据相交的面积值决定像素显示的亮度级别
