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

  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 xinc and yinc as follows: xinc = (dx / n) and yinc = (dy / n)
  5. Now we draw the points from P to Q. The successive points are calculated as follows: (xnext, ynext) = (x + xinc, y + yinc)
    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 xincand yinc 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.

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

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
XYx = round(x + xinc)y = y + yinc
222 + 0.75 = 2.75 = 32 + 1 = 3
333 + 0.75 = 3.75 = 43 + 1 = 4
444 + 0.75 = 4.75 = 54 + 1 = 5
555 + 0.75 = 5.75 = 65 + 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.

  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 the DDA algorithm

  • DDA algorithm use floating-point arithmetic as it involves the use of division in the calculation of xinc and yinc. 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.





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.