第讲_区域填充和字符处理.ppt

信息科学与工程学院 1999年7月 5.4.1 多边形的扫描转换 多边形的两种表示方法： 顶点表示：用多边形的顶点序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。 点阵表示是用位于多边形内的像素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。 改进的有效边表算法（Y连贯性算法） 有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。 有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。 有效边表的每个结点： x ymax 1/k next 边表（Edge Table）——方便有效边的建立和更新 边表的构造： (1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，其对应多边形覆盖的每一条扫描线。 (2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。 (3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。 x|ymin ymax 1/k next 算法步骤： (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)，否则结束。 5.4.2 边缘填充算法 边缘填充算法基本思想 按任意顺序处理多边形的每条边。在处理每条边时，首先求出该边与扫描线的交点，然后将每一条扫描线上交点右方的所有像素取补。 边缘填充算法最适用于具有帧缓存的图形系统，算法简单，但对于复杂图型，每一像素可能被访问多次，输入输出的量比有效边表算法大得多。 栅栏填充算法 栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。 基本思想：按任意顺序处理多边形的每条边，但在处理每条边与扫描线的交点时，将交点与栅栏之间的像素取补。 尽管栅栏填充算法减少了被重复访问像素的数目，但仍有一些像素会被重复访问。为了改进该方法，可采用先画边界后填色的方法——边标志算法。 边标志算法 分为两个步骤： (1)打标记 对多边形的每条边进行扫描转换，即将多边形边界经过的像素打上边标志。 易知，每条扫描线上打标志的点的个数必为偶数； 对于多边形的局部最高点和最低点，多按“下闭上开”的原则处理。 边标志算法 (2)填充 对每条与多边形相交的扫描线，依从左到右的顺序，按“左闭右开”的原则对扫描线上的像素点进行填色。 使用一个布尔量inside来指示当前点是否在多边形内的状态。Inside的初值为假，每当当前访问的像素为被打上边标志的点，就把inside取反。对未打标志的像素，inside不变。若访问当前像素时，inside为真，说明该像素在多边形内，则把该像素置为填充颜色。 算法描述为： 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); ?? } } EdgeMarkFill(int p[][2],int n,int boundarycolor,int newcolor){　int i,x,y,flag,xmin,xmax,ymin,ymax;　setc