当前位置:
文档之家› 第2章 基本图形的生成与计算_区域填充算法_new
第2章 基本图形的生成与计算_区域填充算法_new
动画演示
扫描线种子填充算法特点
1. 该算法考虑了扫描线上象素的相关性,种子象 素不再代表一个孤立的象素,而是代表一个尚 未填充的区段。 2. 进栈时,只将每个区段选一个象素进栈(每个 区段最右边或最左边的象素),这样解决了堆 栈溢出的问题。 3. 种子出栈时,则填充整个区段。 4. 这样有机的结合:一边对尚未填充象素的登记 (象素进栈),一边进行填充(象素出栈), 既可以节省堆栈空间,又可以实施快速填充。
计算机图形学讲义
第2章 基本图形的生成与计算
—区域填充算法
dx rx dt
黄可坤
嘉应学院
主要内容
1. 逐点判断填充算法 2. 种子填充算法
2.1 深度递归的种子填充算法 2.2 扫描线种子填充算法
3. 扫描线多边形填充算法
1.逐点判断填充算法
区域填充的基本(初级)方法:逐点判断填充算法
– 逐点判断绘图窗口内的每一个像素;
3.扫描线多边形填充算法
扫描线多边形区域填充算法是按扫描线顺序,计 算扫描线与多边形的相交区间,再用要求的颜色显 示这些区间的象素,即完成填充工作。 区间的端点可以通过计算扫描线与多边形边界 线的交点获得。 对于一条扫描线,多边形的填充过程可以分为 四个步骤: (1)求交:计算扫描线与多边形各边的交点; (2)排序:把所有交点按x值递增顺序排序; (3)配对:第一个与第二个,第三个与第四个等 等;每对交点代表扫描线与多边形的一个相交区间; (4)填色:把相交区间内的象素置成多边形颜色;
考察象素与区域的关系,使得几十万甚至几百万个象 素都要一一判别,每次判别又要多次求交点,需要做 大量的乘除运算,花费很多时间。
如何判断点在多边形的内或 外?即包含性检查。
具体计算方法如何? 图形求交中再仔细讲解。
Hale Waihona Puke 2.种子填充算法种子填充算法假设在多边形内有一象 素已知,由此出发利用连通性找到区域内 的所有象素,并进行填充。
扫描线种子填充算法的具体步骤
① 初始化:堆栈置空。将种子点(x,y)入 栈。 ② 出栈:若栈空则结束。否则取栈顶元素(x, y),以y作为当前扫描线。 ③ 填充并确定种子点所在区段:从种子点(x, y)出发,沿当前扫描线向左、右两个方向 填充,直到非内部。分别标记区段的左、 右端点坐标为xl和xr。 ④ 并确定新的种子点:在区间[xl,xr]中检 查与当前扫描线y上、下相邻的两条扫描线 上的象素。若存在非边界、未填充的象素, 则把每一区间的最右象素作为种子点压入 堆栈,返回第(2)步。
3、内点(x,y)的检测条件
– (1) if(getpixel(x,y)!=边界色 &&
getpixel(x,y)!=填充色) – (2) if(getpixel(x,y)!=背景色)
这两个条件任何一个都可以用来检
测象素点(x,y)是不是尚未填充。推 荐使用条件(1)进行象素点检测。
注意: (1) 八连通区域中,既然区域内的两个象素可以通 过对角线相通,那么,区域边界上的象素则不能通过 对角线相连,否则填充就会溢出到区域外,因此,八 连通区域的边界线必须是四连通的,见下图(a); (2)而四连通区域,其边界象素是四连通和八连通的 都可以,见下图(b)。
深度递归的种子填色算法的优缺点 种子填充的递归算法原理和程序都很简单, 容易理解。 但由于多次递归,费时、费内存,效率不高。 太大的区域会由于递归太深而不能运行。虽 然也可利用栈非递归实现,但也有同样的问 题。 可以考虑利用队列进行广度优先填色,但是 也是逐点判断,而且要重复判断一个点很多 次,效率也不高。 为了减少递归次数,提高效率可以采用采用 扫描线种子算法。
1. 填充条件
区域内一点的坐标即种子坐标、边界色、填充色。
2. 连通方式
区域是互相连通着的象素的集合,连通方式可分 为四连通和八连通。 四连通:从区域内一点出发,可通过四个方向: 上、下、左、右到达该区域内部的任意象素。 八连通:区域内部从一个象素到达另一个象素的 移动路径,除了上、下、左、右四个方向外,还 允许沿着对角线方向。
建立或调整AET(ActiveEdgeList);
按照AET中的接点顺序填充;
void polyfill (多边形 polygon, 颜色 color) { for (各条扫描线i ) { 初始化新边表头指针NET [i];把ymin = i 的边放进边表NET [i]; } y = 最低扫描线号; 初始化活性边表AET为空; for (各条扫描线i ) { 把新边表NET[i]中的边结点用插入排序法插入AET表,使 之按x坐标递增顺序排列; 遍历AET表,把y max= i 的结点从AET表中删除,并把y max > i结点的x值递增D x; 若允许多边形的边自相交,则用冒泡排序法对AET表重新 排序; 遍历AET表,把配对交点区间(左闭右开)上的象素(x, y), 用drawpixel (x, y, color) 改写象素颜色值; } } /* polyfill */
3. 已知有一个5边形如下。建立新边表 NET,并写出每一条扫描线经过时活性边 表AET中的数据状态。
2.2 扫描线种子填充算法
算法的基本过程如下:当给定种子点(x,y) 时,首先填充种子点所在扫描线上的位于给 定区域的一个区段,然后确定与这一区段相 连通的上、下两条扫描线上位于给定区域内 的区段,确定新种子点,并依次保存下来。 反复这个过程,直到填充结束。 上述算法对于每一个待填充区段,只需压栈 一次;而在递归算法中,每个象素都需要压 栈。因此,扫描线填充算法提高了区域填充 的效率。
动画演示
扫描线多边形填充算法的特点
该算法充分利用多边形的边相关性
和扫描线的相关性,使用ET表对多 边形的非水平边进行登记; 用AET表的建立和更新来支持填充, 大大地减少了求交点的计算量,有 效地提高了填充速度。
作业
1. 当用深度递归的种子填色算法并选用编号为6 的点作为种子填充如图所示区域时,写出区 域内被填色的点先后顺序。其中采用四连通 算法,填色顺序为右左上下。 2. 当用扫描线种子填色算法并选用编号为6的点 作为种子填充如图所示区域时,写出区域内 被填色的点先后顺序。算法步骤见2.2。
2.1 深度递归的种子填充算法
2.2 扫描线种子填充算法
2.1 深度递归的种子填充算法
种子填色又称边界填色(Boundary Filling)。 它的功能是,给出多边形光栅化后的边界位置及边 界色代码oundary_color,以及多边形内的一点(x, y)位置,要求将颜色fill_color填满多边形。
重合点的处理: 当扫描线和边界相交于左顶点或右顶点时,同时产生 两个交点,通常采用 “起闭终开”或“起开终闭” 。 P4 P3 [P4,P5) [P2,p3) P2
P5 [P5,p1)
P1
[P1,p2)
水平边处理 水平边不参加求交计算,跳过。
把与当前扫描线相交的边称为活性边, 并把它们按与扫描线交点x坐标递增的顺序 存放在一个链表中,称此链表为活性边表 (AET)。 活性边表的每个节点的内容:
扫描线6的活性边表AET
扫描线7的活性边表AET
为了方便活性边表的建立与更新,我们为每一条扫 描线建立一个新边表(NET),存放在该扫描线第一 次出现的边。也就是说, 若某边的较低端点为ymin, 则该边就放在扫描线ymin 的新边表中。
扫描线多边形填充算法的主要步骤 建立NET(NewEdgeList) 从最低扫描线开始到最高扫描线循环:
X ΔX Ymax
第1项存当前扫描线与边的交点坐标x值; 第2项存从当前扫描线到下一条扫描线间x的增量Dx; 第3项存该边所交的最高扫描线号ymax; 第4项存指向下一条边的指针。
假定当前扫描线与多边形某一条边的交点的x 坐标为x,则下一条扫描线与该边的交点不要重计 算,只要加一个增量△x。(连贯性) 设该边的直线方程为:ax+by+c=0; 若y=yi,x=x i;则当y = y i+1时, x i+1=xi-b/a 其中ΔX= -b/a为常数, 另外使用增量法计算时,我们需要知道一条边 何时不再与下一条扫描线相交,以便及时把它从 活性边表中删除出去。
– 若在区域的内部:用指定的属性设置该点; – 否则不予处理;
设有如下函数: Inside(D,x,y)=
True when x D
D
False when x D
取矩形R(x1≤x≤x2,y1≤y≤y2),使R包围D, 则逐点判断填充算法如下:
for(y=y1;y<=y2;y++) for(x=x1;x<=x2;x++) if(inside(D,x,y)) drawpixel(x,y,color); 上述算法原理简单、实用,但效率低;效 率低的原因是没有考虑各象素之间的联系,孤立地
(a) 八连通区域四连通边界
(b) 四连通区域八连通(或四连通)边界
深度递归的种子填色算法
void seed_filling(x,y,fcolor,bcolor ) int x,y,fcolor,bcolor; { int c; c=getpixel(x,y); if(c!=fcolor&&c!=bcolor) { putpixel(x,y,fcolor); seed_filling(x+1,y,fcolor,bcolor); seed_filling(x-1,y,fcolor,bcolor); seed_filling(x,y+1,fcolor,bcolor); seed_filling(x,y-1,fcolor,bcolor); } }