多边形的扫描转换与区域填充 一 多边形的扫描转换 前面讲的画直线是一维图形的光栅化 就是如何在计算机屏幕上即在一个离散的像素集上表示一个连续的图形 而多边形的扫描转换和区域填充这个问题是怎么样在离散的像素集上表示一个连续的二维图形 多边形有两种重要的表示方法 顶点表示和点阵表示 顶点表示是用多边形的顶点序列来表示多边形 这种表示直观 几何意义强 占内存少 易于进行几何变换 但由于它没有明确指出哪些象素在多边形内 故不能直接用于面着色 点阵表示是用位于多边形内的象素集合来刻画多边形 这种表示丢失了许多几何信息 如边界 顶点等 但它却是光栅显示系统显示时所需的表示形式 这涉及到两个问题 第一个问题是如果知道边界 能否求出这个多边形哪些像素在多边形内 众所周知 在计算机上画图形 实际上就是写帧缓存 framebuffer 如果知道多边形哪些像素在里面 就直接写到帧缓存里即可 第二个问题是知道多边形内部的像素 反过来求多边形的边界 很遗憾 这个问题不是图形学关心的问题 是模式识别所关心的问题 图形学 图像处理 模式识别 计算机视觉有密切的联系 我们只关心从顶点表示到点阵表示 光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示 这种转换称为多边形的扫描转换 为什么叫扫描转换 因为光栅显示器是逐行扫描 区域填充 指先将区域的一点赋予指定的颜色 然后将该颜色扩展到整个区域的过程 多边形分为凸多边形 凹多边形 含内环的多边形等 1 凸多边形 任意两顶点间的连线均在多边形内 2 凹多边形 任意两顶点间的连线有不在多边形内的部分 凸多边形凹多边形含内环的多边形 有关概念 1 区域 一组相邻而且又相连的像素 而且具有相同属性的封闭区域 3 区域填充 以某种属性对整个区域进行设置的过程 2 种类 单域 复合域 逐点判断填充算法 区域填充的基本 初级 方法 逐点判断填充算法逐点判断绘图窗口内的每一个像素 若在区域的内部 用指定的属性设置该点 否则不予处理 设有如下函数 TruewhenxDInside D x y FalsewhenxD D 取矩形R x1 x x2 y1 y y2 使R包围D 则逐点判断填充算法如下 for y y1 y y2 y for x x1 x x2 x if inside D x y drawpixel x y color 上述算法原理简单 实用 但效率低 效率低的原因是没有考虑各象素之间的联系 孤立地考察象素与区域的关系 使得几十万甚至几百万个象素都要一一判别 每次判别又要多次求交点 需要做大量的乘除运算 花费很多时间 1 射线法 2 累计角度法 3 编码法 4 如何判断点在多边形的内或外 包含性检查的方法 1 射线法 过被检测点任作一条射线 求其与边界的交点 若交点数为偶数 则该点在边界之外 否则在边界之内 P P 逐点判断法 2 累计角度法步骤从v点向多边形P顶点发出射线 形成有向角计算有相交的和 得出结论 现在的问题是 知道多边形的边界 如何找到多边形内部的点 即把多边形内部填上颜色 对每条横越多边形的扫描线 扫描转换算法确定扫描线与多边形边的交点位置 扫描线 X 扫描线算法填充多边形的基本思想是按扫描线顺序 计算扫描线与多边形的相交区间 再用要求的颜色显示这些区间的像素 即完成填充工作 区间的端点可以通过计算扫描线与多边形边界线的交点获得 根据该原理 X 扫描线算法可以填充凸的 凹的 还可以是带孔的多边形 1 x 扫描线算法 扫描线 对于每条穿越多边形的扫描线 X 扫描线算法确定扫描线与多边形边相交区间的像素点位置 如扫描线y 3与多边形的边界相交于4点 2 3 4 3 7 3 9 3 这四点定义了扫描线从X 2到X 4 从X 7到X 9两个落在多边形内的区间 该区间内的像素应取填充色 从该例可以看出 算法的核心是需按x递增顺序排列交点的x坐标序列 由此 可得到X 扫描线算法步骤如下 1 确定多边形所占有的最大扫描线数 得到多边形顶点的最小和最大y值 ymin和ymax 2 从y ymin到y ymax 每次用一条扫描线进行填充 3 对一条扫描线填充的过程可分为四个步骤 a 求交 计算扫描线与多边形各边的交点 b 排序 把所有交点按递增顺序进行排序 注意 交点在计算时未必是按递增顺序排列的 c 交点配对 第一个与第二个 第三个与第四个等等 每对交点就代表扫描线与多边形的一个相交区间 d 区间填色 把这些相交区间内的像素置成不同于背景色的填充色 在填充过程 当扫描线与多边形顶点相交时 交点的取舍问题 交点的个数应保证为偶数个 当扫描线与多边形顶点相交时 会出现异常情况 解决方案 1 若共享顶点的两条边分别落在扫描线的两边 交点只算一个 2 若共享顶点的两条边在扫描线的同一边 这时交点作为零个或两个 具体实现方式是 检查共享顶点的两条边的另外两个端点的y值 按这两个y值中大于交点y值的个数是0 1 2来决定交点数取0 1 2 0 1 1 1 1 0 2 2 2 但这个算法效率比较低 因为这个算法的关键问题是求交 而求交是很可怕的 求交的计算量是非常大的 假设一个100边形 一个卡通片至少是100 200个边形 现在每条扫描线和这个多边形求交点 一共有1024条扫描线 一共要进行10万多次求交运算 每次求交还要做大量的加减乘除法 计算量太大 最理想的算法是不求交 排序 配对 填色总是要的 如果不求交 那会极大提高算法的效率 为了计算每条扫描线与多边形各边的交点 最简单的方法是把多边形的所有边放在一个表中 在处理每条扫描线时 按顺序从表中取出所有的边 分别与扫描线求交 扫描转换算法重要意义是提出了图形学里两个重要的思想 第一个思想是扫描线的思想 当处理图形图像时按一条条扫描线处理 第二个思想是增量的思想 DDA在算y值的时候是采用增量的方法 求交点的时候能不能也采取增量的方法 每条扫描线的y值都知道 关键是求x的值 X是什么 2 多边形的扫描转换算法 可以从三方面考虑加以改进 1 在处理一条扫描线时 仅对与它相交的多边形的边 有效边 进行求交运算 2 需要考虑扫描线的连贯性 即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似 这样在当前扫描线处理完毕之后 不必为下一条扫描线从头开始构造交点信息 3 最后考虑多边形的连贯性 即当某条边与当前扫描线相交时 它很可能也与下一条扫描线相交 为了避免求交运算 需要引进一套特殊的数据结构 这套数据结构在后面的消隐算法中还要出现 数据结构 随着扫描线的移动 扫描线与多边形的交点和上一次交点相关 设边的直线斜率为k 若y yi时 x xi 则当y yi 1 yi 1时 xi 1 xi 1 k 活性边表 AET 把与当前扫描线相交的边称为活性边 并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中 结点内容 一个结点在数据结构里可用结构来表示 x 当前扫描线与边的交点坐标 x 从当前扫描线到下一条扫描线间x的增量ymax 该边所交的最高扫描线的坐标值ymax 即 x 1 k为常量 则下一条扫描线与该边的交点不要重新计算 只要加一个增量 x 其中x为当前扫描线与边的交点 ymax是边所在的最大扫描线值 通过它可以知道何时才能 抛弃 该边 x表示从当前扫描线到下一条扫描线之间的x增量即斜率的倒数 next为指向下一条边的指针 另外使用增量法计算时 我们需要知道一条边何时不再与下一条扫描线相交 以便及时把它从有效边表中删除出去 避免下一步进行无谓的计算 综上所述 有效边表AET的每个结点存放对应边的有关信息如下 一个多边形与若干扫描线 看扫描线y 6的活性边表 为了方便有效边表的建立与更新 需构造一个新边表 NET 用来存放多边形的边的信息 分为4个步骤 1 首先构造一个纵向链表 链表的长度为多边形所占有的最大扫描线数 链表的每个结点 称为一个桶 对应多边形覆盖的每一条扫描线 2 将每条边的信息链入与该边最小y坐标 ymin 相对应的桶处 也就是说 存放在该扫描线第一次出现的边 若某边的较低端点为ymin 则该边就放在扫描线ymin的新边表中 3 每条边的数据形成一个结点 内容包括 该扫描线与该边的初始交点x 即较低端点的x值 1 k 以及该边的最大y值ymax 4 同一桶中若干条边按X ymin由小到大排序 若X ymin相等 则按照1 k由小到大排序 一个多边形与若干扫描线 这个结构实际上是一个指针数组 数组的每个变量是个指针 这个指针指向所有的以这个y值作为起点的边 把多边形所有的边全部填成这样的结构 插到这个指针数组里面来 如y 1 y 5指向哪些边 从上面这个指针数组里面就知道多边形是从哪里开始的 在这个指针数组里只有1 2 3 5处有边 因此当从下往上进行扫描转换的时候 从y 1开始做 而在1这条线上有两条边进来了 然后就把这两条边放进活性边表来处理 当处理y 2这条扫描线时 活性边里有2条边 先看活性边表里是否有边要退出和加入 实际上p1p2边要退出了 y ymax p1p6边要加入了 退出的边要从活性边表里去掉 不退出的边要进行处理 即把x值加上一个增量 一个多边形与若干扫描线 即每做一次新的扫描线时 要对已有的边进行三个处理 一是否被去除掉 如果不被去除 第二就要对它的数据进行更新 所谓更新数据就是要更新它的x值 即x x 最后 就是有没有新的边进来 新的边在NET里 可以插入排序插进来 这个算法过程从来没有求交 这套数据结构使得你不用求交点 避免了求交运算 voidpolyfill polygon color intcolor 多边形polygon for 各条扫描线i 初始化新边表头指针NET i 把ymin i的边放进边表NET i y 最低扫描线号 初始化活性边表AET为空 for 各条扫描线i 把新边表NET i 中的边结点用插入排序法插入AET表 使之按x坐标递增顺序排列 遍历AET表 把配对交点区间 左闭右开 上的象素 x y 用putpixel x y color 改写象素颜色值 遍历AET表 把ymax i的结点从AET表中删除 并把ymax i结点的x值递增 x 若允许多边形的边自相交 则用冒泡排序法对AET表重新排序 polyfill 3 边缘填充算法 其基本思想是按任意顺序处理多边形的每条边 在处理每条边时 首先求出该边与扫描线的交点 然后将每一条扫描线上交点右方的所有像素取补 多边形的所有边处理完毕之后 填充即完成 逐边向右取 边缘填充算法缺点 每一个象素可能被访问多次引入栅栏 以减少填充算法访问象素的次数 栅栏 与扫描线垂直的直线 通常过一顶点 且把多边形分为左右二半 基本思想 扫描线与多边形的边求交 将交点与栅栏之间的象素取补 若交点位于栅栏左边 则将交点之右 栅栏之左的所有象素取补 若交点位于栅栏右边 则将交点之左 栅栏之右的所有象素取补 减少了象素重复访问数目 但不彻底 栅栏填充算法 6 边界标志算法 基本思想 帧缓冲器中对多边形的每条边进行直线扫描转换 亦即对多边形边界所经过的象素打上标志 然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色 使用一个布尔量inside来指示当前点是否在多边形内的状态 voidedgemark fill polydef color 多边形定义polydef intcolor 对多边形polydef每条边进行直线扫描转换 inside FALSE for 每条与多边形polydef相交的扫描线y for 扫描线上每个象素x if 象素x被打上边标志 两个交点之间的区域填充inside inside if inside FALSE putpixel x y color elsedrawpixel x y background 用软件实现时 扫描线算法与边界标志算法的执行速度几乎相同 由于边界标志算法不必建立维护边表以及对它进行排序 所以边界标志算法更适合硬件实现 这时它的执行速度比有序边表算法快一至两个数量级 小结 扫描线法可以实现已知多边形域边