Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Line rasterisation: Cover all pixels, regardless of line gradient?

Tags:

Basically, I want to use a line algo to determine which cells to check for collisions for my raycaster.

Bresenham isn't great for this as it uses a unified-thickness approach, meaning that it ignores cells that aren't at least half-covering the line. Not great at all, because it means that some segments of my line aren't being checked for intersections with the cells, leading to errors.

I can't seem to find any "thick-line" algorithms, can anyone help me find one?

Red: Bad. Green: Good!
Green: What I would like.
Red: What I currently have and don't want.

like image 928
Steffan Donal Avatar asked Dec 07 '10 20:12

Steffan Donal


People also ask

What is the purpose of Bresenham's line drawing algorithm?

This algorithm is used for scan converting a line. It was developed by Bresenham. It is an efficient method because it involves only integer addition, subtractions, and multiplication operations. These operations can be performed very rapidly so lines can be generated quickly.

What is Bresenham s line algorithm Theorem?

Bresenham's line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points.

Why Bresenham's line algorithm is preferred to DDA algorithm?

Bresenhams algorithm is faster than DDA algorithm in line drawing because it performs only addition and subtraction in its calculation and uses only integer arithmetic so it runs significantlyfaster. Accuracy & EfficiencyDDA algorithm is not as accurate and efficient as Bresenham algorithm.

What is error term in Bresenham's line algorithm?

The error term is initially set as e = 2 Δy - Δx where Δy = y2 - y1, and Δx = x2 - x1. Then according to value of e following actions are taken, while ( e ≥ 0) { y = y + 1 e = e - 2 * Δx } x = x + 1 e = e + 2 * Δy.


2 Answers

I had exactly the same problem as you and found an very simple solution. Usually, Bresenham has two consecutive if's to determine whether it should increase the coordinate for the two dimensions:

public void drawLine(int x0, int y0, int x1, int y1, char ch) {
    int dx =  Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
    int err = dx + dy, e2; // error value e_xy

    for (;;) {
        put(x0, y0, ch);

        if (x0 == x1 && y0 == y1) break;

        e2 = 2 * err;

        // horizontal step?
        if (e2 > dy) {
            err += dy;
            x0 += sx;
        }

        // vertical step?
        if (e2 < dx) {
            err += dx;
            y0 += sy;
        }
    }
}

Now all you have to do is to insert an else before the second if:

public void drawLineNoDiagonalSteps(int x0, int y0, int x1, int y1, char ch) {
    int dx =  Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
    int err = dx + dy, e2;

    for (;;) {
        put(x0, y0, ch);

        if (x0 == x1 && y0 == y1) break;

        e2 = 2 * err;

        // EITHER horizontal OR vertical step (but not both!)
        if (e2 > dy) { 
            err += dy;
            x0 += sx;
        } else if (e2 < dx) { // <--- this "else" makes the difference
            err += dx;
            y0 += sy;
        }
    }
}

Now the algorithm doesn't change both coordinates at once anymore. I haven't thoroughly tested this but it seems to work pretty well.

like image 158
Gen. Error Avatar answered Sep 22 '22 16:09

Gen. Error


This thread old, but I thought it'd be worth putting this on the Internet:

// This prints the pixels from (x, y), increasing by dx and dy.
// Based on the DDA algorithm (uses floating point calculations).
void pixelsAfter(int x, int y, int dx, int dy)
{
    // Do not count pixels |dx|==|dy| diagonals twice:
    int steps = Math.abs(dx) == Math.abs(dy)
            ? Math.abs(dx) : Math.abs(dx) + Math.abs(dy);
    double xPos = x;
    double yPos = y;
    double incX = (dx + 0.0d) / steps;
    double incY = (dy + 0.0d) / steps;
    System.out.println(String.format("The pixels after (%d,%d) are:", x, y));
    for(int k = 0; k < steps; k++)
    {
        xPos += incX;
        yPos += incY;
        System.out.println(String.format("A pixel (%d) after is (%d, %d)",
            k + 1, (int)Math.floor(xPos), (int)Math.floor(yPos)));
    }
}
like image 41
ants280 Avatar answered Sep 19 '22 16:09

ants280