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.
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.
If there is an explanation of that online, I'd be interested. I have a teenage girl who is interested in knitting, and I'd love to give her something work more math into it.
Not that I'm aware of. It was just something we figured out together.
It had something to do with partial rows that looped back on themselves to create wedges that increased the row count on one side of the garment versus the other. There was a need to create partial rows of different lengths to make sure the garment fanned correctly, but I don't know how she figured that part out. She was specifically attempting to create a garment where the rows ran 90 degrees to down the length of the garment, instead of across, to give a different texture.
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."
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.
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.
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.
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.
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.
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
17 comments
[ 4.0 ms ] story [ 39.3 ms ] threadhttps://news.ycombinator.com/item?id=4352943 (2012) 46 comments
https://news.ycombinator.com/item?id=15074080 (2017) 41 comments
It had something to do with partial rows that looped back on themselves to create wedges that increased the row count on one side of the garment versus the other. There was a need to create partial rows of different lengths to make sure the garment fanned correctly, but I don't know how she figured that part out. She was specifically attempting to create a garment where the rows ran 90 degrees to down the length of the garment, instead of across, to give a different texture.
https://observablehq.com/@mbostock/evenly-spaced-sampling
It’s just so elegant. Not only that, it has a bunch of non-graphics applications (eg projection onto any discrete codomain).
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
[1] [PDF] https://web.archive.org/web/20080528040104/http://www.resear...