哈尔滨工业大学计算机科学与技术学院：《计算机图形学》第3章 基本图形生成算法（二）（苏小红）

实区域填充算法 计算机学院 苏小红

第三章 基本图形生成算法 实区域填充算法 计算机学院 苏小红

实区域填充算法 解决的主要问题是什么? 确定待填充的象素,即检查光栅的每一像素是 否位于多边形区域内 图案填充还有一个什么象素填什么颜色的问题 曲线围成的区域,可用多边形逼近

实区域填充算法 确定待填充的象素，即检查光栅的每一像素是 否位于多边形区域内 解决的主要问题是什么？ 图案填充还有一个什么象素填什么颜色的问题 曲线围成的区域，可用多边形逼近

点在多边形内的包含性检验 检验夹角之和 射线法检验交点数

点在多边形内的包含性检验 检验夹角之和 射线法检验交点数

检验夹角之和 若夹角和为0,则点p在多边形外若夹角和为360°,则点p在多边形内

检验夹角之和 若夹角和为0，则点p在多边形外 若夹角和为360°，则点p在多边形内 A B C D E P A B C D E P

夹角如何计算? 大小:利用余弦定理 方向:令 T P A (xA-xp(eB-p(xB-xp(z B P A B B A P 当7BP斜率,为顺时针角当>0时,AP斜率<BP斜率,为逆时针角

夹角如何计算？ 大小：利用余弦定理 方向：令 ( )( ) ( )( ) A P B P B P A P B P B P A P A P x x z z x x z z x x z z x x z z T = − − − − − − − − − = 当TBP斜率，为顺时针角 当T>0时，AP斜率<BP斜率，为逆时针角 z x A B P z x B A P

射线法检验交点数 X P n A E B B 左闭右开 D D 交点数=偶数(包括0)交点数=奇数 点在多边形之外 点在多边形之内

射线法检验交点数 A B C D E P A B C D E P 交点数=偶数（包括0） 点在多边形之外 交点数=奇数 点在多边形之内 z x 左闭右开

逐点测试效率低不实用怎么办? 包围盒法 凸多边形 凹多边形

包围盒法 凸多边形 凹多边形 逐点测试效率低不实用怎么办？

实区域填充算法分类 ·扫描线填充算法 扫描线顺序 ·种子填充算法 内部一个点出发

实区域填充算法分类 扫描线填充算法 ◼ 扫描线顺序 种子填充算法 ◼ 内部一个点出发

扫描线填充算法 利用图形的空间连贯性 和扫描线的连贯性 扫描线 P4 扫描线2 P2 求交:4,2 012345678910 3,12: 排序:1,2,12 交点配对:(1,12),(3 区间填色

扫描线填充算法 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 y x 8 8 9 10 扫描线5 P4 P1 P2 P3 P5 扫描线2 I1 I2 I3 I4 求交：I4 , I3 , I2 , I1 排序：I1 , I2 , I3 , I4 交点配对：(I1 , I2 ), (I3 , I4 ) 区间填色 利用图形的空间连贯性 和扫描线的连贯性

填充扩大化间题 765432 步步步 解决方法 1234567X a取中心扫描线y+0.5 检查交点右方像素的中心是否落在区间内 X下X+0.5≤X 1234 0112345167

填充扩大化问题 解决方法： ◼ 取中心扫描线y+0.5 ◼ 检查交点右方像素的中心是否落在区间内 xl≤x+0.5≤xr 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 y 0 1 2 3 4 5 6 7 x 1 2 3 4 5 6 7 y x P1 P2 P4 P3 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 y 0 1 2 3 4 5 6 7 x 1 2 3 4 5 6 7 y x P1 P2 P4 P3