计算机图形学3-3.ppt

简单的种子填充算法（递归实现） 基本方法：设种子像素为(x,y)是四向连通区域内的一点，old_color为区域内的原有像素的颜色，new_color是要填充的颜色，递归填充的过程是如果种子像素是区域内原有颜色old_color，说明该种子像素在区域内，则将像素置为被填充颜色new_color，同时将种子像素的上、下、左、右像素当作种子递归调用填充递归算法；否则说明该像素已被填充，不再处理。 Void SeedFill4(int x,int y,int oldcolor,int newcolor) {if(getpixel(x,y)==oldcolor) { setpixel(x,y,newcolor); SeedFill4(x,y+1,oldcolor,newcolor); SeedFill4(x,y-1,oldcolor,newcolor); SeedFill4(x-1,y,oldcolor,newcolor); SeedFill4(x+1,y,oldcolor,newcolor); } } 种子递归填充算法 递归算法原理和程序都很简单，但由于多次递归十分费时，且占用大量资源，将使计算机的效率非常低。采用栈结构来实现简单的种子填充算法。算法描述如下： 1．将种子象素入栈； 2．当栈非空时，重复： ①栈顶象素出栈； ②若该象素未填充，则将出栈象素置成填充色 ③以该象素为中心，检查出栈象素的4-邻接点，依“左上 右下”顺序将非边界象素和未填充象素压入堆栈。若其中某 个象素点不是边界色且未置成填充色，则把该象素入栈 xhc * xhc 3.3 区域填充算法 3.3.1 基础知识 区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。　　 计算机图形学中，多边形区域有两种重要的表示方法：顶点表示和点阵表示。 所谓顶点表示，即是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于区域填充。 所谓点阵表示，则是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于进行填充。 根据区域的定义，可以采用不同的填充算法，其中最具代表性的是：适应于顶点表示的扫描线类算法和适应于点阵表示的种子填充类算法。 多边形的表示方法 顶点表示 点阵表示 填色算法分为两大类： 　⒈ 扫描线填色(Scan-Line Filling)算法。这类算法 建立在多边形边界的矢量形式数据之上，可用于程序填 色，也可用于交互填色。 　⒉ 种子填色(Seed Filling)算法。这类算法建立在多 边形边界的图像形式数据之上，并还需提供多边形边界 内一点的坐标。所以，它一般只能用于人机交互填色， 而难以用于程序填色。 　 多边形填色一个首要的问题，是判断一个像素是在多边形内还是多边形外。数学上提供的方法是“扫描交点的奇偶数判断法”。 3.3.2 多边形扫描线填充算法 算法的基本思想: 多边形以n、x_array、y_array 的形式给出，其中，x_array、y_array中存放着多边形的n个顶点的x，y坐标。 用水平扫描线自底向上扫描由点线段构成的多段定义成的多边形。每根扫描线与多边形各边产生一系列交点。 这些交点按照x坐标进行排序，将排序后的交点成对取出，作为两个端点，以所需要填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。 扫描线填充算法 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 P1(2,2) P6(2,7) P2(5,4) P3(11,1) P4(11,6) P5(5,8) A B C D F G 对于一条扫描线，多边形的填充过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间； (4) 填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。 扫描线算法需要解决或改进的几个问题： 1、如何处理奇数个交点？ 2、如何处理水平边？ 3、如何计算交点坐标？ 4、如何减少求交计算量？ 第一个问题：处理奇数个交点 规定： 共享顶点的两条边分别落在扫描线的两边，交点只取1个； 共享顶点的两条边都落在扫描线的下方，交点算0个； 共享顶点的两条边都落在扫描线的上方，交点算2个； 第二个问题：处理水平线 扫