5 ms·
The Beauty of Bresenham's Algorithm (2016)
- bmn__ 6y agoPreviously: https://news.ycombinator.com/item?id=4352943 https://news.ycombinator.com/item?id=4352943 (2012) 46 comments https://news.ycombinator.com/item?id=15074080 https://news.ycombinator.com/item?id=15074080 (2017) 41 comments
- layoutIfNeeded 6y agohttps://web.archive.org/web/20210412072337/http://members.chello.at/easyfilter/bresenham.html https://web.archive.org/web/20210412072337/http://members.ch...
- bsenftner 6y agoI 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.
- moron4hire 6y agoIncidentally, 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.
- btilly 6y agoIf 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.
- moron4hire 6y agoNot 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.
- mettamage 6y agoIt’s quite easy to make a fun drawing app with Bresenham such as Google Jamboard.
- rgovostes 6y agoJust 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 https://observablehq.com/@mbostock/evenly-spaced-sampling
- cletus 6y agoYears 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).
- pfrench42 6y agoI use the algorithm for fast image resizing as well. The error term gives you the blend value for two adjacent pixels.
- bbbbbr 6y agoAlso 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 https://twitter.com/0xbbbbbr/status/1350982144450027525
- taylorius 6y agoAt 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.
- PythagoRascal 6y agoYou wouldn't happen to have a write-up about your modified algorithm somewhere?
- janci 6y agoI 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.
- ghusbands 6y agoAt 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.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf https://web.archive.org/web/20080528040104/http://www.resear...
- loopz 6y agoThis 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.
- AtomicOrbital 6y agoback 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