计算机图形学 区域填充

1、1. 有关概念2. 逐点判断填充算法3. 种子填充算法4. 区域填充图案5. 扫描线多边形填充算法6. 边填充算法1. 1. 有关概念有关概念 1) 区域：一组相邻而且又相连的像素，而且具有相同属性的封闭区域。 3) 区域填充：以某种属性对整个区域进行设置的过程。 2）种类：单域 复合域 4）区域的建立（定义）方式： 内定区域：在所定义的区域内所有的像素具有相同的属性（如颜色等）。 （内部定义方式） 边界定义区域：以区域的内外属性来划分，区域内的像素和边界上的像素可具有不同的属性。 （外界定义方式） 5）连通性：分为四向连通和八向连通。 四连通：各像素在水平、垂直的上、下、左、右四个方向上是连

2、通的。 八连通：各像素在上、下、左、右以及四个对角线方向都是连通的。 2.逐点判断填充算法区域填充的基本(初级)方法:逐点判断填充算法逐点判断绘图窗口内的每一个像素；若在区域的内部：用指定的属性设置该点；否则不予处理；设有如下函数： 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;x i+1结点的x值递增D x； 若允许多边形的边自相交，则用冒泡排序法对AET表重新排序； /* polyfill */桶结构桶结构 用于存放按照一定的

3、规则（顺序）排列的若干组数据或处理对象。 通常情况下，桶采用向量形式和链表形式构造的一种数据结构。6 6边界标志算法边界标志算法 边界标志算法的基本思想是：在帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。对每条与多边形相交的扫描线依从左到右的顺序，逐个访问该扫描线上的象素。使用一个布尔量inside来指示当前点是否在多边形内的状态。Inside的初值为假，每当当前访问的象素为被打上边标志的点，就把inside取反。对未打标志的象素，inside不变。若访问当前象素时，inside为真，说明

4、该象素在多边形内，则把该象素置为填充颜色。1. 对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。2.填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。取一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。Inside 的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，inside不变。边界标志算法步骤边界标志算法:算法过程void edgemark_fill(polydefvoid edgemark_fill(polydef, color),

5、 color)多边形定义多边形定义 polydefpolydef； intint color; color; 对多边形对多边形polydefpolydef 每条边进行直线扫描转换；每条边进行直线扫描转换； inside = FALSE;inside = FALSE; for ( for (每条与多边形每条与多边形polydefpolydef相交的扫描线相交的扫描线y )y ) for ( for (扫描线上每个象素扫描线上每个象素x )x ) if( if(象素象素 x x 被打上边标志被打上边标志) ) inside = ! (inside); inside = ! (inside); if

6、(inside if(inside！= FALSE)= FALSE) drawpixel drawpixel (x, y, color); (x, y, color); else drawpixel else drawpixel (x, y, background); (x, y, background); 边界标志算法：void edgemark_fill(polydef, color)多边形定义 polydef； int color; 对多边形polydef 每条边进行直线扫描转换； inside = FALSE; for (每条与多边形polydef相交的扫描线y ) for (扫描线上

7、每个象素x ) if(象素 x 被打上边标志)inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); 用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。* * 边缘填充算法边缘填充算法( (正负相消法正负相消法) )基本思想： 对于每条边上的每一点都将所在扫描线上其右方的所有象素的颜色取补。 算法简单，但对于复杂图

8、型，每一象素可能被访问多次。边缘填充算法求余运算求余运算：假定A为一个正整数，则M的余定义为A M, 记为 。计算机中取A为n位能表示的最大整数。即，A=0 xFFFFFFFFA=0 xFFFFFFFF由来由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。算法基本思想算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。MM1、将当前扫描线上的 所有象素着上 颜色；2、求余：for(i = 0;i = m; i+)在当前扫描线上， 从

9、横坐标为Xi的交 点向右求余； M算法1（以扫描线为中心的边缘填充算法）1、将绘图窗口的背景色置为 ；2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余；M算法2（以边为中心的边缘填充算法）算法2（以边为中心的边缘填充算法）边缘填充算法 适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。 优点：算法简单 缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比有序边表算法大得多。 引入栅栏，以减少填充算法访问象素的次数。 栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。 基本思想：扫描线与多边形的边求交，将交点与栅栏之间的象素取补。 减少了象素重复访问数目，但不彻底。栅栏填充算法边界标志算法特点 用软件实现时，扫描线算法与