6 ms·

Drawing Lines is Hard – an interactive look at GPU line rendering

123 points by mattdesl 12y ago

i_am_ralpht 12y ago
By some wonderful coincidence I need to implement antialiased line rendering this afternoon. Previously I'd done the 6-triangle method (but I also rasterized any kind of path with all sorts of fancy fills, and it made more sense for that). Thanks for such a clear write-up and all the links.
archagon 12y ago
I wish OpenVG/NV_path_rendering were more supported, especially on mobile platforms where they're needed the most. I'm making an app that involves hardware-accelerated line/path rendering and dealing with triangulation, color, batching, stroke vs. fill, patterns, etc. manually is a pain. Libraries like MonkVG and nanovg exist but they're a little half-baked at the moment.
- mrec 12y ago
  If anyone has seen the alpha spec and isn't under NDA, I'd be very interested to know whether OpenVG/NV_path_rendering could be efficiently implemented as libraries on top of Vulkan, given that it's a lot lower-level than GL. I remember from Mark Kilgard's notes that NV_path_rendering on top of the stock OpenGL pipeline wasn't feasible, which pretty much killed it for general usage. Fantastic functionality, but nobody outside NVIDIA was ever going to implement that extension; the thing was gigantic.
- dietrichepp 12y ago
  OpenVG has been thoroughly dead for a while now. I think the half-baked libraries are as good as you're going to get.
  - archagon 12y ago
    Yes, but it's a good idea. And there's plenty of software that relies on hardware-accelerated vectors: maps, browsers, animations, games, etc. The problem is that everyone has their own implementation!
eshyong 12y ago
Slightly off topic, I was messing around with the triangulated lines demo, and I get this rendering glitch: https://imgur.com/FPEaVTC https://imgur.com/FPEaVTC Anyone know the reason behind this? I'm guessing it's sort of triangle bounding error where something is being divided by a tiny divisor. It happens when I draw the snake in an arc, then retrace the arc from the same angle but in the opposite direction.
- delluminatus 12y ago
  He actually mentions it in the article: Note: a drawback that comes with miter-joined lines is sharp edges. When the angle connecting two segments is very sharp, the miter length grows exponentially toward infinity, and causes huge artifacts in rendering. In some applications this may not be a problem, in others you might want to limit the miter or fall back to another join (i.e. bevel) when the angle is too sharp.
  - eshyong 12y ago
    Awesome, thanks! I knew I should have read the article more closely.
  - jheriko 12y ago
    there is a solution to this called 'mitre limiting' its quite simple really. beyond a certain angle (dot product) threshold between adjacent segments you don't mitre the corner, but you 'cap' it, either with a simple triangle filling the gap, or with a fan to create a nice, rounded appearance.
- 0x0 12y ago
  Yeah, I get that a lot if I just wiggle left and right by a few pixels.
inDigiNeous 12y ago
Yeah, it is hard to do properly. Been looking into several different methods and implementations, and this is the one I went with on my project (missing from the article): Shader-Based Antialiased, Dashed, Stroked Polylines http://jcgt.org/published/0002/02/08/ http://jcgt.org/published/0002/02/08/ This is a very throughout implementation with many different drawing features and beautiful results. The actual implementation provided with the Python examples is a bit difficult to understand and not perhaps the most optimal, but still the paper and the theory behind it is one of the most comprehensive I've found.
- mattdesl 12y ago
  This looks great. I'm tempted to add it as another implementation. :)
  - Apofis 12y ago
    Do it!
- deleted 12y ago
  [deleted]
Vektorweg 12y ago
I wrote some animated SVG's in the past. It was often slow but good enough for most tasks. Quality was/is browser-dependent, but it worked well in overall. I'm not sure what people want to achieve. So, how well works Scalable Vector Graphics for you?
- jheriko 12y ago
  you need to render the SVG data somehow and the problem being discussed is how to achieve that. the format in which the strokes or shapes are stored is not relevant.
adamzegelin 12y ago
A good example (a little out of date now, circa 2003) showing invariance in OpenGL implementations across hardware: http://arek.bdmonkeys.net/bugs/invariance/index.html http://arek.bdmonkeys.net/bugs/invariance/index.html
jankins 12y ago
Another good article on this subject is https://www.mapbox.com/blog/drawing-antialiased-lines/ https://www.mapbox.com/blog/drawing-antialiased-lines/
lmeyerov 12y ago
It gets even more fun when you get into curves, or try to draw 1MM lines! (If this sounds like your cup of tea, message me :))
- eru 12y ago
  Are you hiring?
  - lmeyerov 12y ago
    Yep! Our fullstack / GPU / infrastructure spots are full (team of 5), but we've been holding two spots open here: * infoviz lead: handling design+impl of high-density data viz (imagine interacting with million node graphs). Coding-wise, clientside WebGL, D3, and serverside, node + c + opencl + our custom (GP)GPU cluster stack. It'll involve pushing what's possible in data viz, both in design & performance. * frontend lead: UX/app/product design, meaning JS/CSS/whatever frameworks you want to bring in (e.g., React). GL is not necessary, but you'll probably want to get your hands dirty. Msg build@graphistry.com and we can figure it out!
    - eru 12y ago
      Sounds interesting. I'm probably too dumb. But I referred a friend to your post!

123 points by mattdesl 12y ago

By some wonderful coincidence I need to implement antialiased line rendering this afternoon. Previously I'd done the 6-triangle method (but I also rasterized any kind of path with all sorts of fancy fills, and it made more sense for that). Thanks for such a clear write-up and all the links.

archagon 12y ago

I wish OpenVG/NV_path_rendering were more supported, especially on mobile platforms where they're needed the most. I'm making an app that involves hardware-accelerated line/path rendering and dealing with triangulation, color, batching, stroke vs. fill, patterns, etc. manually is a pain. Libraries like MonkVG and nanovg exist but they're a little half-baked at the moment.

mrec 12y ago
If anyone has seen the alpha spec and isn't under NDA, I'd be very interested to know whether OpenVG/NV_path_rendering could be efficiently implemented as libraries on top of Vulkan, given that it's a lot lower-level than GL. I remember from Mark Kilgard's notes that NV_path_rendering on top of the stock OpenGL pipeline wasn't feasible, which pretty much killed it for general usage. Fantastic functionality, but nobody outside NVIDIA was ever going to implement that extension; the thing was gigantic.
dietrichepp 12y ago
OpenVG has been thoroughly dead for a while now. I think the half-baked libraries are as good as you're going to get.
- archagon 12y ago
  Yes, but it's a good idea. And there's plenty of software that relies on hardware-accelerated vectors: maps, browsers, animations, games, etc. The problem is that everyone has their own implementation!

eshyong 12y ago

Slightly off topic, I was messing around with the triangulated lines demo, and I get this rendering glitch: https://imgur.com/FPEaVTC https://imgur.com/FPEaVTC Anyone know the reason behind this? I'm guessing it's sort of triangle bounding error where something is being divided by a tiny divisor. It happens when I draw the snake in an arc, then retrace the arc from the same angle but in the opposite direction.

delluminatus 12y ago
He actually mentions it in the article: Note: a drawback that comes with miter-joined lines is sharp edges. When the angle connecting two segments is very sharp, the miter length grows exponentially toward infinity, and causes huge artifacts in rendering. In some applications this may not be a problem, in others you might want to limit the miter or fall back to another join (i.e. bevel) when the angle is too sharp.
- eshyong 12y ago
  Awesome, thanks! I knew I should have read the article more closely.
- jheriko 12y ago
  there is a solution to this called 'mitre limiting' its quite simple really. beyond a certain angle (dot product) threshold between adjacent segments you don't mitre the corner, but you 'cap' it, either with a simple triangle filling the gap, or with a fan to create a nice, rounded appearance.
0x0 12y ago
Yeah, I get that a lot if I just wiggle left and right by a few pixels.

inDigiNeous 12y ago

Yeah, it is hard to do properly. Been looking into several different methods and implementations, and this is the one I went with on my project (missing from the article): Shader-Based Antialiased, Dashed, Stroked Polylines http://jcgt.org/published/0002/02/08/ http://jcgt.org/published/0002/02/08/ This is a very throughout implementation with many different drawing features and beautiful results. The actual implementation provided with the Python examples is a bit difficult to understand and not perhaps the most optimal, but still the paper and the theory behind it is one of the most comprehensive I've found.

mattdesl 12y ago
This looks great. I'm tempted to add it as another implementation. :)
- Apofis 12y ago
  Do it!
deleted 12y ago
[deleted]

Vektorweg 12y ago

I wrote some animated SVG's in the past. It was often slow but good enough for most tasks. Quality was/is browser-dependent, but it worked well in overall. I'm not sure what people want to achieve. So, how well works Scalable Vector Graphics for you?

jheriko 12y ago
you need to render the SVG data somehow and the problem being discussed is how to achieve that. the format in which the strokes or shapes are stored is not relevant.

adamzegelin 12y ago

A good example (a little out of date now, circa 2003) showing invariance in OpenGL implementations across hardware: http://arek.bdmonkeys.net/bugs/invariance/index.html http://arek.bdmonkeys.net/bugs/invariance/index.html

jankins 12y ago

Another good article on this subject is https://www.mapbox.com/blog/drawing-antialiased-lines/ https://www.mapbox.com/blog/drawing-antialiased-lines/

lmeyerov 12y ago

It gets even more fun when you get into curves, or try to draw 1MM lines! (If this sounds like your cup of tea, message me :))

eru 12y ago
Are you hiring?
- lmeyerov 12y ago
  Yep! Our fullstack / GPU / infrastructure spots are full (team of 5), but we've been holding two spots open here: * infoviz lead: handling design+impl of high-density data viz (imagine interacting with million node graphs). Coding-wise, clientside WebGL, D3, and serverside, node + c + opencl + our custom (GP)GPU cluster stack. It'll involve pushing what's possible in data viz, both in design & performance. * frontend lead: UX/app/product design, meaning JS/CSS/whatever frameworks you want to bring in (e.g., React). GL is not necessary, but you'll probably want to get your hands dirty. Msg build@graphistry.com and we can figure it out!
  - eru 12y ago
    Sounds interesting. I'm probably too dumb. But I referred a friend to your post!