基本图形生成算法.ppt

基本图形生成算法
第1页，共48页，编辑于2022年，星期三
实区域填充算法
确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内
解决的主要问题是什么？
图案填充还有一个什么象素填什么颜色的问题
曲线围成的4页，共48页，编辑于2022年，星期三
即算法中采用较灵活的数据结构。它由新边表ET（Edge Table）和活性边表AEL（Active Edge List）两部分组成。
表结构ET和AEL中的基本元素为多边形的边。边的结构由以下四个域组成：
x: 在ET中表示边的下端点的x坐标，在AEL中则表示边与扫描线的交点的坐标；
Δx:边的斜率的倒数；
ymax:边的上端点的y坐标；
next:指向下一条边的指针。
有序边表算法
第15页，共48页，编辑于2022年，星期三
y
x
0
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
5
6
7
8
P6
P4
P1
P5
P2
P3
新边表









∧
∧
∧
∧
∧
5
2
8
.
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=
2
0
7
.
8
3
3
∧
P6P1
P2P3
y=
2
0
7
.
11
0
8
∧
P6P1
P3P4
y=
5
2
8
.
P4P5
11
0
8
∧
P3P4
5
-
7
P5P6
2
0
7
.
P6P1
y=
7
2
8
.
P4P5
11
0
8
∧
P3P4

-
7
P5P6
2
0
7
.
P6P1
y=
9
2
8
.
P4P5
11
0
8
∧
P3P4
y=
2
0
7
.
11
0
8
∧
P6P1
P3P4
y=
第16页，共48页，编辑于2022年，星期三
step1：把新边表ET［i］中的边结点，用插入排序法
插入活性边表AET，使之按X坐标递增顺序排序；
step2：遍历AET表，把配对交点之间的区间(左闭右开)上的各 象素(X，Y)，用drawpixel(x,y,color)改写象素颜色值；
step3：遍历AET表，把Ymax=i的结点从AET表中删除，并把
Ymax＞i的结果点的X值递增△X；
step4：重复各扫描线
算法：(对每一条扫描线i)
第17页，共48页，编辑于2022年，星期三
有序边表算法
优点：
对每个像素只访问一次
与设备无关
缺点：
数据结构复杂
只适合软件实现
第18页，共48页，编辑于2022年，星期三
边填充算法
第19页，共48页，编辑于2022年，星期三
边填充算法
优点：
最适合于有帧缓存的显示器
可按任意顺序处理多边形的边
仅访问与该边有交点的扫描线上右方的像素，算法简单
缺点：
对复杂图形，每一像素可能被访问多次，输入/输出量大
图形输出不能与扫描同步进行，只有全部画完才能打印
第20页，共48页，编辑于2022年，星期三
栅栏填充算法
引入栅栏的目的？
第21页，共48页，编辑于2022年，星期三
种子填充算法
种子填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。种子填充算法要求区域是连通的
6
7
5
4
S
9
3
2
8
第22页，共48页，编辑于2022年，星期三
种子填充算法
假设多边形区域内至少有一个像素已知
区域定义法：
Interior-defined
Boundary-defined
Flood-fill algorithm
Boundary-fill algorithm
区域连通方式：
4-connected
8-connected
*
第23页，共48页，编辑于2022年，星期三