CG03区域填充

《CG03区域填充》由会员分享，可在线阅读，更多相关《CG03区域填充（30页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,区域填充的算法,1,,多边形填充,2,,实面积图形,填充后的多边形称为实面积图形，实面积图形在其封闭的轮廓内具有相同的颜色，这意味着要填充光栅显示器上封闭图形内的每一个像素点。实面积图形既能描述物体的几何轮廓，又能表现物体的表面颜色，与人们观察物体表面的习惯相一致，同时，实面积图形也是描述三维物体、绘制三维真实感图形的基础。,3,,多边形的定义,4,,1.凸多边形,多边形上任意两顶点间的连线都在多边形之内，凸点对应的内角小于180度，只具有凸点的多边形称为凸多边形。,5,,2.凹多边形,多边

2、形上任意两顶点间的连线有不在多边形内部的部分，凹点对应的内角大于180度，有凹点的多边形称为凹多边形。,6,,环,多边形内包含有另外的多边形。如果规定每条有向边的左侧为期内部面积区域，则当观察者沿着边界行走时，内部区域总在其左侧，也就是说多边形外轮廓线的环行方向为逆时针，内轮廓线的环行方向为顺时针。这种定义了环行方向的多边形称为环。,7,,多边形的表示,8,,顶点表示法,多边形的顶点表示法是用多边形的顶点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换。,9,,点阵表示法,多边形的点阵表示法就是用多边形覆盖

3、的像素点集来描述。特点是便于直接确定实面积图形覆盖的像素点，是多边形填充所需要的表示形式，但是缺少了多边形顶点的几何信息。,10,,多边形的扫描转换,将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出多边形内部的各个像素点信息。,11,,多边形的填充,多边形的填充是指从多边形的顶点信息出发，求出其覆盖的每个像素点，置为填充色，而将多边形外部的像素点保留为背景色。多边形填充的主要工作是确定穿越多边形内部的扫描线的覆盖区间。,,首先确定多边形覆盖的扫描线条数，对每一条扫描线，计算机扫描线与多边形边界交点区间。然后再将该区间内的像素赋予指定的颜色。

4、,12,,区域填充,区域是指一组相邻而又具有相同忏悔的像素，可以理解为多边形的内部。区域的边界色和填充色不一致，填充算法只对区域内部进行填充。种子填充算法是从给定的种子位置开始，按填充颜色点亮种子的相邻像素考虑到颜色不同的边界像素为止。种子填充算法主要有4邻接点简洁和8邻接点算法。,13,,区域填充算法,区域填充可以分两步进行，第一步先确定需要填充哪些象素。第二步确定用什么颜色值来填充。,14,,1．  扫描线多边形域的填充,基本原理：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形的界线的交点获得。,15,,一

5、个多边形与若干扫描线,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

6、坐标序列。,,（1）,,求交：计算扫描线与多边形各边的交点；,,（2）,,排序：把所有交点按递增顺序进行排序；,,（3）,,交点配对：第一个与第二个，第三个与第四个等等。每对交点就代表扫描线多边形的一个相交区间；,,区间填色：把这些相交的区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。,16,,当扫描线与多边形顶点相交时，会出现异常情况。扫描线2与P,1,相交。按前术方法求得交点（x坐标）序列2，2，8。这将导致[2，8]区间内的象素取背景色，而这个区间的象素正是属于多边形内部，需要填充的。所以，我们所考虑当扫描线与多边形的顶点相交时，相同的交点只取一个。这样，扫描线路与多边形边的交

7、点序列就成为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,17,,2.,边界上象素的取舍,,对左下角为（1，1），在上角为（3，3）的正方形填充时，若对边界上所有象素均进行填充，就得到图2-8的的结果。被填充的象素复盖的面积为3X

8、3个单位，而方形的实际面积只有2X2个单位。为了克服这个问题，我们,规定落在右/上边界的象素不予填充，而落在左/下边界的象素予以填充。,,对区域边界上象素全部填充的结果,,x,3,2,1,3,0,1,2,18,,有效边和有效边表,有效边：多边形内与当前扫描线相交的边称为有效边。在处理一条扫描线时仅对有效边进行求交运算，可以避免与多边形的所有边求交，提高了算法效率。,,有效边表：把有效边按照与扫描线交点x坐标递增的顺序存放在一个链表中，称为有效边表(cactive edge table,AET),,x,ymax,1/k,next,19,,桶表和边表,边表：从有效边表的建立过程可以看出，有效边表缎

9、带出了扫描线和有效边交点坐标的计算机方法，但是没有给出新边出现的位置坐标。为了确定在哪条扫描线上手稿了新边，就需要构造一个边表(edge table,ET)，用以存放扫描线上多边形各条边出现的信息。,20,,桶表和边表的表示法,首先构造一个纵向扫描线链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点称为桶，对应多边覆盖的每一条扫描线。,,将每条边的信息链入与该最小,y,坐标,(,y,min,),相对应的桶处。,,对于每一条扫描线，如果新增多条边，则按,x|ymin,坐标递增的顺序存放在一个链表中，若,x|ymin,相等，则按照,1/k,由小到大排序，这样就形成了边表。,21,,边填充

10、算法,22,,基本原理：对于每一条扫描线和每条多边形边的交点（x,1,,y,1,）,将该扫描线上交点右方的所有象素取补。如图。,边填充算法示意图,23,,使用栅栏,为了减少边填充算法访问象素的次数，可引入栅栏。栅栏指的是一条与扫描线垂直的直线，栅栏位置通常取过多边形顶点、且把多边形分为左右两半。,,栅栏填充算法的基本思想是：对于每个扫描线与多边形边的交点，就将交点与栅栏之间的象素取补。若交点位于栅栏左边，则将交点置右，栅栏之左的所有象素取补；若交点位于栅栏的右边，则将交点置左，交点之左的象素取补。栅栏填充算法只是减速少了被重复访问的角素的数目，但仍有一些象素会被重复访问。,24,,边标志算法,

11、边标志算法（轮廓填充算法）可使每个象素访问一次。首先对多边形的每条边进行直线扫描转换，即对多边形边界所经过的像素打上标志；然后对每条与多边形相交的扫描线依次从左到右顺序，逐个访问该扫描线像素，使用一个布尔量inside来指示当前点的状态，inside的初始值为False。每当当前的访问像素为打上边标志的点，就将inside取反，对未打标志的像素，inside不变；对inside作必要操作后，若inside为真，是把该像素量按多边形填充。,25,,区域填充算法,用点阵方法表示的多边形区域，如果其内部像素具有同一种颜色，而边界像素具有另一种颜色，可以使用种子算法进行填充。,26,,四邻接点和八邻接

12、点,四邻接点：对于多边形区域内部任意一个种子像素，其左、上、右、下这4个像素称为四邻接点。,,八邻接点：对于多边形区域内部任意一个种子像素，其左、右、上、下以及左上、右上、右下、左下这8个像素称为八邻接点。,27,,四连通域和八连通域,种子填充算法要求多边形区域内部必须是连通的，才能将种子像素的颜色扩散到多边形区域内部的所有像素点，一般将多边形区域划分为四连通域和八连通域,,可以以,4,邻接点形式遍历区域内的所有像素点的称,4,连通域。,,可以以,8,邻接点形式遍历区域内的所有像素点的称,8,连通域。,28,,邻接点填充算法,栈顶像素出栈,,按填充色绘制出栈像素。,,左开始沿顺时针方向，若该像素的颜色不是边界色并且未围成填充色，则把该像素入栈；否则丢充该像素,29,,扫描线种子填充算法,栈顶像素出栈,,沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止。同时记录填充该区间，其最左端像记为,x,l,，最右端像素记为,x,r,。,30,,