文档介绍：第三章基本图形生成算法 实区域填充算法
计算机学院
苏小红
实区域填充算法
确定待填充的象素,即检查光栅的每一像素是否位于多边形区域内
解决的主要问题是什么?
图案填充还有一个什么象素填什么颜色的问题
曲线围成的区域,可用多边形逼近
点在多边形内的包含性检验
检验夹角之和
射线法检验交点数
检验夹角之和
若夹角和为0,则点p在多边形外
若夹角和为360°,则点p在多边形内
A
B
C
D
E
P
A
B
C
D
E
P
夹角如何计算?
大小:利用余弦定理
方向:令
当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
左闭右开
包围盒法
凸多边形
凹多边形
逐点测试效率低不实用怎么办?
实区域填充算法分类
扫描线填充算法
扫描线顺序
种子填充算法
内部一个点出发
扫描线填充算法
求交:I4, I3, I2, I1
排序:I1, I2, I3, I4
交点配对:(I1, I2), (I3, I4)
区间填色
利用图形的空间连贯性和扫描线的连贯性
填充扩大化问题
解决方法:
取中心扫描线y+
检查交点右方像素的中心是否落在区间内
xl≤x+≤xr