多边形的转换及区域填充课件

《多边形的转换及区域填充课件》由会员分享，可在线阅读，更多相关《多边形的转换及区域填充课件（65页珍藏版）》请在装配图网上搜索。

1、 2023/8/161多边形的转换及区域填充课件内容内容n 基本概念基本概念n 扫描转换矩形扫描转换矩形n 扫描转换多边形扫描转换多边形n 区域填充区域填充n 光栅图形的反走样光栅图形的反走样多边形的扫描转换及区域填多边形的扫描转换及区域填充充2基本概念基本概念n多边形有两种重要的表示方法n顶点表示 n用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内，故不能直接用于面着色 n点阵表示 n用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。多边形的扫描转

2、换及区域填多边形的扫描转换及区域填充充3基本概念基本概念n多边形的扫描转换n把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应象素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。n区域填充（演示）n是指先将在点阵表示的多边形区域内的一点（称为种子点）赋予指定的颜色和灰度，然后将这种颜色和灰度扩展到整个区域内的过程。多边形的扫描转换及区域填多边形的扫描转换及区域填充充4扫描转换矩形扫描转换矩形n问题：n矩形是简单的多边形，那么为什么要单独处理矩形？n应用非常多，特别是窗口系统n比一般多边形可简化计算n共享边界如何处理？n左闭

3、右开n下闭上开属于谁？多边形的扫描转换及区域填多边形的扫描转换及区域填充充5扫描转换矩形扫描转换矩形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(x,y,color);/*end of FillRectangle()*/多边形的扫描转换及区域填多边形的扫描转换及区域填充充6扫描转换多边形扫描转换多边形n凸多边形n任意两顶点间的连线均在多边形内n凹多边形n任意两顶点间的连线有不在多边形内的部分 n含内环的多边形n

4、多边形内再套有多边形，多边形内的多边形也叫内环，内环之间不能相交多边形的扫描转换及区域填多边形的扫描转换及区域填充充7扫描转换多边形扫描转换多边形n几种方法n逐点判断算法n逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。n扫描线算法（要求重点掌握）n利用相邻像素之间的连贯性，避免逐点判断和反复求交运算。n边缘填充算法n利用求余运算，来达到填充的目的。多边形的扫描转换及区域填多边形的扫描转换及区域填充充8逐点判断算法逐点判断算法void FillPolygonPbyP(Polygon*P,int polygonColor)int x,y;for(y=

5、ymin;y=ymax;y+)for(x=xmin;x i结点的x值递增 x；n n/*polyfill*/多边形的扫描转换及区域填多边形的扫描转换及区域填充充37多边形扫描线算法分析多边形扫描线算法分析100246810122468P3P2P1P4P5P6e3e4e2e1e5e6-2.5791.511013110291.575-2.573012345677ETymax x deltaxe1e2e6e5e3e4多边形的扫描转换及区域填多边形的扫描转换及区域填充充38100246810 122468P3P2P1P4P5P6e3e4e2e1e5e6-2.5791.511013110291.575-

6、2.573012345677ETymax x deltaxe1e2e6e5e3e4 (11.5,10)-(13,10)AET=空空y=1 AET=-2.573空1.575(7,1)-(7,1)y=2 AET=-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)-

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 AET=空空11011101.511130(10,9)-(13,9)多边形的扫描转换及区域填多边形的扫描转换及区域填充充39扫描线算法与逐点判断法的比较扫描线算法与逐点判断法的比较n扫描线算法的数据结构和算法本身都比逐点判断法复杂得多。n扫描线算法利用边的连贯性以加速交点的计算，利用ET以排除盲目求交。n扫描线算法利用扫描线的连贯性以避免逐点判别，所以速度要比逐点判断算法快得多。多边形的扫

8、描转换及区域填多边形的扫描转换及区域填充充40区域填充区域填充 n区域n指已经表示成点阵形式的填充图形,它是相互连通的一组像素的集合。n区域填充 n是对区域重新着色的过程。是指先将区域的一点（称为种子点）赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。多边形的扫描转换及区域填多边形的扫描转换及区域填充充41区域填充区域填充n区域的表示形式n1.内点表示n枚举出给定区域内所有像素n内部的所有像素着同一个颜色n边界像素着与内部像素不同的颜色n2.边界表示n枚举出给定区域所有边界上像素n边界上的所有像素着同一颜色n内部像素着与边界像素不同的颜色区域的内点表示和边界表示

9、区域的内点表示和边界表示多边形的扫描转换及区域填多边形的扫描转换及区域填充充42区域填充区域填充n区域填充要求区域是连通的n区域的连通形式n4连通n8连通多边形的扫描转换及区域填多边形的扫描转换及区域填充充43区域填充区域填充n4连通与8连通区域的区别n连通性：4连通可看作8连通区域，但对边界有要求n对边界的要求多边形的扫描转换及区域填多边形的扫描转换及区域填充充44种子填充算法种子填充算法-内点表示区域内点表示区域n设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整

10、个区域G都置为同样的颜色。n步骤：n种子象素入栈，当栈非空时，执行如下三步操作n（1）栈顶象素出栈n（2）将出栈象素置成多边形色n（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。多边形的扫描转换及区域填多边形的扫描转换及区域填充充45种子填充算法种子填充算法-内点表示区域内点表示区域n例：多边形由P0P1P2P3P4构成：P0(1,5)、P1(5,5)、P2(7,3)、P3(7,1)、P4(1,1)n设种子点为（3，3），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示 P0(1,5)P1(5,5

11、)P2(7,3)P3(7,1)P4(1,1)多边形的扫描转换及区域填多边形的扫描转换及区域填充充46种子填充算法种子填充算法-内点表示区域内点表示区域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,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,o

12、ldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);多边形的扫描转换及区域填多边形的扫描转换及区域填充充47种子填充算法种子填充算法-边界表示区域边界表示区域n步骤：n种子象素入栈，当栈非空时，执行如下三步操作n（1）栈顶象素出栈n（2）将出栈象素置成多边形色n（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。填充填充填充填充多边形的扫描转换及区域填多边形的扫描转换及区域填充充48种子填充算法种子填充算法-边界表示区域边界表示区域void BoundaryFill4(int

13、 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);BoundaryFill4(x,y-1,oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);n递归算法可实现如

14、下多边形的扫描转换及区域填多边形的扫描转换及区域填充充49种子填充算法种子填充算法-边界表示区域边界表示区域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)多边形的扫描转换及区域填多边形的扫描转换及区域填充充50种子填充算法种子填充算法 n该算法也可以填充有孔区域。n缺点n有些像素会入栈多次，降低算法效率；栈结构占空间。n递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。n改进算法:n减少递归次数，提高效率。n解决方法：n用扫描线填充算法多边形的扫描转换及区域

15、填多边形的扫描转换及区域填充充51扫描线填充算法扫描线填充算法n目标n减少递归层次n适用范围n内点表示的4连通区域n算法思想n在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的个区段都填充完毕。多边形的扫描转换及区域填多边形的扫描转换及区域填充充52扫描线填充算法扫描线填充算法n步骤：n(1)初始化：堆栈置空。将种子点（x，y）入栈。n(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。n(3)填充并确定种子点

16、所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。n(4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。多边形的扫描转换及区域填多边形的扫描转换及区域填充充53扫描线填充算法扫描线填充算法-举例分析举例分析1 1多边形的扫描转换及区域填多边形的扫描转换及区域填充充54扫描线填充算法扫描线填充算法-举例分析举例分析2 21321多边形的扫描转换及区域填多边形的扫描转换及区域填充充55扫描线填充算法扫描线

17、填充算法-举例分析举例分析2 2321321321多边形的扫描转换及区域填多边形的扫描转换及区域填充充56扫描线填充算法扫描线填充算法-举例分析举例分析2 23212121多边形的扫描转换及区域填多边形的扫描转换及区域填充充57扫描线填充算法扫描线填充算法-举例分析举例分析2 221321多边形的扫描转换及区域填多边形的扫描转换及区域填充充58扫描线填充算法扫描线填充算法-举例分析举例分析2 21多边形的扫描转换及区域填多边形的扫描转换及区域填充充59以图像填充区域以图像填充区域n均匀着色方式n位图不透明填充方式n位图透明填充方式n像素图填充方式多边形的扫描转换及区域填多边形的扫描转换及区域填

18、充充60 多边形扫描转化与区域填充的比较多边形扫描转化与区域填充的比较n联系n都是光栅图形面着色，用于真实感图形显示。可相互转换。n多边形的扫描转换转化为区域填充n当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。n区域填充转化为多边形的扫描转换n若已知给定多边形区域是多边形区域，并且通过一定的方法求出它的顶点坐标，则区域填充问题转化为多边形的扫描转换。n差别n基本思想不同n对边界的要求不同n基于的条件不同多边形的扫描转换及区域填多边形的扫描转换及区域填充充61光栅图形的反走样光栅图形的反走样n走样(aliasin

19、g)n用离散量表示连续量引起的失真现象n反走样(antialiasing)n用于减少或消除这种效果的技术n反走样技术n提高分辨率n区域采样n加权区域取样多边形的扫描转换及区域填多边形的扫描转换及区域填充充62光栅图形的反走样光栅图形的反走样FSAA Disabled-640 x480 多边形的扫描转换及区域填多边形的扫描转换及区域填充充63光栅图形的反走样光栅图形的反走样1.5 x 1.5 FSAA -640 x480 多边形的扫描转换及区域填多边形的扫描转换及区域填充充64光栅图形的反走样光栅图形的反走样2 x 2 FSAA -640 x480 多边形的扫描转换及区域填多边形的扫描转换及区域填充充65