[pandaman]

Bresenham algorithms replaced expensive (at the time) floating point computation with fast (at the time) flow control. Nowadays it's exactly opposite: float is cheap and control is expensive so they only have historical value.

[userbinator]

Actually, what's really replaced Bresenham is fixed-point. Dead-simple and non-branchy code with less than a dozen instructions in the main loop. Floating-point is still not exactly as fast as integer arithmetic:

https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams...

[pandaman]

Fixed point is a good approach for line drawing but doing a sqrt for circles with integer arithmetics does not work really that well even if you don't know how to convert floats to ints fast (like author of the article you linked :)).

[clarry]

This one shows the branchy and branchless variations of bresenham being nearly equal in speed, within 5% on the older 32 bit CPU, with the branchy old school way being 1% faster on a more recent 64 bit CPU.

Both are significantly faster than the naive floating point version.

That is in line with my experience that floating point can still be quite slow on the CPU; the advantage from using fixed point isn't necessarily in avoiding branches (though it usually helps), but in avoiding floating point computation and conversion between floats & ints. Which is something something you have to deal with as soon as you're addressing memory or trying to pack data e.g. in video coding.

[pandaman]

Did you forget to add a link to your post or something? I repeat this for the final time: floating point can be quite slow but flow control is much slower. Also, fixed point square root is very slow compared to the FP one.

If you have a "brancheless bresenham" then go for it, I've never heard of such a thing so I'd be curious to see that link. But from the description it sounds like a contradiction to the Bresenham's idea.

[clarry]

See userbinator's link for a little performance comparison of the naive floating point code vs. bresenham vs. fixed point.

[pandaman]

There are many problems with that link. First of all - there is no "branchless bresenham" in it. Second - the author, while noticing that float to int conversion in his compiler is slow, decided not to do anything about it instead of doing a simple google search to find how to do it fast enough. Third - he is using 8087 FP instructions, which had been deprecated since late 90s. Fourth - he is essentially measuring function call (look what's happening in his inner loop). And fifth - he is not measuring other Bresenham's algorithms. I'd love to see how he does ellipses with fixed point.

[clarry]

We're still doing plenty of graphics on the CPU. For many applications, I'd prefer that it stay that way. And it doesn't seem like CPUs are becoming massively parallel anytime soon.

[pandaman]

The CPUs still had been doing floating point math much faster than flow control for the past 20 years or so.

[clarry]

Can you point me to relevant examples of line drawing or related things (e.g. triangle or polygon filling) that is faster to do in floating point (which may eventually need to convert to integer for addressing) than the old school way? Besides, it's not like the line drawing needs much in the control flow aside from a bit of setup and then a loop. Which you'll need with floating point too.

And if you're e.g. filling a triangle? Going the barycentric way, you have a relatively speaking big amount of floating point operations per pixel, in addition to the loop, plus some initial setup. And you might have to compare signs...

I don't believe it's faster. But I'm open to being shown wrong.

[pandaman]

Sure, go find a Bresenham line drawing first, verify that it does flow control for every step (a pixel) then compare it to the naive implementation (y = kx + a). Loops are not as expensive as what Bresenham does since even the simple branch prediction works fine for them and there are even better ways the CPU can deal with a loop on newer CPUs. Bresenham's switch is inherently unpredictable since it's comparing accumulated errors.

[alejohausner]

Back in the mid 80s I rediscovered a form of Bresenham on PDP-11 assembler that used integer overflow to avoid branches. I've forgotten the details, but I remember that it was integer only, and used an accumulator word which, on overflow, became a small number (somehow triggering a change in the dependent coordinate). Damn I wish I could remember the details. One of these days I'll dig up the assembler specs and re-derive it.

Or maybe I'll discover I was using a branch after all!

[pandaman]

The whole point of Bresenham is choosing between two integer values to minimize the accumulated error. You can totally implement any conditional computation without explicit conditional branch instructions e.g. using jump tables, conditional moves or predication etc. But the nature of your algorithm will remain conditional and a modern CPU still won't be able to process it as fast as a naive implementation.