计算机图形学 区域填充.ppt

1、第四讲 区域填充,有关概念 逐点判断填充算法 3. 种子填充算法 4. 区域填充图案 5. 扫描线多边形填充算法 6. 边填充算法,1. 有关概念,1) 区域：一组相邻而且又相连的像素，而且具有相同属性的封闭区域。,3) 区域填充：以某种属性对整个区域进行设置的过程。,2）种类：单域 复合域,4）区域的建立（定义）方式： 内定区域：在所定义的区域内所有的像素具有相同的属性（如颜色等）。 （内部定义方式） 边界定义区域：以区域的内外属性来划分，区域内的像素和边界上的像素可具有不同的属性。 （外界定义方式）,5）连通性：分为四向连通和八向连通。 四连通：各像素在水平、垂直的上、下、左、右四个方向上

2、是连通的。 八连通：各像素在上、下、左、右以及四个对角线方向都是连通的。,2.逐点判断填充算法,区域填充的基本(初级)方法:逐点判断填充算法 逐点判断绘图窗口内的每一个像素； 若在区域的内部：用指定的属性设置该点； 否则不予处理；,设有如下函数： True when x D Inside(D,x,y)= False when x D,D,取矩形R(x1xx2,y1yy2)，使R包围D， 则逐点判断填充算法如下： for(y=y1;y=y2;y+) for(x=x1;x=x2;x+) if(inside(D,x,y) drawpixel(x,y,color); 上述算法原理简单、实用，但效率低；

3、 效率低的原因是没有考虑各象素之间的联系，孤立地考察象素与区域的关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。,1）射线法； 2）累计角度法； 3）编码法； 4）. 这些内容在本书第八章几何造型中有专门介绍。,如何判断点在多边形的内或外？（包含性检查的方法）,这里以射线法为例进行说明：,过被检测点任作一条射线,求其与边界的交点,若交点数为偶数,则该点在边界之外,否则在边界之内。,当射线经过顶点时,可通过”左开右闭”,或”上开下闭”进行处理。,P,P,3.种子填充算法,1）深度递归的种子填充算法 2）扫描线种子填充算法,种子填充算法假设

4、在多边形内有一象素已知，由此出发利用连通性找到区域内的所有象素，并进行填充。,1）深度递归的种子填充算法(漫水法）,从已知种子点出发，每填充一点，在其周围寻找新种子点，重复进行，直到再无未填充的点为止。 针对内点表示的4连通区域的递归填充具体步骤: 1.种子入栈. 2.当栈非空时,进行下面的操作,否则结束. 3.栈顶元素出栈,如果是未填充的内部点,则将其填充. 继续考察与其连通的点,若是未填充的内部点,则该点入栈.返回2.,准备工作： typedef struct int x,y; seed; typedef struct seed s6400;int top; seedstack;,VC+程

5、序实现,可以直接利用函数的递归调用来实现.,设（x,y）为内点表示的4连通区域内的一点，oldcolor为区域的原色，要将整个区域填充为新的颜色newcolor。 内点表示的4连通区域的递归填充算法:,void FloodFill4(int x,int y,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) drawpixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,o

6、ldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor); ,边界表示的4连通区域的递归填充算法: void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) int color= Getpixel(x,y); if(color!=newcolor 对于内点表示和边界表示的8连通区域的填充，只要将上述相应代码中递归填充相邻的4个象素增加到递归填充8个象素即可。,2）扫描线种子填充算法,种子填充的递归算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归次数

7、，提高效率可以采用采用扫描线算法。 算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，确定新种子点，并依次保存下来。反复这个过程，直到填充结束。,上述算法对于每一个待填充区段，只需压栈一次；而在递归算法中，每个象素都需要压栈。因此，扫描线填充算法提高了区域填充的效率。,扫描线区域填充算法可由下列四个步骤实现：,(1)初始化：堆栈置空。将种子点（x，y）入栈。 (2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点（x，y）

8、出发，沿当前扫描线向左、右两个方向填充，直到非内部。分别标记区段的左、右端点坐标为xl和xr。 (4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。,例题: 针对下图所示的区域及给定的种子点H， 说明填充的过程。,VC+程序实现,4区域填充图案,前面介绍的区域填充算法，把区域内部的全部的象素设置为同一种颜色。但在实际应用中，有时需要用一种图案来填充平面区域。 可以通过对前述算法中写象素的那部分内容稍作修改来实现：在确定了区域内一象素之后，不是马上往该象素填色，而是先查询

9、图案位图的对应位置。若以透明方式填充图案，则当图案表的对应位置为1时，用前景色写象素，否则，不改变该象素的值。而以不透明方式填充图案，则当图案表的对应位置为1时，用前景色写象素，否则，用背景色写象素。,进行图案填充时，在不考虑图案旋转的情况下，必须确定区域与图案之间的位置关系。这可以通过把图案原点与区域某点对齐的办法来实现。 对齐方法有两种：第一种是把图案原点与填充区域边界或内部某点对齐。第二种方法是把图案原点与填充区域外部的某点对齐。 用第一种方法填充的图案，将随着区域的移动而移动，看起来很自然。对于多边形，可取区域边界上最左边的顶点。而对于圆和椭圆这样具有光滑边界的区域，则最好取区域内部的

10、某一点，如中心，对应图案原点。,从算法复杂性看，第二种方法比较简单，并且在相邻区域用同一图案填充时，可以达到无缝连接的效果。但当区域移动时，图案不会跟着移动，区域内的图案变了。 下面来讨论在第二种方式下，如何对平面区域进行填充。,假定图案是一个M*N位图，用M*N数组存放。M，N一般比需要填充的区域的尺寸小得多，所以图案总是周期性的使用。 假定区域内一象素(x,y)， 对应于图案上的(x%M,y%N)。 若以透明方式填充图案， if (patternx%My%N) putpixel(x,y); 若以不透明方式填充图案， if (patternx%My%N) putpixel(x,y,color

11、); else putpixel(x,y,bkcolor);,5.扫描线多边形填充算法,扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。 区间的端点可以通过计算扫描线与多边形边界线的交点获得。 对于一条扫描线，多边形的填充过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; （4）填色：把相交区间内的象素置成多边形颜色;,相交顶点的数目确定：检查相交顶点的两条边的另外两个顶点

12、的y值。按这两个y值中大于交点y值的个数是0,1,2来决定是取零个、一个、还是两个。 边界像素取舍：对扫描线与多边形的相交区间取左闭右开。,重合点的处理: 当扫描线和边界相交于边界顶点时，同时产生两个交点，通常采用 “起闭终开”或“起开终闭” 。,水平边处理 水平边不参加求交计算，跳过。,P1,p2),P4，P5),P2,p3),P5,p1),求交：把多边形的所有边放在一个表中，处理每条扫描线时，按顺序从表中取出所有的边，分别与扫描线求交。 缺点：效率低。 解决办法：仅对与它相交的多边形的边进行求交运算。,把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中

13、，称此链表为活性边表(AET)。 活性边表的每个节点的内容：,第1项存当前扫描线与边的交点坐标x值； 第2项存从当前扫描线到下一条扫描线间x的增量D x； 第3项存该边所交的最高扫描线号ymax； 第4项存指向下一条边的指针。,X,X,Ymax,假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量x。(连贯性) 设该边的直线方程为：ax+by+c=0； 若yyi，x=x i；则当y = y i+1时， x i+1=xi-b/a,其中X= -b/a为常数， 另外使用增量法计算时，我们需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表

14、中删除出去。,扫描线6的活性边表,扫描线7的活性边表,为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表（NET）,存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。,扫描线多边形填充算法的主要步骤,建立NET(NewEdgeList) 从最低扫描线开始到最高扫描线循环： 建立或调整AET(ActiveEdgeList)； 按照AET中的接点顺序填充；,算法描述： void polyfill (多边形 polygon, 颜色 color) for (各条扫描线i ) 初始化新边表头指针NET i；把ymin = i 的边放进边

15、表NET i; y = 最低扫描线号； 初始化活性边表AET为空； for (各条扫描线i ) 把新边表NETi中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列； 遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)，用drawpixel (x, y, color) 改写象素颜色值； 遍历AET表，把y max= i +1的结点从AET表中删除，并把y max i+1结点的x值递增D x； 若允许多边形的边自相交，则用冒泡排序法对AET表重新排序； /* polyfill */,桶结构,用于存放按照一定的规则（顺序）排列的若干组数据或处理对象。 通常情况下，桶采用向量形式和

16、链表形式构造的一种数据结构。,6边界标志算法,边界标志算法的基本思想是：在帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。对每条与多边形相交的扫描线依从左到右的顺序，逐个访问该扫描线上的象素。使用一个布尔量inside来指示当前点是否在多边形内的状态。Inside的初值为假，每当当前访问的象素为被打上边标志的点，就把inside取反。对未打标志的象素，inside不变。若访问当前象素时，inside为真，说明该象素在多边形内，则把该象素置为填充颜色。,1. 对多边形的每一条边进行扫描转换，即

17、对多边形边界所经过的象素作一个边界标志。 2.填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。 取一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。 Inside 的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，inside不变。,边界标志算法步骤,边界标志算法:算法过程,void edgemark_fill(polydef, color) 多边形定义 polydef； int color; 对多边形polydef 每条边进行直线扫描转换； inside = F

18、ALSE; for (每条与多边形polydef相交的扫描线y ) for (扫描线上每个象素x ) if(象素 x 被打上边标志) inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); ,边界标志算法： void edgemark_fill(polydef, color) 多边形定义 polydef； int color; 对多边形polydef 每条边进行直线扫描转换； inside = FALSE; for (每条与多边形polydef相交的扫

19、描线y ) for (扫描线上每个象素x ) if(象素 x 被打上边标志)inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); ,用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。,* 边缘填充算法(正负相消法),基本思想： 对于每条边上的每一点都将所在扫描线上其右方的所有象素的颜色取补。 算法简单，但对于复杂图型，每一象素可能被访问多次。,栅栏填充算法 栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。,边缘填充算法,求余运算：假定A为一个正整数，则M的余定义为A M, 记为 。计算机中取A为n位能表示的最大整数。即，A=0 xFFFFFFFF 由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求