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 two endpoints 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 lines based on this equation interval Dy from the equation

Similarly, x interval Dx from the equations

m = Dy / Dx

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

🎯 Line DDA Algorithm

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

Consider first a line with a 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 value.

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 increments by one 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 than 1, the roles of x and y at the unit y intervals Dy=1 and compute each successive y value.

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 the left endpoint to the right endpoint.

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 )

Intervals Dy=1 and compute each successive y value.

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 and Equation 9 are used to calculate pixel position along a line with a negative slope.

Advantage

  • Faster method for calculating pixel position than the equation of a pixel position. (Y=mx+b)

Disadvantage

  • The accumulation of round of error is the successive addition of the floating point increments used to find the pixel position. Still, 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 Code for line-drawing algorithm

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);

}

}

Sample Output

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.

✍ Related Articles