5 ms·

Drawing Lines is Hard (2015)

109 points by lebek 10y ago

teddyh 10y ago
I thought this would be about Bresenham's line algorithm and its drawbacks.
- godmodus 10y ago
  2015 :P Cool writeup! It's amazing what lina can do.
- GregBuchholz 10y ago
  ...And I was thinking of something like: "How to draw a straight line" https://synthetica.eng.uci.edu/mechanicaldesign101/Kempe-Straight-Line.pdf https://synthetica.eng.uci.edu/mechanicaldesign101/Kempe-Str... https://en.wikipedia.org/wiki/Straight_line_mechanism https://en.wikipedia.org/wiki/Straight_line_mechanism
  - mauvehaus 10y ago
    I was also thinking this might be about how one draws a straight line. If you found those links interesting, you might also enjoy How Round is Your Circle[0]. Fun fact, Bosch's Axial Glide miter saw uses a Sarrus linkage rather than slides to generate it's straight line motion. I thought it was kind of a neat application for the oldest straight line linkage, especially since it didn't get much traction when it was first invented. It turns out for most application, a planar linkage is preferable. [0] https://www.amazon.com/How-Round-Your-Circle-Engineering/dp/0691149925/ref=sr_1_1?ie=UTF8&qid=1487426717&sr=8-1&keywords=how+round+is+your+circle https://www.amazon.com/How-Round-Your-Circle-Engineering/dp/...
- ChristianGeek 10y ago
  I actuallly thought it was going to be about setting boundaries in the workplace or something similar and was amused that it was actually about drawing lines. I'm interested in both topics, so it was still a win!
- userbinator 10y ago
  Bresenham is easily beaten in speed and simplicity by a fixed-point loop: https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams-algorithm/ https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams... Furthermore, fixed-point also allows antialiasing since it always gives how close the line is to the pixel being drawn.
  - lokedhs 10y ago
    This was the standard way to draw lines on the 68000 (the Atari ST for me). It's very fast thanks to the SWAP instruction. In fact, I've always thought that was what Bresenham was.
  - vanderZwan 10y ago
    > The naïve algorithm in float averages 4.81 µs, Bresenham’s algorithm averages at 1.84 µs, my fixed point variation at 1.74 µs. The Fixed point implementation runs about 5% faster. Which isn’t all that much, but still better than Bresenham’s; and much better than the naïve version using mixed floats and integers. > The situation is similar on the 64 bits machine, but the advantage of fixed point vanishes. Both methods takes very similar times: fixed point averages at 0.85 µs and Bresenham 0.84 µs, a difference of about 1%. However, the naïve implementation is still very far behind, at 2.96 µs. When you said "easily beaten" I kind of expected more than just a 1-5% performance improvement. There is also another (potential) problem with fixed point: it works by adding up rounded numbers: > The only thing we need, is to compute the slope m as a fixed point number rather than a floating point number. As a result, the fixed point might create rendering artefacts from adding up a rounded number repeatedly. This makes the whole thing an apples-to-oranges comparison: - floating point method that does multiply/divide every iteration - fixed point that adds a rounded fraction - Bresenham that does unrounded fraction adding by splitting the fraction into an accumulator and divisor (Bresenham is actually really simple primary school math with some geometry on top) To make a truly fair comparison, we should add a version that precomputes the floating point fraction, and adds that each iteration; I suspect the main slowdown of the naive floating point algorithm is the repeated multiply/divides more than the cast to integer, not the casts.
    - 10y ago
gens 10y ago
Xorg seems to agree.
- upofadown 10y ago
  Seeing as how the line drawing function in X doesn't do any anti-aliasing, the result would likely be very consistent across different environments even for fat lines. The problems to some extent are differences of opinion about how to make lines look pretty.
  - gens 10y ago
    Sorry, i meant that it is buggy. Specifically the line\* drawing functions. I filled a 22x22 window with segmented lines and it blanked the window. A line across the leftmost pixels on the window (x=0) behaves differently then anywhere else. And such. At least i think, as there is no hard spec on X11.
ghurtado 10y ago
A while back I made this prompted by a question in Stack Overflow: http://codepen.io/garciahurtado/pen/AGEsf http://codepen.io/garciahurtado/pen/AGEsf It is a less refined version of the techniques in the article, the approach is different in that it uses post-processing to provide the line thickness.
Kenji 10y ago
It's pretty much impossible to draw pixel-perfect lines in OpenGL. Even the library code of SDL2 fails to do it in certain instances, when its 2D drawing functions use OpenGL - and SDL2 is super clean and solid like a rock. Sometimes, you're even better off using images (!!) to draw lines. The sad thing is that Bresenham's line algorithm is so very simple. Somewhere between my program and the GPU, the communication of where exactly the line starts and ends is lost.
mcpherrinm 10y ago
I'm really glad to see this. I attempted to draw lines when first learning OpenGL and wasn't able to get results like I wanted.
dahart 10y ago
Drawing lines in OpenGL & 3d hardware in general has always had some of these issues. The best support for GL/OpenGL line drawing I knew of was in the more expensive SGI machines. (Capitalized on purpose to indicate before they rebranded lowercase -- but this is fuzzy memory and I'm no sgi history expert.) The cheaper ones' lines definitely weren't as good, but SGIs did have pretty nice line support back in the day, better than what you get in WebGL today. One thing I didn't see mentioned here is the line drawing API calls are typically not as well optimized as the triangle mesh calls, or so I've heard. Part of the reason good line drawing support was more expensive was (allegedly) only a few customers truly need antialiased lines with performance as good as the mesh API, and it's extra silicon, lines have specific needs not shared with meshes. FWIW, I've tried all these approaches in production and ended up just doing the meshing myself, and avoiding shader tricks. It's not that bad, it gives the most control, and once you have an abstraction for it, you don't need to think about it again.
- vvanders 10y ago
  For us screen space worked a bit better but I'm sure it varies by use case. Getting the right fall-off on non-aligned pixels is always tricky(including 0.5f offset in Direct3D).
paulddraper 10y ago
You can force MSAA in WebGL by using a larger canvas, and then downsizing it via CSS. Not sure the performance implications, but I use this frequently if MSAA is not natively supported.

109 points by lebek 10y ago

teddyh 10y ago

I thought this would be about Bresenham's line algorithm and its drawbacks.

godmodus 10y ago
2015 :P Cool writeup! It's amazing what lina can do.
GregBuchholz 10y ago
...And I was thinking of something like: "How to draw a straight line" https://synthetica.eng.uci.edu/mechanicaldesign101/Kempe-Straight-Line.pdf https://synthetica.eng.uci.edu/mechanicaldesign101/Kempe-Str... https://en.wikipedia.org/wiki/Straight_line_mechanism https://en.wikipedia.org/wiki/Straight_line_mechanism
- mauvehaus 10y ago
  I was also thinking this might be about how one draws a straight line. If you found those links interesting, you might also enjoy How Round is Your Circle[0]. Fun fact, Bosch's Axial Glide miter saw uses a Sarrus linkage rather than slides to generate it's straight line motion. I thought it was kind of a neat application for the oldest straight line linkage, especially since it didn't get much traction when it was first invented. It turns out for most application, a planar linkage is preferable. [0] https://www.amazon.com/How-Round-Your-Circle-Engineering/dp/0691149925/ref=sr_1_1?ie=UTF8&qid=1487426717&sr=8-1&keywords=how+round+is+your+circle https://www.amazon.com/How-Round-Your-Circle-Engineering/dp/...
ChristianGeek 10y ago
I actuallly thought it was going to be about setting boundaries in the workplace or something similar and was amused that it was actually about drawing lines. I'm interested in both topics, so it was still a win!
userbinator 10y ago
Bresenham is easily beaten in speed and simplicity by a fixed-point loop: https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams-algorithm/ https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams... Furthermore, fixed-point also allows antialiasing since it always gives how close the line is to the pixel being drawn.
- lokedhs 10y ago
  This was the standard way to draw lines on the 68000 (the Atari ST for me). It's very fast thanks to the SWAP instruction. In fact, I've always thought that was what Bresenham was.
- vanderZwan 10y ago
  > The naïve algorithm in float averages 4.81 µs, Bresenham’s algorithm averages at 1.84 µs, my fixed point variation at 1.74 µs. The Fixed point implementation runs about 5% faster. Which isn’t all that much, but still better than Bresenham’s; and much better than the naïve version using mixed floats and integers. > The situation is similar on the 64 bits machine, but the advantage of fixed point vanishes. Both methods takes very similar times: fixed point averages at 0.85 µs and Bresenham 0.84 µs, a difference of about 1%. However, the naïve implementation is still very far behind, at 2.96 µs. When you said "easily beaten" I kind of expected more than just a 1-5% performance improvement. There is also another (potential) problem with fixed point: it works by adding up rounded numbers: > The only thing we need, is to compute the slope m as a fixed point number rather than a floating point number. As a result, the fixed point might create rendering artefacts from adding up a rounded number repeatedly. This makes the whole thing an apples-to-oranges comparison: - floating point method that does multiply/divide every iteration - fixed point that adds a rounded fraction - Bresenham that does unrounded fraction adding by splitting the fraction into an accumulator and divisor (Bresenham is actually really simple primary school math with some geometry on top) To make a truly fair comparison, we should add a version that precomputes the floating point fraction, and adds that each iteration; I suspect the main slowdown of the naive floating point algorithm is the repeated multiply/divides more than the cast to integer, not the casts.
  - 10y ago

gens 10y ago

Xorg seems to agree.

upofadown 10y ago
Seeing as how the line drawing function in X doesn't do any anti-aliasing, the result would likely be very consistent across different environments even for fat lines. The problems to some extent are differences of opinion about how to make lines look pretty.
- gens 10y ago
  Sorry, i meant that it is buggy. Specifically the line\* drawing functions. I filled a 22x22 window with segmented lines and it blanked the window. A line across the leftmost pixels on the window (x=0) behaves differently then anywhere else. And such. At least i think, as there is no hard spec on X11.

ghurtado 10y ago

A while back I made this prompted by a question in Stack Overflow: http://codepen.io/garciahurtado/pen/AGEsf http://codepen.io/garciahurtado/pen/AGEsf It is a less refined version of the techniques in the article, the approach is different in that it uses post-processing to provide the line thickness.

Kenji 10y ago

It's pretty much impossible to draw pixel-perfect lines in OpenGL. Even the library code of SDL2 fails to do it in certain instances, when its 2D drawing functions use OpenGL - and SDL2 is super clean and solid like a rock. Sometimes, you're even better off using images (!!) to draw lines. The sad thing is that Bresenham's line algorithm is so very simple. Somewhere between my program and the GPU, the communication of where exactly the line starts and ends is lost.

mcpherrinm 10y ago

I'm really glad to see this. I attempted to draw lines when first learning OpenGL and wasn't able to get results like I wanted.

dahart 10y ago

Drawing lines in OpenGL & 3d hardware in general has always had some of these issues. The best support for GL/OpenGL line drawing I knew of was in the more expensive SGI machines. (Capitalized on purpose to indicate before they rebranded lowercase -- but this is fuzzy memory and I'm no sgi history expert.) The cheaper ones' lines definitely weren't as good, but SGIs did have pretty nice line support back in the day, better than what you get in WebGL today. One thing I didn't see mentioned here is the line drawing API calls are typically not as well optimized as the triangle mesh calls, or so I've heard. Part of the reason good line drawing support was more expensive was (allegedly) only a few customers truly need antialiased lines with performance as good as the mesh API, and it's extra silicon, lines have specific needs not shared with meshes. FWIW, I've tried all these approaches in production and ended up just doing the meshing myself, and avoiding shader tricks. It's not that bad, it gives the most control, and once you have an abstraction for it, you don't need to think about it again.

vvanders 10y ago
For us screen space worked a bit better but I'm sure it varies by use case. Getting the right fall-off on non-aligned pixels is always tricky(including 0.5f offset in Direct3D).

paulddraper 10y ago

You can force MSAA in WebGL by using a larger canvas, and then downsizing it via CSS. Not sure the performance implications, but I use this frequently if MSAA is not natively supported.