CG3基本图形生成(3.3)ppt课件

3.3区域填充,1,如图1多边形可表示成图2,在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示,多边形可表示成P0P1P2P3P4P0的点序列形式。,点阵表示：用位于多边形内的象素的集合来刻划多边形。,图1多边形的顶点表示,P0,P1,P2,P3,P4,顶点表示：用多边形顶点的序列来刻划多边形。,2,区域填充,区域填充可以分两步进行:先确定需要填充哪些像素再确定用什么颜色值来填充,用一种颜色或图案来填充一个二维区域。,首要问题：判断一个象素是在多边形内还是在多边形外。,3,四种方法：有序边表填充算法边填充算法改进版边填充算法-栅栏填充算法种子填充算法,4,扫描线4,A,B,C,D,扫描线6,扫描线6：四个交点，五个区间,多边形外,多边形内,多边形外,多边形外,多边形内,5,1.求交点：即求出每一条扫描线与多边形所有相交各边的交点，并建立起（xi,yi）的交点表。,2.交点排序：把所有交点按x坐标递增顺序进行排序。,3.交点配对：第一个与第二个，第三个与第四个等等。每对交点就代表扫描线与多边形的一个相交区间。,4.区间填色：把相交区间内的象素置成多边形的颜色，把相交区间外的象素置成背景的颜色。,6,问题:奇点处理.当扫描线恰好与多边形顶点相交时，称该交点为奇点,保证交点正确配对,P1,P2,P3,P4,P5,P6,2,4,6,8,O,7,第一种情况，共享顶点的两条边分别落在扫描线的两边。这时，交点只算一个。第二种情况，共享交点的两条边落在扫描线的同一边，这时交点作为两个,8,扫描线1,扫描线2,扫描线7,E,F,G,(1),(2),x,P1,P2,P3,P4,P5,P6,(2,2),(5,1),(11,3),(2,7),(5,5),(11,8),共享交点的两条边分别落在扫描线的两边,奇点有:点P2P4P5P6,奇点有:点P1P3,共享交点的两条边落在扫描线的同一边,按两个交点计算,按一个交点计算,9,在处理一条扫描线时，只需对与它相交的多边形的边进行求交运算。,计算下一条扫描线与同一条边的交点x值时，只需把当前交点x值加上一个边的反斜率即可：xk+1=xk+1/m(m为边的斜率),10,我们把与当前扫描线相交的边称为活化边,x:当前扫描线与边的交点xx:从当前扫描线到下一条扫描线之间的x增量x=1/mymax:边所交的最高扫描线号,按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活化边表,11,扫描线6的活性边表,12,在处理完当前扫描线后转入下一条扫描线之前，要对交点x坐标进行更新(+dx),插入新加入的边，并把那些与当前扫描线有交，而与下一条扫描线不再相交的边，从活化边表中删除出去(通过检查当前扫描线y值是否等于各边的ymax值来确定)。,13,为了方便活化边表的建立与更新，我们为每一条扫描线建立一个有序边表，存放在该扫描线第一次出现的边。也就是说，若某边的较低端点的y值为ymin，则该边就放在扫描线为ymin的有序边表中。,14,0,1,2,3,4,5,6,7,8,该扫描线与该边的初始交点x（较低端点的x值）,X的增量x,该边的最大y值ymax,15,3.3.2边填充算法,16,基本实现:按任意顺序处理多边形的每条边。在处理每一条边时,首先求出该边与扫描线的交点,然后将每一条扫描线上交点右方的所有象素取补。多边形的所有边处理完毕之后,填充即完成。,优点:简单缺点:对于复杂图形,每一象素可能被访问多次,输入输出的量比有效边表算法大得多.,17,18,为了减少边填充算法访问像素的次数，可引入栅栏。栅栏指的是一条与扫描线垂直的直线，栅栏位置通常取过多边形顶点、且把多边形分为左右两半。,栅栏填充法的基本思想是：对于每个扫描线与多边形的交点，就将交点与栅栏之间的像素取补。,19,图3.10栅栏填充算法示意图,栅栏填充算法只是减少了被重复访问的像素的数目，但仍有一些像素会被重复访问。,20,3.3.3种子填充算法,种子填充算法的原理：从多边形区域内部的一点开始，由此出发找到区域内的所有像素。,种子填充算法采用的边界定义是区域边界上所有像素均具有某个特定的颜色值，区域内部所有像素均不取这一特定颜色,21,区域内部一点(x，y)开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点，然后检测相邻位置，以确定它们是否是边界色和填充色，若不是，就填充该相邻点。这个过程延续到已经检测完区域边界范围内的所有像素为止。,22,从当前点检测相邻像素有两种方法：四向连通和八向连通,八向连通方法指的是区域内每一个像素，可以通过左、右、上、下、左上、右上、左下、右下这八个方向的移动的组合来到达。,四向连通方法指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；,23,种子填充算法中允许从四个方向寻找下一像素者，称为四向算法；允许从八个方向搜索下一像素者，称为八向算法。八向算法可以填充八向连通区域，也可以填充四向连通区域。四向算法只能填充四向连通区域，而不能填充八向填充区域。,24,区域连通方式对填充结果的影响,4连通区域边界填充算法的填充结果,8连通区域边界填充算法的填充结果,25,简单的种子填充算法（4连通边界）,种子像素入栈当栈非空时，重复以下步骤：栈顶像素出栈将出栈象素置成填充色按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈,26,S1,2,3,4,5,6,7,8,9,太多象素压入堆栈，有的象素入栈多次，降低了算法的效率，要求很大存储空间以实现栈结构。,存在问题：,27,在任意一个扫描线与多边形的扫描区间（含若干个连续象素）中，只取一个种子象素。扫描线填充算法,解决办法：,28,1,2,3,1,2,3,4,5,6,7,例1,例2,29,2.扫描线填充算法原理,种子象素入栈；当栈非空时重复执行下面四步操作：,1.栈顶象素出栈；2.沿扫描线对出栈象素的左右象素进行填充，直至遇到边界象素为止，即每出栈一个象素，就对包含该象素的整个扫描区间进行填充；3.上述区间内最左、最右的象素分别记为xl,xr;,4.在区间Xl,Xr中检测与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或已填充的象素，若存在非边界、未填充的象素，则把每一区间的一个象素作为种子象素入栈。,5.对相邻的两扫描线的种子点入栈后，紧接着对种子象素出栈，实现第二步运算，进行迭代计算。,30,13,31,1.基本思想不同扫描线算法是按扫描线顺序进行的。而种子填充算法要求先指定区域内的一点为种子点，然后从这点出发开始对区域进行着色。,2.对边界要求不同在多边形扫描转换中，要求每一条扫描线与多边形边界的交点为偶数,对不封闭边界是允许的。,在区域填充中，要防止进行递归式填充时跨越边界，故要求4连通区域的边界为封闭的8连通区域，而8连通区域的边界要求为封闭的4连通区域。,扫描线算法与种子填充算法的比较,32,3.3.4圆和椭圆的填充,由于圆和椭圆的特殊属性，它们的填充算法比较简单,33,3.3.5图案填充,在实际应用中，有时需要用一种图案来填充平面区域。这可以通过对前述填充算法中写像素的那部分代码稍作修改来实现：在确定了区域内一像素之后,不是马上往该像素填色，而是先查询图案位图的对应位置。,34,图案定义：intpattern88=0,0,0,1,0,0,0,1,0,0,0,1,0,