计算机图形学电子教案

计算机图形学电子教案1第一页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成4.1多边形的扫描转换4.1.1概述4.1.2扫描线算法4.1.3其它算法4.2区域填充4.2.1简单种子填充4.2.2扫描线种子填充4.3字符2第二页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成二维填充图元用颜色或图案填充一个二维区域(由封闭的轮廓线包围)。轮廓线通常是多边形。如果是曲线的话：求出边界像素→区域填充；可以采用直线段逼近→多边形的扫描转换。3第三页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成多边形的两种表示方法：顶点表示（多边形）用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少、易于几何变换；不能直接用于光栅系统显示。点阵表示（区域）用象素的集合(边界/内部)来刻画多边形。失去了许多重要的几何信息；便于光栅系统显示。4第四页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成多边形分类：凸多边形凹多边形含内环的多边形5第五页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成4.1多边形的扫描转换4.1.1概述4.1.2扫描线算法4.1.3其它算法4.2区域填充4.2.1简单种子填充4.2.2扫描线种子填充4.3字符6第六页，共六十一页，编辑于2023年，星期一4.1.1概述－多边形的扫描转换多边形的扫描转换：把多边形的顶点表示转换为点阵表示。也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内对应元素设置相应的灰度，通常称这种转换为多边形的扫描转换。方法：逐点判断法、扫描线算法、边缘填充法、栅栏填充法、边界标志法…7第七页，共六十一页，编辑于2023年，星期一1.扫描转换矩形设矩形的四条边分另为mina，xmax,ymin,ymax。只要填充从ymin到ymax的每条扫描线上位于xmin和xmax之间的象素。ymaxyminxminxmaxvoidFillRectangle(Rectangle*rect，intcolor) {intx，y; for(y=rect->ymin；y<=rect->ymax；y++) for(x=rect->xmin；x<=rect->xmax；x++) SETPixel(x，y，color); }/*endofFillRectangle()*/8第八页，共六十一页，编辑于2023年，星期一1.扫描转换矩形矩形也是多边形，那么为什么要单独处理矩形？扫描转换多边形的算法复杂，而矩形的应用非常多(窗口)，所以对其单独处理以提高效率。共享边界将会被重绘两次，如何处理？ 属于谁？原则：左、下边的象素属于矩形，而右、上边的象素不属于矩形。左闭右开，下闭上开。边界像素重绘问题；填充扩大化问题。9第九页，共六十一页，编辑于2023年，星期一1.扫描转换矩形考虑填充从BL(x，y)到TR（x+5，y+5）的矩形。voidFillRectangle(Rectangle*rect，intcolor) {intx，y; for(y=rect->ymin；y<=rect->ymax；y++) for(x=rect->xmin；x<=rect->xmax；x++) SETPixel(x，y，color); }/*endofFillRectangle()*/10第十页，共六十一页，编辑于2023年，星期一1.扫描转换矩形BL(x,y)TR(x+5,y+5)Area=6*6=36pixelsArea=5*5=25pixels矩形面积为：6*6＝36pixels矩形实际面积应为:

[(x+5)-x]*[(y+5)-y]

＝25pixels采用左闭右开，下闭上开的原则对边界象素进行处理可保证矩形的面积不被扩大。对FillRectangle()进行修改。11第十一页，共六十一页，编辑于2023年，星期一1.扫描转换矩形设矩形的四条边分另为xmin，xmax，ymin，ymax。ymaxyminxminxmaxvoidFillRectangle(Rectangle*rect，intcolor) {intx，y; for(y=rect->ymin；y<rect->ymax；y++) for(x=rect->xmin；x<rect->xmax；x++) SETPixel(x，y，color); }/*endofFillRectangle()*/12第十二页，共六十一页，编辑于2023年，星期一2.

逐点判断法它是扫描转换多边形的最简单算法，即逐个判断绘图窗口内的象素是否在多边形内部。如何判断点在多边形的内外？－计算几何射线法：累计角度法编码法；13第十三页，共六十一页，编辑于2023年，星期一2.

逐点判断法逐点判断的算法虽然程序简单，但不可取。原因是速度太慢。主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，花费很多时间。不适于实际使用，很少采用。14第十四页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成4.1多边形的扫描转换4.1.1概述4.1.2扫描线算法4.1.3其它算法4.2区域填充4.2.1简单种子填充4.2.2扫描线种子填充4.3字符15第十五页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法扫描线算法是扫描转换多边形的常用算法，它充分利用了相邻像素之间的连贯性，避免了逐点判断和反复求交计算，达到了减少计算量和提高算法效率的目的。处理对象：非自交多边形（边与边之间除了顶点外无其它交点）。16第十六页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法开发和利用相邻象素之间的连贯性是光栅图形学算法的重要技巧。扫描线算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。17第十七页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法区域的连贯性：相邻两条扫描线构成一个水平长方形区域，并被多边形的边分割为若干梯形（一类位于多边形的内部；另一类在多边形的外部，且间隔排列）。只需知道该区域内任一梯形中一点关于多边形的内外关系，即可确定区域内所有梯形关于多边形的内外关系。

扫描线的连贯性：区域的连贯性在一条扫描线上的反映；边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交。可通过与当前扫描线的交点计算与下一扫描线的交点(利用斜率)。（区域的连贯性在相邻两扫描线上的反映）y=iXe1Xe2Xe3Xe4Xe8Xe7y=i+1Xd1Xd2Xd3Xd4Xd8Xd7P0P8P7P1P2P3P4P5P618第十八页，共六十一页，编辑于2023年，星期一根据扫描线的连贯性可知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间的点就可填充多边形。如何具体实现（如何找到入点、出点）？4.1.2扫描线算法－原理0246810122468101234入点出点内部点19第十九页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法－原理根据区域的连贯性，分为3个步骤：(1)求出扫描线与多边形所有边的交点；(2)把这些交点按x坐标值以升序排列；(3)对排序后的交点进行奇偶配对，对每一对交点间的区域进行填充。步骤(3)如上图：对y＝8的扫描线，对交点序列按x坐标升序排序得到的交点序列是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。求交、排序、配对、填色02468101224681020第二十页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法－数据结构及实现算法中采用较灵活的数据结构。它由边分类表NET（EdgeTable）和活化边表AET（ActiveEdgeList）两部分组成。21第二十一页，共六十一页，编辑于2023年，星期一求交、排序、配对、填色利用链表：与当前扫描线相交的边称为活化边(ActiveEdge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活化边表AET(AET，ActiveEdgeList)。它记录了多边形边沿扫描线的交点序列。y=6，AET：y=6y=7024681012246810P3P2P1P4P5P6e3e4e2e1e5e6e2e592011130^ymaxxΔxAET中每个对象需要存放的信息：ymax：边所交的最高扫描线；x：当前扫描线与边的交点；Δx：从当前扫描线到下一条扫描线之间的x增量(边的斜率的倒数)；next：指向下一对象的指针。活化边表AET第二十二页，共六十一页，编辑于2023年，星期一求交、排序、配对、填色随扫描线的递增如何更新AET？边的加入、删除，交点的更新。y=6，AET：y=7，AET：y=6y=7024681012246810P3P2P1P4P5P6e3e4e2e1e5e6e2e592011130^ymaxxΔxe2e392097-2.5e4e51171.511130^建立一个新的数据结构：边分类表NET活化边表AET第二十三页，共六十一页，编辑于2023年，星期一边分类表NET（EdgeTable）

：按扫描线i对非水平边进行分类的指针数组。下端点的y坐标值等于i的边归入第i类(在该扫描线第一次出现的边)。同一类中，各边按x值（x值相等时，按Δx的值）递增的顺序排列。有多少条扫描线，就设多少类。024681012246810P3P2P1P4P5P6e3e4e2e1e5e6ymaxxΔxNET中每个对象需要存放的信息：ymax：边所交的最高扫描线；x：边的下端点的x坐标；Δx：从当前扫描线到下一条扫描线之间的x增量(边的斜率的倒数)；next：指向下一对象的指针。第二十四页，共六十一页，编辑于2023年，星期一边分类表NET（EdgeTable）

：按扫描线i对非水平边进行分类的指针数组。下端点的y坐标值等于i的边归入第i类(在该扫描线第一次出现的边)。同一类中，各边按x值（x值相等时，按Δx的值）递增的顺序排列。有多少条扫描线，就设多少类。e2e5e1e6e3e4NET（桶）同一类中的边按x、Δx的递增顺序排列024681012246810P3P2P1P4P5P6e3e4e2e1e5e697-2.51171.5^11130^920^37-2.5571.5^76^54^32^10^ymaxxΔx第二十五页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法－数据结构及实现算法中采用较灵活的数据结构。它由边分类表NET（EdgeTable）和活化边表AET（ActiveEdgeList）两部分组成。NET和AET中的基本元素称为“边”（Edge）。边的结构“Edge”由以下四个域组成：ymax：边的上端点的y坐标；x：在NET中表示边的下端点的

x坐标；在AET中则表示边 与扫描线的交点的x坐标；Δx：边的斜率的倒数；next：指向下一“边”的指针。typedefstruct{intymax；

floatx，deltax；

Edge*next；

}Edge；

ymaxxΔx26第二十六页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法－几点规则求交、排序、配对、填色交点与多边形顶点重合时，会导致“配对”失败，如何处理？下闭上开02468101224681027第二十七页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法－几点规则扫描线与多边形的顶点相交时，交点的取舍(保证交点正确配对)。检查该顶点的两相邻边在扫描线的哪一侧： 只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。(下闭上开)(a)P0P2P1P0P2P1P0P2P1P0P2P1(b)(c)(d)y=e28第二十八页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法－算法描述建立NET，置y为NET中非空桶的最小序号；置AET表为空，且把y桶中NET表的边加入AET表中；whileAET表中非空do

begin

对AET表中的x、Δx按升序排列；

按照AET表中交点前后次序，在每对奇偶交点间的x段予 以填充；

计算下一条扫描线：y=y+1；

if扫描线y=ymax

then从AET表中删除这些边；

对在AET表中的其他边，计算与下一条扫描线的交点： x=x+Δx

按照扫描线y值把NET表中相应桶中的边加入AET表中；

endendofalgorithm29第二十九页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法－几点规则边界象素的取舍问题，避免填充扩大化。若x为整数，即交点落于像素点上（边界象素）。落在右边界的象素(出点)不予填充；“左闭右开”y=e(x,e)(a)y=e(x,e)(b)30第三十页，共六十一页，编辑于2023年，星期一4.1.2扫描线算法－几点规则1.边界上的象素:“左闭右开”，将左边界的点算为内部，而将右边界的点算为外部。2.顶点：“下闭上开”，即丢弃上顶点。扫描线交于一顶点，共享交点的两条边分另处于扫描线的两边，这时交点只取1个，如扫描线y=3，根据“下闭上开”原则，该点被填充1次。共享交点的两条边处于扫描线的上方，这时交点取2个，如扫描线y=1。共享交点的两条边处于扫描线的下方，这时交点取0个，如扫描线y=9，无交点，不填充。02468101224681031第三十一页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成4.1多边形的扫描转换4.1.1概述4.1.2扫描线算法4.1.3其它算法4.2区域填充4.2.1简单种子填充4.2.2扫描线种子填充4.3字符32第三十二页，共六十一页，编辑于2023年，星期一4.1.3其它算法1.

边界标志法33第三十三页，共六十一页，编辑于2023年，星期一1.

边界标志算法取一个布尔变量inside来指示当前点的状态；Inside的初始值为假，每当当前访问象素为被打上边界标志的点，就把inside取反。对未打标志的点，inside不变。没有了求交、排序等运算。02468101224681034第三十四页，共六十一页，编辑于2023年，星期一1.

边界标志算法也称轮廓填充算法－改进的边缘填充法。1.对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。2.填充：对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。取一个布尔变量inside来指示当前点的状态：若点在多边形内，则inside为真；若点在多边形外，则inside为假。Inside的初始值为假，每当当前访问象素为被打上边界标志的点，就把inside取反。对未打标志的点，inside不变。35第三十五页，共六十一页，编辑于2023年，星期一1.

边界标志算法优点：对每个象素只访问一次。不必建立、维护NET及AET等数据结构，也没有了排序、求交等运算，适于硬件实现。用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同。但由于边界标志算法不必建立维护AET以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比扫描线算法快一至两个数量级。36第三十六页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成4.1多边形的扫描转换4.1.1概述4.1.2扫描线算法4.1.3其它算法4.2区域填充4.2.1简单种子填充4.2.2扫描线种子填充4.3字符37第三十七页，共六十一页，编辑于2023年，星期一4.2区域填充多边形的两种表示方法：顶点表示（多边形）用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少、易于几何变换；不能直接用于光栅系统显示。点阵表示（区域）用象素的集合(边界/内部)来刻画多边形。失去了许多重要的几何信息；便于光栅系统显示。38第三十八页，共六十一页，编辑于2023年，星期一4.2区域填充区域可采用两种表示形式:内点表示枚举区域内部的所有像素；内部的所有像素着同一个颜色；边界像素着不同的颜色。边界表示枚举出边界上所有的像素；边界上的所有像素着同一颜色；内部像素着不同的颜色。边界点内点39第三十九页，共六十一页，编辑于2023年，星期一4.2区域填充区域填充先将区域内的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。简单种子算法扫描线种子算法要求区域是“连通”的。边界点内点40第四十页，共六十一页，编辑于2023年，星期一4.2区域填充区域填充要求区域是连通的连通性：4连通：从区域内任意一点出发，可通过上、下、左、右四个方向到达区域内的任意象素；8连通：从区域内任意一点出发，可通过上、下、左、右、左上、左下、右上、右下八个方向到达区域内的任意象素；41第四十一页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成4.1多边形的扫描转换4.1.1概述4.1.2扫描线算法4.1.3其它算法4.2区域填充4.2.1简单种子填充4.2.2扫描线种子填充4.3字符42第四十二页，共六十一页，编辑于2023年，星期一4.2.1简单种子填充算法设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成new_color；（3）按左、上、右、下的顺序检查与出栈象素相邻的四个象素，若其中某个象素为old_color，则把该象素作为新的种子入栈。43第四十三页，共六十一页，编辑于2023年，星期一4.2.1简单种子填充算法/*内点表示的4连通区域*/voidFloodFill4(intx,inty,intoldColor,intnewColor){if(GNETPixel(x,y)==oldColor){SNETPixel(x,y,newColor);FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x,y+1,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);}}/*endofFloodFill4() */44第四十四页，共六十一页，编辑于2023年，星期一8239S4576543210082319S4527634各象素入栈及出栈顺序:S入栈S出栈并填充,(4,7,9,2入栈)2出栈并填充,(3,8入栈)8出栈并填充,(9入栈)9出栈并填充,(无象素入栈)3出栈并填充,(4入栈)4出栈并填充,(5,6入栈)6出栈并填充,(7入栈)7出栈并填充,(无象素入栈)5出栈并填充,(无象素入栈)9出栈7出栈4出栈入栈:

s47923894567出栈:

s28934675974

按左、上、右、下检查出栈象素四个相邻的象素第四十五页，共六十一页，编辑于2023年，星期一4.2.1简单种子填充算法/*边界表示的4连通区域*/voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){ intcolor; color=GETPixel(x,y); if((color!=boundaryColor)&&(color!=newColor)) { drawPixel(x,y,newColor); BoundaryFill4(x,y+1,oldColor,newColor); BoundaryFill4(x,y-1,oldColor,newColor); BoundaryFill4(x-1,y,oldColor,newColor); BoundaryFill4(x+1,y,oldColor,newColor); }}/*endofBoundaryFill4() */

46第四十六页，共六十一页，编辑于2023年，星期一S4.2.1简单种子填充算法采用4向填充算法能否填充此8向连通区域？8连通区域的填充：将搜索方向改为8向。可填充8连通区域和4连通区域？47第四十七页，共六十一页，编辑于2023年，星期一4.2.1简单种子填充算法该算法也可以填充有孔区域。

优点：算法简单缺点：递归执行，效率不高，要求很大的存储空间来实现堆栈。费时费内存。改进：减少递归次数，提高效率。扫描线种子填充算法48第四十八页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成4.1多边形的扫描转换4.1.1概述4.1.2扫描线算法4.1.3其它算法4.2区域填充4.2.1简单种子填充4.2.2扫描线种子填充4.3字符49第四十九页，共六十一页，编辑于2023年，星期一4.2.2扫描线种子算法－原理原理：基于种子填充算法的思想，利用扫描线的连贯性，减少递归层次。基本过程：当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段；然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。50第五十页，共六十一页，编辑于2023年，星期一4.2.2扫描线种子算法－算法描述将种子象素压入堆栈while堆栈非空do

begin

从堆栈中弹出一个种子象素；

沿着扫描线对种子象素的左右象素进行填充，直至遇 到边界象素为止；

标志区间内最左和最右象素为xleft

和xright；

if在xleft≤x≤xright中检查与当前扫描线相邻的上下两 条扫描线全为边界象素或全为已填充过的象素then goto2；在xleft≤x≤xright中标记每一个既不包含边界象素又不 包含已填充过的象素的区间；

将每一区间的最右象素作为种子象素压入堆栈；

endendofalgorithm51第五十一页，共六十一页，编辑于2023年，星期一4.2.2扫描线种子算法－算法示例执行扫描线种子法的过程如图所示，●是种子象素点S。开始时，堆栈只有一个种子象素S，先填充S所在的区段，然后将其上下扫描线未填充的各区段的最右象素1，2，3作为种子象素压入堆栈，再从堆栈中取出种子象素3，填充该区段，并将下一条扫描线未填充的区段的最右象素4压入堆栈，重复执行，直至堆栈为空时结束，整个区域填充完毕。S12312412512612789101278127812711217121212112781134569101252第五十二页，共六十一页，编辑于2023年，星期一4.2.2扫描线种子算法上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线种子填充算法提高了区域填充的效率。53第五十三页，共六十一页，编辑于2023年，星期一第4章二维填充图元生成4.1多边形的扫描转换4.1.1概述4.1.2扫描线算法4.1.3其它算法4.2区域填充4.2.1简单种子填充4.2.2扫描线种子填充4.3字符54第五十四页，共六十一页，编辑于2023年，星期一4.3字符字符：在屏幕上显示的字母、数字、符号、汉字等。由一个数字编码唯一标识。例如：ASCII码，GB2312-80等。为了显示输出字符，必须有相应的字库，用于存储每个字符的形状信息。点阵字符：存储量大，易于显示；矢量字符：存储量小，美观，变换方便;但需要光栅化后才能显示。55第五十五页，共六十一页，编辑于2023年，星期一4.3.1点阵字符点阵式字符将字符形状表示为一个矩形点阵，由点阵