计算机图形学边缘填充算法.ppt
《计算机图形学边缘填充算法.ppt》由会员分享,可在线阅读,更多相关《计算机图形学边缘填充算法.ppt(63页珍藏版)》请在三一文库上搜索。
1、边缘填充算法,思路:利用求余运算代替交点排序、配对、构造填充区间。 原理:象素点颜色值经过偶数次求余运算后保持不变,经过奇数次求余运算后变为其余数 算法: 以扫描线为中心的边缘填充算法 以边为中心的边缘填充算法,基本思想:对于每一条扫描线和每条多边形边的交点 (x1,y1),将该扫描线上交点右方的所有象素取补.对多边形的每条边做此处理,多边形的顺序随意. 该算法的优点是简单,缺点是对复杂图形,每一象素可能被访问多次,输入输出的量比较大.,边缘填充算法,以扫描线为中心的边缘填充算法,基本思想:对于每一条扫描线和每条多边形边的交 点(x1,y1),将该扫描线上交点右方的所 有象素取补.对多边形的每
2、条边做此处理, 多边形的顺序随意.,将当前扫描线上的所有象素着上指定颜色的补色,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,将当前扫描线上的所有象素着上指定颜色的补色,以扫描线为中心的边缘填充算法,将当前扫描线上的所有象素着上指定颜色的补色,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中
3、心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,对各条扫描线循环上述处理过程。,以边为中心的边缘填充算法,原始多边形,以边为中心的边缘填充算法,初始化:将绘图窗口的背景色置为多边形颜色的补色,以边为中心的边缘填充算法,对非水平边上的每个象素点向右求余,以边为中心的边缘填充算法,以边为中心的边缘填充算法,以边为中心的边缘填充算法,该算法的优点是简单,缺点是对复杂图形,每一象素可能被访问多次,输入输出的量比较大. 栅栏填充算法 基本思想:对于每个扫描线与多边形边的交点,仅将交点与栅栏之间的象素取补.,边缘填充算法特点,栅栏填充算法,将当前扫描线上的所有象素着上指定颜色
4、的补色,栅栏填充算法,将当前扫描线上的所有象素着上指定颜色的补色,栅栏填充算法,将当前扫描线上的所有象素着上指定颜色的补色,栅栏填充算法,边标志算法进一步改进了栅栏算法,使得算法对每个象素仅访问一次. 边标志算法分两步进行: 对多边形边界上的象素打上边标志; 填充.,边标志算法,扫描线算法:对每条扫描线,首先计算它与扇形区域边界的交点,再把配对交点之间的像素用指定颜色填充。,Filling Ellipse Arcs,区域(种子)填充是指先将区域内的一点(种子点)赋予给定颜色,然后将颜色扩充到整个区域内的过程(染色过程). 区域:已经表示成点阵形式的象素集合,具有相同颜色.,区域填充(种子填充算
5、法),区域的两种表示:内点表示、边界表示. 边界表示:给位于边界上的所有象素着色,而区 域内不着色.,区域的表示,内点表示:给区域内所有象素都着上同一种颜色 (特征值),边界上pixel不着色.,要求: 区域具有一定的连通性:4连通或8连通 4连通区域:取区域内任意两点,在该区域内(不能通过区域外的点),若从其中一点出发,通过上、下、左、右 四种运动可到达另一点时,则称该区域为4连通区域.,区域连通性(1),4连通运动方向,8连通运动方向,区域连通性(2),区域连通性(3),允许从4个方向搜索下一个象素的填充算法称为是四向填充算法,允许从8个方向搜索下一个象素的填充算法称为是8向填充算法,算法
6、思想: 设G为一内点表示的区域,(x,y)是G内一点,以(x,y)为种子点,先将(x,y)置为newcolor,然后对(x,y)的4(或8)领域进行递归处理,逐步将整个区域G置为newcolor.,(1)递归算法,递归填充算法,初始化:种子象素入栈 第一步:栈顶象素出栈,作为种子点; 第二步:种子点被置为填充色; 第三步:按照上、下、左、右顺序检查与种子点相邻的象素:若非边界且未被填充,则入栈(8向连通区域需考虑更多相邻象素)。 若栈不空,则重复第一步。,void FloodFill4(int x, int y, int oldColor, int newColor) if (GetPixel
7、(x,y)=oldColor) PutPixel(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); ,Algorithm,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,Example:,算法: (1)填充并确定种子点所在的区段; (2)将种子区段压栈; (
8、3)若堆栈非空,栈顶区段出栈;否则算法 结束; (4)填充并确定新的区段, 将其区段信息 压栈.,(2)扫描线算法,扫描线种子填充算法流程(1),初始化:由指定的种子象素点(x,y)生成种子(y,xl,xr),填充并入栈。 (xl,xr分别为种子点所在扫描线上多边形内部区间的左、右端点) 第一步:若种子栈空则算法终止,否则栈顶种子出栈 第二步:确定新种子:分别确定y+1,y-1扫描线上与(y,xl,xr)连通的区间;填充新区间并将新种子压入堆栈 第三步:上述过程循环执行。,扫描线种子填充算法流程(2),考虑到区域可以是凹的或有内环的,所以可能在该扫描线上出现多个填充区间,亦即需定义多个种子。,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 图形学 边缘 填充 算法
链接地址:https://www.31doc.com/p-2922540.html