改进的直线DDA算法

直线是生成各种图形的基本元素, 直线绘制算法也是图形学中最基本的算法, DDA算法和Bresenham算法就是是其中的两种最为经典的算法。传统的DDA算法是根据当前像素的位置经过简单的计算得出下一个像素的位置, 一次只能生成一个像素点。本文通过分析直线的扫描结果, 得出相邻像素点纵坐标小数的变化规律, 将直线分为多段, 一次输出一段上的像素点, 从而为某些直线提供了效率更高的算法。

1 改进DDA算法

设待绘制直线的起点为 (x0, y0) , 终点为 (x1, y1) , 直线方程为y=kx+b, 斜率0

DDA算法的原理是x以步长1从x0递增到x1, x为整数运算;y以斜率k为增量, 是浮点运算, 取 (x, [y+0.5]) 做绘制点 (其中[]表示取整) 。对相邻的两个像素点 (xi, [yi+0.5]) , (xi+1, [yi+1+0.5]) 当[yi+0.5]=[yi+1+0.5]时, 绘制时只需将 (xi, [yi+0.5]) 做水平移动即可;而[yi+0.5]和[yi+1+0.5]是否相等取决于yi+0.5的小数部分加k后是否超过1。

令d表示y+0.5的小数部分, 则有

显然0≤d<1

对于直线上的任意两个相邻像素点 (xi, [yi+0.5]) , (xi+1, [yi+1+0.5]) , 有

则必有di+1-di=k。

因此在区间[0, 1) 上, 小数部分d是以k为增量的单调递增序列;而k>0, 则d在经过一定次数的递增后必然会有d≥1, 此时只要令d=d-1, d必然会重新变成区间[0, 1) 上的实数。通过以上分析, 可以将直线划分为m段:L0, L1, L2…Lm-1;每一段上像素点的y+0.5的小数部分d都是区间[0, 1) 上的单调递增序列。

设段Li上有ni个像素点需要输出, [yi+0.5]是Li上第一个要输出的像素点, di为yi+0.5的小数, 则有

di+ (ni-1) ×k<1且di+ni×k>=1

因此只要绘制出小数为di时候的像素点然后通过水平移动即可得到多个像素点。

根据以上分析, 根据小数部分的变化规律将直线分为多段, 可以完成直线的分段输出。

例:绘制 (0, 0) (10, 2) 的直线

该直线的斜率为0.2

从表1中可看出, 根据小数的变化规律可将该直线分为3段分别绘制。

d有3个单调递增的序列, 分别是{0.5, 0.7, 0.9}, {0.1, 0.3, 0.5, 0.7, 0.9}, {0.1, 0.3, 0.5}。

则可将这11个像素点分成3段输出。

2 算法设计

根据上面的分析, 可写出算法:

4 效率分析

DDA算法效率分析:DDA算法每一个点的计算量有2次有2次浮点数的计算, 1次取整计算, 其他递增量计算及斜率的计算可忽略。

其中:TDDA表示计算n个点需要的时间, T f表示计算一次浮点数所用的时间, Tqz表示一次取整所用的时间;Tq表示计算每个点时的其他操作用时;TDDA2表示初识化的操作用时。

改进的DDA算法:每一段有1次整数加减运算, 1次浮点数加减运算, 1次比较运算;在计算每一点的时候, 有1次整数加减运算, 1次浮点数加减运算, 1次比较运算。

其中TGDDA表示改进的DDA算法的计算n个点需要的时间, TZ表示一次整数加减所用时间, Tf表示计算一次浮点数所用的时间, Tb表示一次比较所用的时间, △T1表示计算每段时的其他用时, △T2表示计算每一点时的其他用时, △TGDDA表示初识化的操作用时。

因此当忽略其他用时后得到时间随点数的变化示意图, (浮点加减用时2, 整数加减用时1, 取整用时1) 在总长度不超过100的前提下, 直线1为DDA算法绘制的。直线2, 3为用改进的DDA算法绘制的, 其中直线2为线段分为10段时, 直线3为线段分为15段时 (如图1) 。

5 结语

通过分析可以看出, 改进的DDA算法整体上明显比DDA算法的效率要高, 而且分的段数越少, 其算法的优越性就越明显

摘要：本文在传统的直线DDA生成算法的基础上, 提出了一种改进的DDA算法, 该算法利用直线上相邻各点纵坐标小数部分的变化规律, 将直线分为多段, 每次可以输出每段上的所有点;该算法克服了DDA算法每次只能输出一个点的缺陷, 从而提高整条直线扫描转换的速度。

关键词：DDA算法,小数,分段

参考文献

[1] 孙家广.计算机图形学 (第三版) [M].北京:清华大学出版社, 2000:166-167,

[2] 王晓云.多段DDA直线扫描算法[J].北京:微计算机信息, 2005, 21 (8) .