人机交互论文——基于扫描线区域填充算法.doc

贵州师范大学
研究生作业（论文）专用封面
作业（论文）题目： 基于扫描线的区域填充算法

课程名称：人机交互与界面设计
任课教师姓名： 刘彬
研究生姓名： 张宝健
学 号： 4201010600351
年 级： 10级研
专 业： 计算机应用技术
学院（部、所）： 数计学院
任课教师评分：

评阅意见：

任课教师签名：
年 月 日
基于扫描线的区域填充算法
数学与计算机科学学院 张宝健(4201010600351)

[摘要] ：图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。从处理技术上来看，图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图，也就是通常所说的真实感图形。计算机图形学一个主要的目的就是要利用计算机产生令人赏心悦目的真实感图形。为此，必须建立图形所描述的场景的几何表示，再用某种光照模型，计算在假想的光源、纹理、材质属性下的光照明效果。
[关键词] ：计算机图形学、区域填充、扫描线算法
第一章 绪论
1.1研究的背景
在计算机中重现真实世界的场景叫做真实感绘制。真实感绘制的主要任务是模拟真实物体的物理属性，简单的说就是物体的形状、光学性质、表面的纹理和粗糙程度，以及物体间的相对位置、遮挡关系等等。实时的真实感绘制已经成为当前真实感绘制的研究热点，而当前真实感图形实时绘制的两个热点问题则是物体网格模型的面片简化和基于图象的绘制（IBR Image Based Rendering）。网格模型的面片简化，就是指对网格面片表示的模型，在一定误差的精度范围内，删除点、边、面，从而简化所绘制场景的复杂层度，加快图形绘制速度。IBR完全摒弃传统的先建模，然后确定光源的绘制的方法。它直接从一系列已知的图象中生成未知视角的图象。这种方法省去了建立场景的几何模型和光照模型的过程，也不用进行如光线跟踪等极费时的计算。该方法尤其适用于野外极其复杂场景的生成和漫游。
1.2研究的主要内容及结构
主要任务是实现多边形区域扫描线填充的有序边表算法，设计相关的数据结构（如链表结构、结点结构等），并将实现的算法应用于任意多边形的填充，区域填充,指的是在输出平面的闭合区域内完整地填充某种颜色或图案。以下所述及的区域填充算法或相关程序,主要针对显示平面内的区域而言。
区域填充的问题一般分两大类,一是多边形填充；一是种子填充；种子填充在学生掌握了“栈”这一抽象数据类型的实现方法的前提下,比较容易完成。而边标志填充算法却是介于这两类之间,部分地具有它们的痕迹,算法思想巧妙,实现起来更容易。多边形填充有一定难度，我们主要对多边形的扫描线算法填充做一些探讨，具体将以五角星为实例。
第二章 理论综述
2.1 区域填充的理论知识
2.1.1 区域填充的概念
将区域的边界表示转换为区域内部象素表示的过程称为区域填充。区域填充是计算机图形学中的一个基本问题， 在计算机辅助设计、 真实感图形显示、 图像分析等领域有着广泛的应用。区域填充算法是指给出一个区域的边界，要求在边界范围内对所有像素单元赋予指定的颜色代码。目前，区域填充算法中最常用的是多边形填色，常用的多边形填色算法有两种： 一类是种子填充算法， 一类是扫描线填充算法。
研究如何用一种颜色或图案来填充一个二维区域。一般来说，区域的封闭轮廓是简单的多边形。若轮廓线由曲线构成，则可将曲线转换成多条直线段顺连而成，此时，区域轮廓线仍然是一种多边形逼近。
　　在计算机图形学中，多边形区域有两种重要的表示方法：顶点表示和点阵表示。所谓顶点表示，即是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少、易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于区域填充。所谓点阵表示，则是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于进行填充。
　　根据区域的定义，可以采用不同的填充算法，其中最具代表性的是：适用于顶点表示的扫描线类算法和适应于点阵表示的种子填充算法。
2.1.2 扫描线算法的描述
扫描线填充算法一般包括四个步骤：求交、排序、交点配对、区域填充。正确求得扫描线与区域填内外轮廓线的交点是算法成败的关键问题。另一方面，采用合适的数据结构又可以简化操作、提高算法的效率。本论文由于采用链表结构记录轮廓线和交点，无需焦点排序的过程，因而提高了算法效率。扫描线来源于光栅显示器的显示原理：对于屏幕上所有待显示像素的信息，将这些信息按从上到下、自左至右的方式显示。
扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为四个步骤：
（1）求交：计算扫描线与多边形各边的交点；
（2）排序：把所有交点按x值递增顺序排序；
（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;
（4）填色：把相交区间内的象素置成多边形颜色;
2.2 数据结构与算法
2.2.1 扫描线多边形填充算法的主要步骤
1.建立NET(NewEdgeList)
2.从最低扫描线开始到最高扫描线循环：
3.建立或调整AET(ActiveEdgeList)；
4.按照AET中的接点顺序填充。
扫描线填充算法的目标是减少递归层次。步骤是填充并确定种段；初始化：将种子区段压入堆栈；出栈：如果堆栈为空，则算法结束；否则取栈顶元素 (y, xLeft, xRight)，以纵坐标为 y 的扫描线为当前扫描线，[xLeft, yLeft]为搜索区间；填充并确定新的区段。
因此，扫描线多边形区域填充算法的基本原理是，待填充区域按y方向(x方向亦可)扫描线顺序扫描生成。具体实现时，首先按扫描线顺序，计算扫描线与多边形的相交区间；再用指定的颜色填充这些区间内的像素，即完成这一条扫描线的填充工作。区间的端点可以通过计算扫描线与多边形边界的交点获得。
为了提高效率，在处理每一条扫描线时，仅对与它相交的多边形的边进行求交运算。我们把当前扫描线相交的边称为活性边(active edge)，并把它们按扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。
　　为了提高速度，假定当前扫描线与多边形某一条边的交点的x坐标为xi，则下一条扫描线与该点的交点不需要重新计算，而是通过增加一个增量△x来获得。对于直线ax+by+c=0,△x=-b/a为常数。
　　另外使用增量法计算时，还需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表中删除出去。因此，活性边表结点的数据结构应保存如下内容：第1项保存当前扫描线与边的交点坐标x值；第2项保存从当前扫描线到下一条扫描线间x的增量△x；第3项保存该边所交的最高扫描线好ymax。第4项存指向下一条边的指针。
活性边表的每个节点的内容：
Ymax
Xmin
deltax

为了方便活性边表的建立与更新，可为每一条扫描线建立一个边表(ET)，存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的边表中。
边的分类表ET按照边的下端点y坐标对非水平边进行分类的指针数组活化边表AEL记录与当前扫描线相交的边（交点）
2.2.2边的算法:
typedef struct{
int ymax;
float x,delta;
struct Edge *nextEdge;
}Edge;
ymax:边的上端点y坐标
x:在AEL中表示当前扫描线与边的交点的x坐标，在ET中的初值为边的下端点的x坐标。
deltax:边的斜率的倒数
nextEdge:指向下一条边的指针。
具体步骤如下:
step1：把新边表NET［i］中的边结点，用插入排序法
插入活性边表AET，使之按X坐标递增顺序排序；
step2：遍历AET表，把配对交点之间的区间(左闭右开)上的各象
素(X，Y)，用drawpixel(x,y,color)改写象素颜色值；
step3：遍历AET表，把Ymax=i的结点从AET表中删除，并把
Ymax＞i的结果点的X值递增△X；
step4：重复各扫描线
2.2.3顶点交点的计数问题 :
扫描线与多边形顶点相交时，必须正确的进行交点个数计算，否则，在进行填充时会出现错误。扫描线与多边形相交的边分处扫描线的两侧，则计一个交点；扫描线与多边形相交的边分处扫描线同侧，且yi<y(i-1),yi<y(i+1)，则计2个交点，若yi>y(i-1),yi>y(i+1)，则计0个交点；扫描线与多边形边界重合，则计1个交点。
是否正确求取扫描线与多边形的交点是扫描线填充算法成败的关键。研究发现，求取扫描线与多边形的交点，既要利用边界点的局部信息，又要利用一条扫描线上所有交点的全部信息。因此，论文的求交过程包括以下三步：
第一步：遍历多边形的边一次，确定扫描线纵坐标的变化范围ymin 和ymax,建立一个空间的扫描线交点链表；
第二步：遍历多边形区域的边一次，根据每一边界点与前驱、后继之间的空间关系，初步求得各扫描线与边的交点；
第三步：对第二步中求得的交点进行修剪，得到正确的扫描线交点表。
当遍历完区域多边形轮廓线上的所有边界点之后，求交过程的第二步结束，此时的扫描线活动边表所记录得是各条扫描线与区域轮廓线的交点。但是，此时还不能保证各条扫描线上的交点的数目为偶数，因此不能直接用于配对，必须对各个扫描线的交点链表进行修剪。
求交点过程的第三步对每一条扫描线的交点链表进行修剪，其目的是删除那些由于出现“半交半切”的情况而多算的交点，以便实现正确的配对。假设待修剪的扫描线为y=i,修正的过程为：
1) 以扫描线y=i的交点链表上的第一个交点Pi,l点作为起点；
2) 如果起点为空，转5）结束；否则，按照从左到右的顺序遍历链表上的每一个点，如果遇到一个标号非零的交点Pf(设其标号值为lf),则从Pf的后继开始，寻找第二个标号非零的交点Ps,设其标号值为ls,此时：
如果lf与ls 符号相同，则转3）；
如果lf与ls符号相反，则转4）；
3) 将Pf和Ps从交点链表中删除，并以Ps 的后继作为起点，转2）；
4) 将Pf从交点链表中删除，令Ps的标号ls=0，并以Ps的后继作为起点，转2）；
5) 结束。
通过分析不难发现，对于任意多边形区域，经上述算法所求的每一条扫描线与多边形的交点数目为偶数，按照先后次序两两配对时，能确保交点之间的区域位于区域的内部。
描述扫描线与多边形交点的数据结构定义一为：
struct crosspoint{
int x;/*交点的横坐标*/
int y;/*交点的纵坐标*/
int l;/*交点的标记*/
crosspoint* pNextPoint;/*下一个交点*/
}
采用单链表的方式记录多边形上的所有与扫描线的交点坐标，下图所示。图中，E表示多边形的边，E，=1,2,…,n。由于多边形的外轮廓具有封闭性，所以链表的起点E和终点E也具有8-连通关系。对于链表中任意一个边界点E，定义E为E的前驱，E为E的后继。后面将会看到，前去和后继对于判断交点的属性是必不可少的。
把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。
AEL ： E1
En
E3
E2

2.3扫描线的算法步骤：
1） 分析多边形区域扫描线填充算法的原理，确定算法流程
① 初始化：构造边表ET，置AET表为空；
② 将第一个不空的ET表中的边插入AET表；
③ 由AET表取出交点进行配对（奇偶）获得填充区间，依次对这些填充区间着色；
④ y=yi+1时，根据x=xi+1/k修改AET表所有结点中交点的x坐标。同时如果相应的ET表不空，则将其中的结点插入AET表，形成新的AET表；
⑤ AET表不空，则转（3），否则结束。
2） 编程实现
① 首先确定多边形顶点和ET/AET表中结点的结构
② 编写链表相关操作（如链表结点插入、删除和排序等）
③ 根据1）中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体功能
④ 编写主函数，测试该算法
3）算法描述：
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.1用扫描线算法实现五角星填充
以（50,0），（60,30），（90,30），（70,45），（80,90），（50,60），（20,90），（30,45），（10,30），（40,30）这十个点作为五角星的十个点，利用扫描线算法将这个五角星进行填充。
3.2画五角星图形
(1)五角星图形
ｙ
９０　　　　　　　　　　　　　　ｐ８　　　　　　　　　　　　　　　　　　　　　ｐ６
８０　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　ｅ７　　　　　ｅ６　
７０
　　　　　　　　　　　　　　　　　　　　　　　　　　　ｐ７　　　　　　　　　　　　　　　　ｙ＝６０
６０　　　　　　　　　　　　　　　ｅ８　　　　　　　　　　　　　　　　　ｅ５

５０　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｙ＝４５　　
　　　　　　　　　　　　　　ｐ９　　　　　　　　　　　　　　　　　　　ｐ５　　　　　　　　　　　　　　　　　　　　

４０　　　　　　　　ｅ９　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｅ４
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｙ＝３０　
３０　　　　　　ｐ０　　　ｅ０　　　　　ｐ１　　　　　　　　　　ｐ３　　　ｅ３　　　　　ｐ４
２０　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　ｅ１ ｅ２ｅ２　　　　　　　　　　　ｙ＝１０
１０　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
０　　　　　１０　　　２０　　　３０　　　４０　　　５０　ｐ２　６０　　　７０　　　８０　　　　９０　　ｘ
图3.1 五角星图形
(2)五角星的边表

构造ET表算法描述如下：
void CreatET(Edge *et[],struct pointtype p[]) /*根据顶点数组构造ET表*/
{
int i,lasty,lastx,nextx,nexty,ymax,cy,cx;
Edge *pe;
for(i=0;i<EDGEMAX;i++){
cy=p[i].y;
cx=p[i].x;

/*确定上一点的坐标及下一点的坐标，考虑数组的首尾点。。。*/
if(0==i){
lasty=p[EDGEMAX-1].y;
lastx=p[EDGEMAX-1].x;
}
else{
lasty=p[i-1].y;
lastx=p[i-1].x;
}
if(EDGEMAX-1==i){
nexty=p[0].y;
nextx=p[0].x;
}
else{
nexty=p[i+1].y;
nextx=p[i+1].x;
}
五角星的边的分类表：
(3)相对应活化边表
（a）y=0对应的活化边表：

(b)y=3对应的活化边表 ：

（c）y=6对应的活化边表：

（4）描述边算法的数据结构定义为：
typedef struct{
int ymax;
float x,delta;
struct Edge *nextEdge;
}Edge;
void CreatET(Edge *et[],struct pointtype p[]); /*根据顶点数组构造ET表*/
void EdgeInAel(Edge *ael,Edge *edge); /*ET表中某边edge插入至AEL表中，并排序，x相同时用下一点x+delta判断*/
void EdgeOutAel(Edge *ael,int y); /*删除AEL中y=ymax的边，并同时修改每边的delta值*/
(5) 顶点交点的计数问题

（6）对AEL中的边两两配对，（1和2为一对，3和4为一对，……）
（7）如果ET中的第y类非空，则将其中的结点插入AET，形成新的AET表
（8）实现五角星主要算法：
void main()
{
int gd=DETECT,gm;
int i,y,ymax;
struct pointtype p[EDGEMAX]={{50,0},{60,30},{90,30},{70,45},{80,90},{50,60},{20,90},{30,45},{10,30},{40,30},{50,0}};
Edge *et[ETMAX]={0};
Edge *ael;
ael->nextEdge=NULL;
initgraph(&gd,&gm,"");

CreatET(et,p);
for(i=0;i<ETMAX;i++){
if(et[i]!=NULL){
y=i;
break;
}
}/*确定y的最小序号*/

ymax=p[0].y;
for(i=0;i<EDGEMAX;i++){
if(p[i].y>ymax){
ymax=p[i].y;
}
}/*确定ymax*/

while(y<=ymax){
EtInAel(et,ael,y);
EdgeDraw(ael,y);
y++;
EdgeOutAel(ael,y);
}
填充算法如下：
void EdgeDraw(Edge *ael,int y)
{
int counter=1; /*奇偶计数器*/
int color,maxcolor;
Edge *pmove;
float xlast,xcur;
int ylast,ycur;
maxcolor=getmaxcolor();
pmove=ael->nextEdge;
while(pmove!=NULL){
if(counter%2==1){
xlast=pmove->x;
}
else{ /*每两次边画线一次并重新赋值开始*/
xcur=pmove->x;
color=random(maxcolor);
setcolor(color);
line((int)xlast+1,y,(int)xcur,y);
xlast=0;
xcur=0;
}
counter++;
pmove=pmove->nextEdge;
}
}
算法运行结果如下：未填充颜色:

填充彩色如下：

结束：
这种方法省去了建立场景的几何模型和光照模型的过程，也不用进行如光线跟踪等极费时的计算。该方法尤其适用于野外极其复杂场景的生成和漫游。
参考文献：
[1]李桂清，李淘渊.扫描线种子填充的问题及改进[J].广西大学学报（自然科学版），1998；（9）：207～212
[2]余正生，马立庄，彭群生.任意区域的边界扫描线转换[J].工程图学学报，1999；（1）：72～77
[3]倪明田，吴良芝. 计算机图形学[M].北京大学出版社，2008.
致谢
感谢刘彬老师给我们耐心地讲解《人机交互与界面设计》，让我更加深刻认识和领悟这一领域的知识！

13