《边缘填充》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息科学与工程学院,*,第,8,讲 多边形的扫描转换,2024/10/8,1,信息科学与工程学院,本节内容安排,上节回顾,5.4,多边形的扫描转换,小结、作业,2024/10/8,2,信息科学与工程学院,上节回顾,直线的扫描转换,圆的扫描转换,椭圆的扫描转换,2024/10/8,3,信息科学与工程学院,5.4 多边形的扫描转换与区域填充,在光栅扫描显示器中表示一个区域，仅仅画出其边界是不够的，有时还要填上一定的灰度、色彩。,多边形的扫描转换,主要是通过,确定,穿越多边形区域的扫描线的覆盖区间来填充。,/,适用于多边形区域和多边形拟合的其他简单曲线区域。,区域填充,是从给定的位置开始涂描直到指定的边界条件为止。,/,适用于复杂边界的多边形以及交互式绘图系统中。,2024/10/8,4,信息科学与工程学院,5.4.1 多边形的扫描转换,多边形的两种表示方法：,顶点表示：,用多边形的顶点序列来刻划多边形。,直观、几何意义强、占内存少；不能直接用于面着色。,点阵表示,是用位于多边形内的像素的集合来刻划多边形。,失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。,1.什么是多边形的扫描转换,P,5,P,0,P,1,P,2,P,3,P,4,2024/10/8,5,信息科学与工程学院,既然大多数图形应用采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形顶点表示到点阵表示的转换，这种转换就称为扫描转换多边形或多边形的填充，,扫描转换多边形或多边形的填充,：从多边形顶点表示到点阵表示的转换,。,也就是从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色,2024/10/8,6,信息科学与工程学院,2.,x-,扫描线算法,基本思想,:,按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，完成填充工作。,根据该原理，此算法可以填充凸的、凹的、带孔的多边形域。,P,5,P,0,P,1,P,2,P,3,P,4,2024/10/8,7,信息科学与工程学院,多边形分为凸多边形、凹多边形、含内环的多边形。,凸多边形：任意两顶点间的连线均在多边形 内,凹多边形任意两顶点间的连线有不在多边内形内的部分,含内环的多边形,2024/10/8,8,信息科学与工程学院,x-,扫描线算法原理：,对于每条穿越多边形的扫描线，此算法确定扫描线与多边形相交区间的像素点位置。,如：,y=3,算法的核心：,必须按,x,递增顺序排列交点的,x,的坐标序列。,2024/10/8,9,信息科学与工程学院,算法步骤,：,(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大,y,值（,y,min,和,y,max,）。,(2),从,y=y,min,到,y=y,max,，,每次用一条扫描线进行填充。对一条扫描线填充的过程可分为四个步骤：,a.,求交：计算扫描线与多边形各边的交点；,b.,排序：把所有交点按,x,值递增顺序排序；,c.,配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;,d.,填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。,2024/10/8,10,信息科学与工程学院,对下图，试想扫描转换过程？,2024/10/8,11,信息科学与工程学院,存在问题：,当扫描线与多边形顶点相交时，交点的取舍问题。,2024/10/8,12,信息科学与工程学院,解决,：,当扫描线与多边形的顶点相交时，,若共享顶点的两条边分别落在扫描线的两边，交点只算一个；,若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。,具体解决方法为：,检查共享顶点的两条边的另外两个端点的,y,值，按这两个,y,值中大于交点,y,值的个数是0、1、2来决定交点数取0、1、2。,2024/10/8,13,信息科学与工程学院,0,1,1,1,1,0,2,2,2,填充过程代,码,2024/10/8,14,信息科学与工程学院,x-,扫描线算法的缺点,x-,扫描线算法在处理每条扫描线时，需要与多边形的所有边求交这样处理效率很低。这是因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交。若在处理每条扫描线时，不分青红皂白地把所有边都拿来与扫描线求交，则其由绝大多数计算都是徒劳无用的。因此将,x,扫描线算法加以改进，形成改进的有效边表算法，也称为,y,连贯性算法,2024/10/8,15,信息科学与工程学院,3.改进的有效边表算法（,Y,连贯性算法）,改进原理,：,处理一条扫描线时，仅对有效边求交,利用扫描线的连贯性,利用多边形边的连贯性,2024/10/8,16,信息科学与工程学院,有效边（,Active Edge）,：,指与当前扫描线相交的多边形的边，也称为活性边。,有效边表（,Active Edge Table,AET）,：,把有效边按与扫描线交点,x,坐标递增的顺序存放在一个链表中，此链表称为有效边表。,有效边表的每个结点：,x y,max,1/k next,x,为当前扫描线与边的交点,y,max,为边所在的最大扫描线值,1/,k,为从当前扫描线到下一条扫描线间,x,的增量,P,5,P,0,P,1,P,2,P,3,P,4,2024/10/8,17,信息科学与工程学院,1.4,12,2/5,P,2,P,1,y=8,7,12,-1,P,0,P,1,7,9,5,P,0,P,6,11.5,9,1/2,P,5,P,6,2024/10/8,18,信息科学与工程学院,有效边表的结点类型可为：,typedef struct LineAE /*,有效边描述结构*/,float x;/*,当前扫描线与边的交点*/,float dx;/*,斜率的倒数*/,int ymax;/*,边所在的最大扫描线值*/,struct LineAE*next;/*,指向下一条有效边*/,ActiveEdge;,2024/10/8,19,信息科学与工程学院,边表（,Edge Table）,方便有效边的建立和更新,边表的构造：,(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个,桶,，其对应多边形覆盖的每一条扫描线。,(2)将每条边的信息链入与该边最小,y,坐标（,y,min,）,相对应的桶处。也就是说，若某边的较低端点为,y,min,，,则该边就放在相应的扫描线桶中。,2024/10/8,20,信息科学与工程学院,(3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点,x（,即较低端点的,x,值），1/,k，,以及该边的最大,y,值,y,max,。,x|,ymin,y,max,1/k next,(4),同一桶中若干条边按,x|,ymin,由小到大排序，若,x|,ymin,相等，则按照1/,k,由小到大排序。,2024/10/8,21,信息科学与工程学院,解决顶点交点计为1时的情形,：,2024/10/8,22,信息科学与工程学院,2024/10/8,23,信息科学与工程学院,2024/10/8,24,信息科学与工程学院,算法步骤,：,(1)初始化：构造边表，,AET,表置空；,(2)将第一个不空的,ET,表中的边与,AET,表合并；,(3)由,AET,表中取出交点对进行填充,。,填充时设一布尔变量,b(,初值为假)，令指针从,AET,中第一个结点到最后一个结点遍历一次，每访问一个结点，把,b,取反一次，若,b,为真，则把从当前结点的,x,值到下一结点的,x,值结束的区间用多边形色填充。填充之后删除,y=y,max,的边。（期间，,x=round(x)）,(,4),y,i+1,=y,i,+1,根据,x,i+1,=x,i,+1/k,计算并修改,AET,表，同时合并,ET,表中,y=y,i+1,桶中的边，按次序插入到,AET,表中，形成新的,AET,表；,(5),AET,表不为空则转(3)，否则结束,。,若将步骤(3)改为先,删除,y=y,max,的边,再填充，则是按照“下闭上开”的原则进行填充，就不必再缩短任何边,2024/10/8,25,信息科学与工程学院,算法描述为,：(参考),void polyfill(,多边形,polygon,int color),for(,各条扫描线,i),初始化新边表头指针,NET i；,把,y,min,=i,的边放进边表,NET i;,y=,最低扫描线号；,初始化活性边表,AET,为空；,for(,各条扫描线,i),把新边表,NETi,中的边结点用插入排序法插入,AET,表，使之按,x,坐标递增顺序排列；,遍历,AET,表，把,y,max,=i,的结点从,AET,表中删除，并把,y,max,i,结点的,x,值递增,Dx；,若允许多边形的边自相交，则用冒泡排序法对,AET,表重新排序；,遍历,AET,表，把配对交点区间(左闭右开)上的像素(,x,y)，,用,putpixel(x,y,color),改写像素颜色值；,2024/10/8,26,信息科学与工程学院,5.4.2 边缘填充算法,边缘填充算法,基本思想,按任意顺序处理多边形的每条边。在处理每条边时，首先求出该边与扫描线的交点，然后将每一条扫描线上交点右方的所有像素取补。,2024/10/8,27,信息科学与工程学院,边缘填充算法,最适用于具有帧缓存的图形系统，,算法简单，但对于复杂图型，每一像素可能被访问多次，输入输出的量比有效边表算法大得多。,栅栏填充算法,栅栏,指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。,基本思想：按任意顺序处理多边形的每条边，但在处理每条边与扫描线的交点时，将交点与栅栏之间的像素取补。,2024/10/8,28,信息科学与工程学院,尽管栅栏填充算法减少了被重复访问像素的数目，但仍有一些像素会被重复访问。为了改进该方法，可采用先画边界后填色的方法边标志算法。,2024/10/8,29,信息科学与工程学院,边标志算法,分为两个步骤：,(1)打标记,对多边形的每条边进行扫描转换，即将多边形边界经过的像素打上边标志。,易知，每条扫描线上打标志的点的个数必为偶数；,对于多边形的局部最高点和最低点，多按“下闭上开”的原则处理。,2024/10/8,30,信息科学与工程学院,边标志算法,(2)填充,对每条与多边形相交的扫描线，依从左到右的顺序，按“左闭右开”的原则对扫描线上的像素点进行填色。,使用一个布尔量,inside,来指示当前点是否在多边形内的状态。,Inside,的初值为假，每当当前访问的像素为被打上边标志的点，就把,inside,取反。对未打标志的像素，,inside,不变。若访问当前像素时，,inside,为真，说明该像素在多边形内，则把该像素置为填充颜色。,2024/10/8,31,信息科学与工程学院,算法描述为,：,void edgemark_fill(,多边形,polydef,int color),对多边形,polydef,每条边进行直线扫描转换；,inside=FALSE;,for(,每条与多边形,polydef,相交的扫描线,y),for(,扫描线上每个像素,x),if(,像素,x,被打上边标志),inside=!(inside);,if(inside！=FALSE)putpixel(x,y,color);,else putpixel(x,y,background);,2024/10/8,32,信息科学与工程学院,与上两个算法相比，边标志算法避免了对帧缓存中大量元素的多次赋值，但需逐条扫描线地对帧缓存中的元素进行搜索和比较。,当用软件实现本算法时，速度与改进的有效边表算法相当，但本算法用硬件实现后速度会有很大提高。,2024/10/8,33,信息科学与工程学院,小结,多边形的扫描转换,X-,扫描线算法,改进的有效边表算法,边缘填充算法,作业,P145,5.10,2024/10/8,34