第四讲：二维图形填充.ppt

内容摘要 字符 矢量字符 点阵字符 字型技术 字符裁剪 反走样基础 提高分辩率 简单的区域反走样算法 卷积积分与反走样算法 半色调技术 内容摘要 区域填充 有序边表算法 边填充算法 边标志算法 种子填充算法 圆域的填充 线宽与线型的处理 直线线宽的处理（笔型：线、方形） 圆弧线宽的处理（笔型：线、方形） 线型的处理 有序边表算法 填充扩大化问题的解决 活性边与活性边表处理方法 新边表处理方法 边填充算法 栅栏填充算法 边标志算法 种子填充算法的连通区域 简单种子填充算法 扫描线种子填充算法 圆域的填充 方形刷子的原理 方刷子的活性边表技术 圆弧线宽的处理（笔） 圆弧线宽的处理(填充法) 线型的处理 字符 矢量字符 点阵字符 字型技术 字型技术 字符裁剪 反走样 通过提高分辩率反走样 简单的区域反走样算法 卷积积分与反走样算法 半色调技术 前面所介绍的反走样技术，都是利用多级光强提高视觉分辩率的技术，而半色调技术则是用最少的光强级别，一般为黑与白来提高视觉分辨的。对于给定的分辩率，通过将几个象素被组合成一个单元来获得多级光强。如在黑白显示器中将四个象素组成一个单元，可以产生5种光强，如右上图 (a)。而(b)、（c）不是组合出来的光强模式，因为采用(b)、( c )会产生细微的结构图，如水平或垂直的光线条。 一般来说，对于两级灰度显示器可能构成的光强数等于单元中象素个数加1。增大单元尺寸可以获得更多的灰度数，如图中为3?3单元。单元也可以为长方形，如右图下。 可见，单元越大，产生的光强就越多。半色调技术是以牺牲空间分辩率为代价的，它的成功与人们的视觉系统引起的调和平滑离散信息的积分作用分不开。 通过上面的讨论，对于图形的走样可以采用不同的方法来克服，这里只做了简单的说明 Ymax 扫描线Y值? 是,从活性表中删掉该线段记录。 Ymin 扫描线Y? 插入新边表中。 本节所介绍的有序边表算法对显示的每个象素只访问一次，这样，输入／输出的要求可降为最少。又由于该算法与输入／输出的细节无关，因而它也与设备无关。该算法的主要缺点是对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。 扫描线与圆域的相交区间可以通过计算扫描线与圆域边界（圆）的交点来确定，而交点的计算可以使用中点画圆法来进行。在该算法的迭代计算过程中，若在某一步迭代之后，y值改变，那么上一步迭代的x值即为改变之前的y值所对应的扫描线与圆边界的交点。为了避免填充扩大化，可把所得交点代入F(x，y)=x2＋ y2 －R2中，并判断符号，以便确定该点是在圆内还是在圆外。若在圆外，则对应端点应往圆内缩进一个象素。函数F的计算可以采用增量法提高效率。 可以为每一条扫描线建立一个新圆表，存放在该行第一次出现的圆的有关信息，然后为当前扫描线设置一个活性圆表。由于一条线与一个圆只能相交一个区间，所以在活性圆表中每个圆只需一个结点即可。结点中存放当前扫描线的区间端点，以及用于计算下一条扫描线与圆相交的区间端点所需的增量。该增量用于在当前扫描线处理完毕之后，对端点坐标进行更新计算，以便得到下条扫描线的区间端点。 * 一般多边形的填充过程，对于一条扫描线Y值，可以分为四个步骤： 求交点X：计算扫描线与多边形各边的交点X的值； 排序：把所有相交点x按递增顺序进行排序； 交点配对：第一个与第二个，第三个与第四个等等。每对交点就代表扫描线与多边形的一个相交区间； 区间填色：把这些相交区间内的象素置成多边形色，把相交区间外的象素置成背景色。 特殊顶点处理: P1、P3情况:相同交点取1个; P2、P5情况:相同交点取2个; P4、P6情况:相同交点取0个; (下闭上开原则，防止填充扩大化) 采用下闭上开、左闭右开原则，防止填充扩大化。 例如填充左下角为（1，1），右上角为（3，3）的区域，得到的图形如图所示九个象素被点亮，而实际区域应是黄区所示。 采取的措施：在具体实现时，只要对扫描线与多边形的相交区间取“左闭右开”。在上述讨论中，当扫描线与多边形顶点相交时，所使用的交点取舍的方法，保证了多边形的“下闭上开”，丢弃上方水平边以及上方非水平边上作为局部最高点的顶点。 如左图 一个多边形与若干扫描线。 为了计算每条扫描线与多边形各边的交点，最简单的方法是把多边形的所有边放在一个表中。在处理每条扫描线时，按顺序从表中取出所有的边，分别与扫描线求交点。这样处理效率很低。这是因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交。若在处理每条扫描线时，不分青红皂白地把所有边都拿来与扫描线求交点，则其中绝大多数都是徒劳无用的。如果采用活性边表，则可减少许多计算。 扫描线依次变化为1,2,3,4,5,6,7,8,…... x是边与当前扫描线的交点； ?x是该边从当前扫描线到下一扫