5 ms·
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 t
by dreamcompiler 10y ago
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.
- pavlov 10y agoThe site focuses on raytracing, so it's all about 3D algorithms.
- dreamcompiler 10y agoFair enough.
- padator 10y ago99% 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 10y agoOur 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/ http://w3.impa.br/~diego/projects/GanEtAl14/
- dahart 10y agoI'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 10y agoSadly 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 10y agoThere are still uses for software 3d rendering. Some modern game engines for example use it for lighting or culling purposes.
- deleted 10y ago[deleted]
- dreamcompiler 10y agoNo 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.
- pandaman 10y agoBresenham 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.
- clarry 10y agoWe'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 10y agoThe CPUs still had been doing floating point math much faster than flow control for the past 20 years or so.
- clarry 10y agoCan 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 10y agoSure, 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.