《第四章 光栅图形的扫描转换与区域填充精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章 光栅图形的扫描转换与区域填充精选文档.ppt（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章 光栅图形的扫描转换与区域填充本讲稿第一页，共六十九页扫描转换矩形问题：问题：矩形是简单的多边形，那么为什么要单独处矩形是简单的多边形，那么为什么要单独处理矩形？理矩形？比一般多边形可简化计算。应用非常多(窗口系统)。共享边界如何处理？共享边界如何处理？原则：左闭右开，下闭上开属于谁？本讲稿第二页，共六十九页方法：方法：void FillRectangle(Rectangle*rect,int color)int x,y;for(y=rect-ymin;y ymax;y+)for(x=rect-xmin;x xmax;x+)PutPixel(x,y,color);/*end of Fil
2、lRectangle()*/扫描转换矩形本讲稿第三页，共六十九页扫描转换多边形 凸多边形 凹多边形 含内环的多边形本讲稿第四页，共六十九页多边形的表示方法多边形的表示方法顶点表示顶点表示点阵表示点阵表示顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。扫描转换多边形本讲稿第五页，共六十九页多边形的扫描转换多边形的扫描转换多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器
3、内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。几种方法几种方法：逐点判断法；扫描线算法；边缘填充法；栅栏填充法；边界标志法。本讲稿第六页，共六十九页void FillPolygonPbyP(Polygon*P,int polygonColor)int x,y;for(y=ymin;y=ymax;y+)for(x=xmin;x e,dyik+1 成立时，则由区域的连贯性可知d的交点序列和e的交点序列之间有以下关系：1）两序列元素的个数相等，如上图所示。2）点(xeir,e)与(xdjr,d)位于多边形P的同一边上，于是 xeir=xdjr+1/kjr (2)这样，运用递
4、推关系式(2)可直接由d的交点序列获得e的交点序列。以上性质称为边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。边的连贯性本讲稿第二十七页，共六十九页当扫描线与多边形P的交点是P的顶点时，则称该交点为奇点。以上所述多边形的三种形式的连贯性都基于这样的几何事实：每一条扫描线与多边形P的边界的交点个数都是偶数。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点，都可能出现奇数个交点。那么如何保证交点数为偶数呢？奇点的处理本讲稿第二十八页，共六十九页若奇点做一个交点处理，则情况A，交点个数不是偶数。若奇点做两个交点处理，则情况B，交点个数不是偶数。奇点的处理本讲稿第二十九页，共六十九页多
5、边形P的顶点可分为两类：极值奇点和非极值奇点。如果(yi-1-yi)(yi+1-yi)0，则称顶点Pi为极值点；否则称Pi为非极值点。规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。奇点的预处理：奇点的处理本讲稿第三十页，共六十九页数据结构与实现步骤 算法基本思想：首先取d=yin。容易求得扫描线y=d上的交点序列为xdj1,xdj2,xdjn，这一序列由位于扫描线y=d上的多边形P的顶点组成。由yin的交点序列开始，根据多边形的边的连贯性，按从上到下的顺序求得各条扫描线的交点序列；根据扫描线的连贯性，可确定各条扫描线上位于多边形P内的区段，并表示成点阵形式。本讲稿第三十一页，共
6、六十九页 所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。如何判断多边形的一条边与扫描线是否相交？如何判断多边形的一条边与扫描线是否相交？与当前扫描线相交的边称为活性边（active edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活化边表（AEL,Active edge table)。它记录了多边形边沿扫描线的交点序列。只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。数据结构与实现步骤本讲稿第三十二页，共六十九页如何计算下一条扫描线与边的交点？如何计算下一条扫描线与边的交点？直线方程：ax+by+c=0当前交点坐标：(xi,yi)下
7、一交点坐标：(xi+1,yi+1)xi+1=(-byi+1)-c)/a=(-byi+1)-c)/a=xi-b/a活化边表中需要存放的信息：x：当前扫描线与边的交点dx-b/a：从当前扫描线到下一条扫描线之间的x增量ymax：边所交的最高扫描线数据结构与实现步骤本讲稿第三十三页，共六十九页增加哪一条边呢？增加哪一条边呢？为了方便边的活化链表的更新，建立另一个表-边表，存放在该扫描线第一次出现的边。存放的信息：x：扫描线与该边的初始交点dx：x的增量ymax：该边的最大y值数据结构与实现步骤本讲稿第三十四页，共六十九页 算法中采用较灵活的数据结构。它由边的分类表ET（Edge Table）和活化边
8、表AEL（Active Edge List）两部分组成。表结构ET和AEL中的基本元素为多边形的边。边的结构由以下四个域组成：ymax 边的上端点的y坐标；x 在ET中表示边的下端点的x坐标，在AEL中则表示边与扫描线的交点的坐标；x 边的斜率的倒数；next 指向下一条边的指针。数据结构与实现步骤本讲稿第三十五页，共六十九页 边的分类表ET是按边的下端点的y坐标对非水平边进行分类的指针数组。下端点的y坐标的值等于i的边归入第i类。有多少条扫描线，就设多少类。同一类中，各边按x值（x值相等时，按x的值）递增的顺序排列成行。数据结构与实现步骤typedef struct int ymax;flo
9、at x,deltax;Edge*nextEdge;Edge;本讲稿第三十六页，共六十九页算法实现步骤 这样，当建立了边的分类表ET后，扫描线算法可按下列步骤进行：（1）取扫描线纵坐标y的初始值为ET中非空元素的最小序号。（2）将边的活化链表AEL设置为空。（3）按从下到上的顺序对纵坐标值为y的扫描线（当前扫描线）执行下列步骤，直到边的分类表ET和边的活化链表都变成空为止。本讲稿第三十七页，共六十九页1）如边分类表ET中的第y类元素非空，则将属于该类的所有边从ET中取出并插入边的活化链表中，AEL中的各边按照x值（当x值相等时，按x值）递增方向排序。2）若相对于当前扫描线，边的活化链表AEL非
10、空，则将AEL中的边两两依次配对，即1，2边为一对，3，4边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。3）将边的活化链表AEL中满足y=ymax的边删去。4）将边的活化链表AEL剩下的每一条边的x域累加x，即x:=x+x。5）将当前的扫描线的纵坐标值y累加1，即y:=y+1。算法实现步骤本讲稿第三十八页，共六十九页本讲稿第三十九页，共六十九页扫描线算法特点：算法效率比逐点填充法高很多。缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。本讲稿第四十页，共六十九页问题：n如何修改扫描线算法，使它能处理边自交的
11、多边形？扫描线算法本讲稿第四十一页，共六十九页边缘填充算法求余运算求余运算：假定A为一个正整数，则正整数M的余定义为AM,记为 。计算机中用n位表示M时，取A为n位能表示的最大整数。即A=0 xFFFFFFFFA=0 xFFFFFFFF由来由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换，就称为边缘填充算法。算法基本思想算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。本讲稿第四十二页，共六十九页1、将当前扫描线上的 所有象素着上 颜色；2、求余：
12、for(i=0;i=m;i+)在当前扫描线上，从横坐标为Xi的交 点向右求余；算法1（以扫描线为中心的边缘填充算法）本讲稿第四十三页，共六十九页1、将绘图窗口的背景色置为 ；2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余；算法2（以边为中心的边缘填充算法）本讲稿第四十四页，共六十九页算法2（以边为中心的边缘填充算法）本讲稿第四十五页，共六十九页边缘填充算法适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。优点：算法简单缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比有序边表算法大得多。本讲稿第四十六页，共六十九页引入栅栏，以减少填充算
13、法访问象素的次数。栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。基本思想：扫描线与多边形的边求交，将交点与栅栏之间的象素取补。减少了象素重复访问数目，但不彻底。栅栏填充算法本讲稿第四十七页，共六十九页1.对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。2.填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。取一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。Inside 的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，in
14、side不变。边界标志算法本讲稿第四十八页，共六十九页边界标志算法:算法过程void edgemark_fill(polydef,color)多边形定义 polydef；int color;对多边形polydef 每条边进行直线扫描转换；inside=FALSE;for(每条与多边形polydef相交的扫描线y)for(扫描线上每个象素x)if(象素 x 被打上边标志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);else drawpixel(x,y,background);本讲稿第四十九页，共六十九页边界标志算法用软件实现时，扫
15、描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。本讲稿第五十页，共六十九页边界标志算法n思考：如何处理边界的交点个数使其成为偶数？本讲稿第五十一页，共六十九页区域填充算法区域区域指已经表示成点阵形式的填充图形，它是象素的集合。区域填充区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。本讲稿第五十二页，共六十九页区域填充表示方法：表示方法：内点表示、边界表示内点表示内点表示枚举处区域内部的所有像素内部的所有像素着同一个
16、颜色边界像素着与内部像素不同的 颜色n边界表示边界表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色本讲稿第五十三页，共六十九页区域填充要求区域是连通的（种子点）区域填充要求区域是连通的（种子点）n连通性连通性 4连通、8连通n4 4连通：连通：8 8连通连通区域填充本讲稿第五十四页，共六十九页4 4连通与连通与8 8连通区域的区别连通区域的区别连通性：连通性：4 4连通可看作连通可看作8 8连通区域，但对边界有要求连通区域，但对边界有要求对边界的要求对边界的要求区域填充本讲稿第五十五页，共六十九页A：适合于内点表示区域的填充算法设G为一内点表示的区域，(x,y
17、)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成多边形色；（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。种子填充算法本讲稿第五十六页，共六十九页例：多 边 形 由 P0P1P2P3P4构 成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)设种子点为（3，3），搜索的方向是上、下、左、右。
18、依此类推，最后像素被选中并填充的次序如图中箭头所示 种子填充算法本讲稿第五十七页，共六十九页递归递归算法可算法可实现实现如下如下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);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor
19、,newColor);/*end of FloodFill4()*/种子填充算法本讲稿第五十八页，共六十九页边界表示的边界表示的4 4连通区域连通区域void BoundaryFill4(int x,int y,int boundaryColor,int newColor)int color;color=GetPixel(x,y);if(color!=boundaryColor)&(color!=newColor)PutPixel(x,y,newColor);BoundaryFill4(x,y+1,oldColor,newColor);BoundaryFill4(x,y-1,oldColor,
20、newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);/*end of BoundaryFill4()*/种子填充算法本讲稿第五十九页，共六十九页该该算法也可以填充有孔区域。算法也可以填充有孔区域。缺点缺点：(1)有些象素会入栈多次，降低算法效率；栈结构占空间。(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。改进算法，减少递归次数，提高效率改进算法，减少递归次数，提高效率。解决方法是用扫描线填充算法解决方法是用扫描线填充算法种子填充
21、算法本讲稿第六十页，共六十九页扫描线算法目标：目标：减少递归层次减少递归层次适用于内点表示的适用于内点表示的4 4连通区域连通区域算算法法思思想想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。本讲稿第六十一页，共六十九页扫描线填充算法(1)初始化：堆栈置空。将种子点（x，y）入栈。(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。(3)填充并确定种子点所在区段：从种子点（x，y）出发
22、，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。(4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。本讲稿第六十二页，共六十九页扫描线算法分析（举例分析）该算法也可以填充有孔区域。像素中的序号标指它所在区段位于堆栈中的位置本讲稿第六十三页，共六十九页扫描线算法分析（举例分析）本讲稿第六十四页，共六十九页扫描线算法分析（举例分析）本讲稿第六十五页，
23、共六十九页扫描线算法分析（举例分析）本讲稿第六十六页，共六十九页多边形扫描转换与区域填充方法比较联系：都是光栅图形面着色，用于真实感图形显示。可相互转换。多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。区域填充转化为多边形的扫描转换：若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。本讲稿第六十七页，共六十九页不同点：1.基本思想不同前者是顶点表示转换成点阵表示，后者只改变区域内填充颜色，没有改变表示方法。2.对边界的要求不同前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。3.基本的条件不同前者：从边界顶点信息出发，后者：区域内种子点。多边形扫描转换与区域填充方法比较本讲稿第六十八页，共六十九页作业nP91-3本讲稿第六十九页，共六十九页