哈尔滨工业大学：《计算机图形学》第3章 基本图形生成算法——实区域填充算法

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

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

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

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

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

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

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

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

夹角如何计算? 大小:利用余弦定理 方向:令 x P (xA-Xp)(=B-p)-( )(=A-2p) B B P B A P P 当TBP斜率,为顺时针角当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

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

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

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

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

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

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

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

扫描线填充算法 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 ) 区间填色 利用图形的空间连贯性 和扫描线的连贯性

填充扩大化间题 y765432 y765 解决方法: 1234567x 1234567X 取中心扫描线y+0.5 检查交点右方像素的中心是否落在区间内 ≤x+0.5≤x 76543210 543 2 12345167 0112345167x

填充扩大化问题 解决方法： ◼ 取中心扫描线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