计算机图形学--图形填充正规版资料.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,计算机图形(txng)学 图形(txng)填充,第一页，共50页。,图形分类,线段图形,直线、圆以及自由曲线等，用于表现物体的几何轮廓,实面积图形,封闭图形，在其封闭的区域内具有相同的颜色。既表现了物体的几何轮廓，也反映了物体表面(biomin)的色彩。,在计算机屏幕上表现为：处于封闭图形内部区域的屏幕象素具有相同的亮度和色彩。,第二页，共50页。,实面积图形的表示,顶点表示法,以封闭多边形的顶点坐标数据（或者，闭合曲线(qxin)的特征数据）来描述实面积图形；其内部以用户指定的颜色填充；基本填充方法：多边形填充。,点阵表示法,以点阵数组的方式描述实面积图形；图形的内部以用户指定的颜色包围或者组成，易于面着色；基本填充方法：种子填充。,顶点(dngdin)表示点阵表示:多边形的扫描转换。,第三页，共50页。,多边形分为凸多边形、凹多边形、含内环的多边形。,注意(zh y)：凹、凸点的判断,第四页，共50页。,实区域(qy)填充算法,确定(qudng)待填充的象素，即检查光栅的每一像素是否位于多边形区域内,解决的主要(zhyo)问题是什么？,图案填充还有一个什么象素填什么颜色的问题,曲线围成的区域，可用多边形逼近,第五页，共50页。,多边形的填充原理,多边形填充的任务:把多边形的顶点表示转换为点阵表示。即，找出所有位于多边形内部的像素点，以所要求的像素值画这些像素点。,可能的做法：,遍历屏幕上的像素点，判断是否在多边形内部，然后填充。,问题：逐点判断，速度太慢；不是(b shi)所有对多边形都容易作内部判断。,关键：寻找一种快速而通用的内部判断方法。,第六页，共50页。,扫描线:点阵图形在屏幕(pngm)上的像素点，可以认为是由位于一条条水平直线上的像素点构成的.,对每一条切割多边形的扫描线，决定扫描线上哪些像素点是在多边形内部，并对这些相应的像素点赋以合适的值表示某种颜色或灰度，就能对整个多边形进行扫描转换。,第七页，共50页。,一条(y tio)扫描线与一个多边形的关系:相交或不相交.若相交,则直线被多边形分割成不同的直线段,其中一些在多边形内,另外一些在多边形外.并且这些多边形内外的直线段大多数情况下相互交替出现.,第八页，共50页。,扫描线连贯性(scan line coherence)：当像素点位于多边形内(外)的直线段上时,它就位于多边形内(外).也就是说，与多边形相交的一条(y tio)扫描线上总会有一组相互相连的像素点都位于多边形之内。,每一个像素点像素点所在的直线段,第九页，共50页。,分析,从扫描线的一端出发(chf),当前在多边形外,当沿扫描线前进到达与多边形的第一个交点时,就进入多边形内；由于扫描线的另一端是在多边形外,继续沿扫描线前进一定会走出多边形内部,于是一定会遇到第二个交点。这时可以看到,第一和第二个交点之间的直线段就位于多边形内；,如果没有更多的交点,则该扫描线上只有一段直线段位于多边形内。否则,继续沿扫描线前进,此时位于多边形外,直到遇到第三个交点后,重新进入多边形内。类似前面的分析,一定有第四个交点。于是第三,第四个交点给出的直线段就位于多边形内；,如果还有更多的交点,就重复这样的过程,直到没有新的交点为止。因为交点个数是有限的,这一过程是一定可以结束的。,第十页，共50页。,射线交点计数的方法：,从多边形外一点，引水平射线（即扫描线）穿过(chun u)多边形，记录扫描线与多边形边的交点个数情况，当交点数为奇数时，扫描线处在多边形内部，当交点数为偶数时，扫描线处在多边形外部。多边形与同一扫描线的交点按x方向大小顺序排列，并两两配对，则可得扫描线在多边形内的直线段，从而可实现多边形填充。,第十一页，共50页。,奇点问题,奇点：当扫描线与多边形的交点是顶点。,如果奇点存在,上述判别过程就不能正确地进行,多边形顶点的潜在问题,这个问题与交点的求解方法有关.,所有交点通过扫描线所在(suzi)直线依次与多边形各边所在(suzi)直线段求解出。如果某个交点恰恰是其中一个边的端点：重复计算。,水平边问题,水平边重合于某一条扫描线：无数多交点，不予处理,第十二页，共50页。,可能(knng)情况图示：,第十三页，共50页。,奇点的处理(chl),多边形的顶点(dngdin)可分为两类：极值奇点和非极值奇点。如果(yi-1-yi)(yi+1-yi)0，则称顶点(dngdin)Pi为极值点；否则称Pi为非极值点。,规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。,第十四页，共50页。,x3 y3 1,0：字符的笔画(bhu)不经过此位，该像素置为背景颜色,设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。,（1）确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。,第四十二页，共50页。,FloodFill4(x,y-1,oldColor,newColor);,不透明填充 1：前景色,边界表示法中，由于边界以特殊(tsh)颜色指定，填充算法可逐个像素地向外处理，直到遇到边界颜色为止。,第三十二页，共50页。,区域填充指先将区域的一点(y din)赋予指定的颜色，然后将该颜色扩展到整个区域的过程。,区域指已经表示成点阵形式的填充图形，它是象素的集合。,直线方程：ax+by+c=0,显示步骤：从字库检索字符数据提出端点(dun din)坐标几何变换根据标志位显示,另一种预处理办法是，通过判断每条斜边的端点y值是否单调来找出奇点，对极值端点不作处理，而对非极值端点则缩短(sudun)其中一条斜边的端点。,(2)出栈：若栈空则结束。,检查交于该顶点(dngdin)的两条边的另外两个端点的y值大于该顶点(dngdin)y值的个数,奇点的计数问题,5,4,3,2,1,0,P,1,P,2,P,3,P,4,I,1,I,2,I,3,I,4,P,5,扫描线5,扫描线4,扫描线3,扫描线2,扫描线1,I,5,I,6,检查交于该顶点(dngdin)的两条边的另外两个端点的y值大于该顶点(dngdin)y值的个数,计数(j sh)0次,计数(j sh)1次,计数2次,第十五页，共50页。,11/10/2025,15,总结：简单地数交点不能解决所有的问题，需要补充规则(guz)完善此射线交点计数法：,（1）忽略多边形的水平边；,（2）与多边形的极值点端点相交时，该点算做两个；,（3）其余的非极值点端点，仅计算一次。,实际操作任务：,（1）判断水平边；,（2）判断奇点；,在求交点过程中，因为是依次计算扫描线与各条边的交点，因此奇点也自然被计算两次。但造成另一个问题是非极值点的顶点也被计算了两次。,第十六页，共50页。,对此问题的一种处理办法是，计算前，先将每条斜边的低端点在y方向上缩小一个(y)屏幕坐标单位，这将忽略极小值,第十七页，共50页。,另一种预处理办法是，通过判断每条斜边的端点y值是否单调来找出奇点，对极值端点不作处理，而对非极值端点则缩短(sudun)其中一条斜边的端点。,此法的缺点是，填充的图形(txng)可能会出现残缺,第十八页，共50页。,这样处理(chl)后，极值点仍计算两次，而非极值点的斜边交点只计算一次。,经上述约定及处理(chl)后，可保证同一扫描线与多边形的交点成对出,现，因此只要算出交点，填充就可以利用画直线算法快速完成。,第十九页，共50页。,枚举出边界上所有(suyu)的像素,对每一条切割多边形的扫描线，决定扫描线上哪些像素点是在多边形内部，并对这些相应的像素点赋以合适的值表示某种颜色或灰度，就能对整个多边形进行扫描转换。,4连通(lintng)、8连通(lintng)、16连通(lintng),在计算机屏幕上表现为：处于封闭图形内部区域的屏幕象素具有相同的亮度和色彩。,确定需要填充(tinchng)的区域与当前扫描线的相交区间,区域填充指先将区域的一点(y din)赋予指定的颜色，然后将该颜色扩展到整个区域的过程。,第三十七页，共50页。,多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界表示(biosh)成八连通区域后，则多边形的扫描转换转化为区域填充。,填充图元生成(shn chn)原理,多边形与同一扫描线的交点按x方向大小顺序排列，并两两配对，则可得扫描线在多边形内的直线段，从而可实现多边形填充。,设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。,区域填充扫描线算法(sun f)（举例分析）,这样处理(chl)后，极值点仍计算两次，而非极值点的斜边交点只计算一次。,连通(lintng)性,如果还有更多的交点,就重复这样的过程,直到没有新的交点为止。,扫描线算法步骤如下：,（1）确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。,（2）从y=ymin到y=ymax，每次用一条扫描线进行(jnxng)填充。,（3）对一条扫描线填充的过程可分为四个步骤：,a、求交：计算扫描线与多边形各边的交点；,b、排序：把所有交点按递增顺序进行(jnxng)排序；,c、交点配对：第一个与第二个，第三个与第四个 等等，每对交点就,代表扫描线与多边形的一个相交区间；,d、区间填色：把这些相交区间内的像素置成不同于背景色的填充色。,第二十页，共50页。,如何计算下一条扫描线与边的交点(jiodin)。,直线方程：ax+by+c=0,当前交点(jiodin)坐标：(xi,yi),下一交点(jiodin)坐标：(xi+1,yi+1),xi+1=(-byi+1)-c)/a=(-byi+1)-c)/a=xi-b/a=xi+1/mi,第二十一页，共50页。,扫描线算法(sun f)特点,特点：算法效率较高。,缺点：对各种表的维持和排序开销(ki xio)太大，适合软件实现而不适合硬件实现。,第二十二页，共50页。,填充图元生成(shn chn)原理,多边形扫描转换,区域(qy)填充,第二十三页，共50页。,区域(qy)填充,区域指已经表示成点阵形式的填充图形，它是象素的集合。,区域填充指先将区域的一点(y din)赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。,第二十四页，共50页。,区域(qy)填充,表示方法：内点表示、边界表示,内点表示,枚举出区域内部的所有(suyu)像素,内部的所有(suyu)像素着同一个颜色,边界像素着与内部像素不同的颜色,边界表示,枚举出边界上所有(suyu)的像素,边界上的所有(suyu)像素着同一颜色,内部像素着与边界像素不同的颜色,第二十五页，共50页。,区域(qy)填充区域(qy)的连通性,连通(lintng)性,4连通(lintng)、8连通(lintng)、16连通(lintng),4连通(lintng)像素（P(xp,yp)）,N4(p)=r|d4(p,r)=1,d4(p,r)=|xp-xr|+|yp-yr|,8连通(lintng)N8(p)=r|d8(p,r)=1,d8(p,r)=max(|xp-xr|,|yp-yr|),p,r,r,r,r,r,r,r,r,p,r,r,r,r,第二十六页，共50页。,区域(qy)填充区域(qy)的连通性,16连通,N16(p)=N8(p)Nk(p),Nk(p)=dk(p,r)=1:马步(m b)邻域,马步(m b)距离,r,r,r,r,p,r,r,r,r,r,r,r,r,r,r,r,r,第二十七页，共50页。,区域(qy)填充区域(qy)的连通性,4连通与8连通区域的区别,连通性：4连通可看作8连通区域，但对边界(binji)有要求,对边界(binji)的要求,第二十八页，共50页。,区域连通方式对填充(tinchng)结果的影响,4连通区域边界填充算法(sun f)的填充结果,8连通区域边界填充算法(sun f)的填充结果,第二十九页，共50页。,区域(qy)填充区域(qy)内外测试,填充过程：确定种子点种子着色区域扩展,问题：如何判断种子合适？,方法：,奇偶规则：射线法。判断射线与多边形边的交点数,奇数：内部点,偶数：外部(wib)点,要求：射线不过顶点,第三十页，共50页。,区域(qy)填充区域(qy)内外测试,用于鉴别物体内外(niwi)点（内部种子点）,非零环绕规则,环绕数：多边形以逆时针方向环绕某一特定点的次数.,多边形内部点环绕数非零,判断方法,差乘法：v A u u*e0 环绕数+1,u*e0 环绕数+1,v e0 环绕数-1,e=VB-VA,第三十一页，共50页。,区域填充(tinchng)边界填充(tinchng)算法,边界表示法中，由于边界以特殊(tsh)颜色指定，填充算法可逐个像素地向外处理，直到遇到边界颜色为止。这种方法称为边界填充算法。,填充算法可以让艺术家或设计师首先勾画图的轮廓，选择填充颜色和填充模式，然后拾取内部点，系统就可以自动给图的内部涂上所需的颜色和图案,填充算法的输入是种子点坐标（x，y），填充色和边界颜色。算法从（x，y）开始检测相邻位置是否是边界颜色，若不是，就用填充色着色，并检测其相邻位置。该过程延续到已经检测完区域边界颜色范围内的所有像素为止。,下面使用栈结构来实现4-连通边界填充算法。可以很容易地将它扩充成8-连通边界填充算法，只要把检查(jinch)4-邻接点改为检查(jinch)8-邻接点即可。步骤如下：,第三十二页，共50页。,设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤如下(rxi)：,种子象素入栈，当栈非空时，执行如下(rxi)三步操作：,（1）栈顶象素出栈；,（2）将出栈象素置成多边形色；,（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,区域填充边界(binji)填充算法,第三十三页，共50页。,区域填充边界(binji)填充算法,递归算法可实现(shxin)如下,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()*/,第三十四页，共50页。,该算法也可以填充(tinchng)有孔区域。,缺点：,(1)有些象素会入栈多次，降低算法效率；栈结构占空间。,(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。,(3)区域内若已有具有填充(tinchng)色的点，递归停止。,改进算法，减少递归次数，提高效率。,解决方法是用扫描线填充(tinchng)算法,区域填充(tinchng)边界填充(tinchng)算法,第三十五页，共50页。,区域填充(tinchng)扫描线算法,扫描线算法,目标：减少递归层次,适用于边界表示的4连通区域,算法思想：在任意不间断区间中只取一个种子(zhng zi)像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的各区段都填充完毕。,第三十六页，共50页。,区域填充(tinchng)扫描线算法,(1)初始化：堆栈置空。将种子点（x，y）入栈。,(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。,(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点(dun din)坐标为xl和xr。,(4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。,上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。,第三十七页，共50页。,区域填充扫描线算法(sun f)（举例分析）,该算法(sun f)也可以填充有孔区域。,像素中的序号标指它所在(suzi)区段位于堆栈中的位置,第三十八页，共50页。,区域(qy)填充扫描线算法（举例分析）,第三十九页，共50页。,区域填充(tinchng)扫描线算法（举例分析）,第四十页，共50页。,区域填充扫描线算法(sun f)（举例分析）,第四十一页，共50页。,区域(qy)填充泛滥填充,问题：边界有多种颜色,区域内部有多种颜色,解决：替换颜色,统一像素颜色，种子(zhng zi)填充,第四十二页，共50页。,区域填充(tinchng)图像填充(tinchng),用一种图案来填充平面区域。,均匀(jnyn)着色,填充方式 位图不透明,位图透明,像素图填充,确定区域内像素点查询图案位图的对应位置,写像素 透明填充 1：前景色,0：不改变,不透明填充 1：前景色,0：背景色,关键：确定区域与图像间的位置关系,第四十三页，共50页。,填充(tinchng)方法:,图案为M*N位图，由数组存放,确定需要填充(tinchng)的区域与当前扫描线的相交区间,确定相交区间内像素点(x,y),图案位图pattern(x%M,y%N),不透明填充(tinchng)或透明填充(tinchng),用透明方式写 不透明方式写,第四十四页，共50页。,多边形扫描转换与区域(qy)填充方法比较,联系：都是光栅图形面着色，用于真实感图形显示。可相互转换。,多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界表示(biosh)成八连通区域后，则多边形的扫描转换转化为区域填充。,区域填充转化为多边形的扫描转换；若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。,第四十五页，共50页。,多边形扫描转换与区域填充(tinchng)方法比较,不同点：,1.基本思想不同；前者是顶点表示转换成点阵表示，后者只改变区域内填充颜色，没有改变表示方法(fngf)。,2.对边界的要求不同,前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。,3.基本的条件不同,前者：从边界顶点信息出发。,后者：区域内种子点。,第四十六页，共50页。,字符(z f)生成,字符：计算机在文本方式下能够在屏幕上显示的数字、字母、音标、标点符号、数学符号、汉字等符号。,编码标准,ASCII码：信息交换用标准代码集,7位二进制编码,GB231280(GB18030-2000)：信息交换用汉字编码字符集基本集,94个区，94个位,采用(ciyng)字节的最高位来标识：0:ASCII码；1:汉字编码。,字库：点阵字库，矢量字库,第四十七页，共50页。,字符(z f)生成点阵字符(z f),字符表示：位图,1：字符的笔画(bhu)经过此位，该像素置为字符颜色,0：字符的笔画(bhu)不经过此位，该像素置为背景颜色,显示步骤：,从字库中检索出位图位图写入帧缓冲器,第四十八页，共50页。,字符(z f)生成矢量字符(z f),字符表示：记录笔画信息笔画端点(dun din)坐标值，连线标志，管理信息，字形信息等,字符的编码,x0 y0 0 不连线,x1 y1 1 连线 2,x2 y2 0 0 1,x3 y3 1,x4 y4 0 4 3 5,x5 y5 1,-1 字符结束标志,显示步骤：从字库检索字符数据提出端点(dun din)坐标几何变换根据标志位显示,第四十九页，共50页。,字符(z f)生成点阵字符(z f)和矢量字符(z f)的比较,点阵字符(z f)矢量字符(z f),位图，对像素变换，图像(t xin)失真,端点坐标，对端点变换，不失真,大,占用空间,字符变换,少,轮廓字形法,美观，轮廓字形法,欠缺,第五十页，共50页。,