二维填充图元生成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不能直接用于光栅系统显示。n点阵表示区域）n用象素的集合(边境

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

3、象素。ymax yminxminxmaxvoid 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扫描转换多边形的算法复杂，而矩形的应用非常多(窗口)，所以对其单独处理以提高效率。n共享边界将会被重绘两次，如何处理？属于谁？n准绳：左、下边的象素属

4、于矩形，而右、上边的象素不属于矩形。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 ); /*end of FillRectangle ()*/1. 扫描转换矩形BL(x,y)TR(x+5,y+5)Area=6*6 =36 pix

5、elsArea=5*5 =25 pixelsn矩形面积为：n6*636 pixelsn矩形实际面积应为:n(x+5)-x*(y+5)-yn25 pixelsn采用左闭右开，下闭上开的原则对边界象素进行处理可保证矩形的面积不被扩大。n对FillRectangle ()进行修改。1. 扫描转换矩形n设矩形的四条边分另为xmin，xmax，ymin，ymax。ymax yminxminxmaxvoid FillRectangle ( Rectangle *rect，int color ) int x，y; for ( y = rect-ymin；y ymax；y+ ) for ( x = rect-

6、xmin；x xmax；x+ ) SetPixel ( x，y，color ); /*end of FillRectangle ()*/2. 逐点判断法n它是扫描转换多边形的最简单算法，即逐个判断绘图窗口内的象素是否在多边形内部。n如何判断点在多边形的内外？2. 逐点判断法n逐点判断的算法虽然程序简单，但不可取。原因是速度太慢。n主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，花费很多时间。n不适于实际使用，很少采用。第4章 二维填充图元生成4.1.2 扫描线算法n扫描线算法是扫描转换多边形的常用算法，

7、它充分利用了相邻像素之间的连贯性，避免了逐点判断和反复求交计算，达到了减少计算量和提高算法效率的目的。n处理对象：非自交多边形 （边与边之间除了顶点外无其它交点）。4.1.2 扫描线算法n开发和利用相邻象素之间的连贯性是光栅图形学算法的重要技巧。n扫描线算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。4.1.2 扫描线算法n区域的连贯性：相邻两条扫描线构成一个水平长方形区域，并被多边形的边分割为若干梯形一类位于多边形的内部；另一类在多边形的外部，且间隔排列）。只需知道该区域内任一梯形中一点关于多边形的内外关系，即可确定区域内所有梯形关于多边形的内外关系。 n扫描线的连

8、贯性：区域的连贯性在一条扫描线上的反映；n边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交。可通过与当前扫描线的交点计算与下一扫描线的交点(利用斜率)。（区域的连贯性在相邻两扫描线上的反映）y=iXe1Xe2Xe3Xe4Xe8 Xe7y=i+1Xd1Xd2Xd3Xd4Xd8Xd7P0P8P7P1P2P3P4P5P6n根据扫描线的连贯性可知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。n所以，对所有的扫描线填充入点到出点之间的点就可填充多边形。n如何具体实现如何找到入点、出点）？4.1.2 扫描线算法原理02468 10 122468101 234入点出点内部

9、点4.1.2 扫描线算法原理n根据区域的连贯性，分为3个步骤：n(1)求出扫描线与多边形所有边的交点；n(2)把这些交点按x坐标值以升序排列；n(3)对排序后的交点进行奇偶配对，对每一对交点间的区域进行填充。n步骤(3)如上图：对y8的扫描线，对交点序列按x坐标升序排序得到的交点序列是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。n求交点、排序、配对、填色02468 10 122468104.1.2 扫描线算法数据结构及实现n算法中采用较灵活的数据结构。它由边分类表ETEdge Table和活化边表AELActive Edge List两部分组成。y=6，AEL

10、：y=6y=702468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e6e2e59 2 011 13 0 ymaxxxnAEL中每个对象需要存放的信息：nymax：边所交的最高扫描线；nx：当前扫描线与边的交点；nx：从当前扫描线到下一条扫描线之间的x增量nnext：指向下一对象的指针。y=6，AEL：y=7，AEL：y=6y=702468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e6e2e59 2 011 13 0 ymaxxxe2e39 2 09 7 -2.5e4e511 7 1.511 13 0 n边分类表ET （Edge Table）

11、：按扫描线i对非水平边进行分类的指针数组。下端点的y坐标值等于i的边归入第i类(在该扫描线第一次出现的边)。同一类中，各边按x值x值相等时，按x的值递增的顺序排列。有多少条扫描线，就设多少类。02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e6ymaxxxnET中每个对象需要存放的信息：nymax：边所交的最高扫描线；nx：边的下端点的x坐标；nx：从当前扫描线到下一条扫描线之间的x增量(边的斜率的倒数)；nnext：指向下一对象的指针。n边分类表ET （Edge Table） ：按扫描线i对非水平边进行分类的指针数组。下端点的y坐标值等于i的边归入第i类(在该扫

12、描线第一次出现的边)。同一类中，各边按x值x值相等时，按x的值递增的顺序排列。有多少条扫描线，就设多少类。e2e5e1e6e3e4ET桶）同一类中的边按x、 x的递增顺序排列02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e69 7 -2.511 7 1.5 11 13 092 03 7 -2.55 7 1.5 76543210ymaxxx4.1.2 扫描线算法数据结构及实现n算法中采用较灵活的数据结构。它由边分类表ETEdge Table和活化边表AELActive Edge List两部分组成。nET和AEL中的基本元素称为“边”（Edge）。n边的结构“Ed

13、ge由以下四个域组成：nymax：边的上端点的y坐标；nx：在ET中表示边的下端点的n x坐标；在AEL中则表示边n 与扫描线的交点的x坐标；nx：边的斜率的倒数；nnext：指向下一“边的指针。typedef struct int ymax； float x，deltax； Edge *next； Edge； ymaxxx4.1.2 扫描线算法几点规则02468 10 122468104.1.2 扫描线算法几点规则n扫描线与多边形的顶点相交时，交点的取舍(保证交点正确配对)。n检查该顶点的两相邻边在扫描线的哪一侧：n只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，

14、1，2，来决定取0，1，2个交点。(下闭上开)(a)P0P2P1P0P2P1P0P2P1P0P2P1(b)(c)(d)y=e4.1.2 扫描线算法算法描述l建立ET，置y为ET中非空桶的最小序号；l置AEL表为空，且把y桶中ET表的边加入AEL表中；lwhile AEL表中非空 do beginl 对AEL表中的x、 x按升序排列；l 按照AEL表中交点前后次序，在每对奇偶交点间的x段予 以填充；l 计算下一条扫描线：y=y+1；l if 扫描线 y=ymax then 从AEL表中删除这些边；l 对在AEL表中的其他边，计算与下一条扫描线的交点：x=x +xl 按照扫描线y值把ET表中相应桶

15、中的边加入AEL表中；endlend of algorithme2e5e1e6e3e4:ET02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e69 7 -2.511 7 1.5 11 13 092 03 7 -2.55 7 1.5 76543210AEL=空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

16、11.5 1.5y=4 AEL=9 2011 130 y=5 AEL=9 2011 130 y=6 AEL=e2e5e1e6e3e4:ET02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e69 7 -2.511 7 1.5 11 13 092 03 7 -2.55 7 1.5 76543210y=7 AEL=(2，7) (7，7)(7，7) (13，7)(2，6) (13，6)AEL：9 209 7 -2.511 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

17、-2.511 8.51.511 13 0 y=9 AEL=(10，9) (13，9)11 10 1.511 13 0 e2e5e1e6e3e4:ET02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e69 7 -2.511 7 1.5 11 13 092 03 7 -2.55 7 1.5 76543210y=10 AEL=(11.5，10) (13，10)AEL：11 11.5 1.5y=9 AEL=(10，9) (13，9)11 10 1.511 13 0 11 13 0 y=11 AEL= 空练习n写出如图所示的多边形的边分类表ET及y=7和y=1对应的活性边表

18、AEL）024681012246810P1(2,2)e3e4e2e1e5y=1y=7P2(5,1)P3(11,3)P4(11,8)P5(2,7)024681012246810P1(2,2)e3e4e2e1e5y=1y=7P2(5,1)P3(11,3)P4(11,8)P5(2,7)e3e5e1e2e48 298 11 02 5 -33 537654321072 0ymaxxx024681012246810P1(2,2)e3e4e2e1e5y=1y=7P2(5,1)P3(11,3)P4(11,8)P5(2,7)y=7，AET：y=1，AET：e4e38 2 98 11 0 ymaxxxe1e22

19、5 -335 3 4.1.2 扫描线算法几点规则02468 10 12246810n交点的取整n利用连贯性计算出的交点可能导致部分像素位于多边形之外。n目的：使生成的像素尽量位于多边形之内，并且避免填充扩大化。4.1.2 扫描线算法几点规则4.1.2 扫描线算法几点规则n假定非水平边与扫描线y=e相交，交点的横坐标为x。若x为小数，即交点落于扫描线上两个相邻像素之间时，规则如下：n(a) 交点位于左边之上(入点)，向右取整；n(b) 交点位于右边之上(出点)，向左取整；y=e(x,e)(a)y=e(x,e)(b)4.1.2 扫描线算法几点规则n边界象素的取舍问题，避免填充扩大化。n若x为整数，

20、即交点落于像素点上边界象素）。n落在右边界的象素(出点)不予填充；n“左闭右开”y=e(x,e)(a)y=e(x,e)(b)4.1.2 扫描线算法几点规则n1.边界上的象素: “左闭右开” ，将左边界的点算为内部，而将右边界的点算为外部。n2.顶点：“下闭上开”，即丢弃上顶点。n扫描线交于一顶点，共享交点的两条边分另处于扫描线的两边，这时交点只取1个，如扫描线y=3，根据“下闭上开” 准绳，该点被填充1次。n共享交点的两条边处于扫描线的上方，这时交点取2个，如扫描线y=1。n共享交点的两条边处于扫描线的下方，这时交点取0个，如扫描线y=9，无交点，不填充。02468 10 122468104.

21、1.2 扫描线算法小结n优点：充分利用了区域的连贯性，算法的效率比逐点填充法高很多。n缺陷：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。n思索：n多边形的水平边对算法有何影响？n上述算法中交点如何实现所述规则的取舍？n算法是否能处理自交多边形？4.1.2 扫描线算法思索ABCDEFGHIJXYn水平边对算法有何影响？n水平边对算法没有影响，可在预处理阶段去除。第4章 二维填充图元生成4.1.3 其它算法1. 边缘填充法2. 栅栏填充法3. 边界标志法n求余运算：假定A为一个正整数(计算机中取A为n位能表示的最大整数。即，A=0 xFFFFFFFF )，则M的余定义为A M, 记

22、为 。n求余可用异或显示模式实现：n光栅图形中，如果某区域已着上值为M的颜色值，做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换，就是边缘填充算法。n算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。1. 边缘填充算法MM MAMMXor AMMXor AXor AM1. 边缘填充算法以边为中心的算法1. 将绘画窗口的背景置为 ；2. 从多边形的每一条非水平边上的象素开始向右求余。M1. 边缘填充算法与扫描线算法的比较n适合用于具有帧缓存的图形系统。n优点：n算法简单，数据结构和程序结构都比扫描

23、线法简单。n缺陷：n对于复杂图形，每一象素可能被访问多次，输入、输出的量比扫描线填充算法大得多；n要对帧缓存的大量象素反复赋值，速度较慢；n并难于用图案填充。2. 栅栏填充算法n边缘填充算法的改进。引入栅栏，以减少填充算法重复访问象素的次数。n栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二部分。n基本思想：将交点与栅栏之间的象素取余。n减少了象素重复访问数目，但不彻底。栅栏3. 边界标志算法n取一个布尔变量inside来指示当前点的状态；Inside 的初始值为假，每当当前访问象素为被打上边界标志的点，就把inside取反。对未打标志的点，inside不变。n没有了求交、排序等运

24、算。02468 10 122468103. 边界标志算法n也称轮廓填充算法改进的边缘填充法。n1. 对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。n2. 填充：对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。n取一个布尔变量inside来指示当前点的状态：若点在多边形内，则inside为真；若点在多边形外，则inside为假。nInside 的初始值为假，每当当前访问象素为被打上边界标志的点，就把inside取反。对未打标志的点，inside不变。3. 边界标志算法n优点：对每个象素只访问一次。不必建立、维护ET及AEL等数据结构，也没有了排

25、序、求交等运算，适于硬件实现。n用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同。n但由于边界标志算法不必建立维护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点阵表示区

26、域）n用象素的集合(边境/内部)来刻画多边形。n失去了许多重要的几何信息；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 从区域内任意一点出发，可通过上、下、左、右四个方

27、向到达区域内的任意象素；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都置为同样的颜色。 步骤如下：种子象素入栈，当栈非

28、空时，执行如下三步操作：（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);FloodFill4(x,y+1,oldColor,n

29、ewColor);FloodFill4(x+1,y,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor);/*end of FloodFill4()*/ 种子填充算法-边界表示区域0 1 2 3 4 54321(3,2)(2,2)(3,3)(4,2)(3,1)(2,1)(4,1)(4,2)(2,2)(1,2)(2,3)(3,3)155(1,6)(6,6)(8,4)(8,1)(1,1)S (4,3)设种子象素为S(4,3)，按左、上、右、下检查出栈象素四个相邻的象素，写出各象素入栈及出栈顺序。入栈顺序： (4,3) (3,3),(4,4)

30、,(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 != boundaryColor) & (color != newColor)SetPixel(x,y,newColor)

31、;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()*/ S4.2.1 简单种子填充算法n采用4向填充算法能否填充此8向连通区域？n8连通区域的填充：n将搜索方向改为8向。n可填充8连通区域和4连通区域？4.2.1 简单种子填充算法n该算法也可以填充有孔区域。 n优点：n算法简单n缺陷：n

32、递归执行，效率不高，要求很大的存储空间来实现堆栈。费时费内存。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当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段；n然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。n反复这个过程，直到填充

33、结束。4.2.2 扫描线种子算法算法描述l将种子象素压入堆栈lwhile 堆栈非空 do beginl 从堆栈中弹出一个种子象素；l 沿着扫描线对种子象素的左右象素进行填充，直至遇 到边界象素为止；l 标志区间内最左和最右象素为xleft 和xright；l if在xleftxxright中检查与当前扫描线相邻的上下两 条扫描线全为边界象素或全为已填充过的象素 then goto 2；l 在xleftxxright中标记每一个既不包含边界象素又不 包含已填充过的象素的区间；l 将每一区间的最右象素作为种子象素压入堆栈；endlend of algorithm4.2.2 扫描线种子算法算法示例n

34、执行扫描线种子法的过程如图所示，是种子象素点S。开始时，堆栈只有一个种子象素S，先填充S所在的区段，然后将其上下扫描线未填充的各区段的最右象素1，2，3作为种子象素压入堆栈，再从堆栈中取出种子象素3，填充该区段，并将下一条扫描线未填充的区段的最右象素4压入堆栈，重复执行，直至堆栈为空时结束，整个区域填充完毕。S1231241251261278910127812781271121712121211278113456910124.2.2 扫描线种子算法n上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线种子填充算法提高了区域填充的效率。多边形扫描转换与区域填充n联络：都是光栅图形的多边形面着

35、色。可相互转换：n当用直线的扫描转换算法将多边形的边界像素求出，并给定多边形内一点为种子点时，则多边形的扫描转换转化为区域填充。n若已知给定区域为多边形，可求出其顶点坐标，则区域填充转化为多边形的扫描转换。多边形扫描转换与区域填充n区别：n基本思想不同n前者：将多边形的顶点表示转换成点阵表示，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.3 图案填充n基本问题n关键是建立区域与图像间的对应关系。n方法1：建立整个绘图空间(xoy)与图像空间(uov)的1-1映射。（遨游）xyo旋转区域oxy填充区域uov图像纹理）2.7 以图像