《计算机图形学5多边形扫描转换和区域填充.ppt》由会员分享，可在线阅读，更多相关《计算机图形学5多边形扫描转换和区域填充.ppt（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、多边形的扫描转换与区域填充多边形的扫描转换与区域填充一、多边形的扫描转换一、多边形的扫描转换 前面讲的画直线是一维图形的光栅化，就是如何在计算机屏幕上即在一个离散的像素集上表示一个连续的图形。而多边形的扫描转换和区域填充这个问题是怎么样在离散的像素集上表示一个连续的二维图形。多边形有两种重要的表示方法：顶点顶点表示和点阵点阵表示。点阵表示P1P2P3P4P5顶点表示P6 顶点表示是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内，故不能直接用于面着色。点阵表示是用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几
2、何信息（如（如边界边界、顶点顶点等），但它却是等），但它却是光栅显示系统显示时所需的表示形式。光栅显示系统显示时所需的表示形式。这涉及到两个问题：第一个问题是如果知道边界，能否求出这个多边形哪些像素在多边形内。众所周知，在计算机上画图形，实际上就是写帧缓存（frame buffer）。如果知道多边形哪些像素在里面，就直接写到帧缓存里即可。第二个问题是知道多边形内部的像素，反过来求多边形的边界。很遗憾，这个问题不是图形学关心的问题，是模式识别所关心的问题。图形学、图像处理、模式识别、计算机视觉有密切的联系。我们只关心从顶点表示到点阵表示。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。
3、这种转换称为多边形的扫描转换多边形的扫描转换。为什么叫扫描转换？因为光栅显示器是逐行扫描！区域填充区域填充:指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。多边形分为凸多边形、凹多边形、含内环的多边形等：（1）凸多边形任意两顶点间的连线均在多边形内。（2）凹多边形任意两顶点间的连线有不在多边形内的部分。凸多边形 凹多边形 含内环的多边形 有关概念有关概念 1)区域：一组相邻而且又相连的像素，而且具有相同属性的封闭区域。3)区域填充：以某种属性对整个区域进行设置的过程。2）种类：单域 复合域逐点判断填充算法区域填充的基本(初级)方法:逐点判断填充算法l逐点判断绘图窗口内的每一个
4、像素；l若在区域的内部：用指定的属性设置该点；l否则不予处理；设有如下函数：True when x DInside(D,x,y)=False when x DD取矩形R(x1xx2,y1yy2)，使R包围D，则逐点判断填充算法如下：for(y=y1;y=y2;y+)for(x=x1;xi 结点的x值递增x；若允许多边形的边自相交，则用冒泡排序法对AET表重新排序；/*polyfill*/3 3、边缘填充算法边缘填充算法 其基本思想是按任意顺序处理多边形的每条边。在处理每条边时，首先求出该边与扫描线的交点，然后将每一条扫描线上交点右方的所有像素取补。多边形的所有边处理完毕之后，填充即完成。逐边向
5、右取右右右右边缘填充算法缺点：每一个象素可能被访问多次引入栅栏，以减少填充算法访问象素的次数。栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。基本思想：扫描线与多边形的边求交，将交点与栅栏之间的象素取补。若交点位于栅栏左边，则将交点之右，栅栏之左的所有象素取补；若交点位于栅栏右边，则将交点之左，栅栏之右的所有象素取补。减少了象素重复访问数目，但不彻底。栅栏填充算法6 6、边界标志算法边界标志算法基本思想：l帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。l然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。l使用一个布尔量in
6、side来指示当前点是否在多边形内的状态。void edgemark_fill(polydef,color)多边形定义 polydef；int color;对多边形polydef 每条边进行直线扫描转换；inside=FALSE;for(每条与多边形polydef相交的扫描线y)for(扫描线上每个象素x)if(象素x被打上边标志)/两个交点之间的区域填充 inside=!(inside);if(inside！=FALSE)putpixel(x,y,color);else drawpixel(x,y,background);用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，由于边界标志
7、算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。小结小结 扫描线法可以实现已知多边形域边界的填充，多边形域可以是凹的、凸的、还可以是带孔的。该填充算法是按扫描线的顺序，计算扫描线与待填充区域的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。这里区间的端点通过计算扫描线与多边形边界的交点获得。所以待填充区域的边界线必须事先知道，因此它的缺点是无法实现对未知边界的区域填充。二、区域填充二、区域填充 区域填充是指将区域内的一点(常称种子点)赋予给定颜色,然后将这种颜色扩展到整个区域内的过程。它是光栅计算机图形学中的一个
8、基本操作，在交互式图形设计、动画、计算机辅助设计等领域有着广泛的应用。区域-指已经表示成点阵形式的填充图形，是象素的集合。在光栅图形学中，区域指的是已经表示成点阵形式的象素的集合。区域可采用内点内点表示和边界边界表示两种表示形式。内点表示：枚举出区域内部的所有像素，内部的所有像素着同一个颜色，边界像素着与内部像素不同的颜色。边界表示：枚举出边界上的所有像素，边界上的所有像素着同一个颜色，内部像素着与边界像素不同的颜色。区域可分为4 4向连通区域向连通区域和和8 8向连通区域向连通区域。四个方向运动 八个方向运动 四连通区域 八连通区域 区域填充算法要求区域是连通的，因为只有在连通区域中，才可能
9、将种子点的颜色扩展到区域内的其它点。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意象素；即：任取区域内两点，在该区域内，通过上、下、左、右四个方向的运动，这两点相互可达。8向连通区域指的是从区域内每一象素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。即：任取区域内两点，通过水平、垂直、两个对角线八个方向的运动，这两点相互可达。四连通区域 八连通区域 种子填充种子填充1 1、简单四连通种子填充算法、简单四连通种子填充算法 种子填充算法的原理是：假设在多边形区域内部有一像素已知，由
10、此出发找到区域内的所有像素，用一定的颜色或灰度来填充。假设区域采用边界定义，即区域边界上所有像素均具有某个特定值，区域内部所有像素均不取这一特定值，而边界外的像素则可具有与边界相同的值。考虑区域的四向连通，即从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素。可以使用栈结构来实现简单的种子填充算法。算法原理如下：种子像素入栈，当栈非空时重复执行如下三步操作：（1）栈顶像素出栈；（2）将出栈像素置成要填充色；（3）按左、上、右、下顺序检查与栈像素相邻的 四个像素，若其中某个像素不在边界且未置 成填充色，则把该像素入栈。种子像素入栈，栈非空时重
11、复执行如下三步：（1）栈顶像素出栈；（2）将出栈像素置成要填充色；（3）按左、上、右、下顺序检查与栈像素相邻的 四个像素，若其中某个像素不在边界且未置 成填充色，则把该像素入栈。扫描线填充算法(1)初始化：堆栈置空。将种子点（x，y）入栈。(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。(4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为
12、种子点压入堆栈，返回第（2）步。上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。扫描线算法分析（举例分析）该算法也可以填充有孔区域。像素中的序号标指它所在区段位于堆栈中的位置扫描线算法分析（举例分析）扫描线算法分析（举例分析）扫描线算法分析（举例分析）2 2、扫描填充与区域填充区别、扫描填充与区域填充区别 基本思想不同基本思想不同基本思想不同基本思想不同l l多边形扫描转换是指将多边形的顶点表示转化为点阵表示；多边形扫描转换是指将多边形的顶点表示转化为点阵表示；多边形扫描转换是指将多边形的顶点表示转化为点阵表示；多边形扫描转换是指将多边形的顶点表示转化为点
13、阵表示；l l区域填充只改变区域的填充颜色，不改变区域表示方法区域填充只改变区域的填充颜色，不改变区域表示方法区域填充只改变区域的填充颜色，不改变区域表示方法区域填充只改变区域的填充颜色，不改变区域表示方法。对边界的要求不同对边界的要求不同对边界的要求不同对边界的要求不同l l多多多多边边边边形形形形扫扫扫扫描描描描转转转转换换换换的的的的扫扫扫扫描描描描算算算算法法法法只只只只要要要要求求求求一一一一条条条条扫扫扫扫描描描描线线线线与与与与多多多多边边边边形形形形边边边边界界界界的的的的交交交交点点点点个个个个数数数数为偶数，为偶数，为偶数，为偶数，多边形的边界可以不封闭；多边形的边界可以不
14、封闭；多边形的边界可以不封闭；多边形的边界可以不封闭；l l在在在在区区区区域域域域填填填填充充充充算算算算法法法法中中中中，为为为为了了了了防防防防止止止止递递递递归归归归填填填填充充充充时时时时跨跨跨跨越越越越区区区区域域域域的的的的边边边边界界界界，要要要要求求求求：区区区区域域域域的边界是封闭的边界是封闭的边界是封闭的边界是封闭 基于的条件不同基于的条件不同基于的条件不同基于的条件不同l l在在在在区区区区域域域域填填填填充充充充算算算算法法法法中中中中，要要要要求求求求给给给给定定定定区区区区域域域域内内内内一一一一点点点点作作作作为为为为种种种种子子子子点点点点，然然然然后后后后从
15、从从从这这这这一一一一点点点点根根根根据据据据连通性将新的颜色扩散到整个区域；连通性将新的颜色扩散到整个区域；连通性将新的颜色扩散到整个区域；连通性将新的颜色扩散到整个区域；l l扫扫扫扫描描描描转转转转换换换换多多多多边边边边形形形形是是是是从从从从多多多多边边边边形形形形的的的的边边边边界界界界(顶顶顶顶点点点点)信信信信息息息息出出出出发发发发，利利利利用用用用多多多多种种种种形形形形式式式式的的的的连连连连贯性进行填充的贯性进行填充的贯性进行填充的贯性进行填充的。4 4、填充图元属性控制填充图元属性控制填充图元属性控制填充图元属性控制 填充一个定义的区域的选择包括填充一个定义的区域的选
16、择包括填充一个定义的区域的选择包括填充一个定义的区域的选择包括:选择实区域颜色或图案填充方式选择实区域颜色或图案填充方式选择实区域颜色或图案填充方式选择实区域颜色或图案填充方式;选择某种颜色和图案。选择某种颜色和图案。选择某种颜色和图案。选择某种颜色和图案。l l取决于可用软件包的能力取决于可用软件包的能力取决于可用软件包的能力取决于可用软件包的能力;l l这这这这些些些些填填填填充充充充选选选选择择择择可可可可应应应应用用用用于于于于多多多多边边边边形形形形区区区区域域域域或或或或用用用用曲曲曲曲线线线线边边边边界界界界定定定定义义义义的的的的区域区域区域区域;l l此外，区域可用多种画笔、
17、颜色和透明度参数来绘制。此外，区域可用多种画笔、颜色和透明度参数来绘制。此外，区域可用多种画笔、颜色和透明度参数来绘制。此外，区域可用多种画笔、颜色和透明度参数来绘制。5 5、填充模式填充模式填充模式填充模式 区域显示有以下几种基本填充模式：区域显示有以下几种基本填充模式：区域显示有以下几种基本填充模式：区域显示有以下几种基本填充模式：l l用用用用实实实实颜颜颜颜色色色色填填填填充充充充的的的的区区区区域域域域：以以以以单单单单一一一一颜颜颜颜色色色色将将将将区区区区域域域域内内内内部部部部填填填填充充充充，也也也也可可可可包包包包含含含含其边界。其边界。其边界。其边界。l l指定图案或设计
18、填充的区域指定图案或设计填充的区域指定图案或设计填充的区域指定图案或设计填充的区域。其它的填充选择包括：其它的填充选择包括：其它的填充选择包括：其它的填充选择包括：l l区域的区域的区域的区域的边类型、边宽度边类型、边宽度边类型、边宽度边类型、边宽度和和和和边颜色边颜色边颜色边颜色。这这这这些些些些属属属属性性性性独独独独立立立立于于于于填填填填充充充充模模模模式式式式或或或或填填填填充充充充颜颜颜颜色色色色而而而而设设设设置置置置，且且且且它它它它们们们们提提提提供供供供与与与与线属性参数线属性参数线属性参数线属性参数(线型、线宽和线颜色线型、线宽和线颜色线型、线宽和线颜色线型、线宽和线颜色
19、)相同的选择，相同的选择，相同的选择，相同的选择，也也也也就就就就是是是是说说说说，可可可可以以以以以以以以点点点点线线线线或或或或划划划划线线线线、宽宽宽宽或或或或扁扁扁扁以以以以及及及及任任任任何何何何可可可可用用用用的的的的颜颜颜颜色色色色来显示区域的边，而不必考虑怎样填充区域。来显示区域的边，而不必考虑怎样填充区域。来显示区域的边，而不必考虑怎样填充区域。来显示区域的边，而不必考虑怎样填充区域。图案填充l图案在区域的局部坐标系中定义记局部坐标系原点为:(x0,y0)valuexy=color(x-x0)%M(y-y0)%n(x0,y0)MN个像素定义的图案前景色与背景色的合成问题像素着
20、色模式问题l透明或不透明l本质：规定前景色与背景色的组合规则，如前景色优先、背景色优先、前景色与背景色的加权组合、或各种规则的组合。像素着色模式图案填充 在扫描转换算法中对像素着色操作需增加额外控制像素着色模式l与图案中1标记位置对应的像素写为前景色l在透明模式下：与图案中0标记位置对应的像素不进行写操作l在不透明模式下：与图案中0标记位置对应的像素写为背景色(图案背景色)(a)山峦景色(b)待填充区域轮廓线(d)(e)(g)(c)图案模式(f)(d)待填充区域的像素位图(e)擦除(a)中(d)区域，将像素写为背景色(f)对待填充区域进行图案填充(g)以透明模式把(f)绘在屏幕上例:以透明模式实现图案填充 小结小结 扫描转换区域填充的核心是知道多边形的边界，要得到多边形内部的像素集，有多种方法。其中扫描线算法是利用一套特殊的数据结构，避免求交，然后一条条扫描线确定。区域填充条件更强一些，不但知道边界，而且还知道区域内的一点，可以利用四连通或八连通区域不断往外扩展。在计算机图形学里通常处理的对象模型是连续的，而计算机硬件设备是离散的，只能有限表示。为了克服这样的困难，需要研究一整套算法，在计算机内部存储表示这些数据，这些算法是图形学最基本最底层的技术，也是非常重要的。