Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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 ?

share|improve this question

2 Answers 2

up vote 18 down vote accepted

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.

share|improve this answer
    
ok thanks, with "how much" you are refearing to anti alasing ? –  Fredrik Boston Westman Mar 3 at 16:20
1  
Yes. There are ways to calculate it, but I can't remember the name of the algorithm. –  Alexandre Vaillancourt Mar 3 at 16:23
5  
Downvoters should add comment. –  Alexandre Vaillancourt Mar 3 at 18:14
    
downvoters are usually frustrated kids –  Leggy7 Mar 5 at 7:39
    
Or perhaps they are people who think that a link-only answer isn't sufficient? –  Josh Petrie Mar 11 at 16:05

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.

share|improve this answer
    
Thanks, wish I could give 2 rigth anwsers :)! –  Fredrik Boston Westman Mar 3 at 16:45
1  
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. –  congusbongus Mar 4 at 4:11
    
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 –  Fredrik Boston Westman Mar 5 at 11:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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