计算机图形学第五讲2.ppt

区域指已经表示成点阵形式的填充图形，它是象素的集合。 区域可采用内点表示和边界表示两种表示形式。 区域可分为4向连通区域和8向连通区域。 区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的 假设多边形区域内至少有一个像素已知 区域连通方式对填充结果的影响 2、简单种子填充算法的优、缺点 ⑴算法操作过程非常简单； ⑵要进行深度递归，花费大量时间，降低了算法的效率；要大量空间构造堆栈； ⑶堆栈内包含很多重复的不必要的信息。 2、扫描线种子填充算法 ⑴初始化 ⑵出栈 ⑶区间填充 ⑷定范围 ⑸进栈 (1)初始化：堆栈置空。将种子点（x，y）入栈。 (2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。 (4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。 上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。 显然，对一个多边形而言，若内部为一个四向连通区（即从任意一象素出发，只需通过“左上右下”四个方向的选择即可遍历所有象素），则上述算法即可完成填充。若内部为一个八向连通区（即从任意一象素出发，需通过“上、下、左、右、左上、左下、右上、右下”八个方向的选择才可遍历所有象素），则需用八向种子填充算法完成。 以下仅讨论四向填充算法。 ⑴. 将种子象素入栈； ⑵. 当栈非空时，重复： ① 栈顶象素弹出； ② 若该象素未填充，则对其填充； ③ 以该象素为中心，依“左上右下” 或者“右上左下”顺序将非边界象素和未填充象素压入堆栈。 以下为四向填充算法伪代码： 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,oldcolor,newcolor); ??????????????? FloodFill4(x+1,y,oldcolor,newcolor); ??? } } * 第五讲 教学重点：多边形区域填充、边填充、种子填充 教学难点：多边形区域填充、边填充、种子填充 教学目的：多边形区域填充、边填充、种子填充 教学方法：讲授法 教学课时：2课时 教学过程： 一．区域填充算法 为使图形的某一区域更加醒目，常常用一种颜色或一种图案对其进行填充。 图形的区域：用多边形近似表示，所以区域填充常常变成为对多边形的填充。 需解决的问题：判断哪些象素点需填充；需要填充什么颜色。 区域填充算法分类 填充算法 扫描转换算法 种子填充算法 有序边表算法 边填充算法 简单种子填充算法 四向填充算法 扫描线种子填充算法 八向填充算法 (一)、多边形区域填充算法： 1、一般方法：依顺序取出每一条扫描线，求其与多边形边界的交点，并对每一对交点中的象素进行填充。主要步骤包括：求交；排序；交点配对；区间填充。如图： 12 10 8 6 4 2 2 4 6 8 10 12 14 扫描线? F b D c d E C B A a x 扫描线 ? 与多边形边界相交于交点a, b, c, d处，于是交点a、b之间、交点c、d之间的象素需填充（或交点序列按区间交错填充，即a → b → c → d） 填充 不填充 填充 但存在以下几个问题： ⑴．若将多边形边界都看成是多边形内部，并对它们填充，则该多边形会放大。于是，采取“左闭右开，下闭上开”办法，即：左、下边界象素为多边形内部，需填充，而右、上边界象素为多边形外部，不予填充。 ⑵．当扫描线与多边形边界之交点为小数值时，如果多边形在此边界右侧，则将该小数值进1作为边界点，否则舍去小数部分。如此可使多边形不扩大。 ⑶．当扫描线与多边形顶点相交时，