DDA Algorithm

DDA Algorithm

Digital Differential Analyzer is a scan conversion line algorithm based on calculating either dy or dx. We sample the line at unit intervals in one coordinate & determine corresponding integer values nearest to the line path for the other coordinate. The algorithm accepts as input the two endpoint pixel positions. Horizontal & vertical differences between the endpoint positions are assigned to parameters dx &dy. The difference with the greater magnitude determines the increment of the parameter steps. Starting with the pixel position (Xa , Ya), we determine the offset needed at each step to generate the next pixel position along the line path. We loop through this process ‘steps’ times. If the magnitude of dx is greater that the magnitude of dy & Xa is less that X_b, the values of the increments in the x & y directions are i & m. It is a faster method of calculating pixel positions. However, the accumulation of round off error in successive additions can cause the calculated pixel positions to draft away from the true line path for long line segments.

Example:  let us consider the algorithm in two cases depending on the slope of the line whether it is > 1 or < 1.

Case 1: slope (m) of line is < 1 (i.e., line 1): In this case to plot the line we have to move the direction of pixel in x by 1 unit every time and then hunt for the pixel value of the y direction which best suits the line and lighten that pixel in order to plot the line. So, in Case 1 i.e., 0 < m < 1 where x is to be increased then by 1 unit every time and proper y is approximated.

                                                     Figure 3.3DDA Line Generation

Case 2: slope (m) of line is > 1 (i.e., line 2) if m > 1 i.e., case of line 2, then the most appropriate strategy would be to move towards the y direction by 1 unit every time and determine the pixel in x direction which best suits the line and get that pixel lightened to plot the line.

So, in Case 2, i.e., (infinity) > m > 1 where y is to be increased by 1 unit every time and proper x is approximated.

DDA or slope method algorithm for line drawing

Step1: compute dx: dx=x2-x1;

Step2: compute dy: dy=y2-y1;

Step3 compute m:m=dy/dx;

Step 4: compute b:b=y1-m*x1;

Step 5: set(x,y) equal to lower left hand endpoint and set x’=largest value of x.if dx<0 then

x=x2,y=y2 and x’=x1.if dx>0 ,then x=x1,y=y1 and x’=x2.

Step 6: Test to determine whether the entire line has been drawn.If x> x’, stop

Step 7: Plot a point at the current(x,y) coordinates.

Step 8: Increment x:x=x+1;

Step 9: compute the next value of y from the equation y=mx+b

Step 10 goto step 6

The drawback of DDA algorithm

Digital differential Analyzer is a scan conversion algorithm based on calculating the differences between the x coordinates and y coordinates. The disadvantage of this algorithm is that the accumulation of the round-off error in successive additions of the floating point increment can cause the calculated pixel positions to drift away from the true line path for long line segments that results in a zigzag line instead of a straight one.