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?
Submitted by Monika Sharma, on April 15, 2020
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.
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).
 First, Calculate dx = (x2  x1) and dy = (y2  y1)
 Now calculate the slope m = (dy / dx)

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

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.
Now, let us have a look at the algorithm that is followed in DDA.
DDA Algorithm
 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_{inc}and y_{inc} as follows,
x_{inc} = (dx / n) and y_{inc} = (dy / n)
 Step 7: Now, Initialize x = x1 and y = y1.

Step 8:
while ( x <= x2 )
x = x + x_{inc}
y = y + y_{inc}
 Step 9: Now, Plot (x,y) on the graph, and hence we get our required line between the given points.
 Step 10: End.
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 :
x_{inc} = 1 x_{inc} = (1 / m) x_{inc} = 1
y_{inc} = m y_{inc} = 1 y_{inc} = 1
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
x_{inc} = dx / n = 3/4 = 0.75
y_{inc} = dy / n = 4 / 4 = 1
X  Y  x = round(x + x_{inc})  y = y + y_{inc} 
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 the DDA algorithm
Now, we will be looking at the advantages that the DDA algorithm offers over other line drawing algorithms.
 It is the simplest line generation algorithm.
 Implementation of the DDA algorithm is very easy as compared to other line generation algorithms.
 It does not use multiplication which reduces the time complexity of implementation.
 It is a faster and a better method than using the direct method of the line equation: i.e. y = mx + c
Disadvantages of the DDA algorithm
 DDA algorithm use floatingpoint arithmetic as it involves the use of division in the calculation of x_{inc} and y_{inc}. This floatingpoint arithmetic makes the algorithm timeconsuming.
 The use of floatingpoint 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.
TOP Interview Coding Problems/Challenges!
ADVERTISEMENT
ADVERTISEMENT