How to draw ugly lines fast

This was wonderful to read. Informative, well explained, and humorous (the reference to "a pixel is not a little square" took me by surprise and made me laugh).

I feel like I've gotten a better understanding of things I thought I knew already. The only question left in my mind is "why does he always need to write new subpixel-accurate line drawers?!"

Re: How to draw ugly lines fast

#5

Post by SeasonalEnnui » Tue, Dec 20, 2022, 8:09 AM UTC

Is it possible to do a SIMD version?

I know compute shaders exist, but I have found that with huge datasets and a wide variety of end-user hardware, it tends to end up with many lines of code and brittleness. So I’m curious about high performance CPU-only implementations.

Re: How to draw ugly lines fast

#6

Post by wiz21c » Tue, Dec 20, 2022, 8:13 AM UTC

On old computers, you could go even faster by precomputing tiles representing little segments at various angles and then copying tiles. The trick here is to realize that you don't need many tiles to represent all the lines. The downside is that it's not quite accurate. But it's much faster. See an example here :

https://github.com/wiz21b/lowtech#the-3d

Re: How to draw ugly lines fast

#7

Post by userbinator » Tue, Dec 20, 2022, 8:35 AM UTC

I personally prefer the fixed-point algorithm for its simplicity and performance: https://news.ycombinator.com/item?id=9954975

Re: How to draw ugly lines fast

#8

Post by danbruc » Tue, Dec 20, 2022, 9:24 AM UTC

userbinator wrote: post #7

I personally prefer the fixed-point algorithm for its simplicity and performance: https://news.ycombinator.com/item?id=9954975

This one will however slowly drift away from the correct line as it accumulates the rounding error of the slope in each iteration. I am not sure what the worst case is and how long of a line you would have to draw to make a visible difference.

Re: How to draw ugly lines fast

#9

Post by IshKebab » Tue, Dec 20, 2022, 9:25 AM UTC

It would help if he defined what "subpixel accurate" means. I can't figure out why you'd care about subpixels if you're producing a bitmap image? Or is he doing something like cleartype but not antialiased?

Re: How to draw ugly lines fast

#10

Post by pubby » Tue, Dec 20, 2022, 9:33 AM UTC

IshKebab wrote: post #9

It would help if he defined what "subpixel accurate" means. I can't figure out why you'd care about subpixels if you're producing a bitmap image? Or is he doing something like cleartype but not antialiased?

The standard bressenham algorithm expects the start and end point of the line segment to be perfectly centered inside the grid. The modified version lets you put the start and end points anywhere.

For example, the standard algorithm would always generate lines that are symmetrical:

    ####
        ####

But the modified version lets you position the endpoints different, so that you'd get:

     ###
        #####

or

     ##
       ######

etc