1. DDA Line Algorithm

Line Equation

The Cartesian slop-intercept equation for a straight line is

y=mx+b ------ (1)
with
m->slope
b->y intercept

The 2 end points of a line segment are specified at a position(x1,y1)

 

Determine the values for the slope m and y intercept b with the following calculation.

here, slope m:
 m = ( y2 - y1) / ( x2 - x1 )

m=Dy / Dx ------( 2 )

y intercept b
b=y1-mx1  ------( 3 )

Algorithms for displaying straight line based on this equation
y interval Dy from the equation  

Similarly x interval Dx from the equation

m = Dy / Dx
Dx =Dy /m------- ( 5 )

Line DDA Algorithm:

The digital differential analyzer(DDA) is a scan conversion line algorithm based on calculation eitherDyor Dx.The line at unit intervals is one coordinate and determine corresponding integer values nearest line for the other coordinate.

Consider first a line with positive slope.

Step : 1

If the slope is less than or equal to 1 ,the unit x intervals Dx=1 and compute each successive y values.

Dx=1

m =Dy / Dx
m = ( y2-y1 ) / 1
m = ( yk+1 - yk ) /1

yk+1= yk + m -------- ( 6 )

 

  • subscript k takes integer values starting from 1,for the first point and increment by 1 until the final end point is reached.
  • m->any real numbers between 0 and 1
  • Calculate y values must be rounded to the nearest integer

Step : 2

If the slope is greater than1 ,the roles of x any y at the unit y intervals Dy=1and compute each successive y values.

Dy=1

m= Dy / Dx
m= 1/ (x2-x1 )
m = 1 / ( xk+1 - xk)

xk+1 =xk +( 1 / m ) ------- ( 7 )
  • Equation 6 and Equation 7 that the lines are to be processed from left end point to the right end point.

Step : 3

If the processing is reversed, the starting point at the right

Dx=-1


m= Dy / Dx
m = ( y2 - y1 ) / -1
yk+1= yk - m  --------( 8 )
  • Iintervals Dy=1and compute each successive y values.

Step : 4

Here,Dy=-1

m= Dy / Dx
m = -1 / ( x2 - x1 )
m = -1 / ( xk+1 - xk)

xk+1 =xk +( 1 / m )-------- ( 9 )
  • Equation 6 andEquation9 used to calculate pixel position along a line with ???ve slope.

 Advantage:

  • faster method for calculating pixel position then the equation of apixel position.
  • Y=mx+b

Disadvantage:

  • The accumulation of round of error is the successive addition of the floating point increments is used to find the pixel position but it takes a lot of time to compute the pixel position.  

Algorithm : A native line-drawing algorithm

dx = x2 - x1
dy = y2 - y1
        
for x from x1 to x2 {
   y = y1 + (dy) * (x - x1)/(dx)
   pixel(x, y)
}

C Programming

void linedda(int xa,int ya,int xb,int yb){

int dx=xb-xa,dy=yb-ya,steps,k;
float xincrement,yincrement,x=xa,y=ya;

if(abs(dx)>abs(dy)) steps=abs(dx);
else steps=abs(dy);

xincrement=dx/(float)steps;
yincrement=dy/(float)steps;

putpixel(round(x),round(y),2)

for(k=0;k<steps;k++) {
x+=xincrement;
y+=yincrement;
putpixel(round(x),round(y),2);
}
}

DDA Line Drawing Algorithm Using C Programming

Example:

xa,ya=>(2,2)
xb,yb=>(8,10)
dx=6
dy=8

xincrement=6/8=0.75
yincrement=8/8=1

1) for(k=0;k<8;k++)

xincrement=0.75+0.75=1.50
yincrement=1+1=2
1=>(2,2)

2) for(k=1;k<8;k++)

xincrement=1.50+0.75=2.25
yincrement=2+1=3
2=>(3,3)


it will be incremented upto the final end point is reached.

Download DDA Line PDF Document

DDA Line Algorithm Tutorial Download