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

31–40 of 47 posts

Re: How to draw ugly lines fast

#31

Post by danbruc »

derefr wrote: post #30
danbruc wrote: post #8

Earlier quoted context omitted.

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…

Well, it is deterministic and all but I like my lines to connect the points I specify and not end at nearby ones. A line from (0, 0) to (90, 70) has a slope of 7/9. If you represent that with one fractional digit as 0.8 and then on each step just add 0.8 to the y coordinate, you will end up at (90, 72). If you want to reach (900, 700) you will end up at (900, 720). Two fractional digits will get you to (900, 702), three will make you actually land on (900, 700), but not exactly but (900, 700.2). And even then some pixels might not be in the correct place.

In the right circumstances this might all be fine and work well enough if you have enough precision for the fractional part, but this is no algorithm that I would recommend to anyone.

Re: How to draw ugly lines fast

#32

Post by brianpaul »

jbay808 wrote: post #24

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…

Bresenham originally developed the algorithm for drawing lines with a plotter (servos).

Re: How to draw ugly lines fast

#33

Post by jffhn »

>It can be done entirely with integer arithmetic.

It's true when first and last points are within or not too far from the screen/clip, but if wanting to draw a long line (if coords are 32 bits ints) that's mostly out of it and don't want clipping to introduce half a pixel size errors/inconsistencies, unless running Bresenham for a long time out of the clip, floating points are a more accurate tool to do the clipping and the drawing.

See for example: https://github.com/jeffhain/jolikit/blob/master/src/main/jav...

[edit: it might actually be possible to jump to the clipped area while staying in integers and not loose accuracy, but I don't recall why I didn't try that]

Re: How to draw ugly lines fast

#34

Post by dahart »

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?

I’d say no because there are different goals that can be incompatible, i.e., “perfect” is not well defined. This article’s focus is on accuracy and speed but not visual quality. Antialiasing goes for visual quality and sometimes speed, but most techniques land in an area that balances those or leans a bit one way or the other, while very few techniques are achieving the known maxima of either, let alone both at the same time.

Sibling comment mentions the famous paper “A Pixel is Not a Little Square”. The implication being that using squares when computing analytic coverage for antialiasing is not “perfect”. The problem is we don’t have a single definition of perfect, because it depends on what display device you’re using. CRTs and LCDs and printers all have completely different ‘pixels’, so no single solution exists that works for all of them. Combine that with the fact that getting close to perfect for any given device is very computationally expensive, and you can see why we don’t usually even shoot for perfect.

Re: How to draw ugly lines fast

#35

Post by derefr »

danbruc wrote: post #31
derefr wrote: post #30

Earlier quoted context omitted.

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…

Well, it is deterministic and all but I like my lines to connect the points I specify and not end at nearby ones. A line from (0, 0) to (90, 70) has a slope of 7/9. If you represent that with one fractional digit as 0.8 and then on each step just add 0.8 to the y coordinate, you will end up at (90, 72). If you want to reach (900, 700) you will end up at (900, 720). Two fractional digits will get you to (900, 702), th…

Can you avoid the error — without needing to use higher-precision math for every step — by 1. using higher-precision math only to calculate some control points along the line; and then 2. partitioning long lines into smaller overlapping lines that connect at the control points; so that you can then 3. draw those short lines with the cheap algorithm?

Re: How to draw ugly lines fast

#36

Post by zozbot234 »

jffhn wrote: post #33

>It can be done entirely with integer arithmetic. It's true when first and last points are within or not too far from the screen/clip, but if wanting to draw a long line (if coords are 32 bits ints) that's mostly out of it and don't want clipping to introduce half a pixel size errors/inconsistencies, unless running Bresenham for a long time out of the clip, floating points are a more accurate tool to do the clipping…

The drawing actually needs arbitrarily high precision in the worst case. Consider a nearly horizontal line segment spanning the whole viewport where the endpoints' y coordinates are arbitrarily close to the boundary line between two pixels, on either side. You've got to decide (1) where to put the endpoints, and (2) where to split the line segment if the endpoints end up being placed at differently rounded y coordinates. Both steps might require high precision, and for either of them it might be computationally infeasible to get an exact result. (The latter step depends on a ratio of arbitrarily small subpixel deltas, and bounding such a ratio exactly is what might be infeasible.)

Re: How to draw ugly lines fast

#37

Post by ErikCorry »

wiz21c wrote: post #6

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

Why 7x7 tiles? Is 8x8 not a much more natural size?

Re: How to draw ugly lines fast

#38

Post by ebjaas_2022 »

rahimnathwani wrote: post #28
ripe wrote: post #26

Earlier quoted context omitted.

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 :(

44200 hits on Google, for that particular misspelling.

Re: How to draw ugly lines fast

#39

Post by moloch-hai »

Agentlien wrote: post #29
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.

That would be extra work, maybe enough the article would not be published. I will take what we got.

Or you could post GIFs yourself. Maybe that seems like too much work?

Re: How to draw ugly lines fast

#40

Post by Agentlien »

moloch-hai wrote: post #39
Agentlien wrote: post #29

Earlier quoted context omitted.

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.

That would be extra work, maybe enough the article would not be published. I will take what we got. Or you could post GIFs yourself. Maybe that seems like too much work?

I am very happy with what we got, as I wrote in another comment. I still find it strange that the author would go out of his way to write the article, produce screenshots, write multiple times how it's hard to explain or show without an animation, yet not record one.

Asking whether I'm willing to provide my own gif isn't quite a fair measure. The author has the code running and he himself commented on the need for moving pictures. I have partial code and no personal investment in this.

I have however written a few articles about stuff I've done for my own work and wherever it seemed relevant I've taken the time to produce and include video. That's been a lot less effort than writing the text, even when it's required a number of changes in the scenes and code.

Post reply on HN