Difference between DDA and Bresenham’s Algorithm

The Digital Differential Algorithm (DDA) and the Bresenhams’s Algorithm are the digital lines drawing algorithms and are used in computer graphics to draw pictures. Previously, we were using analytical analyzers to compute the pixels and thereby line drawings were made possible. But these analytical methods are not as accurate as the digital methods that with the usage of these digital algorithms now and as with every field, we have been inventing higher quality methods in computer graphics as well. The invention of these algorithms is a perfect example.  Before we proceed, let us look at the concept behind these algorithms. Though it seems out of the scope of our discussion, it is essential to point out the basic differences between the two. If you are really familiar with the algorithms, you can jump to the actual differences located at the end of this page.

What is Digital Differential Algorithm (DDA)?

A DDA is mostly used to draw lines in computer graphics and uses real values while predicting the next pixel values. Let us assume the initial pixel value as (X0, Y0) (X0, Y0) and the destination pixel as (X1, Y1) (X1, Y1). We will learn how to calculate the destination pixel values from the known pixel value (X0, Y0) (X0, Y0) as below.

• How to compute the destination point value using DDA?

Step-1: Here we have the input (X0, Y0) (X0, Y0) and we should identify whether the line runs parallel to the x-axis or the y-axis. To find that, let us now calculate the difference between the initial and the destination pixel values.

dx = X1 – X0

dy = Y1 – Y0

Step-2: Now, we have identified the difference and we should draw the line along the x-axis if ‘dx’ is zero otherwise, we should draw the line parallel to the y-axis. Here is the actual computation in terms of the computer language.

if (absolute (dx) >  absolute (dy))

Steps = absolute (dx);

else

Steps = absolute (dy);

Step-3: Now, it’s time to identify the actual ‘x’ coordinate or the ‘y’ coordinates pixel values in order to draw the line.

X increment = dx / (float) steps;

Y increment = dy / (float) steps;

Step-4: This has to be computed till we reach the destination pixel. The DDA algorithm rounds-off the pixel value to the nearest integer value while doing the computation. Here is the code sample of what we have discussed now.

For (int v=0; v < Steps; v++)

{

x = x + X increment;

y = y + Y increment;

putpixel (Round(x), Round(y));

}

We are done with drawing the line using the DDA and let us move on to the Bresenham’s now!

What is Bresenham’s Algorithm?

It is also a digital line drawing algorithm and was invented by Bresenham in the year 1962 and that is why it has got the same name. This algorithm is more accurate and it used subtraction & addition to computing the pixel value while drawing the line. The accuracy of the Bresenham’s algorithm is reliable while drawing curves & circles as well. Let us look how this algorithm work.

Step-1: The Bresenham’s algorithms assume the initial pixel coordinate as (x_a+1, y_a).

Step-2: It automatically computes the next pixel value as (x_a+1, y_a+1), Here ‘a’ is the incremental value and the algorithm computes it by adding or subtracting the equations that it had formed.

This algorithm calculates accurate values with no rounding off and looks easier as well!

• Numerical Example of Bresenham’s Algorithm:

Let us now consider the points (0,0) and (-8, -4) and let us draw a line between these points using the Bresenham’s algorithm.

Given data, (x1, y1) = (0, 0) and (x2, y2)= (-8,-4).

Let us now compute the differential values as below.

∆x=x2-x1=-8-0=8

Therefore, the incremental value for x = ∆x / x2 = 8/-8 = -1.

∆y=y2-y1=-4-0=4

Therefore, the incremental value for y = ∆y / y2 = 4 / -4 = -1.

Decision Variable=e=2*(∆y)-(∆x)

Therefore, e= 2*(4)-(8) = 8-8 =0

With the above computation, let us tabulate the resultant values. The values of y-coordinate are adjusted based on a decision variable and we are just ignoring its computation here.

Differences between DDA & Bresenham’s Algorithm:

• Arithmetic Calculation:

The DDA uses real values in its computations with the usage of floating points. The next pixel or point values are determined with differential equations

X increment = dx / (float) steps

Y increment = dy / (float) steps

Here no fixed constants are used but in Bresenham’s algorithm fixed points are used in arithmetic computations. The Bresenham’s algorithm uses Integer arithmetic, unlike the DDA.

• Type of operation used:

The DDA solves the differential equations with multiplication and division operations. You could notice the same here, X increment = dx / (float) steps. The Bresenham’s algorithm uses addition and subtraction operations and you can notice the same here in its next pixel value computation equation (x_a+1, y_a+1). The arithmetic is simpler in Bresenham’s when compared to the DDA.

• Efficiency:

As we have discussed earlier, Bresenham’s algorithm uses simpler arithmetic than the DDA and it results in efficient results.

• Speed: As DDA uses floating point integers along with multiplication & division operations, it is comparatively slower whereas Bresenham’s algorithm uses just integer arithmetic along with additions & subtractions alone. This considerably reduces the time taken for its computations and hence it faster than the DDA.
• Accuracy: Though DDA uses floating point values, the accuracy of DDA is not as better as the Bresenham’s. A variety of factors affect this concept and therefore, Bresenham’s is more accurate than the DDA.
• Rounding off: Just look at the computation of the DDA here.

X increment = dx / (float) steps

You could notice the ‘float’ and therefore it does not round off the values whereas the Bresenham’s algorithm rounds off the values to the nearest integer. Therefore, the values used are simpler in Bresenham’s algorithm.

• What does it draw?

The DDA is capable of drawing circles and curves apart from drawing lines. The Bresenham’s algorithm is also capable of drawing all those mentioned above and its accuracy is really higher than that of the DDA. Similarly, the Bresenham’s algorithm could come up with efficient curves than that produced by the DDA. Both the algorithms can draw triangles and polygons as well.

• Which is expensive?

As DDA includes rounding off as well, it is expensive than the usage of Bresenham’s algorithm.

• Which is an optimized algorithm?

From our above discussion, it is very clear that the Bresenham’s algorithm is an optimized one in terms speed, cost, and usage of operations.

Let us look at the differences in a tabular form.

We have dealt with every possible difference between the DDA and the Bresenham’s algorithm. It might even seem to be repetitive but there is some valid reason for mentioning those points again and you would come to know when you understand it completely. If you still feel that there exists an ambiguity, please leave us a comment. Let us learn together by sharing the proper knowledge!