几种直线画法的比较

几种画直线的方法比较

李琳（09号）

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

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

关键字：Bresenham ，DDA

Comparison of several drawing a straight line

Li Lin

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

Bresenham 画线算法程序：

void Bresenhamline (intx0,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

{drawpixel (x,y, color);

x=x+1；e=e+k;

if (e 0)

{y++；e=e-1;}

}

}

上述Bresenham 算法在计算直线斜率与误差项时用到小数与除法。可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：2*e *dx 。

2. DDA 算法

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

DDA 画线算法程序：

void DDALine(floatx1,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;

dx=x2-x1;

else

while(x

{

SetPixel(hdc,x,y,color);

if(fabs(dx)>=dy)

{

else

{x=x+m;y++;}y=y+m;x++;}y=y1;dy=y2-y1;m=dy/dx;m=dx/dy;if(fabs(dx)>=fabs(dy))

}

}

3. 对称式八步增量算法

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

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

参考文献：

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

03期。

2. 王朝网络www.wangchao.net.com

3. 程序员开发网www.pudn.com