Home » Computer Graphics

DDA (Digital Differential Analyzer) Algorithm in Computer Graphics

Computer Graphics | DDA (Digital Differential Analyzer) Algorithm: In this tutorial, we are going to learn about the DDA (Digital Differential Analyzer) Algorithm in Computer Graphics, how it is implemented in drawing of a line by defining its entire algorithm? By Monika Sharma Last updated : April 05, 2024

DDA (Digital Differential Analyzer) Algorithm

In computer graphics, the DDA algorithm is the simplest algorithm among all other line generation algorithms. Here, the DDA is an abbreviation that stands for "Digital Differential Analyzer". It is an incremental method, i.e. it works by incrementing the source coordinate points according to the values of the slope generated.

DDA (Digital Differential Analyzer) Definition

Hence, we can define DDA as follows,

"DDA stands for Digital Differential Analyzer. This algorithm is incremental and is used for the rasterization of lines, triangles, and polygons."

Working of the DDA Algorithm

Suppose we have to draw a line PQ with coordinates P (x1, y1) and Q (x2, y2).

1. First, Calculate dx = (x2 - x1) and dy = (y2 - y1)
2. Now calculate the slope m = (dy / dx)
3. Calculate the number of points to be plotted (i.e. n) by finding the maximum of dx and dy, i.e. n = abs (max (dx , dy))
   To draw an accurate line, more number of points are required. Therefore, the maximum of the two values is used here.
4. Now as the n is calculated, to know by how much each source point should be incremented, calculate x_inc and y_inc as follows: x_inc = (dx / n) and y_inc = (dy / n)
5. Now we draw the points from P to Q. The successive points are calculated as follows: (x_next, y_next) = (x + x_inc, y + y_inc)
   Start plotting the points from P and stop when Q is reached. In case the incremented values are decimal, use the round off values.

DDA Algorithm

Now, let us have a look at the algorithm that is followed in DDA.

• Step 1: Start.
• Step 2: Declare x1, y1, x2, y2.
• Step 3: Calculate the following,

      dx = x2 - x1
      dy = y2 - y1
  

• Step 4: Calculate slope as follows,

      m = dy / dx
  

• Step 5: Calculate the no. of points (n) between x1 and x2 as follows,

      n = abs ( max ( dx , dy ) )
  

• Step 6: Calculate x_incand y_inc as follows,

      xinc = (dx / n) and yinc = (dy / n)
  

• Step 7: Now, Initialize x = x1 and y = y1.
• Step 8:

      while ( x <= x2 )
          x = x + xinc
          y = y + yinc
  

• Step 9: Now, Plot (x,y) on the graph, and hence we get our required line between the given points.
• Step 10: End.

DDA Algorithm Formula

In the entire DDA algorithm, there are three conditions and according to these conditions, the formula for calculating the coordinates is changed. These formulas are as follows,

    If m < 1 :      If m > 1 :          If m = 1 :
        xinc = 1        xinc = (1 / m)      xinc = 1
        yinc = m        yinc = 1            yinc = 1

DDA Algorithm Example

Now let us take an example to understand the whole working of the DDA algorithm,

Question: Draw a line from A(2 , 2) to B(5 , 5) using the DDA algorithm.

Solution:

    Given:
    x1 = 2 , y1 = 2
    x2 = 5 , y2 = 6 

    Calculating:    
    dx  = (x2 - x1) = (5 - 2) = 3
    dy  = (y2 - y1) = (6 - 2) = 4
    n   = abs (max (dx , dy ) ) = abs (max (3 , 4) ) = 4

    xinc = dx / n = 3/4 = 0.75
    yinc = dy / n = 4 / 4 = 1

X	Y	x = round(x + xinc)	y = y + yinc
2	2	2 + 0.75 = 2.75 = 3	2 + 1 = 3
3	3	3 + 0.75 = 3.75 = 4	3 + 1 = 4
4	4	4 + 0.75 = 4.75 = 5	4 + 1 = 5
5	5	5 + 0.75 = 5.75 = 6	5 + 1 = 6

Stop here as we have reached point B.

Now, Plot the points ( (2 , 2) , (3 , 3) , (4 , 4) , (5 , 5) ) on the graph and thus we get our required line from point A to point B.

Advantages of DDA Algorithm

Now, we will be looking at the advantages that the DDA algorithm offers over other line drawing algorithms.

1. It is the simplest line generation algorithm.
2. Implementation of the DDA algorithm is very easy as compared to other line generation algorithms.
3. It does not use multiplication which reduces the time complexity of implementation.
4. It is a faster and a better method than using the direct method of the line equation: i.e. y = mx + c

Disadvantages of DDA Algorithm

• DDA algorithm use floating-point arithmetic as it involves the use of division in the calculation of x_inc and y_inc. This floating-point arithmetic makes the algorithm time-consuming.
• The use of floating-point arithmetic decreases the accuracy of the generated points. Hence the points that we get are not accurate, i.e. they may not lie accurately on the line.
• As the points that we get from the DDA algorithm are not accurate, the lines generated by this algorithm are not smooth, i.e. some discontinuation and zigzag nature can be commonly seen in the lines drawn through this algorithm.