[HN Gopher] The Beauty of Bresenham's Algorithm (2016)
       ___________________________________________________________________
        
       The Beauty of Bresenham's Algorithm (2016)
        
       Author : ingve
       Score  : 90 points
       Date   : 2021-04-12 10:17 UTC (1 days ago)
        
 (HTM) web link (members.chello.at)
 (TXT) w3m dump (members.chello.at)
        
       | cletus wrote:
       | 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).
        
       | bsenftner wrote:
       | 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.
        
       | mettamage wrote:
       | It's quite easy to make a fun drawing app with Bresenham such as
       | Google Jamboard.
        
       | janci wrote:
       | 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.
        
       | bmn__ wrote:
       | Previously:
       | 
       | https://news.ycombinator.com/item?id=4352943 (2012) 46 comments
       | 
       | https://news.ycombinator.com/item?id=15074080 (2017) 41 comments
        
       | ghusbands wrote:
       | 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...
        
       | bbbbbr wrote:
       | 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
        
       | rgovostes wrote:
       | 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
        
       | taylorius wrote:
       | 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.
        
         | PythagoRascal wrote:
         | You wouldn't happen to have a write-up about your modified
         | algorithm somewhere?
        
       | pfrench42 wrote:
       | I use the algorithm for fast image resizing as well. The error
       | term gives you the blend value for two adjacent pixels.
        
       | moron4hire wrote:
       | 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.
        
         | btilly wrote:
         | 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.
        
       | layoutIfNeeded wrote:
       | https://web.archive.org/web/20210412072337/http://members.ch...
        
       ___________________________________________________________________
       (page generated 2021-04-13 23:02 UTC)