3 ms·

Things get a lot more complicated than the standard bresenham in the real world. For instance, if you plot (x0,y0) to (x1,y1), will it visit the same pixels as

Things get a lot more complicated than the standard bresenham in the real world. For instance, if you plot (x0,y0) to (x1,y1), will it visit the same pixels as plotting (x1,y1) to (x0,y0)? Probably not, unless you take care. If you need to consider clipping, then setup requires multiplication and division (or you can step N times until you are inside the clipping region, but that can be slower). Snapping to integer endpoints produces very noticeable artifacts for animated graphics (yes, noticeable even if the lines aren't antialiased).

vanderZwan 9y ago
> For instance, if you plot (x0,y0) to (x1,y1), will it visit the same pixels as plotting (x1,y1) to (x0,y0)? Probably not, unless you take care. Well, the simplest way around this is performing a x0 < x1 test and swapping (x0,y0) and (x1, y1) before running the algorithm if that doesn't hold true. You'd still get artifacts due to snapping, but they would be consistent at least. Alternatively, if you don't mind a bit of redundancy, wouldn't it suffice to turn the original function y(x) (which is what the standard Bresenham algorithm does) into two that go x(t) and y(t), and set the step-size of t to a small enough number to never skip a pixel?
- tasty_freeze 9y ago
  In the first case, then yes, you are taking care to avoid one of the problems a naive approach has. In the second case, you'll end up with blobby lines. For an x-major line, the standard algorithm would plot one pixel for every unit in X. With your approach, some x's would get one pixels, and some would get two (at adjacent y's on either side of the ideal y)
  - vanderZwan 9y ago
    Ah true, you need some form of anti-aliasing for that, which would basically end up at something like Xiaolin Wu's algorithm. https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm

vanderZwan 9y ago

> For instance, if you plot (x0,y0) to (x1,y1), will it visit the same pixels as plotting (x1,y1) to (x0,y0)? Probably not, unless you take care. Well, the simplest way around this is performing a x0 < x1 test and swapping (x0,y0) and (x1, y1) before running the algorithm if that doesn't hold true. You'd still get artifacts due to snapping, but they would be consistent at least. Alternatively, if you don't mind a bit of redundancy, wouldn't it suffice to turn the original function y(x) (which is what the standard Bresenham algorithm does) into two that go x(t) and y(t), and set the step-size of t to a small enough number to never skip a pixel?

tasty_freeze 9y ago
In the first case, then yes, you are taking care to avoid one of the problems a naive approach has. In the second case, you'll end up with blobby lines. For an x-major line, the standard algorithm would plot one pixel for every unit in X. With your approach, some x's would get one pixels, and some would get two (at adjacent y's on either side of the ideal y)
- vanderZwan 9y ago
  Ah true, you need some form of anti-aliasing for that, which would basically end up at something like Xiaolin Wu's algorithm. https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm