计算机图形学——生成直线的DDA算法

古城微笑少年丶 2022-06-13 12:45 389阅读 0赞

本博客计算机图形学系列文章索引：

地址：[《计算机图形学系列相关文章索引（持续更新）》][Link 1]

数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法。

一、直线DDA算法描述：

设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得

<table> 
 <tbody> 
  <tr> 
   <td>dy/dx<br> =(y2-y1)/(x2-x1)<br> =△y/△x</td> 
   <td><span style="font-size:18px">= m =直线的斜率</span></td> 
   <td align="right"><span style="font-size:18px">(2－1)</span></td> 
  </tr> 
 </tbody> 
</table>

可通过计算由x方向的增量△x引起y的改变来生成直线：

也可通过计算由y方向的增量△y引起x的改变来生成直线：

式(2－2)至(2－5)是递推的。

二、直线DDA算法思想：

选定x2－x1和y2－y1中较大者作为步进方向(假设x2－x1较大)，取该方向上的增量为一个象素单位(△x=1)，然后利用式(2－1)计算另一个方向的增量(△y=△x·m=m)。通过递推公式(2－2)至(2－5)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。

之所以取x2－x1和y2－y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。

另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。

![1335945498_2346.png][]

三、直线DDA算法实现：

1、已知直线的两端点坐标：(x1，y1)，(x2，y2)  
　　2、已知画线的颜色：color  
　　3、计算两个方向的变化量：dx=x2－x1  
　　　　　　　　　　　　　　 dy=y2－y1  
　　4、求出两个方向最大变化量的绝对值：  
　　　　　　　　　　　　　　 steps=max(|dx|，|dy|)  
　　5、计算两个方向的增量(考虑了生成方向)：  
　　　　　　　　　　　　　　 xin=dx/steps  
　　　　　　　　　　　　　　 yin=dy/steps  
　　6、设置初始象素坐标：x=x1,y=y1  
　　7、用循环实现直线的绘制：  
　　　　for(i=1；i<=steps；i++)  
　　　　\{

putpixel(x，y，color)；/\*在(x，y)处，以color色画点\*/  
　　　　　x=x+xin；  
　　　　　y=y+yin；  
　　　　\}

四、直线DDA算法演示：

使用swf文件演示，演示文件放在我的网盘上了。

地址为：[http://www.kuaipan.com.cn/file/id\_14024936532213950.htm][http_www.kuaipan.com.cn_file_id_14024936532213950.htm]

五、直线DDA算法特点：

该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。

[Link 1]: http://blog.csdn.net/zhangkaihang/article/details/7529327
[1335945498_2346.png]: https://img-my.csdn.net/uploads/201205/02/1335945498_2346.png
[http_www.kuaipan.com.cn_file_id_14024936532213950.htm]: http://www.kuaipan.com.cn/file/id_14024936532213950.htm