How do you draw a straight line between two points in a bitmap?

Question

I'm playing around with height maps (bitmaps), trying to create some of my own in my game, and for that I need to implement some basic drawing methods. I've quickly realized that drawing straight lines isn't as basic as I thought.

It simple's if your points share an X or Y coordinate, or if they are aligned so you can draw a perfectly diagonal line. But in all other cases its trickier.

What algorithm do you use to determine what pixels need to be coloured for it to become a "straight" line ?

Answer 1

I think what you need is Bresenham's line algorithm.

From what I remember it is used to determine what point should be coloured, not how much each point should be coloured.

Answer 2

Bresenham's line algorithm can be used to determine which points in a raster grid to plot in order to achieve a appropriate visual approximation of a line segment.

The algorithm covers the rasterization of a line defined by the origin and endpoints in a coordinate space where the origin is in the upper left. Integer coordinates are presumed to map to pixel centers. Notably, the basic form of the algorithm only covers one octant of the circle: the one where the line has increasing X and Y coordinates but a negative slope with an absolute value less than 1. All other octants can be derived as simple transformations of this basic octant.

In psuedocode, this basic form looks like:

void DrawLine(Point origin, Point endpoint, Bitmap surface) {
    deltaX = endpoint.X - origin.X
    deltaY = endpoint.Y - origin.Y
    error = 0

    // Note the below fails for completely vertical lines.
    deltaError = absoluteValue(deltaY / deltaX)

    Y = origin.Y
    for (X from origin.X to endpoint.X) {
        surface.PlotPixel(X, Y)
        error = error + deltaError 
        if (error >= 0.5) {
            ++Y;
            error -= 1.0
        }
    }
}

The Rosetta Code website has a collection of concrete implementations in a variety of languages.

You may also be interested in Wu's line algorithm, which allows for anti-aliasing.

Answer 3

Here is an extremely simple way of drawing lines. The function can easily be changed to be used in projects.

void draw_line(float x0, float y0, const float& x1, const float& y1)
{
    float x{x1 - x0}, y{y1 - y0};
    const float max{std::max(std::fabs(x), std::fabs(y))};
    x /= max; y /= max;
    for (float n{0}; n < max; ++n)
    {
        // draw pixel at ( x0, y0 )
        x0 += x; y0 += y;
    }
}