Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to draw ugly lines fast

cohost.org

Post reply on HN
Print view View original

21–30 of 47 posts

Re: How to draw ugly lines fast

#21

Post by fsloth »

OscarCunningham wrote: post #17

Is there a theoretical ideal of what line-drawing and anti-alliasing algorithms are aiming for? Is there a perfect line drawing algorithm you can use if you have the time?

There is a very good signal theoretic framework to discuss this.

You can start reading from example Alvy Ray Smith's "A pixel is not a little square" http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf

But in the end, the sampling kernel you choose to sample your line, and, what sort of geometric primitive your line is in the first place, defaults back to matters of taste so there is a very good theoretical basis for discussing all of this, but, there is no ultimate absolutely correct answer that it will provide.

Re: How to draw ugly lines fast

#22

Post by Sharlin »

scotty79 wrote: post #15
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?

I was confused about this too. What he means is fractionally accurate endpoints of the lines. So it's just about line endings coordinates not being exact integers.

And the reason why fractionally accurate endpoints matter is that they affect what exact pixels get drawn, which in turn makes animation look much smoother. Eg. a line that "crawls" from 0 to 6 as the endpoints move fractionally upward looks much less jittery than a line that's always 3.

    0 #
       #######

      ##
        ######

      ###
         #####
 
    3 ####
          ####

      #####
           ###

      ######
            ##

    6 #######
             #

Re: How to draw ugly lines fast

#23

Post by Agentlien »

soegaard wrote: post #20
Agentlien wrote: post #4

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?!"

Under his picure, you get the explanation. Tom Forsyth GPU designer and gfx coder Gfx coder and chip designer. Worked at Oculus, Valve, RAD, Muckyfoot, 3Dlabs, now back at Intel. Blade2, Larrabee, TF2, VR and many other atrocities.

Yes, I did read this. It was more a comment in appreciation of the humour of that opening. I suppose it makes sense if you take "every now and then" to be every few years rather than every few weeks, but it still sounded funny.

Re: How to draw ugly lines fast

#24

Post by jbay808 »

Just an aside, but in addition to graphics, this kind of thing is also relevant to motion control applications, where you have some kind of trajectory that you need to follow and must discretize it into a series of servo motor coordinate positions for the axes of (e.g.) an XY gantry.

This needs to be correct, and very fast -- sometimes the computational burden can limit your machine's top speed before the mechanical limitations are reached.

Re: How to draw ugly lines fast

#25

Post by riskable »

If the author is here (or notices this post) I found a typo in the article:

> "But in practice you can do significantly better, especially for lines that are nearly horziontal..."

I must say though, "horziontal" does sound fancy!

I signed up to make a comment about it in the article but it "takes a day or two" for the account to be allowed to comment :shrug:

Re: How to draw ugly lines fast

#26

Post by ripe »

riskable wrote: post #25

If the author is here (or notices this post) I found a typo in the article: > "But in practice you can do significantly better, especially for lines that are nearly horziontal..." I must say though, "horziontal" does sound fancy! I signed up to make a comment about it in the article but it "takes a day or two" for the account to be allowed to comment :shrug:

Love your observation! I hope the author never fixes his typo. I can always google this essay by "horziontal"!

Re: How to draw ugly lines fast

#27

Post by slingnow »

This is one of those articles that could benefit immensely with a single picture or quick video/gif, but provides neither.

> The other thing I need to do is subpixel-correct lines, because they're so much more nicer in motion than non-subpixel-correct lines. Don't confuse this with AA lines - you can have chunky non-AA single-colour pixel lines that are ALSO subpixel-correct.

> Why this is important is hard to convey in a static picture, but in motion the quality difference is very obvious. And it turns out the speed difference is not actually significant, so why not go for the extra quality?

This claim is made almost immediately in the article, but then provides no poof in picture OR video!

The breakdown of the algorithm and general writing is great though.

Re: How to draw ugly lines fast

#28

Post by rahimnathwani »

ripe wrote: post #26
riskable wrote: post #25

If the author is here (or notices this post) I found a typo in the article: > "But in practice you can do significantly better, especially for lines that are nearly horziontal..." I must say though, "horziontal" does sound fancy! I signed up to make a comment about it in the article but it "takes a day or two" for the account to be allowed to comment :shrug:

Love your observation! I hope the author never fixes his typo. I can always google this essay by "horziontal"!

That won't work. There are many pages containing that misspelled word :(

Re: How to draw ugly lines fast

#29

Post by Agentlien »

slingnow wrote: post #27

This is one of those articles that could benefit immensely with a single picture or quick video/gif, but provides neither. > The other thing I need to do is subpixel-correct lines, because they're so much more nicer in motion than non-subpixel-correct lines. Don't confuse this with AA lines - you can have chunky non-AA single-colour pixel lines that are ALSO subpixel-correct. > Why this is important is hard to convey…

I was a bit surprised by this. Unless this was originally meant to be printed I can't see why a simple animation couldn't have been included.

It's essentially pointing out the biggest issue with the article and then shrugging it off, while obviously putting a lot of effort into the writing.

Re: How to draw ugly lines fast

#30

Post by derefr »

danbruc wrote: post #8
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.

As long as the accumulated error is deterministic (i.e. you get the same wrong output given the same line), and that error is continuous over the field of possible lines, rather than jumping around (i.e. a line that sags to the left a bit, if translated by one subpixel, will still sag to the left a bit, rather than now sagging to the right), that'd be fine for what the author is trying to do, no? The lines just need to stay stable under animation rather than doing the https://tvtropes.org/pmwiki/pmwiki.php/Main/LineBoil thing.
Post reply on HN