DDA Algorithm

Computer Graphics / Tuesday, August 7th, 2018
(Last Updated On: August 7, 2018)

DDA Line Generation Algorithm

Two of the most popular line generation algorithms are DDA Algorithm and Bresenham Algorithm. The full form of DDA algorithm is Digital Differential Analyser algorithm. To understand it we have to clear about some mathematical terms discussed below.

Need to know:

Any point ‘P’ in 2D represented as (x, y) where x is termed as abscissa which is distance of the point from origin i.e., (0, 0) in the direction of X-axis and y is termed as ordinate which is distance of the point from origin i.e., (0, 0) in the direction of Y-axis.

Now, if we are given the co-ordinates of end points of a line segment PQ , P(x1, y1) and Q(x2, y2) then the equation of the line is,
$y-{{y}_{1}}=m(x-{{x}_{1}})$
Where, m = Slope of the line and it is calculated as,
$m=\frac{{{y}_{2}}-{{y}_{1}}}{{{x}_{2}}-{{x}_{1}}}$
$i.e.,m=\frac{{{y}_{(end)}}-{{y}_{(start)}}}{{{x}_{(end)}}-{{x}_{(start)}}}$

For example, let us find the slope of the line joining the points (2, 3) and (8, 11).
$m=\frac{{{y}_{(end)}}-{{y}_{(start)}}}{{{x}_{(end)}}-{{x}_{(start)}}}=\frac{11-3}{8-2}=\frac{8}{6}=\frac{4}{3}$

The slope of any particular line is fixed and its does not changes if we calculate it using any two points on the line.

Again, remember
$\Delta x=dx={{x}_{2}}-{{x}_{1}}$
$\Delta y=dy={{y}_{2}}-{{y}_{1}}$
$\therefore m=\frac{\Delta y}{\Delta x}=\frac{dy}{dx}$

Now we are ready to understand DDA algorithm.

It is an incremental conversion method. In this approach next step is calculated using results from the preceding step. Suppose at step k we have calculated (xk, yk) to be a point on the line then the next point (xk+1, yk+1) should satisfy m.

Case 1:
If the slope m < 1, we increase the value of x by 1 i.e., dx = 1 and calculate successive y values.
Case 2:
If the slope m > 1, we increase the value of y by 1 i.e., dy = 1 and calculate consecutive x values.
Case 3:
If the slope m = 1, we increase the value of x and y both by 1.

Rule:

 m xk+1 yk+1 m < 1 xk+1 = xk  + 1 yk+1= yk + m m > 1 xk+1 = xk  + (1/m) yk+1= yk + 1 m = 1 xk+1 = xk  + 1 yk+1= yk + 1
 Example 01

Draw line segment from point (2, 4) to (9, 9) using DDA algorithm.

Solution:

We know general equation of line is given by
$y-{{y}_{1}}=m(x-{{x}_{1}})$
Where,
$m=\frac{{{y}_{(end)}}-{{y}_{(start)}}}{{{x}_{(end)}}-{{x}_{(start)}}}$
Given, (xstart, ystart) → (2, 4) and (xend , yend) → (9, 9)
$\Rightarrow m=\frac{{{y}_{(end)}}-{{y}_{(start)}}}{{{x}_{(end)}}-{{x}_{(start)}}}=\frac{9-4}{9-2}=\frac{5}{7}<1$
As 0 < m < 1 so according to DDA algorithm case 1.
xk+1 = xk  + 1, yk+1= yk + m

Iteration 1:
Given, (x1, y1) → (2, 4)
$\therefore {{x}_{2}}={{x}_{1}}+1=2+1=3$
$\therefore {{y}_{2}}={{y}_{1}}+m=4+\frac{5}{7}=\frac{33}{7}$
Put pixel (x2, round y2, color) i.e., put on (3, 5)

Iteration 2:
${{x}_{3}}={{x}_{2}}+1=3+1=4$
${{y}_{3}}={{y}_{2}}+m=\frac{33}{7}+\frac{5}{7}=\frac{38}{7}$
Put pixel (x3, round y3, color) i.e., put on (4, 5)

Similarly go on till (9, 9) is reached.