用扫描线算法实现多边形填充

计计算算机机图图形形学学论论文文 基于扫描线的区域填充算法基于扫描线的区域填充算法 姓 名 魏艳娜 学 号 2012151115 班 级 201201 第 0 页 基于扫描线的区域填充算法 摘摘 要要 图形通常由点 线 面 体等几何元素和灰度 色彩 线型 线宽等非几何属性组成 从处理技术上来看 图形主要分为两类 一类是基于 线条信息表示的 如工程图 等高线地图 曲面的线框图等 另一类是明暗图 也就是通常所说的真实感图形 为此 必须建立图形所描述的场景的几何表示 再用某种光照模型 计算在假想的光源 纹理 材质属性下的光照明效果 计 算机图形学的内容非常广泛 如图形硬件 图形标准 图形交互技术 光栅图 形生成算法 以及科学计算可视化 计算机动画 虚拟现实等 这里重点研究 区域填充 关键词关键词 计算机图形学 区域填充 扫描线算法 第第 1 1 章章 绪论绪论 1 11 1 研究的背景研究的背景 在计算机中重现真实世界的场景叫做真实感绘制 真实感绘制的主要任务是模拟真实 物体的物理属性 简单的说就是物体的形状 光学性质 表面的纹理和粗糙程度 以及物 体间的相对位置 遮挡关系等等 实时的真实感绘制已经成为当前真实感绘制的研究热点 而当前真实感图形实时绘制的两个热点问题则是物体网格模型的面片简化和基于图象的绘 制 网格模型的面片简化 就是指对网格面片表示的模型 在一定误差的精度范围内 删 除点 边 面 从而简化所绘制场景的复杂层度 加快图形绘制速度 IBR 完全摒弃传统 的先建模 然后确定光源的绘制的方法 它直接从一系列已知的图象中生成未知视角的图 象 这种方法省去了建立场景的几何模型和光照模型的过程 也不用进行如光线跟踪等极 费时的计算 该方法尤其适用于野外极其复杂场景的生成和漫游 1 21 2 研究的主要内容及结构研究的主要内容及结构 主要任务是实现多边形区域扫描线填充的有序边表算法 设计相关的数据结构 并将 实现的算法应用于任意多边形的填充 区域填充 指的是在输出平面的闭合区域内完整地填 充某种颜色或图案 以下所述及的区域填充算法或相关程序 主要针对显示平面内的区域而 言 区域填充的问题一般分两大类 一是多边形填充 一是种子填充 种子填充在学生掌握 了 栈 这一抽象数据类型的实现方法的前提下 比较容易完成 而边标志填充算法却是介 于这两类之间 部分地具有它们的痕迹 算法思想巧妙 实现起来更容易 多边形填充有一定 难度 我们主要对多边形的扫描线算法填充做一些探讨 具体将以五角星为实例 第第 2 2 章章 理论综述理论综述 2 12 1 区域填充的理论知识区域填充的理论知识 2 1 12 1 1 区域填充的概念区域填充的概念 将区域的边界表示转换为区域内部象素表示的过程称为区域填充 区域填充是计算机图 形学中的一个基本问题 在计算机辅助设计 真实感图形显示 图像分析等领域有着广 泛的应用 区域填充算法是指给出一个区域的边界 要求在边界范围内对所有像素单元赋 第 1 页 予指定的颜色代码 目前 区域填充算法中最常用的是多边形填色 常用的多边形填色算 法有两种 一类是种子填充算法 一类是扫描线填充算法 研究如何用一种颜色或图案来填充一个二维区域 一般来说 区域的封闭轮廓是简单 的多边形 若轮廓线由曲线构成 则可将曲线转换成多条直线段顺连而成 此时 区域轮 廓线仍然是一种多边形逼近 在计算机图形学中 多边形区域有两种重要的表示方法 顶点表示和点阵表示 所谓 顶点表示 即是用多边形的顶点序列来表示多边形 这种表示直观 几何意义强 占内存 少 易于进行几何变换 但由于它没有明确指出哪些像素在多边形内 故不能直接用于区 域填充 所谓点阵表示 则是用位于多边形内的像素集合来刻画多边形 这种表示丢失了 许多几何信息 但便于进行填充 根据区域的定义 可以采用不同的填充算法 其中最具代表性的是 适用于顶点表示 的扫描线类算法和适应于点阵表示的种子填充算法 2 1 22 1 2 扫描线算法的描述扫描线算法的描述 扫描线填充算法一般包括四个步骤 求交 排序 交点配对 区域填充 正确求得扫 描线与区域填内外轮廓线的交点是算法成败的关键问题 另一方面 采用合适的数据结构 又可以简化操作 提高算法的效率 本论文由于采用链表结构记录轮廓线和交点 无需焦 点排序的过程 因而提高了算法效率 扫描线来源于光栅显示器的显示原理 对于屏幕上 所有待显示像素的信息 将这些信息按从上到下 自左至右的方式显示 扫描线多边形区域填充算法是按扫描线顺序 计算扫描线与多边形的相交区间 再用 要求的颜色显示这些区间的象素 即完成填充工作 区间的端点可以通过计算扫描线与多 边形边界线的交点获得 对于一条扫描线 多边形的填充过程可以分为四个步骤 1 求交 计算扫描线与多边形各边的交点 2 排序 把所有交点按 x 值递增顺序排序 3 配对 第一个与第二个 第三个与第四个等等 每对交点代表扫描线与多边形的一个 相交区间 4 填色 把相交区间内的象素置成多边形颜色 2 22 2 数据结构与算法数据结构与算法 2 2 12 2 1 扫描线多边形填充算法的主要步骤扫描线多边形填充算法的主要步骤 1 建立 NET NewEdgeList 2 从最低扫描线开始到最高扫描线循环 3 建立或调整 AET ActiveEdgeList 4 按照 AET 中的接点顺序填充 扫描线填充算法的目标是减少递归层次 步骤是填充并确定种段 初始化 将种子区 段压入堆栈 出栈 如果堆栈为空 则算法结束 否则取栈顶元素 y xLeft xRight 以 纵坐标为 y 的扫描线为当前扫描线 xLeft yLeft 为搜索区间 填充并确定新的区段 因此 扫描线多边形区域填充算法的基本原理是 待填充区域按 y 方向 x 方向亦可 扫描线顺序扫描生成 具体实现时 首先按扫描线顺序 计算扫描线与多边形的相交区间 再用指定的颜色填充这些区间内的像素 即完成这一条扫描线的填充工作 区间的端点可 以通过计算扫描线与多边形边界的交点获得 为了提高效率 在处理每一条扫描线时 仅对与它相交的多边形的边进行求交运算 我们 把当前扫描线相交的边称为活性边 active edge 并把它们按扫描线交点 x 坐标递增的顺序 存放在一个链表中 称此链表为活性边表 AET 为了提高速度 假定当前扫描线与多边形某一条边的交点的 x 坐标为 xi 则下一条扫 描线与该点的交点不需要重新计算 而是通过增加一个增量 x 来获得 对于直线 ax by c 0 x b a 为常数 另外使用增量法计算时 还需要知道一条边何时不再与下一条扫描线相交 以便及时 第 2 页 把它从活性边表中删除出去 因此 活性边表结点的数据结构应保存如下内容 第 1 项保 存当前扫描线与边的交点坐标 x 值 第 2 项保存从当前扫描线到下一条扫描线间 x 的增量 x 第 3 项保存该边所交的最高扫描线好 ymax 第 4 项存指向下一条边的指针 为了方便活性边表的建立与更新 可为每一条扫描线建立一个边表 ET 存放在该扫描 线第一次出现的边 也就是说 若某边的较低端点为 ymin 则该边就放在扫描线 ymin 的 边表中 边的分类表 ET 按照边的下端点 y 坐标对非水平边进行分类的指针数组活化边表 AEL 记录 与当前扫描线相交的边 交点 2 2 22 2 2 边的算法边的算法 typedef struct int ymax float x delta struct Edge nextEdge Edge ymax 边的上端点 y 坐标 x 在 AEL 中表示当前扫描线与边的交点的 x 坐标 在 ET 中的初值为边的下端点的 x 坐标 deltax 边的斜率的倒数 nextEdge 指向下一条边的指针 具体步骤如下 step1 把新边表 NET i 中的边结点 用插入排序法 插入活性边表 AET 使之按 X 坐标递增顺序排序 step2 遍历 AET 表 把配对交点之间的区间 左闭右开 上的各象 素 X Y 用 drawpixel x y color 改写象素颜色值 step3 遍历 AET 表 把 Ymax i 的结点从 AET 表中删除 并把 Ymax i 的结果点的 X 值递增 X step4 重复各扫描线 2 2 32 2 3 顶点交点的计数问题顶点交点的计数问题 扫描线与多边形顶点相交时 必须正确的进行交点个数计算 否则 在进行填充时会出 现错误 扫描线与多边形相交的边分处扫描线的两侧 则计一个交点 扫描线与多边形相 交的边分处扫描线同侧 且 yi y i 1 yiy i 1 yi y i 1 则 计 0 个交点 扫描线与多边形边界重合 则计 1 个交点 是否正确求取扫描线与多边形的交点是扫描线填充算法成败的关键 研究发现 求取 扫描线与多边形的交点 既要利用边界点的局部信息 又要利用一条扫描线上所有交点的 全部信息 因此 论文的求交过程包括以下三步 第一步 遍历多边形的边一次 确定扫描线纵坐标的变化范围 ymin 和 ymax 建立一 个空间的扫描线交点链表 第二步 遍历多边形区域的边一次 根据每一边界点与前驱 后继之间的空间关系 初步求得各扫描线与边的交点 第三步 对第二步中求得的交点进行修剪 得到正确的扫描线交点表 当遍历完区域多边形轮廓线上的所有边界点之后 求交过程的第二步结束 此时的扫描 线活动边表所记录得是各条扫描线与区域轮廓线的交点 但是 此时还不能保证各条扫描 线上的交点的数目为偶数 因此不能直接用于配对 必须对各个扫描线的交点链表进行修 剪 第 3 页 求交点过程的第三步对每一条扫描线的交点链表进行修剪 其目的是删除那些由于出现 半交半切 的情况而多算的交点 以便实现正确的配对 假设待修剪的扫描线为 y i 修 正的过程为 1 以扫描线 y i 的交点链表上的第一个交点 Pi l 点作为起点 2 如果起点为空 转 5 结束 否则 按照从左到右的顺序遍历链表上的每一个点 如果 遇到一个标号非零的交点 Pf 设其标号值为 lf 则从 Pf 的后继开始 寻找第二个标号非零 的交点 Ps 设其标号值为 ls 此时 如果 lf 与 ls 符号相同 则转 3 如果 lf 与 ls 符号相反 则转 4 3 将 Pf 和 Ps 从交点链表中删除 并以 Ps 的后继作为起点 转 2 4 将 Pf 从交点链表中删除 令 Ps 的标号 ls 0 并以 Ps 的后继作为起点 转 2 5 结束 通过分析不难发现 对于任意多边形区域 经上述算法所求的每一条扫描线与多边形 的交点数目为偶数 按照先后次序两两配对时 能确保交点之间的区域位于区域的内部 描述扫描线与多边形交点的数据结构定义一为 struct crosspoint int x 交点的横坐标 int y 交点的纵坐标 int l 交点的标记 crosspoint pNextPoint 下一个交点 采用单链表的方式记录多边形上的所有与扫描线的交点坐标 下图所示 图中 E 表 示多边形的边 E 1 2 n 由于多边形的外轮廓具有封闭性 所以链表的起点 E 和 终点 E 也具有 8 连通关系 对于链表中任意一个边界点 E 定义 E 为 E 的前驱 E 为 E 的后继 后面将会看到 前去和后继对于判断交点的属性是必不可少的 把与当前扫描线相交的边称为活性边 并把它们按与扫描线交点 x 坐标递增的顺序存放 在一个链表中 称此链表为活性边表 AET 2 32 3 扫描线的算法步骤 扫描线的算法步骤 1 分析多边形区域扫描线填充算法的原理 确定算法流程 初始化 构造边表 ET 置 AET 表为空 将第一个不空的 ET 表中的边插入 AET 表 由 AET 表取出交点进行配对 奇偶 获得填充区间 依次对这些填充区间着色 y yi 1 时 根据 x xi 1 k 修改 AET 表所有结点中交点的 x 坐标 同时如果相应的 ET 表不空 则将其中的结点插入 AET 表 形成新的 AET 表 AET 表不空 则转 3 否则结束 2 编程 首先确定多边形顶点和 ET AET 表中结点的结构 编写链表相关操作 如链表结点插入 删除和排序等 根据 1 中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体 功能 编写主函数 测试该算法 3 算法描述 void polyfill 多边形 polygon 颜色 color for 各条扫描线 i 第 4 页 初始化新边表头指针 NET i 把 ymin i 的边放进边表 NET i y 最低扫描线号 初始化活性边表 AET 为空 for 各条扫描线 i 把新边表 NET i 中的边结点用插入排序法插入 AET 表 使之按 x 坐标递增顺序排列 遍历 AET 表 把 y max i 的结点从 AET 表中删除 并把 y max i 结点的 x 值递增 D x 若允许多边形的边自相交 则用冒泡排序法对 AET 表重新排序 遍历 AET 表 把配对交点区间 左闭右开 上的象素 x y 用 drawpixel x y color 改写象素颜色值 polyfill 第第 3 3 章章 多边形填充实例多边形填充实例 多边形区域填充算法 多边形区域填充主要有以下步骤 第一步是确定哪些像素位于 图元内部 第二步是确定用何种颜色显示那些像素 经过上一章的知识 本章将以五角星 为实例进行用扫描线算法的填充 3 13 1 用扫描线算法实现五角星填充用扫描线算法实现五角星填充 以 50 0 60 30 90 30 70 45 80 90 50 60 20 90 30 45 10 30 40 30 这十个点作为五角星的十个点 利用扫描线算法将这个 五角星进行填充 3 23 2 画五角星图形画五角星图形 1 五角星图形 2 五角星的边表 构造 ET 表算法描述如下 void CreatET Edge et struct pointtype p 根据顶点数组构造 ET 表 int i lasty lastx nextx nexty ymax cy cx Edge pe for i 0 inextEdge NULL initgraph CreatET et p for i 0 i ETMAX i if et i NULL y i break 第 6 页 确定 y 的最小序号 ymax p 0 y for i 0 iymax ymax p i y 确定 ymax while ynextEdge while pmove NULL if counter 2 1 xlast pmove x else 每两次边画线一次并重新赋值开始 xcur pmove x color random maxcolor setcolor color line int xlast 1 y int xcur y xlast 0 xcur 0 counter pmove pmove nextEdge 结束语结束语 这种方法省去了建立场景的几何模型和光照模型的过程 也不用进行如光线 跟踪等极费时的计算 该方法尤其适用于野外极其复杂场景的生成和漫游 第 7 页 参考文献 参考文献 1 李桂清 李淘渊 扫描线种子填充的问题及改进 J 广西大学学报 自然科学版 1998 9 207 212 2 余正生 马立庄 彭群生 任意区域的边界扫描线转换 J 工程图学学报 1999 1 72 77 3 倪明田 吴良芝 计算机图形学 M 北京大学出版社 2008 Area Filling Algorithm Based On Scan Line Abstract Abstract graphics usually consist of non geometric properties such as point line surface body etc From the point of view of the processing technology graphics can be divided into t