扫描线算法有序边表算法.ppt

北大计算机系多媒体与人机交互 4.9 不规则边界区域填充方法 区域内部的所有像素都具有颜色old_color，从区域 内部某一像素（x,y）开始对区域进行填充（该像素称为 种子点），将区域内部的所有像素都设置为填充颜色 fill_color。 基本方法是：测试像素（x,y）是否在区域内尚未被 填充的部分，即测试像素（x,y）的颜色，若该像素的颜 色等于old_color且不等于fill_color，则设置该像素的 颜色为fill_color，并对与该像素相邻的像素作同样处理 （递归调用）；否则说明该像素在区域外或已被填充过， 不再进行处理。 4.9 不规则边界区域填充方法 void flood_fill_4(int x, y, old_color, fill_color) { int current; current = read_pixel(x, y); if ( current==old_color current!=fill_color ) { write_pixel(x, y, fill_color); flood_fill_4(x, y+1, old_color, fill_color); /* 上 */ flood_fill_4(x, y-1, old_color, fill_color); /* 下 */ flood_fill_4(x-1, y, old_color, fill_color); /* 左 */ flood_fill_4(x+1, y, old_color, fill_color); /* 右 */ } } 适用于四连通内部定义区域的边界填充算法为： 4.9 不规则边界区域填充方法 适用于四连通边界定义区域的边界填充算法为： void boundary_fill_4(int x, y, boundary_color, fill_color) { int current; current = read_pixel(x, y); if ( current!=boundary_color current!=fill_color ) { write_pixel(x, y, fill_color); boundary_fill_4(x, y+1, boundary_color, fill_color); /* 上 */ boundary_fill_4(x, y-1, boundary_color, fill_color); /* 下 */ boundary_fill_4(x-1, y, boundary_color, fill_color); /* 左 */ boundary_fill_4(x+1, y, boundary_color, fill_color); /* 右 */ } } 4.9 不规则边界区域填充方法 当区域内部某些像素的颜色为fill_color时，上述边界填充算法可能无法正确工作。 解决方法:首先建立一个与帧缓冲区对应的临时缓冲区，帧缓冲区中颜色为boundary_color的像素在临时缓冲区中用0来表示，颜色不为boundary_color的像素在临时缓冲区中用1来表示，再用上述算法在临时缓冲区中用2进行填充，最后在帧缓冲区中将对应于临时缓冲区中为2的像素填充为fill_color。 4.5.1 填充模式 涉及到的坐标系 参数坐标系可以用来建立曲线、曲面。 纹理坐标系用来识别要被映射的图像上的点。 世界坐标系从概念上说，就是映射发生的地方。 屏幕坐标系最终图像生成的地方。 4.5.1 填充模式 映射函数 考虑从纹理坐标到曲面上一点的映射。 直观地看，需要如下函数 x=x(s,t) y=y(s,t) z=z(s,t) w=w(s,t) 实际采用的是间接方法。 4.5.1 填充模式 逆映射 给定对象上的一个点，我们想知道它对应 于纹理中的哪个点。 此时需要如下形式的映射 s = s(x,y,z,w) t = t(x,y,z,w) 这样的函数一般是很难求出来的。 4.5.1 填充模式 实际困难 假设要计算中心在(xs, ys)的一个矩形像素的颜色。 中心点对应于对象上的点(x,y,z) 。 如果对象是弯曲的，那么矩形像素的原像是一个曲 边四边形。 这个曲边四边形在纹理上的原像才是对当前矩形像 素的颜色有贡献的纹理元素。 4.5.1 填充模式 纹理坐标到屏幕坐标的映射 xs=xs(s,t) ys=ys(s,t) (xs,ys)表示颜色缓存中的某个位置。 4.