分享
分销 收藏 举报 申诉 / 69

类型第四章 光栅图形的扫描转换与区域填充.ppt

  • 上传人:s4****5z
  • 文档编号:14011922
  • 上传时间:2026-05-27
  • 格式:PPT
  • 页数:69
  • 大小:587KB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

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

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:第四章 光栅图形的扫描转换与区域填充.ppt
    链接地址:https://www.zixin.com.cn/doc/14011922.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork