《计算机图形学第3章二维基本图3.ppt》由会员分享，可在线阅读，更多相关《计算机图形学第3章二维基本图3.ppt（20页珍藏版）》请在三一文库上搜索。
1、3.4 区域填充,前面介绍的直线和圆都属于线划图，然而，光栅显示的一个重要特点是能进行面着色，区域填充就是在一个闭合区域内填充某种颜色或图案。 区域填充一般分两类：多边形填充和种子填充。 一、多边形填充 1、填充条件 多边形的顶点序列(Pi，i=0，1，n)、填充色。 2、多边形内点的判别准则 对多边形进行填充，关键是找出多边形内的象素。在顺序给定多边形顶点坐标的情况下，如何判明一个象素点是处于多边形的内部还是外部呢？,多边形内点的判别准则和奇异点,从测试点引出一条伸向无穷远处的射线(假设是水平向右的射线)，因为多边形是闭合的，那么： 若射线与多边形边界的交点个数为奇数时，则该点为内点(例：图
2、中测试点4引出的射线)； 反之，交点个数为偶数时，则该点为外点。(例：测试点2引出的射线)。,3、奇异点的处理： 上述的判别准则，在大多数情况下是正确的，但当水平扫描线正好通过多边形顶点时，要特别注意。例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准则它们应该是内点，但实际上却是外点。 而图中过顶点的射线3、射线5，对于判别准则的使用又是正确的。,多边形内点的判别准则和奇异点,综合以上情况，我们将多边形的顶点分为两大类： (1) 局部极值点：如图中的点P1、P2、P4和P6。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的同一侧。 (2)非极值点：如图
3、中的点P3、P5。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的两侧。 处理奇异点规则： （1）对于局部极值点，应看成两个点； （2）对于非极值点，应看成一个点。,多边形内点的判别准则和奇异点,4、逐点判别算法步骤： (1)求出多边形的最小包围盒：从Pi(xi，yi)中求极值，xmin、ymin、xmax、ymax。 (2)对包围盒中的每个象素引水平射线进行测试。 (3)求出该射线与多边形每条边的有效交点个数。 (4)如果个数为奇数：该点置为填充色。 (5)否则：该点置为背景色。 逐点判别算法虽然简单，但不可取，原因是速度慢。它割断了各象素之间的联系，孤立地考虑问题，由于要对
4、每个象素进行多次求交运算，求交时要做大量的乘除运算，从而影响了填充速度。,3.3.1边相关扫描线多边形填充算法,边相关扫描线填充算法属于多边形填充类。它比逐点判别算法速度提高很多，是一种较经典的多边形填充算法。 该算法利用了扫描线的相关性和多边形边的相关性，而不是逐点进行处理。,一、边相关扫描线填充算法描述 扫描线的相关性：某条扫描线上相邻的象素，几乎都具有同样的内外性质，这种性质只有遇到多边形边线与该扫描线的交点时才发生改变。见下图(a)。 边的相关性：由于相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描线yi与该边的交点为xi，而后一条扫描线yi+1=yi+1与该边的交点则
5、为xi+1=xi+1/m，利用这种相关性可以省去大量的求交运算。见下图(b)所示。,边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。 1、边表（ET：Edge Table） 用来对除水平边外的所有边进行登记，来建立边的记录。边的记录定义为：,扫描线 y 对应的ET表,第一项：某边的最大y值（ymax）。注意要进行奇异点处理：对于非极值点应该ymax=ymax-1。 第二项：某边的最小的y对应的x值。 第三项：某边斜率的倒数:1/m。 第四项：指针。用来指向同一条扫描线相交的其它边，如果其它边不存在，则该项置空。,二、边相关扫描线填充算法思想 1、根据给出的多边形顶点
6、坐标，建立ET表； 求出顶点坐标中最大y值ymax和最小y值ymin。 2、初始化AET表指针，使它为空。,2、活动边表（AET：Active Edge Table） ET表建立以后，就可以开始扫描转换了。对不同的扫描线，与之相交的边线也是不同的，当对某一条扫描线进行扫描转换时，我们只需要考虑与它相交的那些边线，为此需要建立一个只与当前扫描线相交的边记录链表，称之为活动边表。,3、使用扫描线的yj值作为循环变量，使其初值为ymin。 对于循环变量yj的每一整数值，重复作以下事情，直到yj大于ymax，或ET表与AET表都为空为止： (1) 如果ET表中yj桶非空，则将yj桶中的全部记录合并到A
7、ET表中。 (2) 对AET表链中的记录按x的大小从小到大排序。 (3) 依次取出AET表各记录中的xi坐标值，两两配对填充，即将每对xi之间的象素填上所要求的颜色。 (4) 如果AET表中某记录的ymax=yj，则删除该记录。 (5) 对于仍留在AET表中的每个记录，用xi+1/m代替xi进行修改，这就是该记录的边线与下一条扫描线yj+1的交点。 (6) 使yj加1，以便进入下一轮循环。,三、边相关扫描线填充算法举例 对下图(a)的多边形利用边相关扫描线填充算法进行处理： 1、首先建立ET表。 注意：在做奇异点处理时，当该边最大y值对应的顶点为非极值点时，边记录的第一项：ymax=ymax-
8、1。例如：P3P4边、P3P2边、P4P5边，见下图(b)。 2、接着建立AET表。AET表的建立过程就是有效地进行填充的操作，在这个期间不断地做以下工作：,(a) 多边形 (b) ET表 (c) AET表,1）合并ET表；2）x递增排序； 3）实施填充；4）删除ymaxyj的边； 5）修改边记录xi=xi+1/m；6）yj+1进入下一轮循环。,四、边相关扫描线填充算法实现 1、根据给定的多边形顶点坐标，建立ET 表。 2、AET表初始化，每个桶置空。 3、for(y=ymin;y= ymax;y+) 合并当前扫描线y的ET表； 将y桶中每个记录按x项升序排列； 在当前y值下，将两两记录的x值
9、之间的象素进行填充； 删除y=ymax的边记录； 修改边记录x=x+1/m； ,五、边相关扫描线填充算法特点 该算法充分利用多边形的边相关性和扫描线的相关性，使用ET表对多边形的非水平边进行登记；用AET表的建立和更新来支持填充，大大地减少了求交点的计算量，有效地提高了填充速度。,练习： 用边相关扫描线填充算法，对图中多边形建立ET、AET表。,作业：,用边相关扫描线填充算法做出图中多边形的ET表和AET表。,二、种子填充 种子填充是将区域内的一点(种子)赋予给定的颜色，然后将这种颜色扩展到整个区域内的过程。 1、填充条件 区域内一点的坐标即种子坐标、边界色、填充色。 2、连通方式 区域是互相
10、连通着的象素的集合，连通方式可分为四连通和八连通。,四连通：从区域内一点出发，可通过四个方向：上、下、左、右到达该区域内部的任意象素。 八连通：区域内部从一个象素到达另一个象素的移动路径，除了上、下、左、右四个方向外，还允许沿着对角线方向。,注意：（1） 八连通区域中，既然区域内的两个象素可以通过对角线相通，那么，区域边界上的象素则不能通过对角线相连，否则填充就会溢出到区域外，因此，八连通区域的边界线必须是四连通的，见下图(a)；（2）而四连通区域，其边界象素是四连通和八连通的都可以，见下图(b)。,(a) 八连通区域四连通边界 (b) 四连通区域八连通(或四连通)边界,3、内点(x,y)的检测条件 (1) if(getpixel(x,y)!=边界色 & getpixel(x,y)!=填充色) (2) if(getpixel(x,y)!=背景色) 这两个条件任何一个都可以用来检测象素点(x,y)是不是尚未填充。推荐使用条件(1)进行象素点检测。,