CG03区域填充.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,区域填充的算法,多边形填充,实面积图形,填充后的多边形称为实面积图形，实面积图形在其封闭的轮廓内具有相同的颜色，这意味着要填充光栅显示器上封闭图形内的每一个像素点。实面积图形既能描述物体的几何轮廓，又能表现物体的表面颜色，与人们观察物体表面的习惯相一致，同时，实面积图形也是描述三维物体、绘制三维真实感图形的基础。,多边形的定义,1.,凸多边形,多边形上任意两顶点间的连线都在多边形之内，凸点对应的内角小于,180,度，只具有凸点的多边形称为凸多边形。,2.,凹多边形,多边形上任意两顶点间的连线有不在多边形内部的部分，凹点对应的内角大于,180,度，有凹点的多边形称为凹多边形。,环,多边形内包含有另外的多边形。如果规定每条有向边的左侧为期内部面积区域，则当观察者沿着边界行走时，内部区域总在其左侧，也就是说多边形外轮廓线的环行方向为逆时针，内轮廓线的环行方向为顺时针。这种定义了环行方向的多边形称为环。,多边形的表示,顶点表示法,多边形的顶点表示法是用多边形的顶点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换。,点阵表示法,多边形的点阵表示法就是用多边形覆盖的像素点集来描述。特点是便于直接确定实面积图形覆盖的像素点是多边形填充所需要的表示形式，但是缺少了多边形顶点的几何信息。,多边形的扫描转换,将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出多边形内部的各个像素点信息。,多边形的填充,多边形的填充是指从多边形的顶点信息出发，求出其覆盖的每个像素点，置为填充色，而将多边形外部的像素点保留为背景色。多边形填充的主要工作是确定穿越多边形内部的扫描线的覆盖区间。,首先确定多边形覆盖的扫描线条数，对每一条扫描线，计算机扫描线与多边形边界交点区间。然后再将该区间内的像素赋予指定的颜色。,区域填充,区域是指一组相邻而又具有相同忏悔的像素，可以理解为多边形的内部。区域的边界色和填充色不一致，填充算法只对区域内部进行填充。种子填充算法是从给定的种子位置开始，按填充颜色点亮种子的相邻像素考虑到颜色不同的边界像素为止。种子填充算法主要有,4,邻接点简洁和,8,邻接点算法。,区域填充算法,区域填充可以分两步进行，第一步先确定需要填充哪些象素。第二步确定用什么颜色值来填充。,1,扫描线多边形域的填充,基本原理：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形的界线的交点获得。,一个多边形与若干扫描线,y,0,P,4,(11,8),P,6,(2,7),P5(5,5),P,1,(2,2),P,3,(11,3),P,2,(5,1),1,5,10,5,A,B,C,D,G,E,F,基本步骤：,如图所示，扫描线,6,与多边形的边界线交于四点,A,、,B,、,C,、,D,。,这四点反扫描线分为五个区间,0,2,2,3.5,3.5,7,7,11,11,12,。其中，,2,3.5,7,11,两个区间落在多边形内，该区间内的象素应取多边形色。其它区间背景色。,这里的四个交点在计算时未必是按从左到右顺序获得。因此交点序列必需经过排序，才能得到从左到右，按,x,递增增顺序排列的交点,x,坐标序列。,（,1,）,求交：计算扫描线与多边形各边的交点；,（,2,）,排序：把所有交点按递增顺序进行排序3,）,交点配对：第一个与第二个，第三个与第四个等等。每对交点就代表扫描线多边形的一个相交区间；,区间填色：把这些相交的区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。,当扫描线与多边形顶点相交时，会出现异常情况。扫描线,2,与,P,1,相交。按前术方法求得交点（,x,坐标）序列,2,，,2,，,8,。这将导致,2,，,8,区间内的象素取背景色，而这个区间的象素正是属于多边形内部，需要填充的。所以，我们所考虑当扫描线与多边形的顶点相交时，相同的交点只取一个。这样，扫描线路与多边形边的交点序列就成为,2,，,8,。但是，扫描线,7,与多边形边的交点序列为,2,，,9,，,11,这将导致错把,2,，,9,区间作为多边形内部来填充。我们发现当两条边在扫描线的两侧时，交点只取一个。当两条边在扫描线同侧的时侯交点算为,0,个或,2,个。,一个多边形与若干扫描线,0,P,4,(11,8),P,6,(2,7),P5(5,5),P,1,(2,2),P,3,(11,3),P,2,(5,1),1,5,10,A,B,C,D,G,E,F,7,8,11,2.,边界上象素的取舍,对左下角为（,1,，,1,），在上角为（,3,，,3,）的正方形填充时，若对边界上所有象素均进行填充，就得到图,2-8,的的结果。被填充的象素复盖的面积为,3X3,个单位，而方形的实际面积只有,2X2,个单位。为了克服这个问题，我们,规定落在右,/,上边界的象素不予填充，而落在左,/,下边界的象素予以填充。,对区域边界上象素全部填充的结果,x,3,2,1,3,0,1,2,有效边和有效边表,有效边：多边形内与当前扫描线相交的边称为有效边。在处理一条扫描线时仅对有效边进行求交运算，可以避免与多边形的所有边求交，提高了算法效率。,有效边表：把有效边按照与扫描线交点,x,坐标递增的顺序存放在一个链表中，称为有效边表,(,cactive,edge,table,AET,),x,ymax,1/k,next,桶表和边表,边表：从有效边表的建立过程可以看出，有效边表缎带出了扫描线和有效边交点坐标的计算机方法，但是没有给出新边出现的位置坐标。为了确定在哪条扫描线上手稿了新边，就需要构造一个边表,(edge,table,ET,),，用以存放扫描线上多边形各条边出现的信息。,桶表和边表的表示法,首先构造一个纵向扫描线链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点称为桶，对应多边覆盖的每一条扫描线。,将每条边的信息链入与该最小,y,坐标,(,y,min,),相对应的桶处。,对于每一条扫描线，如果新增多条边，则按,x|ymin,坐标递增的顺序存放在一个链表中，若,x|ymin,相等，则按照,1/k,由小到大排序，这样就形成了边表。,边填充算法,基本原理：对于每一条扫描线和每条多边形边的交点（,x,1,y,1,）,将该扫描线上交点右方的所有象素取补。如图。,边填充算法示意图,使用栅栏,为了减少边填充算法访问象素的次数，可引入栅栏。栅栏指的是一条与扫描线垂直的直线，栅栏位置通常取过多边形顶点、且把多边形分为左右两半。,栅栏填充算法的基本思想是：对于每个扫描线与多边形边的交点，就将交点与栅栏之间的象素取补。若交点位于栅栏左边，则将交点置右，栅栏之左的所有象素取补；若交点位于栅栏的右边，则将交点置左，交点之左的象素取补。栅栏填充算法只是减速少了被重复访问的角素的数目，但仍有一些象素会被重复访问。,边标志算法,边标志算法（轮廓填充算法）可使每个象素访问一次。首先对多边形的每条边进行直线扫描转换，即对多边形边界所经过的像素打上标志；然后对每条与多边形相交的扫描线依次从左到右顺序，逐个访问该扫描线像素，使用一个布尔量,inside,来指示当前点的状态，,inside,的初始值为,False,。每当当前的访问像素为打上边标志的点，就将,inside,取反，对未打标志的像素，,inside,不变；对,inside,作必要操作后，若,inside,为真，是把该像素量按多边形填充。,区域填充算法,用点阵方法表示的多边形区域，如果其内部像素具有同一种颜色，而边界像素具有另一种颜色，可以使用种子算法进行填充。,四邻接点和八邻接点,四邻接点：对于多边形区域内部任意一个种子像素，其左、上、右、下这,4,个像素称为四邻接点。,八邻接点：对于多边形区域内部任意一个种子像素，其左、右、上、下以及左上、右上、右下、左下这,8,个像素称为八邻接点。,四连通域和八连通域,种子填充算法要求多边形区域内部必须是连通的，才能将种子像素的颜色扩散到多边形区域内部的所有像素点，一般将多边形区域划分为四连通域和八连通域,可以以,4,邻接点形式遍历区域内的所有像素点的称,4,连通域。,可以以,8,邻接点形式遍历区域内的所有像素点的称,8,连通域。,邻接点填充算法,栈顶像素出栈,按填充色绘制出栈像素。,左开始沿顺时针方向，若该像素的颜色不是边界色并且未围成填充色，则把该像素入栈；否则丢充该像素,扫描线种子填充算法,栈顶像素出栈,沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止。同时记录填充该区间，其最左端像记为,x,l,，最右端像素记为,x,r,。,