计算机图形学论文题目：边缘填充算法思想与改进
院（系）
专业计算机系
班级
学号
姓名
指导老师
摘要
计算机图形学边缘填充算法的基本思想是，逐边向右取补。
它适用于具有帧缓冲区的图形系统。
边缘填充算法包括传统的边缘填充算法﹑栅栏填充算法和打标志算法。
本文通过对边缘填充算法的描述引出栅栏填充算法的改进，通过改进栅栏的选择来。
边缘填充是一类多边形扫描转换算法, 算法思路清晰, 结构简单。
算法的一个不足是对复杂图形的每一象素都要进行多次I/O操作, 影响算法的效率。
本文对此作了改进,给出的改进算法对象素的访问次数较少, 因而有较高的效率。
关键词（宋体小三号）：计算机图形学；边缘填充算法；栅栏填充算法；改进。
目录
摘要 (1)
引言 (3)
一、算法原理 (4)
二、适用领域 (4)
三、算法种类 (4)
四、算法程序节选 (4)
五、算法改进 (6)
结语 (7)
参考文献 (8)
引言
近年来, 随着计算机技术的迅速发展及图形设备价格的下降, 光栅图形技术发展很快, 它的应用领域不断扩大, 并己成为计算机图形学的一个重要分支。
边缘填充算法采用求余的方法, 免去了有序边表算法中对边排序的工作量, 而改用求余运算代替。
其特点为可以按任意顺序处理多边形的边。
算法的主要不足之处在于, 对于较复杂的图形每一象素可能被访问多次, 因此这一算法受到输入=输出条件的限制。
栅栏填充算法要比边缘填充算法访问象素的次数减少。
本文最后给出的栅栏填充改进算法在传统的栅栏填充算法思想上，改进了栅栏的选取，通过过多边形两个顶点的连线作为栅栏线，然后去各个边到栅栏的投影取补，循环一周形成填充效果。
（宋体小四号，字号、行距均同正文）
一．算法原理
边缘填充算法的基本思想是，逐边向右取补。
可以按任意顺序处理多边形的每条边。
在处理每条边时，首先求出该边与扫描线的交点，然后将每一条扫描线上交点右方的所有像素取补。
多边形的所有边处理完毕后，填填充即完成。
二．适用领域
边缘填充算法适用于具有帧缓冲区的图形系统。
因为在处理每条边时，仅访问与该边相交的扫描线上交点的右方的像素。
当处理完所有的边之后，按扫描线顺序读出帧缓冲存储器的内容，送入显示设备。
三．算法种类
边缘填充算法包括传统的边缘填充算法﹑栅栏填充算法和打标志算法。
1．边缘填充算法
如上文所述标准的算法
2．栅栏填充算法
为了减少边缘填充算法访问像素的次数，采用了栅栏填充算法。
这里栅
栏是指一条过多边形顶点且与扫描线垂直的直线，它把多边形分成两半。
该算法的基本思想是，逐边向栅栏取补。
同样按任意顺序处理多边形的
每条边，但在处理每条边与扫描线的交点时，将交点与栅栏之间的像素
取补。
3．打标志算法
打标志算法的思想是，先用一种特殊的颜色在帧缓冲存储器中将多边形
的边界勾画出来，然后将着色的像素点依x坐标递增的顺序两两配对，
再将对每一对像素所构成的扫描线区间内的所有像素置为填充色。
打标
志算法对每个像素仅访问一次。
四．算法程序节选
以C++语言为例节选出填充函数的程序
void CTestView::Draw() //填充多边形{
COLORREF CBackColor=RGB(255,255,255); //白色
CClientDC dc(this);
int m,n,ymin,ymax;
double x,y,k;
for(int i=0;i<=6;i++) //对于多边形所有边循环{
m=i,n=i+1; //对点的循环
if(7==n) n=0;
k=(double(Point[m].x-Point[n].x))/(Point[m].y-Point[n].y);
//计算1/k if(Point[m].y<Point[n].y)
//得到每条边的y最大和y最小值{
ymin=Point[m].y;
ymax=Point[n].y;
x=Point[m].x; //得到x|ymin }
else
{
ymin=Point[n].y;
ymax=Point[m].y;
x=Point[n].x;
}
for(y=ymin;y<ymax;y++) //对每一条边循环{
for(int j=ROUND(x);j<MaxX;j++)
//对每一条扫描线与边的交点的右侧像素循环{
if(dc.GetPixel(j,ROUND(y))==FillColor)
//如果像素的颜色是填充色
{
dc.SetPixel(j,ROUND(y),CBackColor);
//改为背景色
}
else
{
dc.SetPixel(j,ROUND(y),FillColor);
//使用填充色填充
}
}
x+=k; //计算下一个x起点值}
}
}
五．算法改进
1．改进思想。
栅栏填充算法的改进。
在已知图像区域坐标的情况下，任意取两个多边形的顶点连线作为栅栏，通过两点坐标可以计算出栅栏的直线函数，然后依次每条边对栅栏的投影取补。
2．过程图
（1）（2）（3）（4）
（5）（6）（7）（8）
3.算法实现过程
确立坐标系内一个多边形，过多边形任意两点(最好是不相邻)A、B。
由已知的两点坐标建立栅栏线，通过计算可知直线函数y=ax+b。
然后依次取每一
条边到栅栏的投影，每次投影都对所经过的像素点取补，经过一周即可形成填充图形。
结语
结果表明，使用改进过的栅栏填充算法，比传统的栅栏填充算法和边缘填充算法对每个像素点的访问都少。
在同一多边形中，使用改进的栅栏填充算法对像素的访问比其他栅栏填充算法都少。
参考文献
1. 陆风，何云峰.计算机图形学基础(第二版).电子工业出版社，2010.
2.张英慧，张玉连.一种改进的边缘填充算法.燕山大学学报，2000.
3. 百度文库.网址略.。