《计算机图形学边缘填充算法精选文档.ppt》由会员分享，可在线阅读，更多相关《计算机图形学边缘填充算法精选文档.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机图形学边缘填充算法本讲稿第一页，共六十三页基本思想:对于每一条扫描线和每条多边形边的交点 (x1,y1),将该扫描线上交点右方的所有象素取补.对多边形的每条边做此处理,多边形的顺序随意.n该算法的优点是简单,缺点是对复杂图形,每一象素可能被访问多次,输入输出的量比较大.边缘填充算法本讲稿第二页，共六十三页以扫描线为中心的边缘填充算法基本思想:对于每一条扫描线和每条多边形边的交 点(x1,y1),将该扫描线上交点右方的所 有象素取补.对多边形的每条边做此处理,多边形的顺序随意.本讲稿第三页，共六十三页将当前扫描线上的所有象素着上指定颜色的补色以扫描线为中心的边缘填充算法本讲稿第四页，共六十
2、三页向右求余从1)(xa以扫描线为中心的边缘填充算法本讲稿第五页，共六十三页以扫描线为中心的边缘填充算法本讲稿第六页，共六十三页向右求余从2)(xc以扫描线为中心的边缘填充算法本讲稿第七页，共六十三页向右求余从2)(xc以扫描线为中心的边缘填充算法本讲稿第八页，共六十三页向右求余从3)(xd以扫描线为中心的边缘填充算法本讲稿第九页，共六十三页向右求余从3)(xd以扫描线为中心的边缘填充算法本讲稿第十页，共六十三页以扫描线为中心的边缘填充算法本讲稿第十一页，共六十三页以扫描线为中心的边缘填充算法将当前扫描线上的所有象素着上指定颜色的补色本讲稿第十二页，共六十三页以扫描线为中心的边缘填充算法将当前
3、扫描线上的所有象素着上指定颜色的补色本讲稿第十三页，共六十三页以扫描线为中心的边缘填充算法本讲稿第十四页，共六十三页以扫描线为中心的边缘填充算法本讲稿第十五页，共六十三页以扫描线为中心的边缘填充算法本讲稿第十六页，共六十三页以扫描线为中心的边缘填充算法本讲稿第十七页，共六十三页以扫描线为中心的边缘填充算法本讲稿第十八页，共六十三页以扫描线为中心的边缘填充算法本讲稿第十九页，共六十三页以扫描线为中心的边缘填充算法对各条扫描线循环上述处理过程。本讲稿第二十页，共六十三页以边为中心的边缘填充算法原始多边形本讲稿第二十一页，共六十三页以边为中心的边缘填充算法初始化：将绘图窗口的背景色置为多边形颜色的补
4、色本讲稿第二十二页，共六十三页以边为中心的边缘填充算法对非水平边上的每个象素点向右求余本讲稿第二十三页，共六十三页以边为中心的边缘填充算法本讲稿第二十四页，共六十三页以边为中心的边缘填充算法本讲稿第二十五页，共六十三页以边为中心的边缘填充算法本讲稿第二十六页，共六十三页 该算法的优点是简单,缺点是对复杂图形,每一象素可能被访问多次,输入输出的量比较大.n 栅栏填充算法 基本思想:对于每个扫描线与多边形边的交点,仅将交点与栅栏之间的象素取补.边缘填充算法特点本讲稿第二十七页，共六十三页栅栏填充算法向左求余从0)(xa将当前扫描线上的所有象素着上指定颜色的补色本讲稿第二十八页，共六十三页向左求余从
5、1)(xa栅栏填充算法本讲稿第二十九页，共六十三页向左求余从2)(xa将当前扫描线上的所有象素着上指定颜色的补色栅栏填充算法本讲稿第三十页，共六十三页向右求余从3)(xa将当前扫描线上的所有象素着上指定颜色的补色栅栏填充算法本讲稿第三十一页，共六十三页 边标志算法进一步改进了栅栏算法,使得算法对每个象素仅访问一次.边标志算法分两步进行:对多边形边界上的象素打上边标志;填充.边标志算法本讲稿第三十二页，共六十三页 扫描线算法：对每条扫描线，首先计算它与扇形区域边界的交点，再把配对交点之间的像素用指定颜色填充。Filling Ellipse Arcs本讲稿第三十三页，共六十三页 区域（种子）填充是
6、指先将区域内的一点(种子点)赋予给定颜色,然后将颜色扩充到整个区域内的过程(染色过程).n区域:已经表示成点阵形式的象素集合,具有相同颜色.区域填充(种子填充算法)本讲稿第三十四页，共六十三页n区域的两种表示:内点表示、边界表示.n边界表示:给位于边界上的所有象素着色,而区 域内不着色.区域的表示v 内点表示:给区域内所有象素都着上同一种颜色 (特征值),边界上pixel不着色.本讲稿第三十五页，共六十三页要求:区域具有一定的连通性:4连通或8连通4连通区域:取区域内任意两点,在该区域内(不能通过区域外的点),若从其中一点出发,通过上、下、左、右 四种运动可到达另一点时,则称该区域为4连通区域
7、.区域连通性（区域连通性（1）本讲稿第三十六页，共六十三页4连通运动方向8连通运动方向区域连通性（区域连通性（2）本讲稿第三十七页，共六十三页区域连通性（区域连通性（3）允许从4个方向搜索下一个象素的填充算法称为是四向填充算法允许从8个方向搜索下一个象素的填充算法称为是8向填充算法本讲稿第三十八页，共六十三页算法思想：设G为一内点表示的区域，(x,y)是G内一点，以(x,y)为种子点，先将(x,y)置为newcolor，然后对(x,y)的4(或8)领域进行递归处理，逐步将整个区域G置为newcolor.(1)递归算法本讲稿第三十九页，共六十三页递归填充算法n初始化：种子象素入栈n第一步：栈顶象
8、素出栈，作为种子点；n第二步：种子点被置为填充色；n第三步：按照上、下、左、右顺序检查与种子点相邻的象素：若非边界且未被填充，则入栈（8向连通区域需考虑更多相邻象素）。n若栈不空，则重复第一步。本讲稿第四十页，共六十三页void FloodFill4(int x,int y,int oldColor,int newColor)if(GetPixel(x,y)=oldColor)PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,
9、y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);Algorithm本讲稿第四十一页，共六十三页12345678910111213141516171819202122Example：本讲稿第四十二页，共六十三页算法:(1)填充并确定种子点所在的区段；(2)将种子区段压栈;(3)若堆栈非空,栈顶区段出栈;否则算法 结束;(4)填充并确定新的区段,将其区段信息 压栈.(2)扫描线算法本讲稿第四十三页，共六十三页扫描线种子填充算法流程（1）n初始化：由指定的种子象素点(x,y)生成种子(y,xl,xr),填充并入栈。(xl,xr分别为种
10、子点所在扫描线上多边形内部区间的左、右端点)n第一步：若种子栈空则算法终止，否则栈顶种子出栈n第二步：确定新种子：分别确定y+1,y-1扫描线上与(y,xl,xr)连通的区间；填充新区间并将新种子压入堆栈n第三步：上述过程循环执行。本讲稿第四十四页，共六十三页扫描线种子填充算法流程（2）考虑到区域可以是凹的或有内环的，所以可能在该扫描线上出现多个填充区间，亦即需定义多个种子。yy+1同样考虑到凹或有孔的区域，需对扫描线y-1进行同样的处理，获得新的种子。本讲稿第四十五页，共六十三页扫描线种子填充算法的改进思路n算法中的回溯过程并非总是必要的。无需进行填充回溯需要进行填充回溯本讲稿第四十六页，共
11、六十三页Pattern fillingn用图象(pattern)填充区域v Definition of the pattern:v M X N bitmapsv patternij:the value of the position(i,j)本讲稿第四十七页，共六十三页Two issues n the relation of the area of the pattern to that of the primitiveRelative anchorAbsolute anchorn write modeTransparentOpaque本讲稿第四十八页，共六十三页Relative anchor
12、To anchor the pattern at a vertex of the primitive:(x0,y0)valuexy=pattern(x-x0)%M(y-y0)%N(x0,y0)MN个像素定义的图案本讲稿第四十九页，共六十三页Absolute anchor MN个像素定义的图案 To consider the entire screen as being tiled with the pattern and to think of the primitive as consisting of an outline or filled area of transparent bit
13、s that let the pattern show through valuexy=patternx%My%n(x,y)本讲稿第五十页，共六十三页write modenFilling with a pattern:Adding extra control to the part of the scan-conversion algorithm that actually writes each pixelnWrite modenDoing PutPixel with foreground color at a pixel for a 1 in the patternnIn transpar
14、ent mode:若为0，则不改变屏幕上该象素的颜色（不做任何处理）；nIn opaque mode 若为0，则用背景色显示该象素本讲稿第五十一页，共六十三页Pattern filling without repeated scan conversionnRectangle writenTo scan convert a primitive first into a rectangular work area,and then to write each pixel from that bitmap to the appropriate place in the canvas.nTwice a
15、s much work as filling during scan conversionnBe suitable to characters,icons and application symbols本讲稿第五十二页，共六十三页(a)Mountain scene(b)Outline of house icon(d)(e)(g)(c)Brick pattern(f)(d)Bitmap for solid version of house icon.(e)Clearing the scene by writing background(f)Brick pattern applied to hou
16、se icon(g)Writing the screen transparently with patterned house iconAn example:Writing a patterned object in opaque mode with two transparent writes本讲稿第五十三页，共六十三页Thick primitives 在产生一定宽度的线条时,只需用一个“刷子”来替代单象素直线段中扫描生成的单象素即可.线画图元的属性控制本讲稿第五十四页，共六十三页Replicating pixels(1)(线刷子)nUsing more than 1 pixel for e
17、ach column(or row)during scan conversionThick line drawn by column replicationnPixels are duplicated in column for lines with 1slope1nPixels are duplicated in rows for all other lines本讲稿第五十五页，共六十三页原理:假设直线斜率在-1,+1之间,如图(a)所示.这时可把刷子置成垂直方向图(b).首先将刷子的中点对准直线的一个端点,从该点开始,让刷子中点沿直线的轨迹往直线的另一端点平移即可“刷出”具有一定宽度的直线
18、.如图(c).m1m2(a)(b)(c)Replicating Pixels(2)本讲稿第五十六页，共六十三页缺点:(1)线的始末断总是水平或垂直的.(2)线的粗细不一样.水平和垂直线最粗,45斜线最 细.(3)当线宽为偶数个时,绘制的线条宽度不精确.Disadvantages 本讲稿第五十七页，共六十三页 方形刷子是一个宽度为指定线宽的正方形.将正方形的中心对准直线作平移运动即可.m1The Moving Pen(方形刷子)方形刷子本讲稿第五十八页，共六十三页The Moving Pen(方形刷子)Thick line drawn by tracing a rectangular pen.T
19、hick line drawn by column replication本讲稿第五十九页，共六十三页 该方法将会重复的写象素.为避免重复,可采用与活化边表类似的技术.Disadvantages 本讲稿第六十页，共六十三页jj+1 j+2j+3 j+4i-1ii+1i+2i+3i+4jj+1 j+2j+3 j+4i-1ii+1i+2i+3i+4ii+1i+2i+3j,j+2 j,j+2j,j+2(a)ii+1i+2i+3j,j+2 j,j+3j,j+3j+1,j+3(b)Recording spans of the rectangular pen:(a)footprint at x=j+1;(b)x=j+2Recording the spans本讲稿第六十一页，共六十三页 先算出直线的四个角点的坐标,将其顺序连接成一个四边形,再用区域填充的方法将四边形填充.Filling Areas Between Boundariesn 圆弧线宽的处理 圆弧线宽的处理与直线类似.本讲稿第六十二页，共六十三页 如虚线、实线、点划线等不同线的处理.Line Style And Pen Style本讲稿第六十三页，共六十三页