What the f*ck is Digital Differential Analyzer Line Drawing Algorithm? - A Complete Tutorial

DDA (Digital Differential Analyzer) Line Drawing Algorithm is a line drawing algorithm used in computer graphics to generate a line segment between two specified endpoints. It is a simple and efficient algorithm that works by using the incremental difference between the x-coordinates and y-coordinates of the two endpoints to plot the line.

Let's start right off with the DDA Algorithm. In DDA Algorithm, we have been provided with two pieces of information: Starting coordinates = (X₀, Y₀) and Ending coordinates = (X_n, Y_n).

✨ Step One

The first step in DDA Algorithm is to calculate the slope of the line. We know that the slope of the line is given by:
M = ΔY / ΔX
M = (Y_n -Y₀)/(X_n -X₀)

✨ Step Two

The next step is to find the number of points between start and the end coordinate. This is simply the bigger value of ΔY and ΔX. This means if ΔY is bigger then we will have to plot ΔY points between the start and the end and if ΔX is bigger we will have to plot ΔX points between start and the end. Mathematically, we can state that:

P = INT(MAX(ΔY,ΔX))

Here, P is the number of steps.

✨ Step Three

The next step involves actually plotting the points. Suppose the current point is (X_p,Y_p) and the next point is (X_p+1, Y_p+1). We can find the next point by following one of the three cases given below:

Here, m implies the slope. We keep repeating step three P number of times. (From the previous step we know that P implies number of steps).

Let us now look at an example to understand things better.

✨ Solved Example - I

Calculate the points between the starting point (5, 6) and ending point (8, 12).

Step One: State what is given

• Starting coordinates = (X₀, Y₀) = (5, 6)

• Ending coordinates = (X_n, Y_n) = (8, 12)

Step Two: Calculate ΔX, ΔY and M from the given input

• ΔX = X_n – X₀ = 8 – 5 = 3

• ΔY =Y_n – Y₀ = 12 – 6 = 6

• M = ΔY / ΔX = 6 / 3 = 2

Step Three: Calculate the number of points

We know that whichever of ΔY and ΔX is greater will be the number of points.

As |ΔX| < |ΔY| = 3 < 6,
so number of points = ΔY = 6

Step Four: Find the case and repeat

As M > 1, so case-03 is satisfied. Now, Step-03 is executed 6 times.

Now, if we plot this the line will look something like this:

We know that this is not a perfect line on microscopic level, but if we infinitely zoom out, we will get something similar to a line. It must be noted that the more points we take the straighter the line. Let us take another example to understand this better.

✨ Solved Example - II

Calculate the points between the starting point (1, 7) and ending point (11, 17)

Step One: State what is given

• Starting coordinates = (X₀, Y₀) = (1, 7)

• Ending coordinates = (X_n, Y_n) = (11, 17)

Step Two: Calculate ΔX, ΔY and M from the given input

Calculate ΔX, ΔY and M from the given input.

• ΔX = X_n – X₀ = 11 – 1 = 10

• ΔY =Y_n – Y₀ = 17 – 7 = 10

• M = ΔY / ΔX = 10 / 10 = 1

Step Three: Calculate the number of points

As |ΔX| = |ΔY| = 10 = 10, so number of steps = ΔX = ΔY = 10

Step Four: Find the case and repeat

As M = 1, so case-02 is satisfied.

Now, let us plot the line for this.

As we can see the line is comparitively "more like a line". Why this happens is an interesting question, and I would like to quote CS50's lecture on Computer Graphics here.

In the Digital Differential Analyzer (DDA) algorithm, the basic principle is to approximate a line segment between two points by successively plotting intermediate points along the line. The slope of the line determines how many points need to be plotted to create a straighter line.

When you increase the number of points in the DDA algorithm, you are essentially increasing the resolution of the line. This means that more intermediate points are plotted between the start and end points, resulting in a smoother and straighter appearance for the line.

With a higher number of points, the line is divided into smaller segments, and each segment is closer to the actual mathematical representation of the line. As a result, the visual perception of the line becomes smoother and closer to a straight line, especially when rendered on a display with higher resolution.

In summary, increasing the number of points in the DDA algorithm results in a straighter line because it provides a finer approximation of the line by plotting more intermediate points along its path.

This was all about DDA Algorithm. Hope you understood the algorithm and can tackle all the numericals that come with it.