The Beauty of Bresenham's Algorithm
members.chello.at
members.chello.at
More to the point: if you're doing anything but pure rasterising, something that requires anything more than a hash table lookup per cell, is it worth "doing it right"?
Note that this (and not raster display) was actually the problem Bresenham was describing in the 1965 paper.
Amusingly, the stock firmware for the Makeblock XY Plotter kit did not use Bresenham's algorithm-- and has horrible artifacts due to crazy rounding errors. Reimplementing Bresenham on a plotter does feel a bit like a trip to the past.
(I don't know if GPUs bother with it any longer. The OpenGL spec allows but does not mandate a Bresenham-based implementation, so tessellating into triangles is theoretically an option if they can make the diamond exit rule work. Games rarely use lines, but it wouldn't surprise me if they keep the hardware around for CAD software or whatever.)
Of course, how much of that is driver fakery and how much is actual hardware support can be debated, but there's surely some hardware support, otherwise it wouldn't be exposed in Vulkan which is supposed to be a thin layer.
EDIT: I just realised I'm not actually answering your pixels question, but a more generalised question of "when would we want to use this integer arithmetic method instead of floating point multiplication and division?"
As much as the rounding error of repeated addition matters - especially with cumulative addition. The comment by white-flame only regards this from the point of view of pixels, but there are many other applications where Bresenham's algorithm is the best solution. As described on Roman Black's website from 2001:
> Bresenham's Algorithm is a system where 2 imperfect periods can be alternated to produce an average that matches any "perfect" period.
https://www.romanblack.com/one_sec.htm
I probably don't have to convince you that this can still be a serious issue in embedded systems. The most obvious use-case would be long-running code where cumulative errors add up. A famous example of this going horribly wrong is the Patriot Missile disaster:
> It turns out that the cause was an inaccurate calculation of the time since boot due to computer arithmetic errors. Specifically, the time in tenths of second as measured by the system's internal clock was multiplied by 1/10 to produce the time in seconds. This calculation was performed using a 24 bit fixed point register. In particular, the value 1/10, which has a non-terminating binary expansion, was chopped at 24 bits after the radix point. The small chopping error, when multiplied by the large number giving the time in tenths of a second, led to a significant error. Indeed, the Patriot battery had been up around 100 hours, and an easy calculation shows that the resulting time error due to the magnified chopping error was about 0.34 seconds.
http://www-users.math.umn.edu/~arnold/disasters/patriot.html
Bresenham's Algorithm avoids this rounding error altogether (but it only works as long as you have a fixed numerator/denominator ratio - or if you really push it one denominator and a set of numerators).
EDIT2: Also, this does not just apply to repeat addition: calculating xp/k from scratch whenever x changes doesn't always work either. You can still get significan rounding errors if the intermediate calculation of xp is such a large number that it barely fits in a floating point.
Too late to edit that accidental markdown, so replying to myself
It's also where I learned that compiler maturity matters. Everyone else in the class used Turbo Pascal. I used the then-new Turbo C (yes, plain C), and ended up with 1/3 the performance of their code.
http://www.flipcode.com/archives/Theory_Practice-Issue_03_Cu...
http://www.flipcode.com/archives/Theory_Practice-Issue_00_In...
EDIT: Was it ever patented? Might be why people didn't use it.
EDIT2: I googled it, couldn't find any patents (except for other patents mentioning Bresenham's algorithm). However, the Run-Slice algorithm was published in 85, so it hasn't had as much time to become famous. Also, I found this article describing a newer algorithm from 1999 which looks pretty interesting too:
> Nowadays, most of research papers suggest improvements of the DDA method that was first presented by J. Bresenham. This paper proposes a new algorithm based on a careful analysis of the line segments’ properties some of them previously unused.
https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams...
ext = -(d<0);
d -= 2*dy;
y -= ext;
d += ext & (2*dx);
On the other hand, fixed point is better than Bresenham for the anti-aliased case present in the original article.
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).
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?
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)
The modifications required to make it work properly for subpixels are not hard; the question is still what axis the next step is; but I've never seen them described in an article.