《边缘填充》PPT课件.ppt

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