计算机图形学3ppt课件.ppt

3 3区域填充算法 3 3 1基础知识 区域填充即给出一个区域的边界 要求对边界范围内的所有像素单元赋予指定的颜色代码 区域填充中最常用的是多边形填色 计算机图形学中 多边形区域有两种重要的表示方法 顶点表示和点阵表示 所谓顶点表示 即是用多边形的顶点序列来表示多边形 这种表示直观 几何意义强 占内存少 易于进行几何变换 但由于它没有明确指出哪些像素在多边形内 故不能直接用于区域填充 所谓点阵表示 则是用位于多边形内的像素集合来刻画多边形 这种表示丢失了许多几何信息 但便于进行填充 根据区域的定义 可以采用不同的填充算法 其中最具代表性的是 适应于顶点表示的扫描线类算法和适应于点阵表示的种子填充类算法 多边形的表示方法 顶点表示 点阵表示 填色算法分为两大类 扫描线填色 Scan LineFilling 算法 这类算法建立在多边形边界的矢量形式数据之上 可用于程序填色 也可用于交互填色 种子填色 SeedFilling 算法 这类算法建立在多边形边界的图像形式数据之上 并还需提供多边形边界内一点的坐标 所以 它一般只能用于人机交互填色 而难以用于程序填色 多边形填色一个首要的问题 是判断一个像素是在多边形内还是多边形外 数学上提供的方法是 扫描交点的奇偶数判断法 3 3 2多边形扫描线填充算法 算法的基本思想 多边形以n x array y array的形式给出 其中 x array y array中存放着多边形的n个顶点的x y坐标 用水平扫描线自底向上扫描由点线段构成的多段定义成的多边形 每根扫描线与多边形各边产生一系列交点 这些交点按照x坐标进行排序 将排序后的交点成对取出 作为两个端点 以所需要填的色彩画水平直线 多边形被扫描完毕后 填色也就完成 扫描线填充算法 P1 2 2 P6 2 7 P2 5 4 P3 11 1 P4 11 6 P5 5 8 A B C D F G 对于一条扫描线 多边形的填充过程可以分为四个步骤 1 求交 计算扫描线与多边形各边的交点 2 排序 把所有交点按x值递增顺序排序 3 配对 第一个与第二个 第三个与第四个等等 每对交点代表扫描线与多边形的一个相交区间 4 填色 把相交区间内的像素置成多边形颜色 把相交区间外的像素置成背景色 扫描线算法需要解决或改进的几个问题 1 如何处理奇数个交点 2 如何处理水平边 3 如何计算交点坐标 4 如何减少求交计算量 第一个问题 处理奇数个交点 规定 共享顶点的两条边分别落在扫描线的两边 交点只取1个 共享顶点的两条边都落在扫描线的下方 交点算0个 共享顶点的两条边都落在扫描线的上方 交点算2个 第二个问题 处理水平线 扫描线与多边形边界重合 当要区分边界和边界内区域时需特殊处理 则计1个交点 扫描线与边的求交点方法采用递归算法 以 x1 y1 x2 y2 为端点的边与第i 1条扫描线的交点为 可见 已知xi 则xi 1不需要重新计算 而是通过增加一个增量 x来获得 第三个问题 如何求交点坐标 使用增量法计算时 还需要知道一条边的最大y坐标 即如果边的最大y坐标大于扫描线 就不需要再对该边处理了 对于一根扫描线而言 与之相交的边只占多边形全部边的一部分 每根扫描线与多边形所有边求交的操作是一种浪费 把与当前扫描线相交的边称为活性边 并把它们按与扫描线相交的从左到右的顺序存放在链表中 这个链表叫活性边表 ActiveEdgeTable AET 活性边表的采用将多边形的边分成两个子集 与当前扫描线相交的边的集合 以及与当前扫描线不相交的边的集合 对后者不必进行求交运算 这样就提高了算法的效率 第四个问题 减少求交计算量 活性边表的数据结构应保存如下内容 第一项保存当前扫描线与边的交点坐标x值 第2项保存从当前扫描线到下一条扫描线间x的增量 x 第3项保存该边所交的最高扫描线号ymax 例如 y 3的扫描线的活性边表 AET 如下 利用边的连贯性和扫描线的连贯性 在当前扫描线处理完毕后 可以只对当前扫描线的活性边表进行更新 从而得到下一条扫描线的活性边表 为了方便活性边表的建立与更新 可为每一条扫描线建立一个新边表 NET 存放在该扫描线第一次出现的边 也就是说 若某边的较低端点为ymin 则该边就放在扫描线ymin的新边表中 下图是新边表的示意图 数据结构输入参数 顶点数以及顶点坐标数据结构 各条扫描线的新边表 NET 活性边表 AET 当出现新交点时 采用冒泡排序法 出现一条新边时 采用插入排序法 算法的描述 1 输入多边形顶点数及顶点坐标 2 建立各条扫描线的新边表NET 3 根据当前扫描值建立活性边表AET 4 求出扫描线与多边形边界交点 交点配对 填充 5 更新活化边表并重新排序 算法过程见教材P78 P84页 Plygonfill polydef color intcolor 多边形定义 polydef for 各条扫描线i 初始化新边表表头指针NET i 把ymin i的边放进边表NET i y 最低扫描线 初始化活性边表AET为空 For 各条扫描线i 把新边表NET i 中的边结点用插入排序法插入AET表 使之按x坐标递增顺序排列 遍历AET表 把配对交点之间的区间 左闭右开 上的各象素 x y 用SetPixel x y color 改写成象素颜色值 遍历AET表 把ymax i的结点从AET表中删除 并把ymax i结点的x值递增 x 若允许多边形的边自相交 则用冒泡排序法对AET表重新排序 Polygonfill 优点 对显示的每一个象素只访问一次 可使输入输出的要求降为最少 该算法与输入输出的细节无关 可以做到与设备无关性 缺点 对各种表的维持和排序开销太大 不利于硬件的实现 P1 2 2 P6 2 7 P2 5 4 P3 11 1 P4 11 6 P5 5 8 A B C D F G 算法描述实例 P9 2 7 P7 5 7 P5 11 8 P4 11 3 P2 5 1 P1 2 2 A 2 6 D 11 6 C 11 7 B 9 7 E 7 2 练习题 构造区域填充算法活性边表和新边表 P3 9 3 P6 7 6 P8 4 6 P8 2 7 P6 5 7 P4 11 8 P3 11 4 P2 5 1 P1 2 2 A 2 6 D 11 6 C 11 7 B 9 7 E 7 2 练习题 构造区域填充算法活性边表和新边表 P5 7 6 P7 4 6 0 8 练习题活性边表 8765 43210 练习题新边表 种子填充算法的基本思想是 从在一个封闭区域内部的一个已知像素出发 通过某种方法找到区域内的所有像素 3 3 3种子填充算法 算法要求区域是连通的连通性4连通 8连通4连通 从区域内任意一点出发 可通过上 下 左 右四个方向到达区域内的任意象素 8连通从区域内任意一点出发 可通过上 下 左 右 左上 左下 右上 右下八个方向到达区域内的任意象素 把位于给定区域的边界上的象素一一列举出来的方法称为边界表示法 边界填充算法 Boundary fillAlgorithm 列举出给定区域内所有象素的表示方法称为内点表示 泛滥填充算法 Flood fillAlgorithm 简单的种子填充算法 递归实现 基本方法 设种子像素为 x y 是四向连通区域内的一点 old color为区域内的原有像素的颜色 new color是要填充的颜色 递归填充的过程是如果种子像素是区域内原有颜色old color 说明该种子像素在区域内 则将像素置为被填充颜色new color 同时将种子像素的上 下 左 右像素当作种子递归调用填充递归算法 否则说明该像素已被填充 不再处理 VoidSeedFill4 intx inty intoldcolor intnewcolor if getpixel x y oldcolor setpixel x y newcolor SeedFill4 x y 1 oldcolor newcolor SeedFill4 x y 1 oldcolor newcolor SeedFill4 x 1 y oldcolor newcolor SeedFill4 x 1 y oldcolor newcolor 种子递归填充算法 递归算法原理和程序都很简单 但由于多次递归十分费时 且占用大量资源 将使计算机的效率非常低 采用栈结构来实现简单的种子填充算法 算法描述如下 1 将种子象素入栈 2 当栈非空时 重复 栈顶象素出栈 若该象素未填充 则将出栈象素置成填充色 以该象素为中心 检查出栈象素的4 邻接点 依 左上右下 顺序将非边界象素和未填充象素压入堆栈 若其中某个象素点不是边界色且未置成填充色 则把该象素入栈 栈结构实现的种子填充算法 算法缺点 有些像素被重复入栈 出栈时需要判断后决定是否填充 一方面降低了算法的效率 另一方面还要求很大的存储空间以实现栈结构 改进方法 扫描线种子填充算法 基本思想 在任意一个扫描线与边界的相交区间 含若干个连续像素 中 只取一个种子像素 一次填充操作针对区域内扫描线上连续的像素 扫描线种子填充算法的原理 1 将种子象素入栈 2 当栈非空时 重复 栈顶象素出栈 沿扫描线对出栈像素的左右像素进行填充 直至遇到边界像素为止 即每出栈一个像素 就对包含该像素的整个区间进行填充 上述区间内最左 右的像素分别记为xl和xr 在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或已填充的象素 若存在非边界 未填充边界的象素 则把每一区间的最左或最右象素取作种子象素入栈 3 4 1字符编码标准 1 国际字符编码 美国信息交换标准码即ASCII码 2 国际汉字编码即国家标准信息交换编码CB2312 1980 3 4字符处理 字符库 点阵字符库向量字符库 3 4 2点阵式字符 点阵式字符将字符形状表示为一个矩形点阵 由点阵中点的不同值表达字符的形状 使用点阵式字符时 需将字库中的矩形点阵复制到缓冲器中指定的单元中去 在复制过程中 可以施加变换 以获得简单的变化 3 4 2矢量式字符 矢量式字符将字符表达为点坐标的序列 相邻两点表示一条矢量 字符的形状便由矢量序列刻画 B 是由顶点序列 a b c d e f e g h i j k j a l 的坐标表达 可以接受任何对于图形的操作 点阵字符与矢量字符的比较 1 字符变换不同 对点阵字符的变换需要对每一个像素进行 变换 放大或旋转时会失真 表示矢量字符的是终点坐标 对矢量字符的变换是对端点的变换 属于几何变换 不会影响效果 2 占用空间不同 矢量字符占用空间少 矢量字符只需保存一套字符 其他不同型号的字符可以通过相应的几何变换来产生 3 矢量字符美观 除了直线段外 还可以用二次曲线段 三次曲线段等来表示 使字符更加美观 变换更方便 用离散量表示连续量引起的失真现象称之为走样 只要在生成图形时采用点采样技术 都会导致图形走样现象发生 因此从根本上来说 反走样的方法有两种 1 提高采样率 也即提高屏幕分辨率 2