《维填充图元生成》ppt课件

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 字符 第4章 二维填充图元生成 n二维填充图元 n用颜色或图案填充一个二维区域(由封锁的 轮廓线包围)。 n轮廓线通常是多边形。假设是曲线的话： n求出边境像素区域填充； n可以采用直线段逼近多边形的扫描转换。 第4章 二维填充图元生成 n多边形的两种表示方法： n顶点表示多边形 n用多边形顶点的序列来刻 划多边形。 n直观、几何意义强、占内 存少、易于几何变换； n不能直接用于光

2、栅系统显 示。 n点阵表示区域 n用象素的集合(边境/内部) 来描写多边形。 n失去了许多重要的几何信 息； n便于光栅系统显示。 第4章 二维填充图元生成 n多边形分类： 凸多边形凹多边形含内环的多边形 第4章 二维填充图元生成 4.1.1 概述多边形的扫描转换 n多边形的扫描转换： n把多边形的顶点表示转换为点阵表示。 n也就是从多边形的给定边境出发，求 出位于其内部的各个象素，并给帧缓 冲器内对应元素设置相应的灰度，通 常称这种转换为多边形的扫描转换。 n方法： n逐点判别法、扫描线算法、边缘填充 法、栅栏填充法、边境标志法 1. 扫描转换矩形 n设矩形的四条边分另为xmin， xmax

3、，ymin，ymax。 n只需填充从ymin到ymax的 每条扫描线上位于xmin和 xmax之间的象素。 ymax ymin xminxmax 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 ()*/ 1. 扫描转换矩形 n矩形也是多边形，那么为什么要单独处置矩形？ n扫描转换多边形的算法复杂，而矩形的运用

4、非常多 (窗口)，所以对其单独处置以提高效率。 n共享边境将会被重绘两次，如何处置？ 属于谁？ n原那么：左、下边的象素 属于矩形，而右、上边的 象素不属于矩形。 n左闭右开，下闭上开。 n边境像素重绘问题； n填充扩展化问题。 1. 扫描转换矩形 n思索填充从BL(x，y)到TRx+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 ); /

5、*end of FillRectangle ()*/ 1. 扫描转换矩形 BL(x,y) TR(x+5,y+5) Area=6*6 =36 pixels Area=5*5 =25 pixels n矩形面积为： n6*636 pixels n矩形实践面积应为: n(x+5)-x*(y+5)- y n25 pixels n采用左闭右开，下闭 上开的原那么对边境 象素进展处置可保证 矩形的面积不被扩展。 n对FillRectangle ()进展 修正。 1. 扫描转换矩形 n设矩形的四条边分另为xmin， xmax，ymin，ymax。 ymax ymin xminxmax void FillRec

6、tangle ( 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 ()*/ 2. 逐点判别法 n它是扫描转换多边形的最简单算法，即逐个 判别绘图窗口内的象素能否在多边形内部。 n如何判别点在多边形的内外？ 2. 逐点判别法 n逐点判别的算法虽然程序简单，但不可取。 缘由是速度太慢。 n主要是由于该算法割断了各象素之间的联 络，孤立地调查各象素与多边形

7、的内外关 系，使得几十万甚至几百万个象素都要一 一判别，每次判别又要多次求交点，破费 很多时间。 n不适于实践运用，很少采用。 第4章 二维填充图元生成 4.1.2 扫描线算法 n扫描线算法是扫描转换多边形的常用算法， 它充分利用了相邻像素之间的衔接性，防止 了逐点判别和反复求交计算，到达了减少计 算量和提高算法效率的目的。 n处置对象：非自交多边形 边与边之间除了 顶点外无其它交点。 4.1.2 扫描线算法 n开发和利用相邻象素之间的衔接性是光栅图 形学算法的重要技巧。 n扫描线算法综合利用了区域的衔接性、扫描 线的衔接性和边的衔接性等三种方式的衔接 性。 4.1.2 扫描线算法 n区域的衔

8、接性：相邻两条扫描线构成一个程度长方形区域，并 被多边形的边分割为假设干梯形一类位于多边形的内部；另 一类在多边形的外部，且间隔陈列。只需知道该区域内任一 梯形中一点关于多边形的内外关系，即可确定区域内一切梯形 关于多边形的内外关系。 n扫描线的衔接性：区域的衔接性在一条扫描线上的反映； n边的衔接性：某条边与当前扫描线相交，也能够与下一条扫描 线相交。可经过与当前扫描线的交点计算与下一扫描线的交点 (利用斜率)。区域的衔接性在相邻两扫描线上的反映 y=i Xe1 Xe 2 Xe3Xe 4 Xe8 Xe7 y=i+1 Xd1Xd2Xd3Xd4Xd8Xd7 P0 P8 P7 P1 P2 P3 P

9、4 P5 P6 n根据扫描线的衔接性可知：一 条扫描线与多边形的交点中， 入点和出点之间一切点都是多 边形的内部点。 n所以，对一切的扫描线填充入 点到出点之间的点就可填充多 边形。 n如何详细实现如何找到入点、 出点？ 4.1.2 扫描线算法原理 02468 10 12 2 4 6 8 10 1 234 入点 出点 内部点 4.1.2 扫描线算法原理 n根据区域的衔接性，分为3个步骤： n(1)求出扫描线与多边形一切边的 交点； n(2)把这些交点按x坐标值以升序陈 列； n(3)对排序后的交点进展奇偶配对， 对每一对交点间的区域进展填充。 n步骤(3)如上图：对y8的扫描线，对交点序列按x

10、坐标升 序排序得到的交点序列是(2,4,9,13)，然后对交点2与4之 间、9与13之间的一切象素点进展填充。 n求交点、排序、配对、填色 02468 10 12 2 4 6 8 10 4.1.2 扫描线算法数据构造及 实现 n算法中采用较灵敏的数据构造。它由边分 类表ETEdge Table和活化边表AEL Active Edge List两部分组成。 y=6，AEL： y=6 y=7 02468 10 12 2 4 6 8 10P 3 P 2 P 1 P 4 P 5 P 6 e 3 e 4 e 2 e 1 e 5 e 6 e2e5 9 2 011 13 0 ymax x x nAEL中每个

11、对象需求存放的 信息： nymax：边所交的最高扫描线； nx：当前扫描线与边的交点； nx：从当前扫描线到下一条 扫描线之间的x增量 nnext：指向下一对象的指针。 y=6，AEL： y=7，AEL： y=6 y=7 02468 10 12 2 4 6 8 10P 3 P 2 P 1 P 4 P 5 P 6 e 3 e 4 e 2 e 1 e 5 e 6 e2e5 9 2 011 13 0 ymax x x e2e3 9 2 09 7 -2.5 e4e5 11 7 1.511 13 0 n边分类表ET Edge Table ：按扫描线i对非程度边进 展分类的指针数组。下端点的y坐标值等于i

12、的边归入第i 类(在该扫描线第一次出现的边)。同一类中，各边按x值 x值相等时，按x的值递增的顺序陈列。有多少条扫 描线，就设多少类。 02468 10 12 2 4 6 8 10P 3 P 2 P 1 P 4 P 5 P 6 e 3 e 4 e 2 e 1 e 5 e 6 ymax x x nET中每个对象需求存放的信 息： nymax：边所交的最高扫描线； nx：边的下端点的x坐标； nx：从当前扫描线到下一条 扫描线之间的x增量(边的斜 率的倒数)； nnext：指向下一对象的指针。 n边分类表ET Edge Table ：按扫描线i对非程度边进 展分类的指针数组。下端点的y坐标值等于i

13、的边归入第i 类(在该扫描线第一次出现的边)。同一类中，各边按x值 x值相等时，按x的值递增的顺序陈列。有多少条扫 描线，就设多少类。 e2 e 5 e1e 6 e3e4 ET桶 同一类中的边按x、 x的递增顺序陈列 02468 10 12 2 4 6 8 10P 3 P 2 P 1 P 4 P 5 P 6 e 3 e 4 e 2 e 1 e 5 e 6 9 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 0 ymax x x 4.1.2 扫描线算法数据构造及 实现 n算法中采用较灵敏的数据构造。它由边分类表ET Edge T

14、able和活化边表AELActive Edge List 两部分组成。 nET和AEL中的根本元素称为“边Edge。 n边的构造“Edge由以下四个域组成： nymax：边的上端点的y坐标； nx：在ET中表示边的下端点的 n x坐标；在AEL中那么表示边 n 与扫描线的交点的x坐标； nx：边的斜率的倒数； nnext：指向下一“边的指针。 typedef struct int ymax； float x，deltax； Edge *next； Edge； ymax x x 4.1.2 扫描线算法几点规那么 02468 10 12 2 4 6 8 10 4.1.2 扫描线算法几点规那么 n扫

15、描线与多边形的顶点相交时，交点的取舍(保证交 点正确配对)。 n检查该顶点的两相邻边在扫描线的哪一侧： n只需检查顶点的两条边的另外两个端点的Y值， 两个Y值中大于交点Y值的个数是0，1，2，来决议取 0，1，2个交点。(下闭上开) (a) P0 P2 P1 P0 P2 P1 P0 P2 P1 P0 P2 P1 (b) (c) (d) y=e 4.1.2 扫描线算法算法描画 n建立ET，置y为ET中非空桶的最小序号； n置AEL表为空，且把y桶中ET表的边参与AEL表中； nwhile AEL表中非空 do begin n 对AEL表中的x、 x按升序陈列； n 按照AEL表中交点前后次序，在

16、每对奇偶交点间的x段予 以填充； n 计算下一条扫描线：y=y+1； n if 扫描线 y=ymax then 从AEL表中删除这些边； n 对在AEL表中的其他边，计算与下一条扫描线的交点： x=x +x n 按照扫描线y值把ET表中相应桶中的边参与AEL表中； end nend of algorithm e2 e 5 e1e 6 e3e4 :ET 02468 10 12 2 4 6 8 10P 3 P 2 P 1 P 4 P 5 P 6 e 3 e 4 e 2 e 1 e 5 e 6 9 7 -2.511 7 1.5 11 13 0 92 0 3 7 -2.55 7 1.5 7 6 5 4

17、 3 2 1 0 AEL=空 y=1 AEL= (7，1) (7，1) (4.5，2) (8.5，2) (2，3) (10，3) (2，4) (11.5，4) (2，5) (13，5) (2，6) (13，6) AEL： 3 7 -2.55 7 1.5 3 4.5-2.55 8.5 1.5y=2 AEL= 9 205 10 1.5y=3 AEL= 9 205 11.5 1.5y=4 AEL= 9 2011 130 y=5 AEL= 9 2011 130 y=6 AEL= e2 e 5 e1e 6 e3e4 :ET 02468 10 12 2 4 6 8 10P 3 P 2 P 1 P 4 P

18、5 P 6 e 3 e 4 e 2 e 1 e 5 e 6 9 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 0 y=7 AEL= (2，7) (7，7) (7，7) (13，7) (2，6) (13，6) AEL： 9 209 7 -2.5 11 7 1.511 13 0 9 2011 130 y=6 AEL= y=8 AEL= (2，8) (4.5，8) (8.5，8) (13，8) 9 209 4.5-2.5 11 8.51.511 13 0 y=9 AEL= (10，9) (13，9) 11 10 1.511 13

19、0 e2 e 5 e1e 6 e3e4 :ET 02468 10 12 2 4 6 8 10P 3 P 2 P 1 P 4 P 5 P 6 e 3 e 4 e 2 e 1 e 5 e 6 9 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 0 y=10 AEL= (11.5，10) (13，10) AEL： 11 11.5 1.5 y=9 AEL= (10，9) (13，9) 11 10 1.511 13 0 11 13 0 y=11 AEL= 空 练习 n写出如下图的多边形的边分类表ET及 y=7和y=1对应的活性边表AEL

20、 0 24681012 2 4 6 8 10 P1(2,2) e3 e4 e2 e1 e5 y=1 y=7 P2(5,1) P3(11,3) P4(11,8) P5(2,7) 0 24681012 2 4 6 8 10 P1(2,2) e3 e4 e2 e1 e5 y=1 y=7 P2(5,1) P3(11,3) P4(11,8) P5(2,7) e3 e 5 e1e 2 e4 8 29 8 11 0 2 5 -33 53 7 6 5 4 3 2 1 0 72 0 ymax x x 0 24681012 2 4 6 8 10 P1(2,2) e3 e4 e2 e1 e5 y=1 y=7 P2(

21、5,1) P3(11,3) P4(11,8) P5(2,7) y=7，AET： y=1，AET： e4e3 8 2 98 11 0 ymax x x e1e2 2 5 -335 3 4.1.2 扫描线算法几点规那么 02468 10 12 2 4 6 8 10 n交点的取整 n利用衔接性计算出的 交点能够导致部分像 素位于多边形之外。 n目的：使生成的像素 尽量位于多边形之内， 并且防止填充扩展化。 4.1.2 扫描线算法几点规那么 4.1.2 扫描线算法几点规那么 n假定非程度边与扫描线y=e相交，交点的横坐标为x。 假设x为小数，即交点落于扫描线上两个相邻像素之 间时，规那么如下： n(a

22、) 交点位于左边之上(入点)，向右取整； n(b) 交点位于右边之上(出点)，向左取整； y=e (x,e) (a) y=e (x,e) (b) 4.1.2 扫描线算法几点规那么 n边境象素的取舍问题，防止填充扩展化。 n假设x为整数，即交点落于像素点上边境象 素。 n落在右边境的象素(出点)不予填充； n“左闭右开 y=e (x,e) (a) y=e (x,e) (b) 4.1.2 扫描线算法几点规那么 n1.边境上的象素: “左闭右开 ，将左边境的点算 为内部，而将右边境的点算为外部。 n2.顶点：“下闭上开，即丢弃上顶点。 n扫描线交于一顶点，共享交点的两条边分另处于扫描线的两 边，这时

23、交点只取1个，如扫描线y=3，根据“下闭上开 原那么，该点被填充1次。 n共享交点的两条边处于扫描线 的上方，这时交点取2个，如 扫描线y=1。 n共享交点的两条边处于扫描线 的下方，这时交点取0个，如 扫描线y=9，无交点，不填充。 02468 10 12 2 4 6 8 10 4.1.2 扫描线算法小结 n优点：充分利用了区域的衔接性，算法的 效率比逐点填充法高很多。 n缺陷：对各种表的维持和排序开销太大， 适宜软件实现而不适宜硬件实现。 n思索： n多边形的程度边对算法有何影响？ n上述算法中交点如何实现所述规那么的取 舍？ n算法能否能处置自交多边形？ 4.1.2 扫描线算法思索 AB

24、 CD E FG HI J X Y n程度边对算法有何影响？ n程度边对算法没有影响，可在预处置阶段去除。 第4章 二维填充图元生成 4.1.3 其它算法 1. 边缘填充法 2. 栅栏填充法 3. 边境标志法 n求余运算：假定A为一个正整数(计算机中取A为n位能表示 的最大整数。即，A=0 xFFFFFFFF )，那么M的余定义为A M, 记为 。 n求余可用异或显示方式实现： n光栅图形中，假设某区域已着上值为M的颜色值，做偶数次 求余运算，该区域颜色不变；而做奇数次求余运算，那么 该区域颜色变为值为 的颜色。这一规律运用于多边形扫 描转换，就是边缘填充算法。 n算法根本思想：对于每条扫描线

25、和每条多边形边的交点， 将该扫描线上交点右方的一切象素取余。 1. 边缘填充算法 M M MAMMXor A MMXor AXor AM 1. 边缘填充算法以边为中心的 算法 1. 将绘画窗口的背景置为 ； 2. 从多边形的每一条非程度边上的象素开场向右求 余。 M 1. 边缘填充算法与扫描线算法 的比较 n适宜用于具有帧缓存的图形系统。 n优点： n算法简单，数据构造和程序构造都比扫描线 法简单。 n缺陷： n对于复杂图形，每一象素能够被访问多次， 输入、输出的量比扫描线填充算法大得多； n要对帧缓存的大量象素反复赋值，速度较慢； n并难于用图案填充。 2. 栅栏填充算法 n边缘填充算法的改

26、良。引入栅栏，以减少填充算法 反复访问象素的次数。 n栅栏：与扫描线垂直的直线，通常过一顶点，且把 多边形分为左右二部分。 n根本思想：将交点与栅栏之间的象素取余。 n减少了象素反复访问数目，但不彻底。 栅栏 3. 边境标志算法 n取一个布尔变量inside来指示当前点的形状；Inside 的初始值为假，每当当前访问象素为被打上边境标 志的点，就把inside取反。对未打标志的点，inside 不变。 n没有了求交、排序等运算。 02468 10 12 2 4 6 8 10 3. 边境标志算法 n也称轮廓填充算法改良的边缘填充法。 n1. 对多边形的每一条边进展扫描转换，即对多边形 边境所经过

27、的象素作一个边境标志。 n2. 填充：对每条与多边形相交的扫描线，按从左到 右的顺序，逐个访问该扫描线上的象素。 n取一个布尔变量inside来指示当前点的形状：假设点 在多边形内，那么inside为真；假设点在多边形外， 那么inside为假。 nInside 的初始值为假，每当当前访问象素为被打上边 境标志的点，就把inside取反。对未打标志的点， inside不变。 3. 边境标志算法 n优点：对每个象素只访问一次。不用建立、维护 ET及AEL等数据构造，也没有了排序、求交等运 算，适于硬件实现。 n用软件实现时，扫描线算法与边境标志算法的执 行速度几乎一样。 n但由于边境标志算法不用

28、建立维护AEL以及对它 进展排序，所以边境标志算法更适宜硬件实现， 这时它的执行速度比扫描线算法快一至两个数量 级。 第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.2 区域填充 n多边形的两种表示方法： n顶点表示多边形 n用多边形顶点的序列来刻 划多边形。 n直观、几何意义强、占内 存少、易于几何变换； n不能直接用于光栅系统显 示。 n点阵表示区域 n用象素的集合(边境/内部) 来描写多边形。 n失去了许多重要的几

29、何信 息； n便于光栅系统显示。 4.2 区域填充 n区域可采用两种表示方式: n内点表示 n枚举区域内部的一切像素； n内部的一切像素着同一个颜色； n边境像素着不同的颜色。 n边境表示 n枚举出边境上一切的像素； n边境上的一切像素着同一颜色； n内部像素着不同的颜色。 边境点 内 点 4.2 区域填充 n区域填充 n先将区域内的一点赋予指定的颜色，然后 将该颜色扩展到整个区域的过程。 n简单种子算法 n扫描线种子算法 n要求区域是“连通的。 边境点 内 点 4.2 区域填充 n区域填充要求区域是连通的 n连通性： n4连通： n 从区域内恣意一点出发， 可经过上、下、左、右四个 方向到达

30、区域内的恣意象素； n8连通： n 从区域内恣意一点出发， 可经过上、下、左、右、左 上、左下、右上、右下八个 方向到达区域内的恣意象素； 第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.2.1 简单种子填充算法 n设G为一内点表示的区域，(x,y)为区域内一点， old_color为G的原色。现取(x,y)为种子点对区域G进展 填充：即先置像素(x,y)的颜色为new_color，然后逐渐 将整个区域G都置为同样的颜色

31、。 步骤如下： 种子象素入栈，当栈非空时，执行如下三步操作： 1栈顶象素出栈； 2将出栈象素置成new_color ； 3按左、上、右、下的顺序检查与出栈象素相邻 的四个象素，假设其中某个象素为old_color，那 么把该象素作为新的种子入栈。 4.2.1 简单种子填充算法 /*内点表示的4连通区域*/ void FloodFill4(int x,int y,int oldColor,int newColor) if(GetPixel(x,y) = oldColor) SetPixel(x,y,newColor); FloodFill4(x-1,y,oldColor,newColor); F

32、loodFill4(x,y+1,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor); /*end of FloodFill4()*/ 种子填充算法-边境表示区域 0 1 2 3 4 5 4 3 2 1 (3,2)(2,2) (3,3) (4,2) (3,1)(2,1) (4,1)(4,2) (2,2)(1,2) (2,3)(3,3) 1 5 5 (1,6)(6,6) (8,4) (8,1) (1,1) S (4,3) 设种子象素为S(4,3)，按左、上、 右、下

33、检查出栈象素四个相邻的象 素，写出各象素入栈及出栈顺序。 入栈顺序： (4,3) (3,3),(4,4),(5,3),(4,2) (3,2),(5,2) (5,3),(6,2) . 出栈填色顺序:(4,3) (4,2) (5,2) (6,2) . 栈内象素: (3,3),(4,4), (5,3),(3,2), (5,3) 4.2.1 简单种子填充算法 /*边境表示的4连通区域*/ void BoundaryFill4(int x,int y,int boundaryColor,int newColor) int color; color = GetPixel(x,y); if(color !=

34、 boundaryColor) BoundaryFill4(x,y+1,oldColor,newColor); BoundaryFill4(x,y-1,oldColor,newColor); BoundaryFill4(x-1,y,oldColor,newColor); BoundaryFill4(x+1,y,oldColor,newColor); /*end of BoundaryFill4()*/ S 4.2.1 简单种子填充算法 n采用4向填充算法能否填 充此8向连通区域？ n8连通区域的填充： n将搜索方向改为8向。 n可填充8连通区域和4连 通区域？ 4.2.1 简单种子填充算法 n

35、该算法也可以填充有孔区域。 n优点： n算法简单 n缺陷： n递归执行，效率不高，要求很大的存储空 间来实现堆栈。费时费内存。 n改良： n减少递归次数，提高效率。 n扫描线种子填充算法 第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.2.2 扫描线种子算法原理 n原理：基于种子填充算法的 思想，利用扫描线的衔接性， 减少递归层次。 n根本过程： n当给定种子点时，首先填充种子点所在的扫描 线上的位于给定区域的一个区段；

36、 n然后确定与这一区段相通的上下两条扫描线上 位于给定区域内的区段，并依次保管下来。 n反复这个过程，直到填充终了。 4.2.2 扫描线种子算法算法描 画 n将种子象素压入堆栈 nwhile 堆栈非空 do begin n 从堆栈中弹出一个种子象素； n 沿着扫描线对种子象素的左右象素进展填充，直至遇 到边境象素为止； n 标志区间内最左和最右象素为xleft 和xright； n if在xleftxxright中检查与当前扫描线相邻的上下两 条扫描线全为边境象素或全为已填充过的象素 then goto 2； n 在xleftxxright中标志每一个既不包含边境象素又 不 包含已填充过的象素

37、的区间； n 将每一区间的最右象素作为种子象素压入堆栈； end nend of algorithm 4.2.2 扫描线种子算法算法例 如 n执行扫描线种子法的过程如下 图，是种子象素点S。开场 时，堆栈只需一个种子象素S， 先填充S所在的区段，然后将 其上下扫描线未填充的各区段 的最右象素1，2，3作为种子 象素压入堆栈，再从堆栈中取 出种子象素3，填充该区段， 并将下一条扫描线未填充的区 段的最右象素4压入堆栈，反 复执行，直至堆栈为空时终了， 整个区域填充终了。 S1 2 3 1 2 4 1 2 5 1 2 6 1 2 7 8 910 1 2 7 8 1 2 7 8 1 2 7 11 2

38、 1 712 1 2 1 2 1 1 2 7 8 11 3 4 5 6 9 10 12 4.2.2 扫描线种子算法 n上述算法对于每一个待填充区段，只需 压栈一次；因此，扫描线种子填充算法 提高了区域填充的效率。 多边形扫描转换与区域填充 n联络：都是光栅图形的多边形面着色。可 相互转换： n当用直线的扫描转换算法将多边形的边境 像素求出，并给定多边形内一点为种子点 时，那么多边形的扫描转换转化为区域填 充。 n假设知给定区域为多边形，可求出其顶点 坐标，那么区域填充转化为多边形的扫描 转换。 多边形扫描转换与区域填充 n区别： n根本思想不同 n前者：将多边形的顶点表示转换成点阵表 示， n

39、后者：只改动区域的填充颜色，没有改动 表示方法。 n对边境的要求不同 n前者：只需求扫描线与多边形边境交点个 数为偶数。边境可以不封锁例如对程度 边的预处置。 n后者：区域封锁，防止递归填充跨界。 n基于的条件不同 n前者：从边境顶点信息出发。 n后者：区域内种子点。 第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.3 图案填充 n根本问题 n关键是建立区域与图像间的对应关系。 n方法1：建立整个绘图空间(xoy)与图像空间 (uov)的1-1映射。遨游 x y o 旋转区域 o x y 填充区域 u o v 图像纹理 2.7 以图