基本图形生成算法.ppt

基本图形生成算法
第一页，共48页
实区域填充算法
确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内
解决的主要问题是什么？
图案填充还有一个什么象素填什么颜色的问题
曲线围成的区域，可用多边形逼近
第二页，共48页
点在多边形内的包含性检验
检验夹角之和
射线法检验交点数
第三页，共48页
检验夹角之和
若夹角和为0，则点p在多边形外
若夹角和为360°，则点p在多边形内
A
B
C
D
E
P
A
B
C
D
E
P
第四页，共48页
射线法检验交点数
A
B
C
D
E
P
A
B
C
D
E
P
交点数=偶数（包括0）
点在多边形之外
交点数=奇数
点在多边形之内
z
x
左闭右开
第五页，共48页
包围盒法
凸多边形
凹多边形
逐点测试效率低不实用怎么办？
第六页，共48页
实区域填充算法分类
扫描线填充算法---扫描线顺序
有序边表算法
边填充算法
种子填充算法---内部一个点出发
简单种子算法
扫描线种子算法
第七页，共48页
扫描线填充算法
求交：I4, I3, I2, I1
排序：I1, I2, I3, I4
交点配对：(I1, I2), (I3, I4)
区间填色
利用图形的空间连贯性和扫描线的连贯性
第八页，共48页
填充扩大化问题
解决方法：
取中心扫描线y+
检查交点右方像素的中心是否落在区间内
xl≤x+≤xr
y
x
y
0
1
2
3
4
5
6
7
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
1
2
3
4
5
6
7
x
P
1
P
2
P
3
P
4
x
第九页，共48页
顶点交点的计数问题
5
4
3
2
1
0
P1
P2
P3
P4
I1
I2
I3
I4
P5
扫描线5
扫描线4
扫描线3
扫描线2
扫描线1
I5
I6
检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数
计数0次
计数1次
计数2次
*
第十页，共48页