图元属性多边形填充

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,多边形的填充,1,：多边形的扫描转换,2,：多边形的区域填充,3,：光栅图形的反走样算法,1,讨论二维区域的填充问题，即面着色的问题，也就是为指定的平面区域填上所需要的颜色。,3.4,多边形的扫描转换与填充,窗口,2,3.4.1,基本概念,多边形：（定义）限定为有封闭折线边界且无交叉边的平面图形,多边形分类：凸多边形、凹多边形,判别凸凹多边形的方法,1,、凸多边形所有向量叉积均同号。若有些叉积取正而有些为负，则是凹多边形,2,、观察多边形顶点位置与每条延长线的关系，若有些顶点在某一延长线的一侧而其他一些顶点在另一侧，则是凹多边形。,分割凹多边形：向量方法、旋转方法,3,分割凹多边形,x,y,向量方法,旋转方法,E,1,E,2,E,3,E,4,E,5,E,6,V,2,V,1,V,3,V,4,4,内,-,外测试,不自交的多边形、自相交的多边形,常用解决方法,:,奇,-,偶规则、非零环绕数规则,1),奇,-,偶规则（,Odd-even Rule,）,从任意位置,p,作一条射线，若与该射线相交的多边形边的数目为奇数，则,p,是多边形内部点，否则是外部点。,5,图例,1,1,3,3,1,6,图例,P,2,2,2,4,7,2),非零环绕数规则（,Nonzero Winding Number Rule,）,首先使多边形的边变为矢量。,将环绕数初始化为零。,再从任意位置,p,作一条射线,(,不经过多边形顶点,),。当从,p,点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形的边从右到左穿过射线时，环绕数加,1,，从左到右时，环绕数减,1,。,处理完多边形的所有相关边之后，若环绕数为非零，则,p,为内部点，否则，,p,是外部点。,8,内,-,外测试,奇,-,偶规则,非零环绕数规则,9,多边形的表示方法,1,、表示方法：定点表示和点阵表示,1,）顶点表示,是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些像素在多边形内。,2,）点阵表示,是用位于多边形内的象素的集合来刻划多边形，该方法虽然没有多边形的几何信息，是面着色所需要的图像表示形式。,多边形填充就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。,实际上，也就是多边形内的区域的着色过程。,图,3.15,多边形顶点表示,图,3.16,多边形点阵表示,10,3.4.2,扫描转换的常用算法,逐点判断算法,扫描线算法,边缘填充算法,边界标志算法,11,3.4.2.1,逐点判断算法,思想：逐个象素判别，确定它们是否在多边形内部，从而给出位于多边形内的点（象素）的集合。,难点：如何确定一个点是否在多边形内部？,12,需要注意的问题,在计算交点时，如果交点恰恰就是多边形的顶,点，必须小心处理，即要观察在此顶点相遇的两条,边，如果这两条边的其余两个顶点在新构成线段的同,一侧，应认为此线段与多边形相交二次；若多边形两,条边的其余两个顶点在新线段的异侧，则认为此线段,与多边形相交一次,（奇点的处理）,。,13,算法的实现,现设,P=P,0,P,1,P,n,P,0,为一给定的多边形。,Framebuffer(x,y),是与点,(x,y),相对应的帧缓冲器中的元素。则逐点判断的算法可以表示成为如下的程序：,for y:= screen-ymin to screen-ymax do,for x:= screen-xmin to screen-xmax do,if inside(p, x, y),then setpixel(framebuffer, x, y, polygon-color),else setpixel(framebuffer, x, y, back-color);,14,逐点判断的算法虽然程序简单，但是不可取。原因是速度太慢，该算法割断了各个象素之间的联系，孤立的考察各个象素和多边形,P,的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别都要多次求交点，需要做大量的乘除运算，花费大量的时间。,15,3.4.2.2,多边形填充的扫描线算法,1,、,特点,：充分利用了相邻象素之间的连续性，避免对象素的逐,点判断和反复求交运算，减少了计算量，提高了算法速度,.,基本概念：,1,）,扫描线的连续性,：扫描线即电子枪由左向右扫过的一行，或用座标的观点来说即,y,=,i,这样的一条线,2,）,边的连续性,3,）,奇点,：扫描线与多边形,P,的交点是,P,的顶点，该交点称为,奇点。,16,设多边形,P,的顶点,又设,是各顶,点,P,i,的纵坐标,y,i,的递减数列,当 时,屏幕上位,于,和 两条扫描线之间的长方形区域被多边形,P,的边分割成若干梯形。,17,1,）扫描线的连续性,设,e,为一整数 ,e,。若扫描线,y=e,与多边形,P,的边,P,i,-1,P,i,相交，则记其交点的横,坐标为 。令：,是该扫描线与,P,的边界各交点横坐标的递增序列，记为,序列,1,。,由区域的连贯性可知，此交点序列具有以下,性质：,(1),l,是偶数。,(2),在该扫描线上，只有区段 位于多边形,P,内,.,P,内,P,内,P,内,18,2,）边的连续性,若,d,为一整数，,d,=,e,1,，且,y,i,0,y,y,i,n,；设位于扫描线,y,=,d,上的交点序列为 ，,记为序列,2,。,若,多边形,P,的边,Pi,-1,Pi,与扫描线,y,=,e,y,=,d,都相交，即：,则序列,1,和 序列,2,有以下关系：,a,：两个序列元素个数相等，即,l=h,b,：点 和 位于多边形的同一个边上，于是有,其中,m,r,为边,P,r,-1,P,r,的斜率,递推式,1,e,d,y,63,y,24,19,3,）奇点的处理,a:,多边形,P,的顶点可分为两类,：,极值点和非极值点,。,如果 ，称顶点,P,i,为极值点,(P,1,P,2,P,3,P,5, P,6,P,8,),；否则称,P,i,为非极值点,(P,0,P,4,P,7,),。,若扫描线与多边形相交于多边形的顶点，则该交点,(,顶点,),称为奇点。,b:,处理时遇到的问题,如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数，如上图中的 扫描线的情况；但若将每一奇点都简单地计为两个交点，同样会导致反常的结果，如上图中 扫描线的情况。,20,3,）奇点的处理,c:,奇点的处理,为了使交点个数保持为偶数，规定当奇点是,P,的极值点时，该点按两个交点计算；否则按一个交点计算。,d:,实际算法,预处理,:,若,P,i,是非极值点，则将 两边中位于扫描线,y,=,y,i,上方的那条边在,P,i,点处截去一单位长,21,扫描线算法,奇点的处理,p,1,p,3,p,4,p,5,属于局部极值点，要把他们两次存入交点表中。 如扫描线,y=7,上的交点中，有交点,(2,7,13),，按常规方法填充不正确，而要把顶点,(7,7),两次存入交点表中,(2,7,7,13),。,p,2,，,p,6,为非极值点，则不用如上处理。,0,2,4,6,8,10,12,2,4,6,8,10,1,2,3,4,0,2,4,6,8,10,12,2,4,6,8,10,1,2,3,p,1,p,2,p,3,p,4,p,5,p,6,p,1,p,2,p,3,p,4,p,5,p,6,22,2,、扫描线算法的实现,对于,每一条扫描线，,多边形的填充过程可分为以下,4,步：,1,4,2,3,把所有的交点按,x,值递增的顺序进行排列；,计算扫描线与多边形各边的交点，设交点个数为,n,；,将排序后的第,1,个与第,2,个交点，第,3,个与第,4,个交点，,第,n-1,个与第,n,个交点配对，每对交点就代表扫描,线与多边形的一个相交区间；,4,把相交区间内的像素置成多边形的颜色，相交区间外,的像素置成背景色。,23,扫描线算法的实现步骤,对于一条扫描线填充过程可以分为四个步骤：,求交,排序,配对,填色,24,2,、扫描线算法的实现,25,3,、扫描线算法的数据结构,a,：数据结构,边的分类表,ET,和边的活化链表,AEL,。,ET,和,AEL,中的多边形的边由四个域组成：,y,max,边的上端点的,y,坐标；,x,ET,中为边的下端点的,x,坐标，在,AEL,中是边与扫描线交点的,x,坐标,x,边的斜率的倒数,next,指向下一条边的指针。,告诉处理到哪条扫描线时，就,可以结束这条边了,记录了初始扫描线与这条边的,初始,x,值,记录当前扫描线与某条边的交点,x,值,dy/dx,，扫描线加,1,时，即,y=y+1,时,x=x+1/m,相交的边对在哪，即要填充哪,两条边之间的区域。,26,3,、扫描线算法的数据结构,AEL,边的活化链表,AEL,由与,当前扫描线相交的所有多边形的边,组成。它记录了多边形边沿扫描线的交点序列,.,当前扫描线与该边的交点坐标为,(,x,i,y,i,),，,则下一条扫描线与该边的交点,(,x,i+1,y,i+1,),不需要重新计算，只要加一个增量即可。,边,的,活,化,链,表,-5/3,5,7,AEL,e,0,e,5,4,2,12,AEL,在,y=2,扫描线上的状态,-5/3,5,5,AEL,e,0,e,5,4,2,14,AEL,在,y=3,扫描线上的状态,2,y,max,x,1/m,AEL,中的各边按照,x,值,(,当,x,的值相等时，按,x,值,),递增方向排序。,27,3,、扫描线算法的数据结构,ET,分类表,ET,按边下端点的纵坐标,y,对边进行分类。也就是说，,如果某边的较低端点为,ymin,，则该边就放在扫描线,ymin,的新边表中。,同一类中，各边按,x,值递增的顺序排列成行。,对于图,3.20,的多边形：,P,0,P,1,P,2,P,3,P,4,P,5,P,6,=,(2,5) (2,10) (9,6) (16,11) (16,4) (12,2) (7,2),多边形的边,y,筒,注意：,其中,P,0,和,P,4,点是非极值点，我们在做,y,边的分类之前已经做过对边,e,1,和,e,4,的,预处理,：分别在,P,0,和,P,4,处截掉一个单,位以保证扫描线,y,=,y,i,只与,Pi-1Pi,、,P,i,P,i+1,两边的一边相交，只求得一个交点。同,时由于,e,6,是水平边，不参加分类。,y,1,2,5,6,28,4,、扫描线算法的步骤：,步骤,1,:(,AEL,初始化,),将边的活化链表,AEL,设置为空,。,步骤,2,:(,y,初始化,),取扫描线,纵坐标,y,的初始值为,ET,中非空元素的,最小序号,步骤,3,：按,从下到上的顺序,对纵坐标值为,y,的扫描线,(,当前扫描线,),执行,下列步骤,，直到边的分类表,ET,和边的活化链表,AEL,都,变成空为止,。,29,5,、扫描线算法的具体步骤：,如边分类表,ET,中的第,y,类元素非空，则将,属于该类的所有边从,ET,中取出并插入边的活化链表,AEL,中,，,AEL,中的各边按照,x,值,(,当,x,的值相等时，按,x,值,),递增方向排序。,-5/3,5,7,AEL,e,0,e,5,4,2,12,AEL,在,y=2,扫描线上的状态,2,从,ET,中选择当前扫,描线的边表，方便活,性边表的建立和更新,30,5,、扫描线算法的具体步骤：,若相对于当前扫描线，边的活化链表,AEL,非空，则将,AEL,中的边两两依次配对，即第,1,，,2,边为一对，第,3,，,4,边为一对，依此类推。,每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点,(,象素,),按多边形属性着色。,利用了扫描线,的连续性,-5/3,5,7,AEL,e,0,e,5,4,2,12,AEL,在,y=2,扫描线上的状态,31,5,、扫描线算法的具体步骤：,将边的活化链表,AEL,中满足,y,=,y,max,的边删去。,(,表明一条边已经结束,),将边的活化链表,AEL,剩下的每一条边的,x,域累加,x,，即,x,:=,x,+,x,。,(,下一条扫描线与边的交点,x,，利用了边的连续性,),将当前的扫描线的纵坐标值,y,累加，即,y,:=,y,+1,(,求下一条扫描线,),-5/3,5,7,AEL,e,0,e,5,4,2,12,AEL,在,y=2,扫描线上的状态,-5/3,5,5,AEL,e,0,e,5,4,2,14,AEL,在,y=3,扫描线上的状态,e0:m=-5/3,所以,x,变为,7,5/3,5,e5:m=2,所以,x,变为,12+2,14,y=y+1,即,y=2+1=3,32,-5/3,5,5,AEL,e,0,e,5,4,2,14,AEL,在,y=3,扫描线上的状态,-5/3,5,3,AEL,e,0,e,5,4,2,16,AEL,在,y=4,扫描线上的状态,-5/3,5,2,AEL,e,0,e,4,9,2,16,AEL,在,y=5,扫描线上的状态,5,4,因为对于,e5,y,的,max,已经到了，,故去掉,e5,，而,从,ET,表中加入,e4,33,扫描线算法描述,建立,ET,表，置,y,为,ET,表中非空的最小,y,坐标值,置,AEL,表为空，且按照,y,值将,ET,表的边加入,AEL,表中,while AEL,表非空并且,ET,表中非空,dobegin,对,AEL,表中的,x,min,值按升序排列,按照,AEL,表中交点前后次序，在每对奇偶交点间的,x,段予以填充,if,扫描线,y=y,max,then,从,AEL,表中删除这些边,对在,AEL,表中的其他边，计算与下一条扫描线的交点：,x=x+1/m,计算下一条扫描线：,y=y+1,按照扫描线,y,值把,ET,表中相应的边加入,AEL,表中,end,end of algorithm,34,扫描线算法性能分析,扫描线算法的数据结构和程序结构都远比逐点判断算法复杂，对各种表的维护和排序的耗费很大。但是由于它充分利用的多边形的区域、扫描线和边的三种形式的连贯性，从而避免了反复求交点的大量运算，因此速度比逐点判断法快的多。,35,3.4.2.3,边缘填充算法,1,、特点：,采用对图像进行逐位求反的方法，免去对边排序,的工作量,2,、,预备知识：,对颜色,M,作偶数次求反运算，其结果还是,M,，而对,M,作奇数次,求反运算的结果是,M,的反,M,。,在光栅图形中，如某区域已着,上值为,M,的某种颜色，则上述求反运算得到的结果是：对区,域作偶数次求反运算后，该区域的颜色不变；作奇数次求反,运算后，该区域的颜色则变成值为,M,的颜色。,36,3,、边缘填充算法的实现,实现：对多边形,P,的每一非水平边上的各像素做向右求反运算,即可，见下图，其中,(a),为给定的多边形；,(b),为对区域赋初值；,(c),，,(d),，,(e),和,(f),表示逐边向右求反。,37,3.4.2.4,边界标志算法,1,、基本原理：首先,用一种,特殊的颜色,在帧缓冲器中将多边形,的,边界,（水平边的部分边界除外）,勾画,出来。,然后,再把位于,多,边形内,的各个,像素着上所需的颜色。,2,、,算法具体实现步骤：,步骤,1,：,以值为,boundary-color,的特殊颜色,勾画,多边形,P,的,边界,。设多边形顶点为,P,i,= (,x,i,y,i,),0,i,n,，,x,i,y,i,均为整数；置,P,n,+1,=,P,0,。,每一条扫描线上着上这种特殊颜色的点的个数必定是偶数,(,包括零,),。,步骤,2,：,设,interior_point,是一布尔变量。对每一条扫描线从左到右进行搜索，如果当前是,像素,位于,多边形,P,内,，则,interior_point=true,，,需要,填上,值为,polygon_color,的颜色；否则该,像素,在,多边形,P,外,，需要填上值为,background_color,的颜色。,38,3,、边界标志算法实例,标志边界并处理奇点,P,2,(9,6),P,0,(2,5),P,1,(2,11),P,3,(15,9),P,4,(15,3),P,5,(12,1),P,6,(7,1),for(i=0;i0)x=pi.x;else x=pi+1.x;,ymax=(Math.max(pi.y,pi+1.y);,ymin=(Math.min(pi.y,pi+1.y);,for (y=ymin+1;y=ymax ;y+ ), x=(int)(x+dx+.5);,if(pixels(x, y)=blue),pixels(x+1, y)=blue;,else pixels(x, y)=blue;,/ for(i=0;i=n;i+),确定某条边的,上下,端点,水平边不考虑,多边形的边数,边界颜色,蓝色,P0P1,的底端点,ymin,P0P1,的上端点,ymax,X,X,X,X,X,X,P1P2,的底端点,ymin,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,39,3,、边界标志算法实例,P,2,(9,6),P,0,(2,5),P,1,(2,11),P,3,(15,9),P,4,(15,3),P,5,(12,1),P,6,(7,1),X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,/maxx,、,maxy,、,minx,、,miny,是获得的多边,/,形最小矩形包围盒边界值,for(y1 = miny - 1,;,y1= maxy,;y1+), in_flag = 0;,/,多边形内部标志变量,for( x1 = minx - 1;,x1=maxx - 1;,x1+),l,= pixels(x, y);,/,多边形边界颜色,blue,if (,l,= blue) ,if (in_flag = 0) in_flag = 1;,else in_flag = 0;,if (in_flag),pixels(x, y)=blue;,/,在多边形内部填充色蓝色,else,pixels(x, y)=white;,miny,minx,maxx,maxy,获得当前象素,颜色以判断是否,是边界色,如果是边界，且第一,/,三次碰到边界，就置,flag,为,1,，表明其后的象素要置成多边形的颜色,如果是第二,/,四次遇到边界，就置,flag,为,0,，对其后的元素置背景色为白色。,40,3,、边界标志算法实例,P,2,(9,6),P,0,(2,5),P,1,(2,11),P,3,(15,9),P,4,(15,3),P,5,(12,1),P,6,(7,1),X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,P,2,(9,6),P,0,(2,5),P,1,(2,11),P,3,(15,9),P,4,(15,3),P,5,(12,1),P,6,(7,1),X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,41,3.3.2.5,区域填充,一、区域的基本概念,1,、区域,是指已经表示成点阵形式的像素集合。,在光栅图形,中，区域可采用内点表示和边界表示两种形式进行描述。,内点表示法：,把位于给定区域,内,的所有,像素,一一,列举,出来的方法称为内点表示法。,图,3.25,内点表示的区域,图,3.26,边界表示的区域,边界表示法：,把位于给定区域,边界,上的,像素,一一,列举,出来的方法称为边界表示法。,42,1,）,4,连通的区域,:,取区域内任意两,点，在该区域内若从其中一点出发,通过上、下、左、右四种运动可到,达另一点。,图,3.24,四个方向的运动,2,）,8,连通的区域,:,取区域内任意两,点，若从其中任一点出发，在该,区域内通过沿水平方向、垂直方向,和对角线方向的八种运动可到达另,一点。,图,3.25,八个方向的运动,2,、区域的连通性,43,3,）,4,连通区域也可理解成,8,连通区域，即,4,连通能达到的,8,连通肯定能达到，,4,连通只是,8,连通的一种特殊情况。,图,3.26,内点表示的八连通区域,图,3.27,边界表示的八连通区域,8,连通而,非,4,连通,的地方,连通不是指边界而是边界内的区域这里是,X,围起来的区域,号是区域,X,是边界,44,但是两者的边界,不尽相同,。如果图中标有,号的象素组成的区域作为,4,连通区域，则其边界由图中的标有,号的象素组成。如果将该区域作为,8,连通的区域，则其边界由图中标有,号和,号的两种象素组成。,因为如果区域是,8,连通的， 边界不能将区域有效封堵，,X,的位置和区域又是连通的了。,图,3.28,四连通区域与八连通区域的不同边界,45,二、简单的种子填充算法,基本思想：给定区域,G,一种子点,（,x,y,）,首先,判断该,点,是否是,区域内,的一点，如果是，则将该点,填充,为,新的颜色,，然后将,该点周围的四个点,（四连通）或,八,个点,（八连通）作为新的,种子点,进行同样的处理，通,过这种,扩散,完成对整个区域的填充。,46,算法描述如下：,1,将种子象素入栈；,2,当栈非空时，重复：,栈顶象素出栈；,若该象素未填充，则将出栈象素置成填充色,以该象素为中心，检查出栈象素的,4-,邻接点，依“左上右下”顺序将非边界象素和未填充象素压入堆栈。若其中某个象素点不是边界色且未置成填充色，则把该象素入栈,47,简单的种子填充算法,void flood_fill_8(int pixels, int x, int y, int old_color, int new_color),if(x0&y0), if (pixelsy*w+x=old_color),pixelsy*w+x= new_color);,flood_fill_8(pixels, x,y+1,old_color,new_color);,flood_fill_8(pixels, x,y-1,old_color,new_color);,flood_fill_8(pixels, x-1,y,old_color,new_color);,flood_fill_8(pixels, x+1,y,old_color,new_color);,flood_fill_8(pixels, x+1,y+1,old_color,new_color);,flood_fill_8(pixels, x+1,y-1,old_color,new_color);,flood_fill_8(pixels, x-1,y+1,old_color,new_color);,flood_fill_8(pixels, x-1,y-1,old_color,new_color);, ,48,堆栈变化步骤,例子：,49,种子象素为（,3,，,2,）,填充（,3,，,2,），入栈（,3,，,2,）,出栈（,3,，,2,），填充并入栈（,2,，,2,），（,3,，,3,），（,4,，,2,），（,3,，,1,）,出栈（,3,，,1,），填充并入栈（,2,，,1,），（,4,，,1,）,出栈（,4,，,1,），出栈（,2,，,1,），出栈（,4,，,2,），,出栈（,3,，,3,），填充并入栈（,2,，,3,）,出栈（,2,，,3,），出栈（,2,，,2,），填充并入栈（,1,，,2,），出栈（,1,，,2,）,50,递归算法的性能分析,区域填充的递归算法程序简单，表达清楚。但由于多层递归，系统堆栈反复进出，费时费内存。,51,三、扫描线种子填充算法,1,、基本思想：,从,给定的,种子点开始，,填充,当前扫描线上,种子,点所在,的一,区段,，然后确定与这一段相邻的,上下两条,扫描线,上位于区域内的区段（需要填充的区间），从,这些区间上,各取一个种子点,依次把它们存起来，,作为,下次填充的种子点,。反复进行这过程，直到所保存的,各区段都填充完毕。,52,2,、算法步骤：,步骤,1,：,（初始化）,将算法设置的堆栈置为空。将给定的,种子点,（,x,y,）,压入堆栈,步骤,2,：,（出栈）,如果堆栈为空，算法结束；否则取栈顶,元素（,x, y,）作为种子点,1,2,栈,种子,53,步骤,3,：,（区段填充）,从种子点,（,x, y,）,开始，沿纵坐标为,y,的当前扫描线向左右两个方向逐个像素用新的颜色值进行填充，直到边界为止即象素颜色等于边界色。设区间两边界的横坐标分别为,xleft,和,xright,。,步骤,4,：,在与当前扫描线相邻的上下两条扫描线上，以区间,xleft, xright,为搜索范围，求出需要填充的,各小区间,，把,各小区间,中最右边的点并作为种子点压入堆栈，转到步骤,2,。,1,2,种子点,xleft xright,54,区域填充的扫描线算法描述,将种子象素点压入堆栈,while,堆栈非空,do begin,从堆栈中弹出一个种子象素,沿着扫描线对种子象素的左右象素进行填充，直至遇到边界 象素为止,标志区间内最左和最右象素为,x,left,和,x,right,if,在,x,left,xx,right,中检查与当前扫描线相邻的上下两条扫描线全为边界象素或全为已填充过的象素,then goto 2,在,x,left,xx,right,中标记每一个既不包含边界象素又不包含已填充过的象素的区间,将每一区间的最右象素作为种子象素压入堆栈,end,end of algorithm,55,3,、算法的关键原则：,1,）搜索原则：,从前一个填充的区间（边界之间的,范围,xleft,xright,）作为后一条扫描线种子点寻找的范围。,2,）填充原则：,从种子点往,左，右,填，填到边界,1,2,1,2,如果种子,点在这里,xleft,xright,搜索确定种子点,种子点填充,56,1,2,1,2,1,0,2,2,2,2,3,3,2,2,2,2,2,4,、实例,57,Stack stack=new Stack();,/,堆栈,pixel_stack,初始化,Stack.push (point),；,/(x,y),是给定的种子像素,while (!stack.empty(),p=(Point)(stack.pop(),；,/,出栈，从堆栈中取一像素作种子像素,x=p.x; y=p.y;,savex=x,；,/,保存种子点的横坐标,x,的值,while (dc.GetPixel(x,y)!= boundary_color),dc.SetPixel(x,y,new_color);,x+;,/,从种子像素开始向右填充到边界,xright=x1;,/,保存线段的右端点,x=savex1;,/,设定种子点往左填充的起点,x-1,填充过程,x,xr,5,、程序实现,58,while (,dc.GetPixel(x,y)!= boundary_color,),dc.SetPixel(x,y,new_color);,x=x1;,/,从种子像素开始向左填充到边界，以上两步完成区间填充。,xleft=x+1,；,/,保存线段的左端点，加,1,是因为前面,/,循环时多减一次,x=xleft;,/,起点是上次的左端点,y=y+1;,/,开始处理上一条扫描线,填充过程,x,x-1,xleft,59,while(x=xright) ,/,在上一条扫描线上检查是否需要填充,span_need_fill=false,;,/,先设定为不需要填充,while (dc.GetPixel(x,y)=old_color,&x=xright,) ,/,待填充的线段,span_need_fill=true;,/,发现有旧象素，需要填充,x=x+1;,/,待填充的线段处理完，即遇到边界色，,!=old_color,跳出,if (span_need_fill) ,/,如果区间需要填充，则将其右端点作,为种子点压进堆栈,p=new Point(x-1,y);,stack.push (p);,/,进栈,span_need_fill=false;,60,/,继续向右检查以防有遗漏,while (,dc.GetPixel(x,y),!=old_color &x=xright ),x=x+1;,/,在上一条扫描线上检查完,x,xleft,；,y=y2;,/,形成下一条扫描线的,y,值,/,在下一条扫描线上从左向右检查位于区间,xleft,，,xright,上的像素，其方法与在上一条扫描线上检查的情况完全一样。,/,出栈完,如果种子,点在这里,1,2,1,2,3,xleft,xright,61,扫描转换和区域填充的比较,多边形的扫描转换和区域填充是两类典型的面着色问题，在一定条件下两者可以相互转换。但二者的基本思想是不同的。,多边形的扫描转换是指,将多边形的顶点表示转换成点阵表示,，在扫描转换过程中利用了多边形各种形式的连贯性；,区域填充,只改变区域的颜色，不改变区域的表示方法。,在填充过程中应用了区域的连通性。,62,3.4,字符的生成,3.4.1,点阵式字符,在点阵字符库中，每个字符由一个位图表示。该位为,1,表示字符的笔画经过此位，对应于此位的象素应置为字符颜色。该位为,0,表示字符的笔画不经过此位，对应于此位的象素应置为背景颜色。在实际应用中，有多种字体（如宋体、楷体等），每种字体又有多种大小型号，因此字库的存储空间是很庞大的。,63,常用的点阵大小有,79,、,88,、,1616,等。下图所示的是字母“,P”,的点阵式表示。显示点阵式字符时，只需将字库中的矩形点阵映射到帧缓冲器中的单元即可。,64,3.4.2,轮廓式字符,轮廓式字符是将每个字符定义为一条曲线或多边形的轮廓，显示时需要进行扫描转换。如下图所示为字母“,B”,的轮廓表示，轮廓线构成了一个或若干个封闭的平面区域，显示时字符轮廓的内部需用扫描线填充程序来填充。,65,3.5,光栅图形的反走样算法,a:,图形的边界一般都呈阶梯形,b:,图形的细节失真、狭小图形遗失,（,a,） 待显示的细小图形,（,b,） 显示结果,细节失真,（,a,）待显示的狭小矩形,（,b,） 显示结果,狭小图形的遗失,阶梯形边界,阶梯形线段,3.5.1,光栅图形的走样现象,66,3.5.2,提高分辨率的反走样方法,采用,硬件,:,采用高分辨率的光栅图形显示器，花费的代价大。,采用,软件,:,花费的代价小，也容易实现。,高分辨率计算,：将低分辨的图形显示象,素划分为许多子象素，如,22,划分，,33,划分等，然后按通常的算法计算 出各个子象素的颜色值或灰度值。,低分辨率显示,：将一象素内的各个子象,素的颜色值或灰度值的平均值作为该,象素的颜色值或灰度值。求平均值时,可取算术平均，也可取加权平均。,加权表,1,、用,软件,提高分辨率的方法是：,高分辨率计算，低分辨率显示。,67,3.5.3,区域采样的反走样算法,1,、线段的反混淆算法的,基本思想,可归纳如下：,(1),把线段看作是有,宽度,的狭长的,矩形,(,因为线段是有宽度的,),，,所以,(2),线段具有一定的面积，当线段通过某象素时，可以求出,线段与像素的面积的交，,然后,(3),根据每一象素与线段相交部分的面积值决定该象素的颜色值或灰度值。,有宽度的线段,反走样后线段的显示,68,3.5.3,区域采样的反走样算法,设一条直线的斜率为,m,，其宽度为一个像素单位，则直线与像,素相交的情况共有,5,种。,(a),(b),(c),(d),(e),在计算阴影面积时，（,a,）与（,e,）、（,b,）与（,d,）类似，（,c,）可用正方形的面积减去,2,个三角形的面积。因此只讨论（,a,）和（,b,）的情况。如下图，情况（,a,）的阴影面积为,D,2,/2m,；情况（,b,）的阴影面积为,D-m/2,。,D,D/m,D,m,(a),(b),阴影面积的计算,69,3.5.3,区域采样的反走样算法,上述阴影面积是介于,0,1,之间的正数，用它乘以像素的最大灰度值，再取整，就可得到像素的显示灰度值。将这种区域采样的反走样算法用于直线段时，就相当于将线段上位于原相邻阶梯之间的像素置为了过渡颜色或灰度，从而使得颜色或者灰度过渡自然，变化柔和。阶梯被淡化后，线形自然就显得平直了。,为了简化运算，有时候还可以采用离散的方法。即将屏幕像素均分成,n,个子像素，计算中心点落在直线段内的子像素的个数,k,，那么该像素的亮度就是最大灰度值乘以相交区域面积的近似值,k/n,。左图所示是,n=9,，,k=3,，近似面积为,1/3,的情况。,70,3.5.4,加权区域采样的反走样算法,将像素均分成,n,个子像素，每个子像素的面积为,1/n,，计算每个子像素对原像素的贡献，并保存在一张二维的加权表中（,3.5.2,节的图中的（,a,）、（,b,）就是将一个像素分别均分为,33,个子像素和,77,个子像素时所对应的加权表）；求出所有中心落在直线段内的子像素组成的集合，并计算这些子像素对原像素的亮度贡献之和的值，该值乘以像素的最大灰度值就得到该像素最终要显示的亮度。,71,课件等相关资料下载：,E-Mail,：,密码：,geoscience2008,72,