第6讲扫描转换与区域填充.ppt

多边形的扫描转换扫描线算法边界标志算法区域填充区域填充的递归算法扫描线填充算法 第6讲扫描转换与区域填充 顶点表示 线 点阵表示 填充 用多边形的顶点序列来表示 用位于多边形内的象素集合来表示 扫描转换 多边形的表示方法 顶点表示 用多边形顶点的序列来刻划多边形 直观 几何意义强 占内存少 不能直接用于面着色 点阵表示 用位于多边形内的象素的集合来刻划多边形 失去了许多重要的几何信息 便于运用帧缓冲存储器表示图形 易于面着色 多边形的表示方法 多边形的扫描转换 把多边形的顶点表示转换为点阵表示 也就是从多边形的给定边界出发 求出位于其内部的各个象素 并给帧缓冲器内的各个对应元素设置相应的灰度和颜色 通常称这种转换为多边形的扫描转换 两种方法 扫描线算法 边界标志法 多边形的扫描转换 按扫描线顺序 计算扫描线与多边形的相交区间 再用要求的颜色显示这些区间的象素 即完成填充工作 扫描线算法基本思想 用水平扫描线从上到下扫描 每根扫描线与多边形各边产生一系列交点 这些交点按照x坐标进行分类 将分类后的交点成对取出 作为两个端点 以所需要填的色彩画水平直线 多边形被扫描完毕后 填色也就完成 一条扫描线填充过程的步骤 1 求交 2 排序 3 配对 4 填色 扫描线算法基本思想 算法描述 扫描线的相关性 某条扫描线上相邻的象素 几乎都具有同样的内外性质 这种性质只有遇到多边形边线与该扫描线的交点时才会发生改变 边的相关性 由于相邻扫描线上的交点是与多边形的边线相关的 对同一条边 前一条扫描线yi与该边的交点为xi 而后一条扫描线yi 1 yi 1与该边的交点则为xi 1 xi 1 m 利用这种相关性可以省去大量的求交运算 扫描线的相关性 边的相关性 当扫描线与多边形P的交点是P的顶点时 则称该交点为奇点 以上所述多边形的的连贯性都基于这样的几何事实 每一条扫描线与多边形P的边界的交点个数都是偶数 但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点 都可能出现奇数个交点 那么如果保证交点数为偶数呢 奇异点的处理 奇异点的处理 将多边形的顶点分为两大类 局部极值点进入该点的边线和离开该点的边线位于过该点扫描线的同一侧 点P1 P2 P4和P6 非极值点对于这些点来说 进入该点的边线和离开该点的边线位于过该点扫描线的两侧 点P3 P5 处理奇异点规则 对于局部极值点 看成两个点 对于非极值点 看成一个点 活性边表 AET 把与当前扫描线相交的边称为活性边 并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中第一项 当前扫描线与边的交点坐标x第二项 从当前扫描线到下一条扫描线间x的增量 x第三项 该边所交的最高扫描线号ymax第四项 指针 用来指向同一条扫描线相交的其它边 如果其它边不存在 则该项置空 扫描线算法数据结构 活性边表 扫描线为6的活性表 假定当前扫描线与多边形某一条边的交点的x坐标为x 则下一条扫描线与该边的交点不要重计算 只要加一个增量 x 设该边的直线方程为 ax by c 0 若y yi x xi 则当y yi 1 yi 1 时 其中为常数 是斜率的倒数 活性边表 为了方便边的活化链表的更新 建立另一个表 边表 存放在该扫描线第一次出现的边 存放的信息 x 扫描线与该边的初始交点dx x的增量ymax 该边的最大y值 新边表 新边表 NET 存放在该扫描线第一次出现的边 若某边的较低端点为ymin 则该边就放在扫描线ymin的新边表中 新边表 规则1 X为小数 即交点落于扫描线上两个相邻像素之间 a 交点位于左边之上 向右取整 b 交点位于右边之上 向左取整 扫描线算法 规则2 边界上象素的取舍问题 避免填充扩大化 解决方法 边界象素 规定落在右上边界的象素不予填充 具体实现时 只要对扫描线与多边形的相交区间左闭右开 扫描线算法 voidpolyfill polygon color intcolor 多边形polygon for 各条扫描线i 初始化新边表头指针NET i 把ymin i的边放进边表NET i y 最低扫描线号 初始化活性边表AET为空 for 各条扫描线i 扫描线算法 把新边表NET i 中的边结点用插入排序法插入AET表 使之按x坐标递增顺序排列 遍历AET表 把配对交点区间 左闭右开 上的象素 x y 用drawpixel x y color 改写象素颜色值 遍历AET表 把ymax i的结点从AET表中删除 并把ymax i结点的x值递增 x 若允许多边形的边自相交 则用冒泡排序法对AET表重新排序 polyfill 扫描线算法 特点 对于顶点表示的多边形 算法效率较高 缺点 对各种表的维持和排序开销太大 适合软件实现而不适合硬件实现 扫描线算法 边界标志算法 扫描线的相关性 某条扫描线上相邻的象素 几乎都具有同样的内外性质 这种性质只有遇到多边形边线与该扫描线的交点时才会发生改变 边界标志算法 基本思想先在屏幕上生成多边形轮廓线 然后逐条扫描处理 处理中 逐点读取象素值 若为边界色 则对该象素值进行颜色切换 边界标志算法 算法实现 1 用边界色画出多边形轮廓线 也就是将多边形边界所经过的象素打上边标志 2 为了缩小范围 加快填充速度 须找出多边形的最小包围盒 xmin ymin xmax ymax 3 逐条扫描线进行处理 对每条扫描线依从左往右的顺序 逐个访问该扫描线上的象素 每遇到边界象素 标志取反 然后 按照标志是否为真决定象素是否为填充色 演示 边界标志算法 算法特点该算法思想简单 实现容易 既不需要求交点 交点排序 边的登记 也不需要使用链表 堆栈等数据结构 用软件实现时 扫描线算法与边界标志算法的执行速度几乎相同 但由于边界标志算法不必建立维护边表以及对它进行排序 所以边界标志算法更适合硬件实现 这时它的执行速度比有序边表算法快一至两个数量级 二区域填充 区域的含义这里讨论的区域指已经表示成点阵形式的填充图形 它是像素的集合 区域填充 区域表示方法 区域填充 区域表示方法 内点表示 边界表示内点表示枚举出区域内部的所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同的颜色边界表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色 区域填充的含义是指先将区域的一点赋予指定的颜色 然后将该颜色扩展到整个区域的过程 区域填充 区域填充算法要求区域是连通的 八连通 区域内部从一个象素到达另一个象素的移动路径 除了上 下 左 右四个方向外 还允许沿着对角线方向 区域的连通性 四连通 从区域内一点出发 可通过四个方向 上 下 左 右到达该区域内部的任意象素 八连通区域 四连通区域 区域的连通性 区域填充算法 已知条件 G为一内点表示的区域 x y 为区域内一点old color为G的原色如何对G进行填充 区域填充的递归算法 已知条件 G为一内点表示的区域 x y 为区域内一点old color为G的原色现取 x y 为种子点对区域G进行填充 即先置像素 x y 的颜色为new color然后逐步将整个区域G都置为同样的颜色 区域填充的递归算法 步骤如下 种子像素入栈 当栈非空时 执行如下三步操作 1 栈顶像素出栈 2 将出栈像素置成多边形色 3 按上 下 左 右的顺序检查与出栈像素相邻的四个像素 若其中某个像素不在边界上且未置成多边形色 则把该像素入栈 s1 234 98765 11121314 10 递归算法 例 多边形P0 1 5 P1 5 5 P2 7 3 P3 7 1 P4 1 1 种子点为 3 3 搜索的方向是上 下 左 右 内点表示的四连通区域的递归填充算法voidFloodFill4 intx inty intoldcolor intnewcolor if getpixel x y oldcolor 属于区域内点oldcolor drawpixel x y newcolor FloodFill4 x y 1 oldcolor newcolor FloodFill4 x y 1 oldcolor newcolor FloodFill4 x 1 y oldcolor newcolor FloodFill4 x 1 y oldcolor newcolor 递归算法 边界表示的四连通区域的递归填充算法voidBoundaryFill4 intx inty intboundarycolor intnewcolor intcolor if color newcolor 递归算法 递归算法 假设在多边形内一个像素已知 由此出发利用连通性找到区域内的所有像素 内点检测条件用来判断任何一个检测像素点 x y 是不是尚未填充内点表示边界表示 if getpixel x y 边界色 getpixel x y 填充色 if getpixel x y 原色 递归算法特点 1 有些像素会入栈多次 降低算法效率 栈结构占空间 2 递归执行 算法简单 但效率不高 区域内每一像素都引起一次递归 进 出栈 改进算法 减少递归次数 提高效率 方法之一使用扫描线填充算法 扫描线填充算法 算法思想 扫描线填充算法 首先填充当前扫描线上的位于给定区域内的一区段然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段如果存在 则依次把它们保存起来 反复这个过程 直到所保存的各区段都填充完毕 算法思想 算法实现 1 初始化堆栈 2 种子压入堆栈 3 while 堆栈非空 1 从堆栈弹出种子像素 2 如果种子像素尚未填充 则 a 求出种子区段 xleft xright b 填充整个区段 c 检查相邻的上扫描线的xleft x xright区间内 是否存在需要填充的新区段 如果存在的话 则把每个新区段在xleft x xright范围内的最右边的象素 作为新的种子象素依次压入堆栈 d 检查相邻的下扫描线的xleft x xright区间内 是否存在需要填充的新区段 如果存在的话 则把每个新区段在xleft x xright范围内的最右边的象素 作为新的种子象素依次压入堆栈 算法演示 扫描线填充算法 1 该算法考虑了扫描线上象素的相关性 种子象素不再代表一个孤立的象素 而是代表一个尚未填充的区段 2 进栈时 只将每个区段选一个象素进栈 每个区段最右边或最左边的象素 这样解决了堆栈溢出的问题 3 种子出栈时 则填充整个区段 4 这样有机的结合 一边对尚未填充象素的登记 象素进栈 一边进行填充 象素出栈 既可以节省堆栈空间 又可以实施快速填充 算法特点 多边形扫描转换与区域填充方法比较 基本思想不同 前者 后者 多边形扫描转换与区域填充方法比较 基本思想不同 前者 顶点表示转换成点阵表示后者 只改变区域内填充颜色 没有改变表示方法 多边形扫描转换与区域填充方法比较 基本思想不同 前者 顶点表示转换成点阵表示后者 只改变区域内填充颜色 没有改变表示方法 对边界的要求不同 前者 后者 多边形扫描转换与区域填充方法比较 基本思想不同 前者 顶点表示转换成点阵表示后者 只改变区域内填充颜色 没有改变表示方法 对边界的要求不同 前者 只要求扫描线与多边形边界交点个数为偶数后者 区域封闭 防止递归填充跨界 多边形扫描转换与区域填充方法比较