计算机图形学第3章二维基本.ppt

3 4区域填充 前面介绍的直线和圆都属于线划图 然而 光栅显示的一个重要特点是能进行面着色 区域填充就是在一个闭合区域内填充某种颜色或图案 区域填充一般分两类 多边形填充和种子填充 一 多边形填充1 填充条件多边形的顶点序列 Pi i 0 1 n 填充色 2 多边形内点的判别准则对多边形进行填充 关键是找出多边形内的象素 在顺序给定多边形顶点坐标的情况下 如何判明一个象素点是处于多边形的内部还是外部呢 多边形内点的判别准则和奇异点 从测试点引出一条伸向无穷远处的射线 假设是水平向右的射线 因为多边形是闭合的 那么 若射线与多边形边界的交点个数为奇数时 则该点为内点 例 图中测试点4引出的射线 反之 交点个数为偶数时 则该点为外点 例 测试点2引出的射线 3 奇异点的处理 上述的判别准则 在大多数情况下是正确的 但当水平扫描线正好通过多边形顶点时 要特别注意 例如 图中过顶点的射线1 射线6 它们与多边形的交点个数为奇数 按照判别准则它们应该是内点 但实际上却是外点 而图中过顶点的射线3 射线5 对于判别准则的使用又是正确的 多边形内点的判别准则和奇异点 综合以上情况 我们将多边形的顶点分为两大类 1 局部极值点 如图中的点P1 P2 P4和P6 对于这些点来说 进入该点的边线和离开该点的边线位于过该点扫描线的同一侧 2 非极值点 如图中的点P3 P5 对于这些点来说 进入该点的边线和离开该点的边线位于过该点扫描线的两侧 处理奇异点规则 1 对于局部极值点 应看成两个点 2 对于非极值点 应看成一个点 多边形内点的判别准则和奇异点 4 逐点判别算法步骤 1 求出多边形的最小包围盒 从Pi xi yi 中求极值 xmin ymin xmax ymax 2 对包围盒中的每个象素引水平射线进行测试 3 求出该射线与多边形每条边的有效交点个数 4 如果个数为奇数 该点置为填充色 5 否则 该点置为背景色 逐点判别算法虽然简单 但不可取 原因是速度慢 它割断了各象素之间的联系 孤立地考虑问题 由于要对每个象素进行多次求交运算 求交时要做大量的乘除运算 从而影响了填充速度 3 3 1边相关扫描线多边形填充算法 边相关扫描线填充算法属于多边形填充类 它比逐点判别算法速度提高很多 是一种较经典的多边形填充算法 该算法利用了扫描线的相关性和多边形边的相关性 而不是逐点进行处理 一 边相关扫描线填充算法描述扫描线的相关性 某条扫描线上相邻的象素 几乎都具有同样的内外性质 这种性质只有遇到多边形边线与该扫描线的交点时才发生改变 见下图 a 边的相关性 由于相邻扫描线上的交点是与多边形的边线相关的 对同一条边 前一条扫描线yi与该边的交点为xi 而后一条扫描线yi 1 yi 1与该边的交点则为xi 1 xi 1 m 利用这种相关性可以省去大量的求交运算 见下图 b 所示 边相关扫描线填充算法的实现需要建立两个表 边表 ET 和活动边表 AET 1 边表 ET EdgeTable 用来对除水平边外的所有边进行登记 来建立边的记录 边的记录定义为 扫描线y对应的ET表 第一项 某边的最大y值 ymax 注意要进行奇异点处理 对于非极值点应该ymax ymax 1 第二项 某边的最小的y对应的x值 第三项 某边斜率的倒数 1 m 第四项 指针 用来指向同一条扫描线相交的其它边 如果其它边不存在 则该项置空 二 边相关扫描线填充算法思想1 根据给出的多边形顶点坐标 建立ET表 求出顶点坐标中最大y值ymax和最小y值ymin 2 初始化AET表指针 使它为空 2 活动边表 AET ActiveEdgeTable ET表建立以后 就可以开始扫描转换了 对不同的扫描线 与之相交的边线也是不同的 当对某一条扫描线进行扫描转换时 我们只需要考虑与它相交的那些边线 为此需要建立一个只与当前扫描线相交的边记录链表 称之为活动边表 3 使用扫描线的yj值作为循环变量 使其初值为ymin 对于循环变量yj的每一整数值 重复作以下事情 直到yj大于ymax 或ET表与AET表都为空为止 1 如果ET表中yj桶非空 则将yj桶中的全部记录合并到AET表中 2 对AET表链中的记录按x的大小从小到大排序 3 依次取出AET表各记录中的xi坐标值 两两配对填充 即将每对xi之间的象素填上所要求的颜色 4 如果AET表中某记录的ymax yj 则删除该记录 5 对于仍留在AET表中的每个记录 用xi 1 m代替xi进行修改 这就是该记录的边线与下一条扫描线yj 1的交点 6 使yj加1 以便进入下一轮循环 三 边相关扫描线填充算法举例对下图 a 的多边形利用边相关扫描线填充算法进行处理 1 首先建立ET表 注意 在做奇异点处理时 当该边最大y值对应的顶点为非极值点时 边记录的第一项 ymax ymax 1 例如 P3P4边 P3P2边 P4P5边 见下图 b 2 接着建立AET表 AET表的建立过程就是有效地进行填充的操作 在这个期间不断地做以下工作 a 多边形 b ET表 c AET表 1 合并ET表 2 x递增排序 3 实施填充 4 删除ymax yj的边 5 修改边记录xi xi 1 m 6 yj 1进入下一轮循环 四 边相关扫描线填充算法实现1 根据给定的多边形顶点坐标 建立ET表 2 AET表初始化 每个桶置空 3 for y ymin y ymax y 合并当前扫描线y的ET表 将y桶中每个记录按x项升序排列 在当前y值下 将两两记录的x值之间的象素进行填充 删除y ymax的边记录 修改边记录x x 1 m 五 边相关扫描线填充算法特点该算法充分利用多边形的边相关性和扫描线的相关性 使用ET表对多边形的非水平边进行登记 用AET表的建立和更新来支持填充 大大地减少了求交点的计算量 有效地提高了填充速度 练习 用边相关扫描线填充算法 对图中多边形建立ET AET表 作业 用边相关扫描线填充算法做出图中多边形的ET表和AET表 二 种子填充种子填充是将区域内的一点 种子 赋予给定的颜色 然后将这种颜色扩展到整个区域内的过程 1 填充条件区域内一点的坐标即种子坐标 边界色 填充色 2 连通方式区域是互相连通着的象素的集合 连通方式可分为四连通和八连通 四连通 从区域内一点出发 可通过四个方向 上 下 左 右到达该区域内部的任意象素 八连通 区域内部从一个象素到达另一个象素的移动路径 除了上 下 左 右四个方向外 还允许沿着对角线方向 注意 1 八连通区域中 既然区域内的两个象素可以通过对角线相通 那么 区域边界上的象素则不能通过对角线相连 否则填充就会溢出到区域外 因此 八连通区域的边界线必须是四连通的 见下图 a 2 而四连通区域 其边界象素是四连通和八连通的都可以 见下图 b a 八连通区域四