Line drawing algorithms in computer graphics

A line drawing algorithm is a graphical algorithm for approximating a line segment on discrete graphical media such as pixel-based and printers. There are some general requirements for drawing a line, which are:

• A straight line must appear as a straight line;
• It must start and end accurately;
• It should have a constant brightness;
• It should be drawn rapidly.

The equation of the straight line connects two points \((x_0, y_0)\) and \((x_1, y_1)\) is \begin{equation} ax + by + c = 0, \tag{1} \end{equation} in which: \(a = y_1 - y_0\), \(b = -(x_1 - x_0)\), \(c = x_1y_0 - x_0y_1\).

If \(x_1 \neq x_2\), we can frame the equation in the slope-intercept form as below: \begin{equation} y = mx + b, \tag{2} \end{equation} in which:

For our line drawing algorithms, we have to distinguish between the two following cases. In each case, we can frame the problem of drawing a line in different ways:

• When drawing a line with a slope \(m\) between \(-1\) and \(1\) (\(m \in [-1, 1]\)), the problem is to find the corresponding \(y\) value for each unique \(x\) value;
• When drawing a line with a slope \(m\) less than \(-1\) or greater than \(1\) (\(m \in (-\infty, -1) \cup (1, \infty)\)), the problem is to find the corresponding \(x\) value for each unique \(y\) value.

They are quite similar, aren’t they? One problem can be framed as the other problem by swapping the roles between \(x\) and \(y\). So for simplicity, We will assume that \(x_0 < x_1\) and the slope of our line is between \(-1\) and \(1\).

1. Direct implementation using the line equation

With direct implementation using the line equation, we will loop the \(x\) value from \(x_0\) to \(x_1\). For each \(x\) value, we plug it into the equation \((2)\) to find the corresponding \(y\) value.

This algorithm performs a floating-point multiplication for every \(x\) value. Therefore, it requires an enormous number of floating-point multiplications and is therefore expensive.

The following Python function is to draw a line using the line equation directly:

def draw_line_equation(x_0, y_0, x_1, y_1):
    vertices = []
    if x_0 == x_1 and y_0 == y_1:
        vertices += [x_0, y_0]
    else:
        d_x = x_1 - x_0
        d_y = y_1 - y_0
        if abs(d_x) >= abs(d_y):
            if x_0 > x_1:
                x_0, x_1 = x_1, x_0
                y_0, y_1 = y_1, y_0
            m = float(d_y) / d_x
            b = y_0 - m * x_0
            for x in range(x_0, x_1 + 1):
                vertices += [x, int(math.floor(m * x + b + 0.5))]
        else:
            if y_0 > y_1:
                x_0, x_1 = x_1, x_0
                y_0, y_1 = y_1, y_0
            m = float(d_x) / d_y
            b = x_0 - m * y_0
            for y in range(y_0, y_1 + 1):
                vertices += [int(math.floor(m * y + b + 0.5)), y]
    return vertices

You can find the complete version of the code here.

2. DDA line drawing algorithm

DDA line drawing algorithm, also known as Digital Differential Analyzer follows an incremental approach, which performs computations at each step and uses the outcome of the previous step. It draws the given line according to the difference in the pixel points.

We only need to compute \(m\) once, as the start of the scan-conversion. The DDA line drawing algorithm does not use the floating-point multiplication which makes it faster than the direct implementation using the line equation, however, it does use the floating-point addition. It is not precise because of the usage of floating-point representation could cause computed points to drift away from their actual position when the line is relatively long.

The following Python function is to draw a line using DDA algorithm:

def draw_line_dda(x_0, y_0, x_1, y_1):
    vertices = []
    if x_0 == x_1 and y_0 == y_1:
        vertices += [x_0, y_0]
    else:
        d_x = x_1 - x_0
        d_y = y_1 - y_0
        if abs(d_x) >= abs(d_y):
            if x_0 > x_1:
                x_0, x_1 = x_1, x_0
                y_0, y_1 = y_1, y_0
            m = float(d_y) / d_x
            y = y_0
            for x in range(x_0, x_1 + 1):
                vertices += [x, int(math.floor(y + 0.5))]
                y = y + m
        else:
            if y_0 > y_1:
                x_0, x_1 = x_1, x_0
                y_0, y_1 = y_1, y_0
            m = float(d_x) / d_y
            x = x_0
            for y in range(y_0, y_1 + 1):
                vertices += [int(math.floor(x + 0.5)), y]
                x = x + m
    return vertices

You can find the complete version of the code here.

3. Bresenham line drawing algorithm

Bresenham line drawing algorithm also provides a raster scan method for generating lines where incremental integer calculations are used. The developer of the algorithm is Jack Elton Bresenham, and the algorithm was named after him.

Now let’s understand Bresenham’s approach, considering a scan-conversion technique for a line having a positive slope of less than \(1\). This method allows integer-only arithmetic, which is generally faster than using floating-point arithmetic. It begins from the left endpoint \((x_0, y_0)\) of the given line, then each consecutive column is considered. In one column, a pixel is plotted where the \(y\) value (at that column) of the mathematical line closer to. Let’s suppose that we have the pixel \((x_k, y_k)\) to be displayed, the question becomes which one of the two pixels \((x_k + 1, y_k)\) and \((x_k + 1, y_k + 1)\) we will display next.

Figure 1. Bresenham line drawing algorithm.

In the column \(x_k + 1\), the vertical separations by the mathematical line are labelled as \(d_1\) and \(d_2\). The \(y\) value of the mathematical line at that \(x_k + 1\) column is \begin{equation} y = m(x_k + 1) + b. \tag{7} \end{equation}

So \(d_1\) and \(d_2\) are given as follows:

and

You can use those to determine which pixel is closer to the \(y\) value (at that \(x_k + 1\) column) of the mathematical line. Let’s have a look at the following subtraction:

A positive \(d_1 - d_2\) means that pixel \((x_k + 1, y_k + 1)\) is closer to the \(y\) value (at that \(x_k + 1\) column) of the mathematical line; otherwise \((x_k + 1, y_k)\) is the closer pixel. The decision parameter \(p_k\) for the \(k^{th}\) iteration of the Bresenham line drawing algorithm is given by

From \((3)\) we have \(m = \dfrac{\Delta y}{\Delta x}\), let’s plug it in \((11)\). The formula for decision parameter becomes

Here, we have the sign of \(p_k\) is equal to \(d_1 - d_2\) as \(\Delta x\) is greater than \(0\). The value of the parameter \(C\) is \(2\Delta y + 2\Delta x.b -\Delta x\) which is constant, not affected by the pixel position and can be removed in the recursive calculation of \(p_k\).

Integrated changes along the line occur in unit steps in any of the direction \(x\) or \(y\). Therefore, the consequent decision parameters can be calculated using an incremental approach. At \(k + 1\) iteration, the decision parameter is calculated as

Subtracting the equation \((12)\) from the equation \((13)\), we get

But \(x_{k = 1} = x_k + 1\), so that

The term \(y_{k + 1} - y_k\) is either \(0\) or \(1\), according to the sign of parameter \(p_k\). This iterative calculation of decision parameter is carried out at every integer \(x\) position, beginning from \(x_0\). So the only other thing we need is to find the initial parameter \(p_0\). The equation \((12)\) at the pixel \((x_0, y_0)\) is

From \((3)\) and \((4)\) we have \(b = y_0 - mx_0 = y_0 - \dfrac{\Delta y}{\Delta x}x_0\), let’s plug it in \((16)\). The formula for initial parameter becomes

Similarly, adopt the Bresenham’s approach for a line having a negative slope of greater than \(-1\), we have:

The following Python function is to draw a line using Bresenham algorithm:

def draw_line_bresenham(x_0, y_0, x_1, y_1):
    vertices = []
    if abs(x_1 - x_0) > abs(y_1 - y_0):
        if x_0 > x_1:
            x_0, x_1 = x_1, x_0
            y_0, y_1 = y_1, y_0
        d_x = x_1 - x_0
        d_y = y_1 - y_0
        if d_y > 0:
            p = 2 * d_y - d_x
            y = y_0
            for x in range(x_0, x_1 + 1):
                vertices += [x, y]
                if p > 0:
                    y = y + 1
                    p = p - 2 * d_x
                p = p + 2 * d_y
        else:
            p = 2 * d_y + d_x
            y = y_0
            for x in range(x_0, x_1 + 1):
                vertices += [x, y]
                if p < 0:
                    y = y - 1
                    p = p + 2 * d_x
                p = p + 2 * d_y
    else:
        if y_0 > y_1:
            x_0, x_1 = x_1, x_0
            y_0, y_1 = y_1, y_0
        d_x = x_1 - x_0
        d_y = y_1 - y_0
        if d_x > 0:
            p = 2 * d_x - d_y
            x = x_0
            for y in range(y_0, y_1 + 1):
                vertices += [x, y]
                if p > 0:
                    x = x + 1
                    p = p - 2 * d_y
                p = p + 2 * d_x
        else:
            p = 2 * d_x + d_y
            x = x_0
            for y in range(y_0, y_1 + 1):
                vertices += [x, y]
                if p < 0:
                    x = x - 1
                    p = p + 2 * d_y
                p = p + 2 * d_x
    return vertices

You can find the complete version of the code here.

References

• https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
• https://en.wikipedia.org/wiki/Digital_differential_analyzer_(graphics_algorithm)
• https://en.wikipedia.org/wiki/Line_drawing_algorithm
• https://techdifferences.com/difference-between-dda-and-bresenham-line-drawing-algorithm.html