DDA算法

DDA算法，是計算機圖形學中一種基於直線的微分方程來生成直線的方法，由於有浮點數運算與取整，該算法不利於硬體實現。

基本介紹

• 中文名：DDA算法
• 外文名：DDA algorithm
• 全稱：Digital Differential Analyzer
• 別名：數值微分法

算法思想

直線的基本微分方程為： 。

設直線通過點 和 ，則直線方程可表示為： 。

如果已知第 點的坐標，可用步長 和 得到第 點的坐標為：

或

如下圖：

將算得的直線上每個點的當前坐標，按四捨五入得到光柵點的位置。

算法描述

DDA算法的C語言描述如下。當 時，實現代碼：

voidDDALine(intx0,inty0,intx1,inty1,intcolor){intx;floatdx,dy,y,k;dx=x1-x0,dy=y1-y0;k=dy/dx,y=y0;for(x=x0;x<=x1;x++){Drawpixel(x,int(y+0.5),color);y=y+k;}}

當 時，實現代碼：

voidDDALine(intx0,inty0,intx1,inty1,intcolor){inty;floatdx,dy,x,k;dx=x1-x0,dy=y1-y0;k=dx/dy,x=x0;for(y=y0;y<=y1;y++){Drawpixel(int(x+0.5),y,color);x=x+k;}}

任意斜率代碼實現如下：（注意自己補上，此處n做分母可能為0）

voidDDALine(intx0,inty0,intx1,inty1,intcolor){ intdx,dy,n,k;floatxinc,yinc,x,y;dx=x1-x0;dy=y1-y0;if(abs(dx)>abs(dy))n=abs(dx);elsen=abs(dy);xinc=(float)dx/n;yinc=(float)dy/n;x=(float)x0;y=(float)y0;for(k=1;k<=n;k++){Drawpixel(int(x+0.5),int(y+0.5),color);x+=xinc;y+=yinc;}}