填充图元的生成.ppt

重庆邮电学院 第四章 填充图元的生成 扫描转换矩形 扫描转换多边形 扫描转换扇形区域 区域填充 以图像填充区域 字符的表示与输出 多边形的扫描转换与区域填充 多边形有两种重要的表示方法：顶点表示和点阵表示。 多边形的扫描转换:把多边形的顶点表示转换为点阵表示。 区域可采用内点表示和边界表示两种表示形式。 区域填充:指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。 扫描转换的一般步骤 确定哪些像素位于填充图元的内部 扫描转换：矩形、多边形、扇形 确定以什么颜色填充这些像素 均匀填色，图像填充 扫描转换矩形 方法： 扫描转换矩形 问题： 矩形是简单的多边形，那么为什么要单独处理矩形？(比一般多边形可简化计算。应用非常多，如窗口系统。 ) 光栅系统的特点:边有宽度. 共享边界如何处理？ 原则：左闭右开，下闭上开 扫描转换多边形 多边形的表示方法 顶点表示 点阵表示 扫描转换多边形： 将顶点表示形式转换 成点阵表示形式 三种方法： 逐点判断法； 扫描线算法； 边缘填充法。 扫描转换多边形--逐点判断法 逐个判断绘图窗口内的像素： 射线法： 累计角度法 编码法； 算法优点：简单 算法缺点：计算量太大，速度慢 扫描转换多边形--逐点判断法 逐点判断算法 方法 扫描转换多边形--逐点判断法 问题：如何判别点(x,y)关于多边形区域P的内外关系？ 射线法 步骤： 从待判别点v发出射线 求交点个数k K的奇偶性决定了 点与多边形的内外关系， 若交点个数偶数，V点在外边，反之在多边形内部 奇异情况处理 交点通过多边形顶点 扫描转换多边形--逐点判断法 累计角度法 步骤 从v点向多边形P顶点发出射线，形成有向角 ,取绝对值小于180度的角 计算有向角的和 扫描转换多边形--逐点判断法 累计角度法 奇异情况处理 对于落在边上的点,作预处理 由于所求解以2pi为周期, 应取角度的绝对值小于pi的解.等于pi时,点落在边上,已在预处理过程中处理掉了. 扫描转换多边形--逐点判断法 累计角度方法的离散方法（编码方法） 扫描转换多边形--逐点判断法 扫描转换多边形--逐点判断法 扫描转换多边形--扫描线算法 扫描线算法 目标：利用像素之间的连贯性，提高算法效率 处理对象：非自交多边形 扫描转换多边形--扫描线算法 扫描线的连贯性：扫描线与多边形有偶数个交点，排序后(1,2), (3,4)…区段位于多边形内部。 利用扫描线的连贯性填充每一条扫描线位于多边形内部的区段 扫描转换多边形--扫描线算法 基本原理 一条扫描线与多边形的边有偶数个交点 步骤： 求交 排序 填充（交点配对，填充区段） 扫描转换多边形--扫描线算法 利用边的连贯性(一条边与相继的两条扫描线的交点的连贯性),提高求交效率 第一类交点：新出现的边与扫描线的交点 第二类交点：位于同一条边上的后继交点 扫描转换多边形--扫描线算法 第二类交点可以利用边的连贯性来获得 边的连贯性与扫描转换直线段算法中用到的递推关系完全一致,所以求交过程中可以直接利用直线段的中点算法递推式. 用于线画图元扫描转换的四舍五入原则,将导致部分像素位于多边形之外.为了使得所求得的像素点都落在多边形区域内,需要对算法作一些改进. 扫描转换多边形--扫描线算法 交点的取整规则 要求：使生成的像素全部位于多边形之内 假定非水平边与扫描线y=e 相交，交点的合作标为x, 规则如下 扫描转换多边形--扫描线算法 X为小数 (a)交点位于左边之上，向右取整 (b)交点位于右边之上，向左取整 扫描转换多边形--扫描线算法 2. (x,e)落在像素之上 (a) (x,e)位于左边之上，属于多边形 (b) (x,e)位于右边之上，不属于多边形 扫描转换多边形--扫描线算法 3. 交点位于多边形的顶点 (a) 算作1个交点 (b) 算作1个交点 (c) 算作2个交点 (d) 算作0个交点 扫描转换多边形--扫描线算法 特殊情况处理 水平边:扔掉！ 尖角：反混淆 扫描转换多边形--扫描线算法 数据结构 边 边的分类表E 按照边的下端点y坐标对非水平边进行分类的指针数组 活化边表AEL 纪录与当前扫描线相交的边（交点） 扫描转换多边形--扫描线算法 几个概念 活性边：与当前扫描线相交的边。按交点x的增量顺序存放在一个链表中； 活性边表：活性边表的每个结点存放对应边的有关信息。 边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交。 扫描线的连贯性：当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序可能相同或类似。 扫描转换多