LINE-DRAWING ALGORITHMS - DDA Algorithm -MASTER GUIDE

 LINE-DRAWING ALGORITHMS - DDA Algorithm

The slope intercept equation for the straight line is y= mx + b­ ­-->(1)                        Where m is the slope of the line and b is the y intercept. Let (x1, y1) and (x2, y2) be the two end points of the line segment. We can determine the values for m and b using following equations: 

m = 𝑦2−𝑦1 𝑥2−𝑥1 --->  (2) 

and b= y1- m. x1 -----> (3) 

Algorithms for displaying straight lines are based on equation (1) and calculations given in (2) and (3). 

For a small change in x interval ∆𝑥 along a line, we can compute the corresponding y interval ∆𝑦 as ∆𝑦 = 𝑚 . ∆𝑥 ------------>(4) 

and we can obtain the x interval ∆𝑥 corresponding to a specified ∆𝑦 as ∆𝑥 = ∆𝑦 𝑚 ----->(5) 

These equations are the basis for determining the values of x and y. 

For slope |m|<1, ∆𝑥=1 and corresponding ∆𝑦 is calculated from equation (4). 

For the lines with slope |m|>1, ∆𝑦=1 and corresponding ∆𝑥 can be calculated using equation (5).

 Lines with slope =1, ∆𝑥 = ∆𝑦.

The digital differential analyser (DDA) is a scan conversion line algorithm based on calculating either ∆𝑥 or ∆𝑦 using equations (4) and (5). 

Consider a line with positive slope.

 If the slope is less than or equal to 1, we sample at unit x intervals (∆𝒙 = 𝟏) and corresponding y value is calculated as 

yk+1 =yk + m ----->(6)  subscript k takes integer values from 1 and increases by 1 until the final end point is reached. Since m can be any real number between 0 and 1, the calculated y values must be rounded to the nearest integer. 

For the lines with a positive slope greater than 1, we reverse the roles of x and y. That is ∆𝒚 = 𝟏 and corresponding x value is calculated as xk+1=xk+ 𝟏 𝒎 ---->(7) 

Equation (6) and (7) are based on the assumption that the line is to be processed from left end point to right.

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

If slope < 1 then ∆𝒙 = −𝟏 and yk+1=yk- m⟶(8) and 

when the slope is > 1 ∆𝒚 = −𝟏 and xk+1=xk - 𝟏 𝒎 ⟶ (9)

#define ROUND(a) ((int)(a+0.5))

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;

 setPixel (Round(x), Round(y));

 for(k=0; k<steps; k++)

 {

     x+= xIncrement;

     y+= yIncrement;

     setPixel (Round(x), Round(y));

 }

}

Advantages 

1. DDA algorithm is simple 

2. It is faster method for calculating pixel positions than the direct method. 

Disadvantages 

1. Floating point arithmetic in DDA is time consuming. 

2. The approximation of pixels due to rounding off produces stair-step effect in the line. 

3. End point accuracy is poor.