23

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.

3
  • Surely it's straightforward to just use cells that contain any part of the line at all?
    – Anon.
    Dec 7, 2010 at 20:35
  • That's exactly what I want. But I do not know how/do not understand the math behind it. Dec 7, 2010 at 20:36
  • How is the line defined? As slope-length-intercept? As slope-length-initial point? As two endpoints?
    – Ben Voigt
    Dec 7, 2010 at 20:40

6 Answers 6

14

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.

4
  • I'll give this a try, and also benchmark it - if it works and is faster than my current method, I'll accept it. Oct 17, 2012 at 13:16
  • 2
    This seems error prone to me. Looking at the Wikipedia article, there is usually just the single if if (e2 < dx). And dy is initialized to a negative of an absolute value!? Removing the negativisation of dy still errror prone. Horizontal lines lose alternate pixels while lines slightly off the horizontal result in infinite loops. Mar 3, 2014 at 22:08
  • @JamesMorris negative value avoids a negative sign in the downstream code also there are two ifs ...
    – Karussell
    Jul 7, 2014 at 15:59
  • 1
    The line drawn by this modification, as algorithm prefers horizontal steps and only does vertical steps if absolutely necessary to keep the error indicator within bounds. A similar modification draws a line that is nearer to the original, selecting either a horizontal or vertical step depending on which minimizes the error. See my answer to a similar question.
    – Franz D.
    Feb 28, 2015 at 20:35
5

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)));
    }
}
1
  • Nice! Rather than specially casing the steps for efficiently extracting just the diagonal in the 45 degrees case, is it easy to adapt this to find all pixels whose corners touch the 45 degree line? I'd like to get all 3 diagonals, as if considering that just touching a pixels corner is enough to count as hitting it. Jan 31, 2015 at 22:21
2

Without loss of generality, assume x2 >= x1, then

int x = floor(x1);
int y = floor(y1);
double slope = (x2 - x1) / (y2 - y1);
if (y2 >= y1) {
  while (y < y2) {
    int r = floor(slope * (y - y1) + x1);
    do {
      usepixel(x, y);
      ++x;
    } while (x < r);
    usepixel(x, y);
    ++y;
  }
}
else {
  while (y > y2) {
    int r = floor(slope * (y - y1) + x1);
    do {
      usepixel(x, y);
      ++x;
    } while (x < r);
    usepixel(x, y);
    --y;
  }
}

The floor calls can probably be written just as a cast-to-integer.

5
  • I imagine, if x2 was less than x1, that I'd swap the two axes? Dec 7, 2010 at 21:13
  • You'd swap the two endpoints, yes. Did it work ok in your testing?
    – Ben Voigt
    Dec 7, 2010 at 23:05
  • What data types are (x1, y1) and (x2, y2) anyway? From your graphic I assumed they were floating-point, but if everything is integer then it can be optimized some more.
    – Ben Voigt
    Dec 7, 2010 at 23:10
  • Well they are floating point, but not to the point where it would be a disadvantage to go integer. Dec 8, 2010 at 7:34
  • If y2 == y1, then you'll be dividing by zero when you define slope.
    – uckelman
    Apr 10, 2011 at 20:40
2

There is an interesting article available in GPU Gems, maybe it can help you: Chapter 22. Fast Prefiltered Lines

5
0

What about Bresenham with an additional constraint that no diagonal moves are allowed: Generate the points with the traditional algorithm, then as a post-processing step insert extra steps needed to make only orthogonal movements.

1
  • This is gonna be done about 60 times a second.I can't afford the overhead :/ Dec 7, 2010 at 20:40
0

You could find all the intersections your ray has with the horizontal grid lines, and then mark all the cells on a row that either have an intersection point on one side, or are between the two cells with the intersections on the row.

Finding the intersections can be done by starting from the origin, advancing the point to the first intersection (and marking the cells in the process), finding out the vector that takes you from an intersection to the next (both these operations are basic similar triangles (or trig)) and then advancing column by column until you've gone far enough. Advancing column by column involves one vector addition per column, and a small loop to fill in the cells between the ones with intersections. Replace "mark" with "process" if you're processing the cells on the fly - this algorithm is guaranteed to mark each cell only once.

The same could be done with the vertical lines, but grids are generally stored in horizontal slices so I chose that. If you're using trig, you'll need to handle straight horizontal lines with a special case.

By the way, as far as I know, this is how old grid-based raycaster "3D" games (like Wolfenstein 3D) were done. I first read about this algorithm from this book, eons ago.

2
  • Buh? I'm confused by this. I check EVERY rectangle for an intersection with the line? Dec 7, 2010 at 21:00
  • @Ruirize: No, you more like, go step by step from the origin to find the intersections. Check Ben Voigt's answer for a piece of code that's (essentially) this... maybe it's more understandable. Dec 7, 2010 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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