第4章二维填充图元的生成

第4章二维填充图元的生成内容摘要：

xi的交点向右求余； M图中次序 ： x0, x1, x2, x3 次序可以任意 39 边缘填充算法 *  算法 2（以边为中心的边缘填充算法） 将绘图窗口的背景色置为 ； 对多边形的每一条非水平边做： 从该边上的每个像素开始向右求余 M40  特点  适合用于具有帧缓存的图形系统。 处理后，按扫描线顺序读出帧缓存的内容，送入显示设备  优点：算法简单  缺点：对于复杂图形，每一像素可能被访问多次，输入 /输出的量比扫描线算法大得多 边缘填充算法 * 41  扇形区域的描述  圆的半径 R  起始角度： 1  终止角度： 2  原理：同扫描转换多边形  对每条扫描线，首先计算与扇形区域边界的交点，再用指定颜色绘制绘制配对交点间的像素  问题  如何确定扫描线与直线段和圆弧段的交点及相交顺序。 扫描转换扇形区域 42  方法：分类  按点 P1(x, y) 和 P2(x, y) 点所处象限的不同，需要将扇形区域分成 4 4=16种情况  假设 P1 点落在第一象限 扫描线和区域边界只有 2个交点 扇形区域的扫描转换分四种情况 (1) P2落在第一象限 区域： OP1A和 AP1P2 扫描转换扇形区域 43 (2)P2落在第二象限，此时又分为两种情况  当 时 三个区域： OAP AP1BP2和 P2BC  当 时 三个区域： OAP AP1BP2和 P1BC 扫描转换扇形区域 y y1 221 yy ),(),( 22212212yyRByy xyA ),(),( 12221121yyRByy xyA 44 (3) P2 落在第三象限  三个区域： P1CA、 BOP1A和 P2OB (4) P2落在第四象限  三个区域： AP1D、 BOP1 A、 CP2OB 和 CEP2 扫描转换扇形区域 ),0()0,(),( 1212 RCRByyRA ),0()0,(),(),( 22221212RDRCyyRByyRA45  遗留问题：当 P1 落在其它区域时 ?  P1 落在第二、三、四象限时，将扇形区域绕坐标原点顺时针旋转 90度（ 180， 270），使 P1 落在第 1象限  扫描转换  再逆时针旋转 90度（ 180， 270） 扫描转换扇形区域 P1 P2 P2 P1 P1落在第四象限 P2 P1 P1落在第一象限 P1 P2 P1落在第四象限 旋转 270度 扫描转换 逆旋转 270度 46  区域：点阵表示的图形，像素集合  表示方法：内点表示、边界表示  内点表示  枚举出区域内部的所有像素  内部的所有像素为同一个颜色  边界像素与内部像素的颜色不同  边界表示  枚举出边界上所有的像素  边界上的所有像素为同一颜色  内部像素与边界像素的颜色不同 区域填充 47  种子填充法  对区域重新着色的过程 将指定的颜色从 种子点 开始扩展到整个区域  区域填充算法要求区域是连通的 区域填充 48  连通性  4连通区域：区域中任意两点 可通过上下左右四个方向互相 到达  8连通区域：区域中任意两点 可通过上下左右和对角线八 个方向互相到达 区域填充 49 区域填充 4连通与 8连通区域的区别  连通性： 4连通可看作 8连通区域，但对边界有要求不同  依据区域内点能否访问到区域外的点，对边界的要求是 4连通区域，边界只要 8连通即可 8连通区域，边界必须是 4连通  例：如左图 （ 1） 4连通区域，边界为 像素 （ 2） 8连通区域，边界为 和 像素 50 种子填充法  种子填充算法（泛滥填充： floodfill） （ 1）内点表示的 4连通区域  种子 P(x,y)，原色 oldColor，新颜色 newColor 方法：先判断 P(x, y)的颜色，若其值不等于 oldColor，说明该像素位于区域外，或已设置为 newColor，算法结束； 否则，置像素颜色 为 newColor，再对 其相邻的上下左右四 个像素分别作为种子 作上述递归处理。 void FloodFill4(int x,int y,int oldColor, int newColor) { if(GetPixel(x,y) == oldColor) { SetPixel(x,y,newColor)。 FloodFill4(x,y+1,oldColor,newColor)。 FloodFill4(x,y1,oldColor,newColor)。 FloodFill4(x1,y,oldColor,newColor)。 FloodFill4(x+1,y,oldColor,newColor)。 } }/*end of FloodFill4() */ 51 种子填充法 ① FloodFill4(x, y+1, oldColor, newColor)。 ② FloodFill4(x, y1, oldColor, newColor)。 ③ FloodFill4(x1, y, oldColor, newColor)。 ④ FloodFill4(x+1, y, oldColor, newColor)。 52 （ 2）边界表示的 4连通区域 种子填充法 void BoundaryFill4(int x, int y, int oldColor, int newColor) {//oldColor边界像素颜色 int color。 color = GetPixel(x, y)。 if((color != oldColor) amp。 amp。 (color != newColor)) { SetPixel(x, y, newColor)。 BoundaryFill4(x,y+1,oldColor,newColor)。 BoundaryFill4(x,y1,oldColor,newColor)。 BoundaryFill4(x1,y,oldColor,newColor)。 BoundaryFill4(x+1,y,oldColor,newColor)。 } }/*end of BoundaryFill4( ) */ 53  缺点  有些像素需要重复判断，降低算法效率  栈结构占空间  递归执行，算法简单，但效率不高，区域内每一像素都引起一次递归，进 /出栈，费时费内存  改进  减少递归次数，提高效率  方法之一使用扫描线填充算法 种子填充法 54 扫描线算法 *  扫描线算法  目标：减少递归层次  适用于内点表示的 4连通区域  基本过程： 当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。 反复这个过程，直到填充结束 55 扫描线算法 *  算法步骤  初始化 ：将种子区段压入堆栈。