[dreamcompiler]

Maybe I missed it, but I didn't see any discussion of the Bresenham family of algorithms. I realize this is always done for you nowadays, but if you're really teaching pixels from scratch, it seems like drawing lines and circles from raw pixels needs to be covered.

[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.

[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!

[pavlov]

The site focuses on raytracing, so it's all about 3D algorithms.

[dreamcompiler]

Fair enough.

[padator]

99% of the computer graphics you see on your screen everyday are made of simple lines, circles, curves, and text in 2D. 3D is useful mostly for games, movies, and CAD software. I don't understand this over focus on 3D. I think the latest edition of "Computer Graphics: principles and practice" does not even teach bresenham anymore. This seems wrong to me.

[jacobolus]

Our current CPU-based 2D vector graphics rendering pipelines are completely unmatched to modern hardware. They’re lumbering decades-old dinosaurs with poor render quality (full of nasty visual artifacts) and ridiculously slow speed compared to the possibilities on a GPU (or even compared to better-cache-optimized CPU algorithms, frankly).

I really wish everyone would move toward something like this instead: http://w3.impa.br/~diego/projects/GanEtAl14/

[dahart]

I'm only arguing for fun, and because I love 3d graphics, don't take this personally. I'm upvoting your comment to offset my argumentative reply. :)

You say 'games and movies' like those are niche markets. You can't watch any TV without seeing 3d graphics. And chances are you see a lot more 3d on your computer than you think while you work. Windows, Mac OSX, & Linux all have 3d hardware accelerated windowing features for task switching, virtual desktops, and lots of other fun tidbits. Plus, you might not be playing enough games, if you play games less than 1% of your time.

I'm not sure who's over focused on 3d, but it'd be pretty weird to put together a site like scratchapixel.com without 3d.

Finally, Bresenham's algorithm has historical significance, but is no longer generally useful, even for line drawing. Maybe if it's gone from CGP&P, that's a clue? Aliased, single pixel wide lines are almost never used. If you want soft edges or thick lines or curves or texture, you're a lot better off focusing on polygons from the start.

[tdicola]

Sadly if you're actually implementing Bresenham's algorithm today you're doing something very wrong (or don't care about performance). Drawing lines and shapes is all a matter of pumping the desired geometry and shaders into your GPU today and letting it take care of the rasterization--running Bresenham's algorithm on your CPU will be many orders of magnitude slower.

[Narishma]

There are still uses for software 3d rendering. Some modern game engines for example use it for lighting or culling purposes.

[dreamcompiler]

No argument. That's why I said I realized this was always done for you today. But somebody had to build and program that GPU, and for those of us who care about such details, it would be nice to learn how rasterization works in a GPU. I had assumed that GPUs were still using Bresenham-like DDAs, but I learned from the above discussion that fixed-point non-branching algorithms may have become more common.