Computer Graphics: Digital Differential Analyzer (DDA) Algorithm

Algorithms

Joining two points on any 2 dimensional plane results a line segment. Unfortunately, we can not obtain a line or join two co-ordinate points in Computer Graphics. What we can do is find the intermediate points between these two points and put a pixel for each intermediate points with a desired color.

The computer graphics function uses the output screen as a coordinate system. The TOP-LEFT corner is considered origin(0, 0). On moving right, the x-ordinate increases and on moving down, y-ordinate increases.

What is DDA Algorithm ?

It is an algorithm for calculating all intermediate points in between two co-ordinate points in order to draw line between them.

The DDA Line Drawing Algorithm

Start
Input line endpoints and store left and right endpoints in (x1, y1) and (x2, y2) respectively.
Calculate values of delta(x) and delta(y) :
delta(x) = x2 – x1
delta(y) = y2 – y1
if(abs(delta(x)) > abs(delta(y))) then
stepLength = abs(delta(x))
otherwise
stepLength = abs(delta(y))
Calculate the values of x-increment and y-increment :
xInc = delta(x)/stepLength
yInc = delta(y)/stepLength
Set x = x1, y = y1
Draw the pixel Round(x), Round(y)
For k = 0 to stepLength, do
x = x + xInc
y = y + yInc
draw Round(x), Round(y)
End

C Implementation Of DDA Line Drawing Algorithm


#include<stdio.h> 
#include<graphics.h> //you need to have this library installed
#include<math.h>

void DDA(int x1, int y1, int x2, int y2) 
{ 
    int dx = x2 - x1; 
    int dy = y2 - y1; 
    int stepLength = abs(dx) > abs(dy) ? abs(dx) : abs(dy); 
    float xInc = dx / (float) stepLength; 
    float yInc = dy / (float) stepLength; 
  
    // Put pixel for each step 
    float x = x1; 
    float y = y1; 
    for (int i = 0; i <= steps; i++) 
    { 
        putpixel (x,y,RED);
        x += xInc;
        y += yInc;
    } 
} 
  
int main() 
{ 
    int gd = DETECT, gm; 
    initgraph (&gd, &gm, "");    
    int x1 = 2, y1 = 2, x2 = 14, y2 = 16; 
    DDA(2, 2, 14, 16); 
    return 0; 
}

Advantages Of DDA

It is the simplest method and involves only integer additions so easier to implement.
It is the fastest method for calculating pixel positions then by direct user equation y = mx + c.

Disadvantages Of DDA

Floating point arithmetic in DDA algorithm is time consuming.
Rounding in DDA is also time consuming.
The algorithm is orientation oriented thus the end point accuracy is poor.

Example Problem Of DDA :

Digitize the line with end points (1, 5) and (7, 2) using DDA Algorithm.

solution : Here,

dx = 7 – 1 = 6

dy = 2 – 5 = -3

stepLength = 6 (since abs(dx) > abs(dy))

xInc = 6/6 = 1

yInc = -3/6 = -1/2 = -.5

k	x(k+1)	y(k+1)	(x(k+1), y(k+1))	plot(x(k+1), y(k+1))
1	2	4.5	(2, 4.5)	(2, 5)
2	3	4	(3, 4)	(3, 4)
3	4	3.5	(4, 3.5)	4. 4)
4	5	3	(5, 3)	(5, 3)
5	6	2.5	(6, 2.5)	(6, 3)
6	7	2	(7, 2)	(7, 2)