ch04 二维填充图元生成0405.ppt

第4章 二维填充图元生成 4.1 多边形的扫描转换 4.1.1 概述 4.1.2 扫描线算法 4.1.3 其它算法 4.2 区域填充 4.2.1 简单种子填充 4.2.2 扫描线种子填充 4.3 图案填充 4.4 字符 第4章 二维填充图元生成 二维填充图元 用颜色或图案填充一个二维区域(由封闭的轮廓线包围)。 轮廓线通常是多边形。如果是曲线的话： 求出边界像素→区域填充； 可以采用直线段逼近→多边形的扫描转换。 第4章 二维填充图元生成 多边形的两种表示方法： 第4章 二维填充图元生成 多边形分类： 第4章 二维填充图元生成 4.1 多边形的扫描转换 4.1.1 概述 4.1.2 扫描线算法 4.1.3 其它算法 4.2 区域填充 4.2.1 简单种子填充 4.2.2 扫描线种子填充 4.3 图案填充 4.4 字符 4.1.1 概述－多边形的扫描转换 多边形的扫描转换： 把多边形的顶点表示转换为点阵表示。 也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内对应元素设置相应的灰度，通常称这种转换为多边形的扫描转换。 方法： 逐点判断法、扫描线算法、边缘填充法、栅栏填充法、边界标志法… 1. 扫描转换矩形 设矩形的四条边分另为xmin，xmax，ymin，ymax。 只要填充从ymin到ymax的每条扫描线上位于xmin和xmax之间的象素。 1. 扫描转换矩形 矩形也是多边形，那么为什么要单独处理矩形？ 扫描转换多边形的算法复杂，而矩形的应用非常多(窗口)，所以对其单独处理以提高效率。 共享边界将会被重绘两次，如何处理？ 1. 扫描转换矩形 考虑填充从BL(x，y)到TR（x+5，y+5）的矩形。 1. 扫描转换矩形 1. 扫描转换矩形 设矩形的四条边分另为xmin，xmax，ymin，ymax。 2. 逐点判断法 它是扫描转换多边形的最简单算法，即逐个判断绘图窗口内的象素是否在多边形内部。 如何判断点在多边形的内外？ 2. 逐点判断法 逐点判断的算法虽然程序简单，但不可取。原因是速度太慢。 主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，花费很多时间。 不适于实际使用，很少采用。 第4章 二维填充图元生成 4.1 多边形的扫描转换 4.1.1 概述 4.1.2 扫描线算法 4.1.3 其它算法 4.2 区域填充 4.2.1 简单种子填充 4.2.2 扫描线种子填充 4.3 图案填充 4.4 字符 4.1.2 扫描线算法 扫描线算法是扫描转换多边形的常用算法，它充分利用了相邻像素之间的连贯性，避免了逐点判断和反复求交计算，达到了减少计算量和提高算法效率的目的。 处理对象：非自交多边形 （边与边之间除了顶点外无其它交点）。 4.1.2 扫描线算法 开发和利用相邻象素之间的连贯性是光栅图形学算法的重要技巧。 扫描线算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。 4.1.2 扫描线算法 区域的连贯性：相邻两条扫描线构成一个水平长方形区域，并被多边形的边分割为若干梯形（一类位于多边形的内部；另一类在多边形的外部，且间隔排列）。只需知道该区域内任一梯形中一点关于多边形的内外关系，即可确定区域内所有梯形关于多边形的内外关系。 扫描线的连贯性：区域的连贯性在一条扫描线上的反映； 边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交。可通过与当前扫描线的交点计算与下一扫描线的交点(利用斜率)。（区域的连贯性在相邻两扫描线上的反映） 4.1.2 扫描线算法－原理 4.1.2 扫描线算法－原理 4.1.2 扫描线算法－数据结构及实现 算法中采用较灵活的数据结构。它由新边表ET（Edge Table）和活性边表AEL（Active Edge List）两部分组成。 求交点、排序、配对、填色 利用链表：与当前扫描线相交的边称为活性边(Active Edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活性边表AEL (AEL， Active Edge List)。它记录了多边形边沿扫描线的交点序列。 求交、排序、配对、填色 随扫描线的递增如何更新AEL？ 边的加入、删除，交点的更新。 新边表ET （Edge Table） ：按扫描线i对非水平边进行分类的指针数组。下端点的y坐标值等于i的边归入第i类(在该扫描线第一次出现的边)。同一类中，各边按x值（x值相等时，按Δx的值）递增的顺序排列。有多少条扫描线，就设多少类。 新边表ET （Edge Table） ：按扫描线i对非水平边进行分类的指针数组。下端点的y坐标值等于i的边归入第i类(在该扫描线第一次出现的边)。