多边形的扫描转换及区域填充讲稿.ppt

《多边形的扫描转换及区域填充讲稿.ppt》由会员分享，可在线阅读，更多相关《多边形的扫描转换及区域填充讲稿.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多边形的扫描转换及区域填充多边形的扫描转换及区域填充第一页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-2 2内容内容n 基本概念基本概念n 扫描转换矩形扫描转换矩形n 扫描转换多边形扫描转换多边形n 区域填充区域填充n 光栅图形的反走样光栅图形的反走样第二页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-3 3基本概念基本概念n多边形有两种重要的表示方法n顶点表示 n用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内，故不能直接用于面着色 n点阵

2、表示 n用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。第三页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-4 4基本概念基本概念n多边形的扫描转换n把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应象素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。n区域填充（演示）n是指先将在点阵表示的多边形区域内的一点（称为种子点）赋予指定的颜色和灰度，然后将这种颜色和灰度扩展到整个区域内的过程。第四页，讲稿共六十二页哦多边

3、形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-5 5扫描转换矩形扫描转换矩形n问题：n矩形是简单的多边形，那么为什么要单独处理矩形？n应用非常多，特别是窗口系统n比一般多边形可简化计算n共享边界如何处理？n左闭右开n下闭上开属于谁？第五页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-6 6扫描转换矩形扫描转换矩形n方法void FillRectangle(Rectangle*rect,int color)int x,y;for(y=rect-ymin;y ymax;y+)for(x=rect-xmin;x xmax;x+)PutPixel(

4、x,y,color);/*end of FillRectangle()*/第六页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-7 7扫描转换多边形扫描转换多边形n凸多边形n任意两顶点间的连线均在多边形内n凹多边形n任意两顶点间的连线有不在多边形内的部分 n含内环的多边形n多边形内再套有多边形，多边形内的多边形也叫内环，内环之间不能相交第七页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-8 8扫描转换多边形扫描转换多边形n几种方法n逐点判断算法n逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区

5、域内的像素的集合。n扫描线算法（要求重点掌握）n利用相邻像素之间的连贯性，避免逐点判断和反复求交运算。n边缘填充算法n利用求余运算，来达到填充的目的。第八页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-9 9逐点判断算法逐点判断算法void FillPolygonPbyP(Polygon*P,int polygonColor)int x,y;for(y=ymin;y=ymax;y+)for(x=xmin;x i结点的x值递增 x；n n/*polyfill*/第三十七页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-38

6、38多边形扫描线算法分析多边形扫描线算法分析100246810122468P3P2P1P4P5P6e3e4e2e1e5e6-2.5791.511013110291.575-2.573012345677ETymax x xe1e2e6e5e3e4第三十八页，讲稿共六十二页哦100246810122468P3P2P1P4P5P6e3e4e2e1e5e6-2.5791.511013110291.575-2.573012345677ETymax x xe1e2e6e5e3e4 (11.5,10)-(13,10)AET=空空y=1 AET=-2.573空1.575(7,1)-(7,1)y=2 AET=-

7、2.54.53空1.58.55(4.5,2)-(8.5,2)y=3 AET=029空1.5105(2,3)-(10,3)y=4 AET=029空1.511.55(2,4)-(11.5,4)y=5 AET=029空13(2,5)-(13,5)y=6 AET=029空01311(2,6)-(13,6)y=7 AET=029-2.579(2,7)-(7,7)1.5711空01311(7,7)-(13,7)y=8 AET=029-2.54.59(2,8)-(4.5,8)1.58.51101311(8.5,8)-(13,8)空y=9 AET=空y=10 AET=1.511.51101311空y=11 A

8、ET=空空11011101.511130(10,9)-(13,9)第三十九页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-4040扫描线算法与逐点判断法的比较扫描线算法与逐点判断法的比较n扫描线算法的数据结构和算法本身都比逐点判断法复杂得多。n扫描线算法利用边的连贯性以加速交点的计算，利用ET以排除盲目求交。n扫描线算法利用扫描线的连贯性以避免逐点判别，所以速度要比逐点判断算法快得多。第四十页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-4141区域填充区域填充 n区域n指已经表示成点阵形式的填充图形,它是相互连通的一

9、组像素的集合。n区域填充 n是对区域重新着色的过程。是指先将区域的一点（称为种子点）赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。第四十一页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-4242区域填充区域填充n区域的表示形式n1.内点表示n枚举出给定区域内所有像素n内部的所有像素着同一个颜色n边界像素着与内部像素不同的颜色n2.边界表示n枚举出给定区域所有边界上像素n边界上的所有像素着同一颜色n内部像素着与边界像素不同的颜色区域的内点表示和边界表示区域的内点表示和边界表示第四十二页，讲稿共六十二页哦多边形的扫描转换及区域

10、填充多边形的扫描转换及区域填充第五章第五章-4343区域填充区域填充n区域填充要求区域是连通的n区域的连通形式n4连通n8连通第四十三页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-4444区域填充区域填充n4连通与8连通区域的区别n连通性：4连通可看作8连通区域，但对边界有要求n对边界的要求第四十四页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-4545种子填充算法种子填充算法-内点表示区域内点表示区域n设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填

11、充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。n步骤：n种子象素入栈，当栈非空时，执行如下三步操作n（1）栈顶象素出栈n（2）将出栈象素置成多边形色n（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。第四十五页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-4646种子填充算法种子填充算法-内点表示区域内点表示区域n例：多边形由P0P1P2P3P4构成：P0(1,5)、P1(5,5)、P2(7,3)、P3(7,1)、P4(1,1)n设种子点为（3，3

12、），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示 P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)第四十六页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-4747种子填充算法种子填充算法-内点表示区域内点表示区域n递归算法可实现如下void FloodFill4(int x,int y,int oldColor,int newColor)int color;color=GetPixel（x，y）;if（color=oldColor）PutPixel(x,y,newColor);FloodFill4(x

13、,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);第四十七页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-4848种子填充算法种子填充算法-边界表示区域边界表示区域n步骤：n种子象素入栈，当栈非空时，执行如下三步操作n（1）栈顶象素出栈n（2）将出栈象素置成多边形色n（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界

14、上且未置成多边形色，则把该象素入栈。填充填充填充填充第四十八页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-4949种子填充算法种子填充算法-边界表示区域边界表示区域void BoundaryFill4(int x,int y,int boundaryColor,int newColor)int color;color=GetPixel(x,y);if(color!=boundaryColor)&(color!=newColor)PutPixel(x,y,newColor);BoundaryFill4(x,y+1,oldColor,newColor);Bo

15、undaryFill4(x,y-1,oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);n递归算法可实现如下第四十九页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-5050种子填充算法种子填充算法-边界表示区域边界表示区域0 1 2 3 4 54321(3,2)(2,2)(3,3)(4,2)(3,1)(2,1)(4,1)(4,2)(2,2)(1,2)(2,3)(3,3)第五十页，讲稿共六十二页哦多边形的扫描转换及区域

16、填充多边形的扫描转换及区域填充第五章第五章-5151种子填充算法种子填充算法 n该算法也可以填充有孔区域。n缺点n有些像素会入栈多次，降低算法效率；栈结构占空间。n递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。n改进算法:n减少递归次数，提高效率。n解决方法：n用扫描线填充算法第五十一页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-5252扫描线填充算法扫描线填充算法n目标n减少递归层次n适用范围n内点表示的4连通区域n算法思想n在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描

17、线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的个区段都填充完毕。第五十二页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-5353扫描线填充算法扫描线填充算法n步骤：n(1)初始化：堆栈置空。将种子点（x，y）入栈。n(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。n(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。n(4)并确定新的种子点：在区间xl，xr中检查与

18、当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。第五十三页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-5454扫描线填充算法扫描线填充算法-举例分析举例分析1 1第五十四页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-5555扫描线填充算法扫描线填充算法-举例分析举例分析2 21321第五十五页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-5656扫描线填充算法扫描线填充算法-举例分析举例分析2 2

19、321321321第五十六页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-5757扫描线填充算法扫描线填充算法-举例分析举例分析2 23212121第五十七页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-5858扫描线填充算法扫描线填充算法-举例分析举例分析2 221321第五十八页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-5959扫描线填充算法扫描线填充算法-举例分析举例分析2 21第五十九页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-

20、6060以图像填充区域以图像填充区域n均匀着色方式n位图不透明填充方式n位图透明填充方式n像素图填充方式第六十页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-6161 多边形扫描转化与区域填充的比较多边形扫描转化与区域填充的比较n联系n都是光栅图形面着色，用于真实感图形显示。可相互转换。n多边形的扫描转换转化为区域填充n当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。n区域填充转化为多边形的扫描转换n若已知给定多边形区域是多边形区域，并且通过一定的方法求出它的顶点坐标，则区域填充问题转化为多边形的扫描转换。n差别n基本思想不同n对边界的要求不同n基于的条件不同第六十一页，讲稿共六十二页哦多边形的扫描转换及区域填充多边形的扫描转换及区域填充第五章第五章-6262光栅图形的反走样光栅图形的反走样n走样(aliasing)n用离散量表示连续量引起的失真现象n反走样(antialiasing)n用于减少或消除这种效果的技术n反走样技术n提高分辨率n区域采样n加权区域取样第六十二页，讲稿共六十二页哦