CODEWITHSUNDEEP
javaalgorithmgraphics
alexanderd5398
alexanderd5398

Reputation: 327

Bug with Bresenham's Line Drawing algorithm

I'm trying to use Bresenham's Line Drawing Algorithm to draw a line on a 20x20 grid of tiles.

So basically, when the variable deltaerror (from the wiki) is greater than 1 (when the change in y is greater than the change in x), the y value becomes almost double what it should be. Hopefully, I explain it better in the comments of the code. I also think I found the source of the error, which I'll also explain in the comments.

This is the code I made, mostly copied from the pseudocode in the wiki. 

public static void drawLine(Tile t1, Tile t2) {
    int dx = t2.x_index - t1.x_index;
    int dy = t2.y_index - t1.y_index;
    double error = 0;
    double d_error = Math.abs((double) dy / dx); // dx =/= 0, therefore no vertical lines

    // when d_error is greater than 1, the bug occurs

    int y = t1.y_index;
    if (d_error <= 1) { // if related acute angle is < 45 degrees
        if (dx < 0) { // line drawn towards left side of screen
            for (int x=t1.x_index; x>=t2.x_index; x--) {
                Board.tiles[x][y].setColour(Color.red);
                error += d_error;
                while (error >= 0.5) {
                    Board.tiles[x][y].setColour(Color.red);
                    y += dy > 0 ? +1 : -1;// this is where I think the error occurs. In the 
                                          // wiki for the algorithm, this should be some 
                                          // function sign(T) which "decides whether t is 
                                          // positive or negative". I wasn't really sure 
                                          // what this meant, so I just assumed it returned 
                                          // -1 if it was negative and +1 if it was positive. 
                                          // Also it's the only place where y is edited
                                          // that seems to be where the error is occurring. 
                    error -= 1.0;
                }
            }
        } else if (dx > 0) { // line drawn towards right side of screen
            for (int x=t1.x_index; x<=t2.x_index; x++) {
                Board.tiles[x][y].setColour(Color.red);
                error += d_error;
                while (error >= 0.5) {
                    Board.tiles[x][y].setColour(Color.red);
                    y += dy > 0 ? +1 : -1;
                    error -= 1.0;
                }
            }
        }

    // update: switched x and y values when d_error is greater than 1.

    } else { // if related acute angle is > 45 degrees
        dx = t2.y_index - t1.y_index; // switch x and y values
        dy = t2.x_index - t1.x_index;

        d_error = Math.abs((double) dy / dx); // recalculate d_error
        y = t1.x_index;
        if (dx < 0) { // line drawn towards left side of screen
            for (int x=t1.y_index; x>=t2.y_index; x--) {
                Board.tiles[x][y].setColour(Color.red);
                error += d_error;
                while (error >= 0.5) {
                    Board.tiles[x][y].setColour(Color.red);
                    y += dy > 0 ? +1 : -1;
                    error -= 1.0;
                }
            }
        } else if (dx > 0) { // line drawn towards right side of screen
            for (int x=t1.y_index; x<=t2.y_index; x++) {
                Board.tiles[x][y].setColour(Color.red);
                error += d_error;
                while (error >= 0.5) {
                    Board.tiles[x][y].setColour(Color.red);
                    y += dy > 0 ? +1 : -1;
                    error -= 1.0;
                }
            }
        }
    }
}

Thanks for your help!

EDIT: Switched x and y values when d_error is greater than 1. The line disappears when the slope is above 1 and below -1.

Upvotes: 0

Views: 1265

Answers (1)

ThorngardSO
ThorngardSO

Reputation: 1211

To quote from a quick google-result:

http://www.math.ubc.ca/~cass/courses/m308-02b/projects/puhalovic/#alldirections

"With slopes greater than 1 or less than -1, we must take the previous implementation and swap all x and y values to "move" the calculations back into the "First Octant"."

IOW: The textbook implementation of the bresenham only works for lines with (in your terms) d_error<=1. You'll have to implement the swapping mentioned in the link above.

Upvotes: 1

Related Questions