多边形的扫描转换与区域填充讲稿.ppt

《多边形的扫描转换与区域填充讲稿.ppt》由会员分享，可在线阅读，更多相关《多边形的扫描转换与区域填充讲稿.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多边形的扫描转换与区域填充第一页，讲稿共六十一页哦2023/4/213.4.1 扫描转换（扫描线）法o多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。o三种方法：n扫描线算法n边填充算法n边界标志法第二页，讲稿共六十一页哦2023/4/22多边形分类o多边形分为凸多边形、凹多边形、含内环的多边形。第三页，讲稿共六十一页哦2023/4/23多边形表示o多边形的表示方法n顶点表示n点阵表示o顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存

2、少；不能直接用于面着色。o点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。第四页，讲稿共六十一页哦2023/4/243.4.1.1扫描线算法-x扫描线法o扫描线算法n目标：利用相邻像素之间的连贯性，提高算法效率n处理对象：非自交多边形（边与边之间除了顶点外无其它交点）第五页，讲稿共六十一页哦2023/4/25步骤(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤：计算扫描线与多边形

3、各边的交点。对求得的交点进行排序。奇偶配对求出扫描线与多边形的相交区间。对这些相交区间填充色。第六页，讲稿共六十一页哦2023/4/26需要解决的几个问题o扫描线与多边形顶点相交时交点的取舍问题o多边形边界上像素点的取舍问题o水平边的处理o减少求交运算问题第七页，讲稿共六十一页哦2023/4/27需要解决的几个问题（一）一、当扫描线与多边形顶点相交时，交点的取舍问题。解决：当扫描线与多边形的顶点相交时，n若共享顶点的两条边分别落在扫描线的两边，交点只算一个；n若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。第八页，讲稿共六十一页哦2023/4/28具体实现时只要检查顶点的两条边的另

4、外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。第九页，讲稿共六十一页哦2023/4/29xy213 4 5 6 7 8 9111234567891011121012与多边形顶点相交的交点的处理第十页，讲稿共六十一页哦2023/4/210011110222 与扫描线相交的多边形顶点的交点数第十一页，讲稿共六十一页哦2023/4/211需要解决的几个问题（二）二、边界上象素的取舍问题，避免填充扩大化。解决方法：边界象素：规定落在右上边界的象素不予填充。具体实现时，只要对扫描线与多边形的相交区间实行：左闭右开（左边界像素填充，右边界像素不填充）下闭上开（下边界

5、像素填充，上边界像素不填充）属于谁？第十二页，讲稿共六十一页哦2023/4/212需要解决的几个问题（三）三、水平边的处理（与扫描线重合）将水平边画出后删去，不参加求交，即求交后的操作（但是在计算交点个数时算作一个点）。第十三页，讲稿共六十一页哦2023/4/213需要解决的几个问题（四）o减少求交算法：x-扫描线法在处理每条扫描线时需要与多边形的所有边求交，而实际上一条扫描线往往只与少数几条边相交，因此降低了效率，于是提出了改进算法有序边表法，也称y连贯性算法。第十四页，讲稿共六十一页哦2023/4/2143.4.1.2 扫描转换法-有序边表法o该法与x-扫描线法基本过程一样，只是在处理求交

6、计算时作了改进。第十五页，讲稿共六十一页哦2023/4/215改进思路可以从以下方面考虑：1 在处理一条扫描线时，仅对与它相交的边（有效边）进行求交运算，于是可以构造活性边表。2 考虑扫描描线的连贯性，即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或者相似。3 多边形边的连贯性，即当一条边与当前扫描线相交时，它可能也与下一条扫描线相交。第十六页，讲稿共六十一页哦2023/4/216o所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。如何判断多边形的一条边与扫描线是否相交？o有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。

7、o有效边表（Active Edge Table,AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效（活性）边表。第十七页，讲稿共六十一页哦2023/4/217数据结构与实现步骤o只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。第十八页，讲稿共六十一页哦2023/4/218如何计算下一条扫描线与边的交点直线方程：ax+by+c=0当前交点坐标：(xi,yi)下一交点坐标：(xi+1,yi+1)xi+1=(-byi+1)-c)/a=(-byi+1)-c)/a=xi-b/a=xi-1/k活动边表中需要存放的信息：x：当前扫描线与边的交点dx-b/a：从

8、当前扫描线到下一条扫描线之间的x增量xymax：边所交的最高扫描线第十九页，讲稿共六十一页哦2023/4/219数据结构与实现步骤o为了方便边的活化链表的更新，建立另一个表-新边表，存放在该扫描线第一次出现的边。存放的信息：x：扫描线与该边的初始交点dx：x的增量ymax：该边的最大y值第二十页，讲稿共六十一页哦2023/4/220数据结构与实现步骤即算法中采用较灵活的数据结构。它由边的新边表NET（new Edge Table）和边的活性边表AET（Active Edge Table）两部分组成。表结构NET和AET中的基本元素为多边形的边。边的结构由以下四个域组成：ymax：边的上端点的y

9、坐标；x：在NET中表示边的最低点的x坐标，在AET中则表示边与扫描线的交点的坐标；x：边的斜率的倒数；（当前扫描线到下一条扫描线x的增量）next：指向下一条边的指针。第二十一页，讲稿共六十一页哦2023/4/221ymaxx1/m(x)nextymaxx1/m(x)nextAET 活性边表NET 新边表X:边的下端点的x坐标X:边与扫描线的交点的坐标第二十二页，讲稿共六十一页哦2023/4/222第二十三页，讲稿共六十一页哦2023/4/223活性边表的例子34-2P3 P456.50.5P3 P2扫描线2AET指针620P4 P5570.5P3 P2扫描线3AET指针(Y(Ymax,ma

10、x,x,x,next)x,x,next)36-2P3 P4560.5P3 P2扫描线1AET指针第二十四页，讲稿共六十一页哦2023/4/224活性边表的例子620P4 P557.50.5P3 P2扫描线4AET指针620P4 P578-1P2 P1扫描线5AET指针724P5 P178-1P2 P1扫描线6AET指针第二十五页，讲稿共六十一页哦2023/4/225新边表724P5 P178-1P2 P1620P4 P536-2P3 P4560.5P3 P2(Ymax,x,x,next)第二十六页，讲稿共六十一页哦2023/4/226算法实现步骤 这样，当建立了边的分类表NET后，扫描线算法可

11、按下列步骤进行：（1）取扫描线纵坐标y的初始值为NET中非空元素的最小序号。（2）将边的活化链表AET设置为空。（3）按从下到上的顺序对纵坐标值为y的扫描线（当前扫描线）执行下列步骤，直到边的分类表ET和边的活化链表都变成空为止。第二十七页，讲稿共六十一页哦2023/4/227算法实现步骤o1）如边分类表NET中的第y类元素非空，则将属于该类的所有边从AET中取出并插入边的活化链表中，AET中的各边按照x值（当x值相等时，按x值）递增方向排序。o2）若相对于当前扫描线，边的活化链表AEL非空，则将AET中的边两两依次配对，即1，2边为一对，3，4边为一对，依次类推。每一对边与当前扫描线的交点所

12、构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。o3）将边的活化链表AET中满足y=ymax的边删去。o4）将边的活化链表AET剩下的每一条边的x域累加x，即x:=x+x。o5）将当前的扫描线的纵坐标值y累加1，即y:=y+1。第二十八页，讲稿共六十一页哦2023/4/228扫描线算法o特点：算法效率较高。o缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。第二十九页，讲稿共六十一页哦2023/4/229扫描线算法o问题：n如何处理多边形的水平边？n如何修改扫描线算法，使它能处理边自交的多边形？第三十页，讲稿共六十一页哦2023/4/2303.4.1.3

13、边填充法o算法简单，但对于复杂图型，每一象素可能被访问多次o算法过程：对于每一条扫描线和每条多边形边的交点（x1,y1）,将该扫描线上交点右方的所有像素取补，对多边形的每条边做同样处理，多边形顺序随意，如下图：第三十一页，讲稿共六十一页哦2023/4/231第三十二页，讲稿共六十一页哦2023/4/2323.4.1.4 栅栏填充算法栅栏填充算法为了减少重复计算，可采用栅栏算法，栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。第三十三页，讲稿共六十一页哦2023/4/233算法过程o对于每个扫描线与多边形的交点，将交点与栅栏之间的像素取补，若交点位于栅栏左边，则将交点之右，栅

14、栏之作的所有像素取补，若交点位于栅栏右边，则将栅栏之左，交点之右的像素取补。第三十四页，讲稿共六十一页哦2023/4/234栅栏算法图示第三十五页，讲稿共六十一页哦2023/4/2353.4.1.5 边界标志算法o1.对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。o2.填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。o取一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。oInside 的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，i

15、nside不变。第三十六页，讲稿共六十一页哦2023/4/236边界标志算法:算法过程ovoid edgemark_fill(polydef,color)o多边形定义 polydef；int color;o 对多边形polydef 每条边进行直线扫描转换；o inside=FALSE;o for(每条与多边形polydef相交的扫描线y)o for(扫描线上每个象素x)o if(象素 x 被打上边标志)o inside=!(inside);o if(inside！=FALSE)o drawpixel(x,y,color);o else drawpixel(x,y,background);o o

16、 第三十七页，讲稿共六十一页哦2023/4/237边界标志算法o用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，o但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。o思考：如何处理边界的交点个数使其成为偶数？第三十八页，讲稿共六十一页哦2023/4/2383.4.2 区域填充算法3.4.2.1 种子填充法o区域指已经表示成点阵形式的填充图形，它是象素的集合。o区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的第三十九页，讲稿共六十一页哦2023/4/2

17、39区域填充o表示方法：内点表示、边界表示o内点表示n枚举出区域内部的所有像素n内部的所有像素着同一个颜色n边界像素着与内部像素不同的 颜色o边界表示n枚举出边界上所有的像素n边界上的所有像素着同一颜色n内部像素着与边界像素不同的颜色第四十页，讲稿共六十一页哦2023/4/240区域填充o区域填充要求区域是连通的o连通性：4连通、8连通n4连通：n8连通44p44(b)p的8-邻接点88888p888(a)p的4-邻接点 邻接点的定义第四十一页，讲稿共六十一页哦2023/4/241区域填充o4连通与8连通区域的区别n连通性：4连通可看作8连通区域，但对边界有要求第四十二页，讲稿共六十一页哦20

18、23/4/242 区域的边界表示和内点表示(a)以边界表示的4-连通区域(d)以内点表示的8-连通区域(b)以内点表示的4-连通区域(c)以边界表示的8-连通区域第四十三页，讲稿共六十一页哦2023/4/243四邻域法不能正确填充一些特殊图形第四十四页，讲稿共六十一页哦2023/4/244种子填充算法-4邻域算法的输入：种子点坐标(x,y)，填充色和边界颜色。栈结构实现4-连通边界填充算法的算法步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)按一定顺序检查出栈象素的4-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈

19、。第四十五页，讲稿共六十一页哦2023/4/245种子填充算法-8邻域栈结构实现8-连通边界填充算法连通边界填充算法的算法步骤算法步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)按一定顺序检查出栈象素的8-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。第四十六页，讲稿共六十一页哦2023/4/246种子填充算法适合于内点表示区域的填充算法设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整

20、个区域G都置为同样的颜色。步骤如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成多边形色；（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。第四十七页，讲稿共六十一页哦2023/4/247举例o以s1为种子，按照左、上、右、下顺序入栈出栈，过程如下：第四十八页，讲稿共六十一页哦2023/4/2484321096S1452378012345第四十九页，讲稿共六十一页哦2023/4/24968454468422684533S1S16845568466S1S1123456789101168446

21、886668498868499684977第五十页，讲稿共六十一页哦2023/4/250种子填充算法o例：多边形由P0P1P2P3P4构成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)o设种子点为（3，3），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示 第五十一页，讲稿共六十一页哦2023/4/251种子填充算法o递归算法可实现如下：void FloodFill4(int x,int y,int oldColor,int newColor)if(GetPixel(x,y)=oldColor)PutPixel(x,y,newColor)

22、;FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);/*end of FloodFill4()*/第五十二页，讲稿共六十一页哦2023/4/252种子填充算法-边界表示的4连通区域void BoundaryFill4(int x,int y,int boundaryColor,int newColor)int color;color=GetPixel(x,y)

23、;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()*/第五十三页，讲稿共六十一页哦2023/4/253种子填充算法该算法也可以填充有孔区域。o缺点：n(1)有

24、些象素会入栈多次，降低算法效率；栈结构占空间。n(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。o解决方法n改进算法，减少递归次数，提高效率。n解决方法是用扫描线填充算法第五十四页，讲稿共六十一页哦2023/4/2543.4.2.2 扫描线种子算法（四连通）o目标：减少递归层次o适用于边界表示的4连通区域o算法思想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的个区段都填充完毕。第五十

25、五页，讲稿共六十一页哦2023/4/255扫描线填充算法(1)初始化：堆栈置空。将种子点（x，y）入栈。(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。(4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。第五十六页，讲稿共六十一页哦2023/4/256扫描线算法分析（例1分析）o该算法也可以填充有孔区域。o像素中的序号标指它所在区段位于堆栈中的位置第五十七页，讲稿共六十一页哦2023/4/257扫描线算法分析（例1分析）第五十八页，讲稿共六十一页哦2023/4/258扫描线算法分析（例1分析）第五十九页，讲稿共六十一页哦2023/4/259扫描线算法分析（例1分析）第六十页，讲稿共六十一页哦2023/4/260扫描线种子算法例2o如图若对图中区域进行扫描填充，s（3，5）为种子像素，则过程如下：图 扫描线种子法填充多边形第六十一页，讲稿共六十一页哦2023/4/261