第第4 4章章 二维填充图元生成二维填充图元生成1第4章 二维填充图元生成4.1 多边形的扫描转换 4.1.1 概述 4.1.2 扫描线算法 4.1.3 其它算法 4.2 区域填充 4.2.1 简单种子填充 4.2.2 扫描线种子填充 4.3 图案填充 4.4 字符2第4章 二维填充图元生成n二维填充图元n用颜色或图案填充一个二维区域(由封闭的轮廓 线包围)。n轮廓线通常是多边形。如果是曲线的话：n求出边界像素区域填充；n可以采用直线段逼近多边形的扫描转换。3第4章 二维填充图元生成n多边形的两种表示方法：n顶点表示（多边形）n用多边形顶点的序列来刻划多 边形。n直观、几何意义强、占内存少 、易于几何变换；n不能直接用于光栅系统显示。n点阵表示（区域）n用象素的集合(边界/内部)来 刻画多边形。n失去了许多重要的几何信息；n便于光栅系统显示。 4第4章 二维填充图元生成n多边形分类：凸多边形凹多边形含内环的多边形5第4章 二维填充图元生成4.1 4.1 多边形的扫描转换多边形的扫描转换 4.1.1 4.1.1 概述概述 4.1.2 扫描线算法 4.1.3 其它算法 4.2 区域填充 4.2.1 简单种子填充 4.2.2 扫描线种子填充 4.3 图案填充 4.4 字符64.1.1 概述多边形的扫描转换n多边形的扫描转换：n把多边形的顶点表示转换为点阵表示。n也就是从多边形的给定边界出发，求出位于 其内部的各个象素，并给帧缓冲器内对应元 素设置相应的灰度，通常称这种转换为多边 形的扫描转换。n方法：n逐点判断法、扫描线算法、边缘填充法、栅 栏填充法、边界标志法71. 扫描转换矩形n设矩形的四条边分另为 xmin，xmax，ymin，ymax 。n只要填充从ymin到ymax的 每条扫描线上位于xmin和 xmax之间的象素。ymaxyminxminxmaxvoid FillRectangle ( Rectangle *rect，int color ) int x，y;for ( y = rect-ymin；y ymax；y+ )for ( x = rect-xmin；x xmax；x+ )SetPixel ( x，y，color ); /*end of FillRectangle ()*/81. 扫描转换矩形n矩形也是多边形，那么为什么要单独处理矩形？n扫描转换多边形的算法复杂，而矩形的应用非常 多(窗口)，所以对其单独处理以提高效率。n共享边界将会被重绘两次，如何处理？属于谁？n原则：左、下边的象素属 于矩形，而右、上边的象 素不属于矩形。n左闭右开，下闭上开。n边界像素重绘问题；n填充扩大化问题。91. 扫描转换矩形n考虑填充从BL(x，y)到TR（x+5，y+5）的矩形。void FillRectangle ( Rectangle *rect，int color ) int x，y;for ( y = rect-ymin；y ymax；y+ )for ( x = rect-xmin；x xmax；x+ )SetPixel ( x，y，color ); /*end of FillRectangle ()*/101. 扫描转换矩形BL(x,y)TR(x+5,y+5 )Area=6*6=36 pixelsArea=5*5=25 pixelsn矩形面积为：6*636 pixelsn矩形实际面积应为:(x+5)-x*(y+5)-y25 pixelsn采用左闭右开，下闭 上开的原则对边界象 素进行处理可保证矩 形的面积不被扩大。n对FillRectangle ()进行 修改。 111. 扫描转换矩形n设矩形的四条边分另为 xmin，xmax，ymin，ymax 。ymaxyminxminxmaxvoid FillRectangle ( Rectangle *rect，int color ) int x，y;for ( y = rect-ymin；y ymax；y+ )for ( x = rect-xmin；x xmax；x+ )SetPixel ( x，y，color ); /*end of FillRectangle ()*/ 122. 逐点判断法n它是扫描转换多边形的最简单算法，即逐个 判断绘图窗口内的象素是否在多边形内部。n如何判断点在多边形的内外？132. 逐点判断法n逐点判断的算法虽然程序简单，但不可取 。原因是速度太慢。n主要是由于该算法割断了各象素之间的联 系，孤立地考察各象素与多边形的内外关 系，使得几十万甚至几百万个象素都要一 一判别，每次判别又要多次求交点，花费 很多时间。n不适于实际使用，很少采用。14第4章 二维填充图元生成4.1 4.1 多边形的扫描转换多边形的扫描转换 4.1.1 概述 4.1.2 4.1.2 扫描线算法扫描线算法 4.1.3 其它算法 4.2 区域填充 4.2.1 简单种子填充 4.2.2 扫描线种子填充 4.3 图案填充 4.4 字符154.1.2 扫描线算法n扫描线算法是扫描转换多边形的常用算法， 它充分利用了相邻像素之间的连贯性，避免 了逐点判断和反复求交计算，达到了减少计 算量和提高算法效率的目的。n处理对象：非自交多边形 （边与边之间除了顶 点外无其它交点）。164.1.2 扫描线算法n开发和利用相邻象素之间的连贯性是光栅图 形学算法的重要技巧。n扫描线算法综合利用了区域的连贯性、扫描 线的连贯性和边的连贯性等三种形式的连贯 性。174.1.2 扫描线算法n区域的连贯性：相邻两条扫描线构成一个水平长方形区域，并 被多边形的边分割为若干梯形（一类位于多边形的内部；另一 类在多边形的外部，且间隔排列）。只需知道该区域内任一梯 形中一点关于多边形的内外关系，即可确定区域内所有梯形关 于多边形的内外关系。 n扫描线的连贯性：区域的连贯性在一条扫描线上的反映；n边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描 线相交。可通过与当前扫描线的交点计算与下一扫描线的交点( 利用斜率)。（区域的连贯性在相邻两扫描线上的反映）y=iXe1Xe2Xe3Xe4Xe8Xe7 y=i+1Xd1Xd2Xd3Xd4Xd8Xd7P0 P8P7P1P2P3P4P5P618n根据扫描线的连贯性可知：一 条扫描线与多边形的交点中， 入点和出点之间所有点都是多 边形的内部点。n所以，对所有的扫描线填充入 点到出点之间的点就可填充多 边形。n如何具体实现（如何找到入点 、出点）？4.1.2 扫描线算法原理02468 10 122468101 234入点出点内部点194.1.2 扫描线算法原理n根据区域的连贯性，分为3个步骤 ：(1)求出扫描线与多边形所有边的 交点；(2)把这些交点按x坐标值以升序 排列；(3)对排序后的交点进行奇偶配对 ，对每一对交点间的区域进行 填充。 n步骤(3)如上图：对y8的扫描线，对交点序列按x坐标升 序排序得到的交点序列是(2,4,9,13)，然后对交点2与4之间 、9与13之间的所有象素点进行填充。n n求交点、排序、配对、填色求交点、排序、配对、填色02468 10 12246810204.1.2 扫描线算法数据结构及实现n算法中采用较灵活的数据结构。它由边分 类表ET（Edge Table）和活化边表AEL（ Active Edge List）两部分组成。21n n求交点、排序、配对、求交点、排序、配对、填色填色n利用链表：与当前扫描线相交的边称为活化边(Active Edge) ，把它们按与扫描线交点x坐标递增的顺序存入一个链表中， 称为活化边表AEL (AEL， Active Edge List)。它记录了多边形 边沿扫描线的交点序列。y=6，AEL：y=6y=702468 10 12246810P3P2P1P4P5P6e3e4e2 e1e5e6e2e59 2 011 13 0 ymaxxx AEL中每个对象需要存放的 信息： ymax：边所交的最高扫描线； x：当前扫描线与边的交点； x：从当前扫描线到下一条扫 描线之间的x增量 next：指向下一对象的指针。活化边表活化边表AELAEL22n n求交、排序、配对、求交、排序、配对、填色填色n随扫描线的递增如何更新AEL？n边的加入、删除，交点的更新。y=6，AEL：y=7，AEL：y=6y=702468 10 12246810P3P2P1P4P5P6e3e4e2 e1e5e6e2e59 2 011 13 0 ymaxxxe2e39 2 09 7 -2.5e4e511 7 1.511 13 0 建立一个新的数据结构建立一个新的数据结构 ： 边分类表ET活化边表活化边表AELAEL23n边分类表ET （Edge Table） ：按扫描线i对非水平边进行 分类的指针数组。下端点的y坐标值等于i的边归入第i类( 在该扫描线第一次出现的边)。同一类中，各边按x值（x 值相等时，按x的值）递增的顺序排列。有多少条扫描线 ，就设多少类。02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e6ymaxxx ET中每个对象需要存放的信 息： ymax：边所交的最高扫描线； x：边的下端点的x坐标； x：从当前扫描线到下一条扫 描线之间的x增量(边的斜率 的倒数)； next：指向下一对象的指针。24n边分类表ET （Edge Table） ：按扫描线i对非水平边进行 分类的指针数组。下端点的y坐标值等于i的边归入第i类( 在该扫描线第一次出现的边)。同一类中，各边按x值（x 值相等时，按x的值）递增的顺序排列。有多少条扫描线 ，就设多少类。e2e5e1e6e3e4ET（桶）同一类中的边按x、 x的递增顺序排列02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e69 7 -2.511 7 1.5 11 13 0 92 0 3 7 -2.55 7 1.5 7 6 5 4 3 2 1 0ymaxxx254.1.2 扫描线算法数据结构及实现n算法中采用较灵活的数据结构。它由边分类表ET （Edge Table）和活化边表AEL（Active Edge List ）两部分组成。nET和AEL中的基本元素称为“边”（Edge）。n边的结构“Edge”由以下四个域组成：nymax：边的上端点的y坐标；nx：在ET中表示边的下端点的x坐标；在AEL中则表示边与扫描线的交点的x坐标；nx：边的斜率的倒数；nnext：指向下一“边”的指针。typedef struct int ymax；float x，deltax；Edge *next；Edge； ymaxxx 264.1.2 扫描线算法几点规则n n求交点、排序、配对、填色求交点、排序、配对、填色n交点与多边形顶点重合时， 会导致“配对”失败，如何处 理？n下闭上开02468 10 12246810274.1.2 扫描线算法几点规则n扫描线与多边形的顶点相交时，交点的取舍(保证交 点正确配对)。n检查该顶点的两相邻边在扫描线的哪一侧： 只要检查顶点的两条边的另外两个端点的Y值，两 个Y值中大于交点Y值的个数是0，1，2，来决定 取0，1，2个交点。(下闭上开)(a)P0P2P1P0P2P1P0P2P1P0P2P1(b)(c)(d)y=e284.1.2 扫描线算法算法描述1.建立ET，置y为ET中非空桶的最小序号； 2.置AEL表为空，且把y桶中ET表的边加入AEL表中； 3.while AEL表中非空 do begin 4. 对AEL表中的x、 x按升序排列； 5. 按照AEL表中交点前后次序，在每对奇偶交点间的x段予以填充； 6. 计算下一条扫描线：y=y+1； 7. if 扫描线 y=ymax then 从AEL