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.