直线算法综述.doc

《直线算法综述.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、南昌大学学生姓名：陈凯学号：405906111033学院：机电工程学院专业：机械设计及理论论文题目：直线生成算法文献综述2012年9月14口直线生成算法综述陈凯(南昌大学机电工程学院江西南昌330031)摘要：本文对现有的直线生成算法进行综述，介绍了各种算法的原理、优缺点、算法基础等。详细说明了基于并行填充模式的直线生成算法，并以此为例子比较了其与Bresenham算法的效率和误差大小，综述了各种算法的适用条件。关键字：直线算法并行填充模式Bresenham算法引言直线是光栅图形学屮最基木的元索之一，直线生成算法的效率和质量直接影响着图形应用系统的效率和质量。直到最近

2、儿年，为了提高直线的绘制速度,仍然有大量的研究工作出现。这些工作集屮在如何一次生成位于直线上尽可能多的像素，在计算机屮生成直线的常用算法有数值微分法(DDA)Jp点画线法和1965年出现的Bresenham算法。其,

3、,Bresenham算法是依据有线的斜率，快速生成直线,这种算法在直线段接近坐标的吋候有很高的效率，但是随着斜率的增大，其效率会显著下降。以上所说的各种直线生成算法的特点都是一次生成尽可能的像素的数H。但是，若增加每次生成像素的数量，则会由于pattern数量过多，造成对误差值判断操作次数增加，致使直线生成的效率反而会下降。因此本文查看了大量的文献，找出

4、了牛成直线的其余常用算法，对常用的直线牛成算法进行综述，并评价其各口的优缺点。正文1、对称式八步直线生成算法由Bresenham直线生成算法的基木思想可知，牛成的下一个像索与半前像素0间存在两种关系沿轴向或沿斜向。如当前像素点为P,则下一个像素点只能选择轴向或者斜向的下一个邻近像素点。若使用4个像素的生成模式來生成直线，即半沪4吋，可以将直线依据其斜率划分为六类，那么通过研究可供选择的生成模式集，每--种被选取的生成模式与这些直线的斜率范围的关系我们发现，直线的斜率不同，其可选模式构成的模式集也不同；每类直线可供选择的生成模式集屮均包含五种生成模式；直线的斜率决定了生

5、成该直线时可供选择的生成模式集。而从生成模式集小具体选择哪一个生成模式⑴，则要由误差的大小來判定。由于线段具有屮点对称性，半我们使用4像素牛成模式来生成直线时，结合直线的屮点对称性，分别从线段的两端沿直线向屮点方向对称生成直线，一次计算即可生成八个像素点，从而可以极大地提高直线生成算法的效率。这就是对称式八步直线生成算法的基本原理。2、基于并行填充模式的直线生成算法通过分析发现，对于一般斜率不为1的直线，在每个象索行上通常有若干个象素点，而且毎个象素行上重复的象素点数基本相同，具有一定的规律。此若干个象素点可预先计算出来，并一次写入帧缓冲区小同吋点亮。H前的图形存储器

6、芯片都支持块写方式，如果能并行的一次写入一个循环单位的象素点数，就可人人提高图形的生成速度，同时算法本身的复杂度降低。因此就可以将算法的注意力由单个的象索点的计算、估测转移到象索点重复个数即Pattern的计算。半直线斜率较小时，此吋一次并行写入并且点亮的象素点数很多，直线生成的速度将显著提高。设直线斜率m=—,先考虑水1的情况⑵。直线沿x轴方向的增量dx=—,dxm由于沿y轴方向的单位长度增量为1,所以dy=l,则dx二丄，此吋的dx即为m直线在y轴单位长度上沿x轴方向的增量，设Pattern为每行的象素点数，那么116rn——om当丄恰为整数时，Pattern是一

7、个固定的单一的值，即每行重复的象素点数tn相同。当丄不为整数吋,Pattern应取接近丄的整数值，或为［丄］小于丄的整数,mmmm或为［丄］+1大于丄的整数。直线与若干象素行相交，则这些象素行上按mmBresenham算法被点亮的象素数H或者相等或者相差1。此时每行重复的Pattern虽值不相同，但具有一定的基本规律。基于这种思想，我们考虑将每行点亮若干象素后的剩余长度作为偏差e。设第j步计算偏差在第j行被点亮的象素区域的右端点处进行，我们定义第j步的偏差勺・为按步长k点亮了k个象素后最后被点亮的象素距该行象素区域的右端点的距离。因为每相邻行丄被点亮的象素区域恰好是首

8、尾相接的，所以第j行象素区域左端点距离该行上第一个被点亮的象素点的距离为1-勺_（勺一为第j-1行的偏差）。则有：£二丄-（k-1）一（1-勺“）。根据上面的思想,若e.>1,m则在右端继续点亮一个象素，同时偏差减1,勺二勺由于起始行被点亮的象素区域的长度为丄，该行丄点亮了k个象素后，其偏差为：勺=—-（k-1）o由Im2m此我们可得到偏差e的递推算法。这样我们在每个象素行仅需进行一次偏差计算。对于斜率Q1的情况，仅需把x和y的地位交换来处理，其算法思想是一样的，这就是基于并行填充模式的直线生成算法。3、基于对称的反走样直线生成算法空间连续的图形经转