几种直线画法的比较

几种画直线的方法比较

李琳（09号）

（唐山师范学院计算机科学系，河北省唐山市 063000）

摘要：直线是生成各种图形的基本元素,直线绘制是光栅图形学最基本的一个任务。直线扫描转换生成算法是计算机图形学、计算机辅助设计、科学计算可视化、虚拟现实、计算机动画等领域最基本、最重要的算法之一。

关键字：Bresenham，DDA

Comparison of several drawing a straight line

Li Lin

(School of Computer Science and Technology,Tangshan Normal College, Tangshan Hebei 063000,China)

Abstract：The line is the basic element in generating graphics. So line drawing is a fundamental task for raster graphics. The line scan conversion generating algorithm is a very important and fundamenatal algorithm in Computer Graphics (CG) and Computer Aided Design (CAD), Visualization in Scientific Computing (VISC), Virtual Reality and Computer Animation.

Keywords: Bresenham，DDA

直线是生成各种图形的基本元素,直线绘制是光栅图形学最基本的一个任务。直线扫描转换生成算法是计算机图形学、计算机辅助设计、科学计算可视化、虚拟现实、计算机动画等领域最基本、最重要的算法之一。直线生成算法的好坏直接影响图形生成与显示的效率。因此,提高和加速传统直线绘制算法具有重要的实际意义。本文简单介绍几种直线的画法和它们之间的比较。

1. Bresenham算法

Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。仍然假定直线斜率在0~1之间，该方法类似于中点法，由一个误差项符号决定下一个象素点。算法原理如下：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求象素。如设直线方程为yi+1=yi+k(xi+1-xi)+k。假设列坐标象素已经确定为xi，其行坐标为yi。那么下一个象素的列坐标为xi＋1，而行坐标要么为yi，要么递增1为yi＋1。是否增1取决于误差项d的值。误差项d的初值d0＝0，x坐标每增加1，d的值相应递增直线的斜率值k，即d＝d＋k。一旦 d≥1，就把它减去1，这样保证d在0、1之间。当d≥0.5时，直线与垂线x=xi＋1交点最接近于当前象素(xi，yi)的右上方象素(xi＋1，yi＋1)；而当d<0.5时，更接近于右方象素(xi＋1，yi)。为方便计算，令e＝d－0.5，e的初值为－0.5，增量为k。当e≥0时，取当前象素(xi，yi)的右上方象素(xi＋1，yi＋1)；而当e<0时，取(xi，yi)右方象素(xi＋1，yi)。 Bresenham画线算法程序：

void Bresenhamline (int x0,int y0,int x1, int y1,int color) { int x, y, dx, dy；

float k, e;

dx = x1-x0；dy = y1- y0；k=dy/dx； e=-0.5； x=x0,；y=y0； for (i=0；i上述Bresenham算法在计算直线斜率与误差项时用到小数与除法。可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：2*e*dx。 2. DDA算法

DDA称为数值微分画线算法，是直线生成算法中最简单的一种。原理相当简单，就是最直观的根据斜率的偏移程度，决定是以x为步进方向还是以y为步进方向。然后在相应的步进方向上，步进变量每次增加一个像素，而另一个相关坐标变量则为Yk_1=Yk+m（以x为步进变量为例，m为斜率）。 DDA画线算法程序：

void DDALine(float x1,float y1,float x2,float y2,int color,HDC hdc) {

float m; float dx,dy; float x,y; x1=(int)(x1+0.5); y1=(int)(y1+0.5); x=x1; y=y1; dx=x2-x1; dy=y2-y1; if(fabs(dx)>=fabs(dy)) m=dy/dx; else m=dx/dy; while(x<=x2) {

SetPixel(hdc,x,y,color); if(fabs(dx)>=dy)

{ y=y+m; x++; } else

{ x=x+m; y++; }

} }

3. 对称式八步增量算法

在分析直线生成模式与直线斜率之间的关系的基础上,提出了一种对称式八步增量算法。该算法一次能画四个象素,结合直线的对称性,在一次循环中可以画八个象素。该算法只用到了整数加法运算、减法运算和左移位运算,大大降低了硬件实现的复杂度,同时有效地提高了速度,易于硬件实现。与Bresenham算法相比,平均每点判断次数只相当于Bresenham算法的30%,平均迭代次数相当于Bresenham算法的25%。

此外还有四步画直线算法，五步直线扫描转换生成算法，六步直线生成算法等算法。其中Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法，DDA算法是直线生成算法中最简单的一种，直线绘制速度最快的是对称式八步增量算法。 参考文献：

1. 作者欧阳开翠,曾令华,谭渊,白宝钢，期刊计算机科学COMPUTER SCIENCE 2008年第

03期。

2. 王朝网络www.wangchao.net.com 3. 程序员开发网www.pudn.com