计算机图形学电子教案c4

1、12第4章 二维填充图元生成4.1 多边形的扫描转换4.1.1 概述4.1.2 扫描线算法4.1.3 其它算法4.2 区域填充4.2.1 简单种子填充4.2.2 扫描线种子填充4.3 字符3第4章 二维填充图元生成n二维填充图元n用颜色或图案填充一个二维区域(由封闭的轮廓线包围)。n轮廓线通常是多边形。如果是曲线的话：n求出边界像素区域填充；n可以采用直线段逼近多边形的扫描转换。4第4章 二维填充图元生成n多边形的两种表示方法：n顶点表示（多边形）n用多边形顶点的序列来刻划多边形。n直观、几何意义强、占内存少、易于几何变换；n不能直接用于光栅系统显示。n点阵表示（区域）n用象素的集合(边界/内

2、部)来刻画多边形。n失去了许多重要的几何信息；n便于光栅系统显示。5第4章 二维填充图元生成n多边形分类：凸多边形凹多边形含内环的多边形6第4章 二维填充图元生成4.1.2 扫描线算法4.1.3 其它算法4.2 区域填充4.2.1 简单种子填充4.2.2 扫描线种子填充4.3 字符74.1.1 概述多边形的扫描转换n多边形的扫描转换：n把多边形的顶点表示转换为点阵表示。n也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内对应元素设置相应的灰度，通常称这种转换为多边形的扫描转换。n方法：n逐点判断法、扫描线算法、边缘填充法、栅栏填充法、边界标志法81. 扫描转换矩形n设矩形的

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

4、，而矩形的应用非常多(窗口)，所以对其单独处理以提高效率。n共享边界将会被重绘两次，如何处理？属于谁？n原则：左、下边的象素属于矩形，而右、上边的象素不属于矩形。n左闭右开，下闭上开。n边界像素重绘问题；n填充扩大化问题。101. 扫描转换矩形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 ); /*e

5、nd of FillRectangle ()*/111. 扫描转换矩形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 ()进行修改。121. 扫描转换矩形n设矩形的四条边分另为xmin，xmax，ymin，ymax。ymax yminxminxmaxvoid FillRectangle ( Rectangle *rect，

6、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 ()*/132. 逐点判断法n它是扫描转换多边形的最简单算法，即逐个判断绘图窗口内的象素是否在多边形内部。n如何判断点在多边形的内外？计算几何n射线法：n累计角度法n编码法；142. 逐点判断法n逐点判断的算法虽然程序简单，但不可取。原因是速度太慢。n主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十

7、万甚至几百万个象素都要一一判别，每次判别又要多次求交点，花费很多时间。n不适于实际使用，很少采用。15第4章 二维填充图元生成4.1.1 概述4.1.3 其它算法4.2 区域填充4.2.1 简单种子填充4.2.2 扫描线种子填充4.3 字符164.1.2 扫描线算法n扫描线算法是扫描转换多边形的常用算法，它充分利用了相邻像素之间的连贯性，避免了逐点判断和反复求交计算，达到了减少计算量和提高算法效率的目的。n处理对象：非自交多边形 （边与边之间除了顶点外无其它交点）。174.1.2 扫描线算法n开发和利用相邻象素之间的连贯性是光栅图形学算法的重要技巧。n扫描线算法综合利用了区域的连贯性、扫描线的

8、连贯性和边的连贯性等三种形式的连贯性。184.1.2 扫描线算法n区域的连贯性：相邻两条扫描线构成一个水平长方形区域，并被多边形的边分割为若干梯形（一类位于多边形的内部；另一类在多边形的外部，且间隔排列）。只需知道该区域内任一梯形中一点关于多边形的内外关系，即可确定区域内所有梯形关于多边形的内外关系。 n扫描线的连贯性：区域的连贯性在一条扫描线上的反映；n边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交。可通过与当前扫描线的交点计算与下一扫描线的交点(利用斜率)。（区域的连贯性在相邻两扫描线上的反映）y=iXe1Xe2Xe3Xe4Xe8Xe7y=i+1Xd1Xd2Xd3Xd4Xd8

9、Xd7P0P8P7P1P2P3P4P5P619n根据扫描线的连贯性可知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。n所以，对所有的扫描线填充入点到出点之间的点就可填充多边形。n如何具体实现（如何找到入点、出点）？4.1.2 扫描线算法原理02468 10 122468101 234入点出点内部点204.1.2 扫描线算法原理n根据区域的连贯性，分为3个步骤：(1)求出扫描线与多边形所有边的交点；(2)把这些交点按x坐标值以升序排列；(3)对排序后的交点进行奇偶配对，对每一对交点间的区域进行填充。n步骤(3)如上图：对y8的扫描线，对交点序列按x坐标升序排序得到的交点序

10、列是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。02468 10 12246810214.1.2 扫描线算法数据结构及实现n算法中采用较灵活的数据结构。它由边分类表NET（Edge Table）和活化边表AET（Active Edge List）两部分组成。n利用链表：与当前扫描线相交的边称为活化边(Active Edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活化边表AET (AET， Active Edge List)。它记录了多边形边沿扫描线的交点序列。y=6，AET：y=6y=702468 10 12246810P3P2P1P4P5

11、P6e3e4e2e1e5e6e2e59 2 011 13 0 ymaxxxnAET中每个对象需要存放的信息：ymax：边所交的最高扫描线；x：当前扫描线与边的交点；x：从当前扫描线到下一条扫描线之间的x增量(边的斜率的倒数)；next：指向下一对象的指针。n随扫描线的递增如何更新AET？n边的加入、删除，交点的更新。y=6，AET：y=7，AET：y=6y=702468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e6e2e59 2 011 13 0 ymaxxxe2e39 2 09 7 -2.5e4e511 7 1.511 13 0 n边分类表NETn边分类表NET （

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

13、i的边归入第i类(在该扫描线第一次出现的边)。同一类中，各边按x值（x值相等时，按x的值）递增的顺序排列。有多少条扫描线，就设多少类。e2e5e1e6e3e4NET（桶）同一类中的边按x、 x的递增顺序排列02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e69 7 -2.511 7 1.5 11 13 092 03 7 -2.55 7 1.5 76543210ymaxxx264.1.2 扫描线算法数据结构及实现n算法中采用较灵活的数据结构。它由边分类表NET（Edge Table）和活化边表AET（Active Edge List）两部分组成。nNET和AET中的

14、基本元素称为“边”（Edge）。n边的结构“Edge”由以下四个域组成：nymax：边的上端点的y坐标；nx：在NET中表示边的下端点的 x坐标；在AET中则表示边 与扫描线的交点的x坐标；nx：边的斜率的倒数；nnext：指向下一“边”的指针。typedef struct int ymax； float x，deltax； Edge *next； Edge； ymaxxx274.1.2 扫描线算法几点规则n交点与多边形顶点重合时，会导致“配对”失败，如何处理？n下闭上开02468 10 12246810284.1.2 扫描线算法几点规则n扫描线与多边形的顶点相交时，交点的取舍(保证交点正确配

15、对)。n检查该顶点的两相邻边在扫描线的哪一侧：只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。(下闭上开)(a)P0P2P1P0P2P1P0P2P1P0P2P1(b)(c)(d)y=e294.1.2 扫描线算法算法描述l建立NET，置y为NET中非空桶的最小序号；l置AET表为空，且把y桶中NET表的边加入AET表中；lwhile AET表中非空 do beginl 对AET表中的x、 x按升序排列；l 按照AET表中交点前后次序，在每对奇偶交点间的x段予 以填充；l 计算下一条扫描线：y=y+1；l if 扫描线 y=ymax t

16、hen 从AET表中删除这些边；l 对在AET表中的其他边，计算与下一条扫描线的交点：x=x +xl 按照扫描线y值把NET表中相应桶中的边加入AET表中；endlend of algorithm304.1.2 扫描线算法几点规则n边界象素的取舍问题，避免填充扩大化。n若x为整数，即交点落于像素点上（边界象素）。n落在右边界的象素(出点)不予填充；n“左闭右开”y=e(x,e)(a)y=e(x,e)(b)314.1.2 扫描线算法几点规则n1.边界上的象素: “左闭右开” ，将左边界的点算为内部，而将右边界的点算为外部。n2.顶点：“下闭上开”，即丢弃上顶点。n扫描线交于一顶点，共享交点的两条

17、边分另处于扫描线的两边，这时交点只取1个，如扫描线y=3，根据“下闭上开” 原则，该点被填充1次。n共享交点的两条边处于扫描线的上方，这时交点取2个，如扫描线y=1。n共享交点的两条边处于扫描线的下方，这时交点取0个，如扫描线y=9，无交点，不填充。02468 10 1224681032第4章 二维填充图元生成4.1.1 概述4.1.2 扫描线算法4.2 区域填充4.2.1 简单种子填充4.2.2 扫描线种子填充4.3 字符334.1.3 其它算法1. 边界标志法341. 边界标志算法n取一个布尔变量inside来指示当前点的状态；Inside 的初始值为假，每当当前访问象素为被打上边界标志的

18、点，就把inside取反。对未打标志的点，inside不变。n没有了求交、排序等运算。02468 10 12246810351. 边界标志算法n也称轮廓填充算法改进的边缘填充法。1. 对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。2. 填充：对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。n取一个布尔变量inside来指示当前点的状态：若点在多边形内，则inside为真；若点在多边形外，则inside为假。nInside 的初始值为假，每当当前访问象素为被打上边界标志的点，就把inside取反。对未打标志的点，inside不变。361. 边界

19、标志算法n优点：对每个象素只访问一次。不必建立、维护NET及AET等数据结构，也没有了排序、求交等运算，适于硬件实现。n用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同。n但由于边界标志算法不必建立维护AET以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比扫描线算法快一至两个数量级。37第4章 二维填充图元生成4.1 多边形的扫描转换4.1.1 概述4.1.2 扫描线算法4.1.3 其它算法4.2.1 简单种子填充4.2.2 扫描线种子填充4.3 字符384.2 区域填充n多边形的两种表示方法：n顶点表示（多边形）n用多边形顶点的序列来刻划多边形。n直观、几何意义强

20、、占内存少、易于几何变换；n不能直接用于光栅系统显示。n点阵表示（区域）n用象素的集合(边界/内部)来刻画多边形。n失去了许多重要的几何信息；n便于光栅系统显示。394.2 区域填充n区域可采用两种表示形式:n内点表示n枚举区域内部的所有像素；n内部的所有像素着同一个颜色；n边界像素着不同的颜色。n边界表示n枚举出边界上所有的像素；n边界上的所有像素着同一颜色；n内部像素着不同的颜色。边界点内 点404.2 区域填充n区域填充n先将区域内的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。n简单种子算法n扫描线种子算法n要求区域是“连通”的。边界点内 点414.2 区域填充n区域填充要求区

21、域是连通的n连通性：n4连通： 从区域内任意一点出发，可通过上、下、左、右四个方向到达区域内的任意象素；n8连通： 从区域内任意一点出发，可通过上、下、左、右、左上、左下、右上、右下八个方向到达区域内的任意象素；42第4章 二维填充图元生成4.1 多边形的扫描转换4.1.1 概述4.1.2 扫描线算法4.1.3 其它算法4.2 区域填充4.2.2 扫描线种子填充4.3 字符434.2.1 简单种子填充算法n设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置

22、为同样的颜色。 步骤如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成new_color ；（3）按左、上、右、下的顺序检查与出栈象素相邻的四个象素，若其中某个象素为old_color，则把该象素作为新的种子入栈。444.2.1 简单种子填充算法/*内点表示的4连通区域*/void FloodFill4(int x,int y,int oldColor,int newColor) if(GNETPixel(x,y) = oldColor) SNETPixel(x,y,newColor); FloodFill4(x-1,y,oldColor,newColo

23、r);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor);/*end of FloodFill4()*/ 8239S4576543210082319S4527634各象素入栈及出栈顺序: S入栈S出栈并填充, (4,7,9,2入栈)2出栈并填充,(3,8入栈)8出栈并填充,(9入栈)9出栈并填充,(无象素入栈)3出栈并填充,(4入栈)4出栈并填充,(5,6入栈)6出栈并填充,(7入栈)7出栈并填充,(无象素入栈)5出栈并填充,(无

24、象素入栈)9出栈7出栈4出栈入栈: s 4 7 9 2 3 8 9 4 5 6 7出栈: s 2 8 9 3 4 6 7 5 9 7 4 按左、上、右、下检查出栈象素四个相邻的象素464.2.1 简单种子填充算法/*边界表示的4连通区域*/void BoundaryFill4(int x,int y,int boundaryColor,int newColor) int color;color = GETPixel(x,y);if(color != boundaryColor) & (color != newColor)drawPixel(x,y,newColor);BoundaryF

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

26、率不高，要求很大的存储空间来实现堆栈。费时费内存。n改进：n减少递归次数，提高效率。-扫描线种子填充算法49第4章 二维填充图元生成4.1 多边形的扫描转换4.1.1 概述4.1.2 扫描线算法4.1.3 其它算法4.2 区域填充4.2.1 简单种子填充4.3 字符504.2.2 扫描线种子算法原理n原理：基于种子填充算法的思想，利用扫描线的连贯性，减少递归层次。n基本过程：n当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段；n然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。n反复这个过程，直到填充结束。514.2.2 扫描线种子算法算法描述l

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

28、象素点S。开始时，堆栈只有一个种子象素S，先填充S所在的区段，然后将其上下扫描线未填充的各区段的最右象素1，2，3作为种子象素压入堆栈，再从堆栈中取出种子象素3，填充该区段，并将下一条扫描线未填充的区段的最右象素4压入堆栈，重复执行，直至堆栈为空时结束，整个区域填充完毕。S123124125126127891012781278127112171212121127811345691012534.2.2 扫描线种子算法n上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线种子填充算法提高了区域填充的效率。54第4章 二维填充图元生成4.1 多边形的扫描转换4.1.1 概述4.1.2 扫描线算法

29、4.1.3 其它算法4.2 区域填充4.2.1 简单种子填充4.2.2 扫描线种子填充554.3 字符n字符：在屏幕上显示的字母、数字、符号、汉字等。n由一个数字编码唯一标识。例如：ASCII码，GB2312-80等。n为了显示输出字符，必须有相应的字库，用于存储每个字符的形状信息。n点阵字符：存储量大，易于显示；n矢量字符：存储量小，美观，变换方便; 但需要光栅化后才能显示。564.3.1 点阵字符n点阵式字符将字符形状表示为一个矩形点阵，由点阵中点的不同值表达字符的形状。0000000000011100000100000010000001000011100010010001001000011111 对应 前景色0 对应 背景色79位图常用位图：799161624574.3.1 点阵字符n点阵字符的存储（点阵字符是由位图表示的，保存字符就是保存它的位图）例：1616点阵汉字：16*16=256位（32个字节） 常用汉字6763个：6763*32=216416字节 16*24=38