Bresenham Line Drawing Algorithm in Computer Graphics

What is Bresenham's line drawing algorithm?

Bresenham's line drawing algorithm is a computer graphics algorithm used to draw a line between two points on a pixel screen. It avoids floating-point arithmetic and rounding by using an integer decision parameter.

The algorithm compares two possible next pixels and chooses the one that stays closer to the true mathematical line. This makes it fast, predictable, and suitable for low-level graphics systems.

Decision parameter formula

For the basic case where the line has a positive slope less than 1, calculate:

At each step, the algorithm plots the next x position. If p < 0, the next pixel stays at the same y value. If p >= 0, y is increased by one pixel. Then the decision parameter is updated.

Steps of Bresenham line drawing algorithm

1. Read the two endpoints of the line.
2. Calculate dx and dy.
3. Initialize the decision parameter.
4. Plot the first point.
5. Move one pixel in the dominant direction.
6. Use the decision parameter to decide whether the other coordinate should change.
7. Update the decision parameter and continue until the endpoint is reached.

Example calculation

Suppose we want to draw a line from (2, 3) to (8, 6).

Because the initial decision parameter is 0, the first move increases both x and y. The plotted points are close to the ideal line:

Bresenham algorithm program in C using graphics.h

This implementation works for horizontal, vertical, diagonal, positive-slope, and negative-slope lines. It uses the same Bresenham error idea, extended to handle all line directions.

#include <graphics.h>
#include <conio.h>
#include <dos.h>
#include <stdio.h>
#include <stdlib.h>

void drawBresenhamLine(int x1, int y1, int x2, int y2)
{
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    int sx;
    int sy;
    int error;
    int doubleError;

    if (x1 < x2)
        sx = 1;
    else
        sx = -1;

    if (y1 < y2)
        sy = 1;
    else
        sy = -1;

    error = dx - dy;

    while (1)
    {
        putpixel(x1, y1, WHITE);

        if (x1 == x2 && y1 == y2)
            break;

        doubleError = 2 * error;

        if (doubleError > -dy)
        {
            error = error - dy;
            x1 = x1 + sx;
        }

        if (doubleError < dx)
        {
            error = error + dx;
            y1 = y1 + sy;
        }

        delay(20);
    }
}

int main()
{
    int gd = DETECT, gm;
    int x1, y1, x2, y2;

    printf("Enter x1 y1: ");
    scanf("%d %d", &x1, &y1);

    printf("Enter x2 y2: ");
    scanf("%d %d", &x2, &y2);

    initgraph(&gd, &gm, "");

    drawBresenhamLine(x1, y1, x2, y2);

    getch();
    closegraph();
    return 0;
}

Advantages of Bresenham algorithm

• It uses integer arithmetic, so it is fast.
• It avoids floating-point rounding errors.
• It is efficient for low-level graphics and raster displays.
• It can be extended to other curves, such as circles.

Limitations of Bresenham algorithm

• The basic classroom formula is easiest only for slopes between 0 and 1.
• Handling every line direction requires extra sign and error logic.
• The line can still look jagged because normal raster pixels do not perform anti-aliasing.

DDA vs Bresenham line algorithm

DDA is easier to understand because it directly adds fractional increments to x and y. Bresenham is usually faster because it uses integer calculations and a decision parameter. In exams, DDA is often introduced first, while Bresenham is taught as the more optimized line drawing method.

Common mistakes

Using only the simple slope formula for every line

The basic formula p = 2dy - dx assumes a specific line direction. For arbitrary points, use a version that handles negative slopes and steep lines.

Forgetting to stop at the endpoint

A Bresenham loop should stop when both x and y reach the final endpoint. Otherwise, the loop may continue past the intended line.

Mixing DDA and Bresenham logic

Bresenham does not need floating-point increments. If your program uses xIncrement and yIncrement, you are writing DDA-style logic, not Bresenham's integer method.

Summary

Bresenham's line drawing algorithm is an efficient integer-based method for plotting a straight line on a pixel screen. It uses a decision parameter to choose the nearest next pixel, avoiding floating-point arithmetic and making it faster than DDA in classic graphics systems.