> The naïve algorithm in float averages 4.81 µs, Bresenham’s algorithm averages at 1.84 µs, my fixed point variation at 1.74 µs. The Fixed point implementation runs about 5% faster. Which isn’t all that much, but still better than Bresenham’s; and much better than the naïve version using mixed floats and integers.
> The situation is similar on the 64 bits machine, but the advantage of fixed point vanishes. Both methods takes very similar times: fixed point averages at 0.85 µs and Bresenham 0.84 µs, a difference of about 1%. However, the naïve implementation is still very far behind, at 2.96 µs.
When you said "easily beaten" I kind of expected more than just a 1-5% performance improvement.
There is also another (potential) problem with fixed point: it works by adding up rounded numbers:
> The only thing we need, is to compute the slope m as a fixed point number rather than a floating point number.
As a result, the fixed point might create rendering artefacts from adding up a rounded number repeatedly. This makes the whole thing an apples-to-oranges comparison:
- floating point method that does multiply/divide every iteration
- fixed point that adds a rounded fraction
- Bresenham that does unrounded fraction adding by splitting the fraction into an accumulator and divisor (Bresenham is actually really simple primary school math with some geometry on top)
To make a truly fair comparison, we should add a version that precomputes the floating point fraction, and adds that each iteration; I suspect the main slowdown of the naive floating point algorithm is the repeated multiply/divides more than the cast to integer, not the casts.
Now that you mention it, I know the basic "add/sub is faster than multiply is much faster than divide" order, but I have no idea how it compares to casts.. why isn't that ever mentioned anywhere?
I'm guessing for the same reason casts are slow; they're not bottlenecks for the most common number crunching workloads, so it doesn't occur to anyone they might be bottlenecks for somewhat less common ones.
I was also thinking this might be about how one draws a straight line. If you found those links interesting, you might also enjoy How Round is Your Circle[0].
Fun fact, Bosch's Axial Glide miter saw uses a Sarrus linkage rather than slides to generate it's straight line motion. I thought it was kind of a neat application for the oldest straight line linkage, especially since it didn't get much traction when it was first invented. It turns out for most application, a planar linkage is preferable.
I actuallly thought it was going to be about setting boundaries in the workplace or something similar and was amused that it was actually about drawing lines. I'm interested in both topics, so it was still a win!
