The Beauty of Bresenham's Algorithm (2016)

Just the other day, @mbostock posted this: "Given an array of length n, how would you select m ≤ n evenly-spaced samples from the array? Surprise: you can use Bresenham’s line algorithm."

https://observablehq.com/@mbostock/evenly-spaced-sampling

I learned 3D graphics in the 80's, when it was research by a Prof. Glenn Bresenham at Boston University. He is an extremely gifted computer scientist, but is not THAT Brensnham. Regardless, when our graphics lab would attend conferences like SIGGRAPH we'd let people assume he was THE Bresenham and have a lot of fun.

At university, I became obsessed with Bresenham's algorithm (I was great fun at parties). I managed to adapt it to render hyperbolic functions, which are used in perspective correct texture mapping (this was back in the days before gpus). This gave a division free algorithm for perspective correct texture mapping, which was something of a holy grail at the time. Then GPUs arrived and made the whole thing moot - still, it was good fun.

Incidentally, I recently taught Bresemham's and the accumulation of error technique in general to my mother, so she could make more complex knitting patterns all while just counting in her head.

Also handy for smooth palette fades using only integers.

It makes it easy to do linear interpolation (lerp) between two RGB colors (or in another color space if you want better color consistency during transition). The transition between each component gets be spaced out over a constant duration regardless of how little integer difference there actually is.

I used this approach to add a color fade transition effect for a Game Boy color puzzle game (made using GBDK). GIF of the effect here: https://twitter.com/0xbbbbbr/status/1350982144450027525

I use the algorithm for fast image resizing as well. The error term gives you the blend value for two adjacent pixels.

back in 1991 I took an assembly language course where we where given boilerplate code on how to draw a point on the screen with a two week assignment to do anything graphical ... for the first 5 days I battled to implement Bresenham's Algorithm so I could draw a line segment ... once working the sky's the limit ... I handed in assembly lang code which drew a stick figure which held up a banner of the university ... it then drew same figure with arms and legs at a half step apart which I animated so it appeared to walk across the screen ... to give it some pizazz I had the stick figure walk around a circle and implemented perspective projection so it become shorter when walking toward the back side of the circle and larger as it approached the front ... with ability to draw a line one can unleash unbounded potential

Previously:

https://news.ycombinator.com/item?id=4352943 (2012) 46 comments

https://news.ycombinator.com/item?id=15074080 (2017) 41 comments

At least the first 2d line drawing given isn't Bresenham's algorithm [1]. Bresenham's is specialised to a particular octant and only requires one comparison inside the loop (which amounts to an overflow check). The algorithm given in the article will necessarily be significantly slower. The same applies to many other forms in the article.

[1] [PDF] https://web.archive.org/web/20080528040104/http://www.resear...

I used this once to precisely derive one-second clock signal from system clock on a MCU. Usually you use 32.768kHz crystal because it divides nicely to 1 Hz. I did not have it available and needed to use sytem clock that was not very precise nor a power of 2.

Years ago in a graphics programming class I learned the algorithms for rasterizing lines and circles (ie Bresenham’s) and it was honestly amazing.

It’s just so elegant. Not only that, it has a bunch of non-graphics applications (eg projection onto any discrete codomain).

This was gold at a time where using fixed point long calculations made sense. Today you'd probably just calculate with doubles and division and be done with it.

It’s quite easy to make a fun drawing app with Bresenham such as Google Jamboard.