第四章二维图形的生成精选文档.ppt

《第四章二维图形的生成精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章二维图形的生成精选文档.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 二维图形的生成2022/10/19西安工程大学计算机图形学1本讲稿第一页，共五十五页2022/10/19西安工程大学计算机图形学2v多边形的表示方法多边形的表示方法顶点表示顶点表示点阵表示点阵表示v顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。义强、占内存少；不能直接用于面着色。v点阵表示：用位于多边形内的象素的集合来刻划多边形。点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面

2、着色。图形，易于面着色。多边形的扫描转换4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第二页，共五十五页2022/10/19西安工程大学计算机图形学3多边形的扫描转换：多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。几种方法：几种方法：逐点判断法；扫描线算法；边缘填充法；栅栏填充法；边界标志法。多边形的扫描转换4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第三页，共五十五页2022/10/19西安工程大学计算

3、机图形学4v多边形扫描转换算法对多边形的形状没有限制，但多边形的边界必须是封闭的，且不自交。我们可以将多边形分为三种：v多边形分为凸多边形、凹多边形、含内环的多边形。多边形的扫描转换4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第四页，共五十五页2022/10/19西安工程大学计算机图形学5矩形的扫描转换v问题：矩形是简单的多边形，那么为什么要单独处理矩形？比一般多边形可简化计算。比一般多边形可简化计算。应用非常多，窗口系统应用非常多，窗口系统。共享边界如何处理？v原则：左闭右开，下闭上开原则：左闭右开，下闭上开属于谁？属于谁？4.3、多边形的扫描转换与区域填充、多边形的

4、扫描转换与区域填充本讲稿第五页，共五十五页2022/10/19西安工程大学计算机图形学7void FillPolygonPbyP(Polygon*P,int polygonColor)int x,y;for(y=ymin;y=ymax;y+)for(x=xmin;x e,dye,dyik+1ik+1成立时，则由区域的连贯性可知成立时，则由区域的连贯性可知d d的交点序列和的交点序列和e e的交点序列之间有的交点序列之间有以下关系：以下关系：1 1）两序列元素的个数相等，如上图所示。）两序列元素的个数相等，如上图所示。2 2）点）点(x(xeireir,e),e)与与(x(xdjrdjr,d),

5、d)位于多边形位于多边形P P的同一边上的同一边上 于是于是 x xeireir=x=xdjrdjr+1/k+1/kjrjr (2)(2)这样，运用递推关系式这样，运用递推关系式(2)(2)可直接由可直接由d d的交点序列获得的交点序列获得e e的交点序列。的交点序列。以上性质称为边的连贯性，它是区域的连贯性在相邻两扫描线上的反以上性质称为边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。映。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充扫描线算法_边的连贯性本讲稿第十七页，共五十五页2022/10/19西安工程大学计算机图形学18u当扫描线与多边形当扫描线与多边形P P的交

6、点是的交点是P P的顶点时，则称该交点为的顶点时，则称该交点为奇点奇点。u以上所述多边形的三种形式的连贯性都基于这样的几何事实：以上所述多边形的三种形式的连贯性都基于这样的几何事实：每一条每一条扫描线扫描线与与多边形多边形P P的边界的边界的交点个数都是的交点个数都是偶数偶数。但。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交是如果把每一奇点简单地计为一个交点或者简单地计为两个交点，都可能出现奇数个交点。那么如果保证交点数为偶数呢？点，都可能出现奇数个交点。那么如果保证交点数为偶数呢？奇点的处理4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第十八页，共五十五页2

7、022/10/19西安工程大学计算机图形学19奇点的处理v若奇点做一个交点处理，则情况若奇点做一个交点处理，则情况A，交点个数不是偶数。，交点个数不是偶数。v若奇点做两个交点处理，则情况若奇点做两个交点处理，则情况B，交点个数不是偶数。，交点个数不是偶数。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充AB本讲稿第十九页，共五十五页2022/10/19西安工程大学计算机图形学20奇点的处理v多多边边形形P P的的顶顶点点可可分分为为两两类类：极极值值奇奇点点和和非非极极值值奇奇点点。如如果果(y yi-1i-1 -y yi i)(y)(yi+1i+1 -y yi i)0)0，则则

8、称称顶顶点点P Pi i为为极极值值点点；否否则则称称P Pi i为为非极值点。非极值点。v规规定定：奇奇点点是是极极值值点点时时，该该点点按按两两个个交交点点计计算算，否否则则按按一一个个交交点点计计算。算。v奇点的预处理：奇点的预处理：4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充Pi处理前的处理前的边边处理后的处理后的边边y=yi+1y=yiy=yi-1扫扫描描线线本讲稿第二十页，共五十五页2022/10/19西安工程大学计算机图形学214.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充Pi处理前的处理前的边边处理后的处理后的边边y=yi+1y=yiy=yi-

9、1扫扫描描线线本讲稿第二十一页，共五十五页2022/10/19西安工程大学计算机图形学22数据结构与实现步骤算法基本思想：算法基本思想：算法基本思想：算法基本思想：首首 先先 取取 d=yd=yinin。容容 易易 求求 得得 扫扫 描描 线线 y=dy=d上上 的的 交交 点点 序序 列列 为为x xdj1dj1,x,xdj2dj2,x xdjn djn，这一序列由位于扫描线，这一序列由位于扫描线y=dy=d上的多边形上的多边形P P的顶点组成。的顶点组成。由由y yinin的的交交点点序序列列开开始始，根根据据多多边边形形的的边边的的连连贯贯性性，按按从从上上到到下下的的顺顺序序求求得得各

10、各条条扫扫描描线线的的交交点点序序列列；根根据据扫扫描描线线的的连连贯贯性性，可可确确定定各各条扫描线上位于多边形条扫描线上位于多边形P P内的区段，并表示成点阵形式。内的区段，并表示成点阵形式。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第二十二页，共五十五页2022/10/19西安工程大学计算机图形学23 即算法中采用较灵活的数据结构。它由边的分类表即算法中采用较灵活的数据结构。它由边的分类表ETET（Edge Edge TableTable）和边的活化链表）和边的活化链表AELAEL（Active Edge ListActive Edge List）两部分组成。）

11、两部分组成。表结构表结构ETET和和AELAEL中的基本元素为多边形的边。边的结构由以下四个域中的基本元素为多边形的边。边的结构由以下四个域组成：组成：y ymaxmax 边的上端点的边的上端点的y y坐标；坐标；x x 在在ETET中表示边的下端点的中表示边的下端点的x x坐标，在坐标，在AELAEL中则表示边与中则表示边与扫描线的交点的坐标；扫描线的交点的坐标；x x 边的斜率的倒数；边的斜率的倒数；next next 指向下一条边的指针。指向下一条边的指针。数据结构与实现步骤4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第二十三页，共五十五页2022/10/19西安

12、工程大学计算机图形学24 边边的的分分类类表表ETET是是按按边边的的下下端端点点的的y y坐坐标标对对非非水水平平边边进进行行分分类类的的指指针针数数组组。下下端端点点的的y y坐坐标标的的值值等等于于i i的的边边归归入入第第i i类类。有有多多少少条条扫扫描描线线，就就设设多多少少类类。同同一一类类中中，各各边边按按x x值值（x x值值相相等等时时，按按xx的值）递增的顺序排列成行。的值）递增的顺序排列成行。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充数据结构与实现步骤 与与当当前前扫扫描描线线相相交交的的边边称称为为活活性性边边（active active edge

13、)edge)，把把它它们们按按与与扫扫描描线线交交点点x x坐坐标标递递增增的的顺顺序序存存入入一一个个链链表表中中，边边的的活活化化链链表表 （AELAEL,Active edge table),Active edge table)。它记录了多边形边沿扫描线的交点序列。它记录了多边形边沿扫描线的交点序列。本讲稿第二十四页，共五十五页2022/10/19西安工程大学计算机图形学25数据结构 例子v已知多边形已知多边形P=(P=(P P0 0P P1 1P P2 2P P3 3P P4 4P P5 5P P6 6P P0 0)；其各边坐标分别为其各边坐标分别为v（2 2，5 5）（）（2 2，1

14、010）（）（9 9，6 6）（）（1616，1111）（）（1616，4 4）（）（1212，2 2）（）（7 7，2 2）v建立其边表和边的活化链表建立其边表和边的活化链表4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充51015510P0P1P2P3P4P5P6e1e2e3e4e5e6e7本讲稿第二十五页，共五十五页2022/10/19西安工程大学计算机图形学2651015510P0P1P2P3P4P5P6e1e2e3e4e5e6e71234565 7-5/34122111601020109-7/41997/5ymaxxxnext例子例子_创建边表创建边表本讲稿第二十六页，

15、共五十五页2022/10/19西安工程大学计算机图形学27例子例子_创建活动边表创建活动边表y=3AEL555/34214y=8AEL10207/410511127/511160e7e5e1e2e3e4ymaxxxnext本讲稿第二十七页，共五十五页2022/10/19西安工程大学计算机图形学28算法实现步骤 当建立了边的分类表当建立了边的分类表ETET后，扫描线算法可按下列步骤进行：后，扫描线算法可按下列步骤进行：（1 1）取扫描线纵坐标）取扫描线纵坐标y y的初始值为的初始值为ETET中非空元素的最小序中非空元素的最小序号。号。（2 2）将边的活化链表）将边的活化链表AELAEL设置为空。

16、设置为空。（3 3）按从下到上的顺序对纵坐标值为）按从下到上的顺序对纵坐标值为y y的扫描线（当前扫描的扫描线（当前扫描线）执行下列步骤，直到边的分类表线）执行下列步骤，直到边的分类表ETET和边的活化链表都变和边的活化链表都变成空为止。成空为止。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第二十八页，共五十五页2022/10/19西安工程大学计算机图形学29算法实现步骤1 1）如如边边分分类类表表ETET中中的的第第y y类类元元素素非非空空，则则将将属属于于该该类类的的所所有有边边从从ETET中取出并插入边的活化链表中。递增方向排序。中取出并插入边的活化链表中。递增

17、方向排序。2 2）若若相相对对于于当当前前扫扫描描线线，边边的的活活化化链链表表AELAEL非非空空，则则将将AELAEL中中的的边边两两依次配对，依此类推。并填色。两两依次配对，依此类推。并填色。3 3）将边的活化链表）将边的活化链表AELAEL中满足中满足y=yy=ymaxmax的边删去。的边删去。4 4）x:=x+x:=x+xx。5 5）y:=y+1y:=y+1。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第二十九页，共五十五页2022/10/19西安工程大学计算机图形学30扫描线算法v特点：算法效率比逐点填充法高很多。v缺点：对各种表的维持和排序开销太大，适合软

18、件实现而不适合硬件实现。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第三十页，共五十五页2022/10/19西安工程大学计算机图形学31边缘填充算法求余运算求余运算：假定A为一个正整数，则M的余定义为A M,记为 。计算机中取A为n位能表示的最大整数。即，A=0 xFFFFFFFFA=0 xFFFFFFFF由来由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。算法基本思想算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的

19、所有象素取余。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第三十一页，共五十五页2022/10/19西安工程大学计算机图形学321 1、将当前扫描线上的、将当前扫描线上的 所有象素着上所有象素着上 颜色；颜色；2 2、求余：、求余：for(i=0;i=m;i+)for(i=0;i=m;i+)在当前扫描线上，在当前扫描线上，从横坐标为从横坐标为XiXi的交的交 点向右求余；点向右求余；算法1（以扫描线为中心的边缘填充算法）4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第三十二页，共五十五页2022/10/19西安工程大学计算机图形学33 1、将绘图窗

20、口的背景色置为 ；2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余；算法2（以边为中心的边缘填充算法）4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第三十三页，共五十五页2022/10/19西安工程大学计算机图形学34边缘填充算法v适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。v优点：算法简单v缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比有序边表算法大得多。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第三十四页，共五十五页2022/10/19西安工程大学计算机图形学35v1.对多边形

21、的每一条边进行扫描转换，即对多边形边界对多边形的每一条边进行扫描转换，即对多边形边界 所经过的象素作一个边界标志。所经过的象素作一个边界标志。v2.填充。对每条与多边形相交的扫描线，按从左到右的填充。对每条与多边形相交的扫描线，按从左到右的 顺序，逐个访问该扫描线上的象素。顺序，逐个访问该扫描线上的象素。v3.取一个布尔变量取一个布尔变量inside来指示当前点的状态，若点在来指示当前点的状态，若点在 多边形内，则多边形内，则inside为真。若点在多边形外，则为真。若点在多边形外，则inside 为假。为假。Inside 的初始值为假，每当当前访问象素为被打的初始值为假，每当当前访问象素为被

22、打 上标志的点，就把上标志的点，就把inside取反。对未打标志的点，取反。对未打标志的点，inside 不变。不变。边界标志算法4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第三十五页，共五十五页2022/10/19西安工程大学计算机图形学36边界标志算法:算法过程void edgemark_fill(polydef,color)void edgemark_fill(polydef,color)多边形定义多边形定义 polydef polydef；int color;int color;对多边形对多边形polydef polydef 每条边进行直线扫描转换；每条边进行直

23、线扫描转换；inside=FALSE;inside=FALSE;for(for(每条与多边形每条与多边形polydefpolydef相交的扫描线相交的扫描线y)y)for(for(扫描线上每个象素扫描线上每个象素x)x)if(if(象素象素 x x 被打上边标志被打上边标志)inside=!(inside);inside=!(inside);if(inside if(inside！=FALSE)=FALSE)drawpixel(x,y,color);drawpixel(x,y,color);else drawpixel(x,y,background);else drawpixel(x,y,ba

24、ckground);4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第三十六页，共五十五页2022/10/19西安工程大学计算机图形学37边界标志算法v用软件实现时，扫描线算法与边界标志算法的执行速度几乎用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，相同，v但由于边界标志算法不必建立维护边表以及对它进行但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。执行速度比有序边表算法快一至两个数量级。4.3、多边形的扫描转换与区域填充、多边形的扫

25、描转换与区域填充本讲稿第三十七页，共五十五页2022/10/19西安工程大学计算机图形学38边界标志算法v思考：如何处理边界的交点个数使其成为偶数？4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第三十八页，共五十五页2022/10/19西安工程大学计算机图形学39区域填充算法v区区域域指已经表示成点阵形式的填充图形，它是象素的集合。v区区域域填填充充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第三十九页，共五十五页2022/10/19西安工程大学计算机图形

26、学40v表示方法：表示方法：内点表示、边界表示内点表示、边界表示v内点表示内点表示枚举处区域内部的所有像素枚举处区域内部的所有像素内部的所有像素着同一个颜色内部的所有像素着同一个颜色边界像素着与内部像素不同的边界像素着与内部像素不同的颜色颜色v边界表示边界表示枚举出边界上所有的像素枚举出边界上所有的像素边界上的所有像素着同一颜色边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色内部像素着与边界像素不同的颜色4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充区域填充算法本讲稿第四十页，共五十五页2022/10/19西安工程大学计算机图形学41区域填充要求区域是连通的区域填充要求

27、区域是连通的v连通性连通性 4连通、8连通v4 4连通连通v8 8连通连通4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充区域填充算法本讲稿第四十一页，共五十五页2022/10/19西安工程大学计算机图形学42v4 4连通与连通与8 8连通区域的区别连通区域的区别连通性：连通性：4 4连通可看作连通可看作8 8连通区域，但对边界有要求连通区域，但对边界有要求对边界的要求对边界的要求4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充区域填充算法本讲稿第四十二页，共五十五页2022/10/19西安工程大学计算机图形学43适合于内点表示区域的填充算法适合于内点表示区域的填充

28、算法 设设G G为为一一内内点点表表示示的的区区域域，(x x,y y)为为区区域域内内一一点点，oldold_ _colorcolor为为G G的的原原色色。现现取取(x x,y y)为为种种子子点点对对区区域域G G进进行行填填充充：即即先先置置像像素素(x x,y y)的的颜颜色色为为newnew_ _colorcolor，然然后后逐逐步步将将整整个个区区域域G G都都置置为为同同样样的的颜颜色色。步步骤如下：骤如下：种子象素入栈，当栈非空时，执行如下三步操作：种子象素入栈，当栈非空时，执行如下三步操作：（1 1）栈顶象素出栈；）栈顶象素出栈；（2 2）将出栈象素置成）将出栈象素置成ne

29、wnew_ _colorcolor ；（3 3）按按上上、下下、左左、右右的的顺顺序序检检查查与与出出栈栈象象素素相相邻邻的的四四个个象象素素，若若其其中中某某个个象象素素在在边边界界内内且且未未置置成成newnew_ _colorcolor ，则则把把该该象素入栈。象素入栈。种子填充算法4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第四十三页，共五十五页2022/10/19西安工程大学计算机图形学44v例例：多多边边形形由由P0P1P2P3P4构构成成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)v设设种种子子点点为为（3，3），搜搜索索的的方

30、方向向是是上上、下下、左左、右右。依依此此类推，最后像素被选中并填充的次序如图中箭头所示类推，最后像素被选中并填充的次序如图中箭头所示 4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充种子填充算法本讲稿第四十四页，共五十五页2022/10/19西安工程大学计算机图形学45递归递归算法可算法可实现实现如下如下void FloodFill4(int x,int y,int oldColor,int newColor)if(GetPixel(x,y)=oldColor)PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);

31、FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);/*end of FloodFill4()*/4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充种子填充算法本讲稿第四十五页，共五十五页2022/10/19西安工程大学计算机图形学46边界表示的边界表示的4 4连通区域连通区域void BoundaryFill4(int x,int y,int boundaryColor,int newColor)int color;c

32、olor=GetPixel(x,y);if(color!=boundaryColor)&(color!=newColor)PutPixel(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);/*end of BoundaryFill4()*/4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充种子填

33、充算法本讲稿第四十六页，共五十五页2022/10/19西安工程大学计算机图形学47v该该算法也可以填充有孔区域。算法也可以填充有孔区域。v缺点缺点：(1)(1)有些象素会入栈多次，降低算法效率；有些象素会入栈多次，降低算法效率；(2)(2)递递归归执执行行，算算法法简简单单，但但效效率率不不高高，区区域域内内每每一一象象素素都都引引起一次递归，进起一次递归，进/出栈，费时费内存。出栈，费时费内存。v改进算法，减少递归次数，提高效率。改进算法，减少递归次数，提高效率。解决方法是用扫描线填充算法解决方法是用扫描线填充算法4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充种子填充算法本讲

34、稿第四十七页，共五十五页2022/10/19西安工程大学计算机图形学48扫描线算法v扫描线算法扫描线算法目标：减少递归层次目标：减少递归层次适用于边界表示的适用于边界表示的4 4连通区域连通区域算算法法思思想想：在在任任意意不不间间断断区区间间中中只只取取一一个个种种子子像像素素（不不间间断断区区间间指指在在一一条条扫扫描描线线上上一一组组相相邻邻元元素素），填填充充当当前前扫扫描描线线上上的的该该段段区区间间；然然后后确确定定与与这这一一区区段段相相邻邻的的上上下下两两条条扫扫描描线线上上位位于于区区域域内内的的区区段段，并并依依次次把把它它们们保保存存起起来来，反反复复进行这个过程，直到所

35、保存的个区段都填充完毕。进行这个过程，直到所保存的个区段都填充完毕。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第四十八页，共五十五页2022/10/19西安工程大学计算机图形学49(1)(1)初始化：堆栈置空。将种子点（初始化：堆栈置空。将种子点（x x，y y）入栈。）入栈。(2)(2)出栈：若栈空则结束。否则取栈顶元素（出栈：若栈空则结束。否则取栈顶元素（x x，y y），以），以y y作为当作为当前扫描线。前扫描线。(3)(3)填充并确定种子点所在区段：从种子点（填充并确定种子点所在区段：从种子点（x x，y y）出发，沿当）出发，沿当前扫描线向左、右两个方向填

36、充，直到边界。分别标记区段的前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为左、右端点坐标为xlxl和和xrxr。(4)(4)并确定新的种子点：在区间并确定新的种子点：在区间xlxl，xrxr中检查与当前扫描线中检查与当前扫描线y y上、下上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（每一区间的最右象素作为种子点压入堆栈，返回第（2 2）步。）步。上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充上述算法对于每一个待填充区段，只需压栈一次；因

37、此，扫描线填充算法提高了区域填充的效率。算法提高了区域填充的效率。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充扫描线算法本讲稿第四十九页，共五十五页2022/10/19西安工程大学计算机图形学50扫描线算法分析（举例分析）v该算法也可以填充有孔区域。像素中的序号标指它所在区段位于堆栈中的位置4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第五十页，共五十五页2022/10/19西安工程大学计算机图形学514.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充扫描线算法分析（举例分析）本讲稿第五十一页，共五十五页2022/10/19西安工程大学计算机

38、图形学52扫描线算法分析（举例分析）4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第五十二页，共五十五页2022/10/19西安工程大学计算机图形学53扫描线算法分析（举例分析）4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第五十三页，共五十五页2022/10/19西安工程大学计算机图形学54多边形扫描转换与区域填充方法比较联系：都是光栅图形面着色，用于真实感图形显示。可相互转换。多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。区域填

39、充转化为多边形的扫描转换；若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充本讲稿第五十四页，共五十五页2022/10/19西安工程大学计算机图形学55v不同点：1.基本思想不同；顶点表示转换成点陈表示后者只改变区域内填充颜色，没有改变表示方法。2.对边界的要求不同v前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。3.基本的条件不同v前者：从边界顶点信息出发。v后者：区域内种子点。4.3、多边形的扫描转换与区域填充、多边形的扫描转换与区域填充多边形扫描转换与区域填充方法比较本讲稿第五十五页，共五十五页