17
\$\begingroup\$

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 ?

\$\endgroup\$
25
\$\begingroup\$

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.

\$\endgroup\$
21
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Just want to warn passers-by not to take the included pseudocode out of context, as it won't work out of the box. It only works for a specific octant (read the rest of the answer). If you're looking for code to copy/paste, try the link to the Rosetta Code website. \$\endgroup\$ – congusbongus Mar 4 '14 at 4:11
  • 1
    \$\begingroup\$ For anyone wanting to check out the c version of Wu's line algorithm I would like to warn you that it is incomplete. In the _dla_changebrightness when you change the brightness you need to change it from : to->red = br * (float)from->red; to this following: to->red = (br * (float)from->red) + ((1-br) * (float) to->red);. Do the same for green and blue respectivly \$\endgroup\$ – Fredrik Boston Westman Mar 5 '14 at 11:09
2
\$\begingroup\$

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;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.