8 ms·
GPU-Friendly Stroke Expansion
- mehmetoguzderin 2y agoFascinating, to say the least, especially considering the execution time in comparison to the best CPU result. I might be skimming too fast, but are there also CPU timings for stress test scenes in the paper, including mmark, etc.?
- raphlinus 2y agoGood catch! We took the mmark CPU numbers out (in response to review feedback) because they made the graphs hard to read, but it scales very much the same way as the Nehab timings dataset. The raw CPU numbers for mmark are in the repo[1] in the "timings" file. [1]: https://github.com/linebender/gpu-stroke-expansion-paper https://github.com/linebender/gpu-stroke-expansion-paper
- mehmetoguzderin 2y agoImpressive! Thank you for the pointer
- montroser 2y agoStroke expansion is one of those things that initially seems obvious and intuitive, but then turns out to be wildly complex once you embark upon handling all of the many edge cases.
- azeirah 2y agoIf this is novel and as reliable as I feel like they're claiming it to be, then this might be really big for svg-rendering in the web, absolutely amazing!
- Klaster_1 2y agoI heard that text rendering on GPU is hard, can the proposed approach pave the road to a reliable and widespread solution?
- iTokio 2y agoHave a look at line bender’s projects https://linebender.org/ https://linebender.org/ They are based on this work, Vello is the vector graphic rendering library and Xilem a high level ui framework.
- homarp 2y agojust to be clearer: Line Bender organization was started by Raph Levien, and he informally leads and drives the work forward. And he is the first author of the paper (and he is also commenting in this same thread)
- mkl 2y agoFonts are defined as filled curves, not stroked curves, so this approach is not directly applicable to most text.
- marhee 2y agoI believe metafont, created by Knuth for Tex, is an exception here in that it does use strokes.
- WillAdams 2y agoYes, so long as one wants pixels. I'd give my interest in Hell for a graphical interface for METAFONT which would take a series of pen strokes and provide the outline --- which reminds me that I never heard back from the METAFOG author on a license....
- raphlinus 2y agoThe technique works for both fills and strokes, and is used by Vello for both, including for the text rendering. One of the nice things we found is that lowering Euler spirals to arcs works particularly well, and you need many fewer arc segments than line segments to accurately approximate a smooth curve. We haven't plumbed arcs all the way through the rendering pipeline yet, but it's planned; the math for rendering arcs is not that much more complicated than lines.
- erwinh 2y agoDoes anyone know of ways to expand this towards 3D paths with consistent screen-space stroke width?
- posix86 2y agoLook at the quadratic bezier fragment shader in https://hhoppe.com/proj/ravg/ https://hhoppe.com/proj/ravg/ might generalize well zo 3d.
- mattdesl 2y agoMuch simpler than the paper, but I have a 3D screen space implementation here[1]. [1] https://mattdesl.svbtle.com/drawing-lines-is-hard https://mattdesl.svbtle.com/drawing-lines-is-hard
- amitp 2y agoI love this page. Thank you. I bookmarked it in 2018 but still haven't used it, doh! https://wwwtyro.net/2019/11/18/instanced-lines.html https://wwwtyro.net/2019/11/18/instanced-lines.html is also nice.
- enriquto 2y agoHappy to see the neverending fruits of using Euler spirals in place of Béziers. Very few people can boast of such influential phd work.
- spencerchubb 2y agoI'm curious whose phd work you are referring to?
- enriquto 2y agoBy the same author https://levien.com/phd/phd.html https://levien.com/phd/phd.html
- posix86 2y agoLooks interesting! Another interesting paper on this subject is 1. They seem to have a different approach; the one I reference uses a quadratic bezier approximation that is fast for random access graphics such as fragment shaders. This is very useful for having screen space constant width shapes in 2- or 3d space, skimming the paper that appears to require much more preprocessing. 1: https://hhoppe.com/proj/ravg/ https://hhoppe.com/proj/ravg/
- djoldman 2y agoGotta like: > Stroke expansion is a global problem, with challenging constraints on continuity and correctness. Nonetheless, we implement it using a fully parallel algorithm suitable for execution in a GPU compute shader, with minimal preprocessing. It's hard but we did it anyway.
- amelius 2y agoI'd like to see calligraphic paths. I.e., you have some primitive like an ellipse that you move along a path while keeping its orientation fixed wrt the coordinate system. This is something that Adobe Illustrator could do 20 years ago, but is still not possible in Inkscape. I.e., you select a path, set a calligraphic pen on it, and then optionally covert the stroke to its outline path.
- a_e_k 2y agoThere's a relatively straightforward trick that you can do here. If you've got a transform that turns a circle into an ellipse with the relative radii and orientation that you want, then: 1. Apply the inverse of that transform to your path. 2. Stroke the path. 3. Apply the transform to the result. This way, the path stays in place but the stroke is transformed to give it a calligraphic look. With a JavaScript Canvas, you can just set the transform after defining the path, but before stroking. JSFiddle example: [0]. (This was something that I tested in my tiny, single-header <canvas>-like 2D rasterizer library for C++ and my Javascript port of its test suite [1].) For Inkscape, I think you can convert an object to a path, apply the inverse transform, do a minimal simplification to bake the transform into the path, stroke it, and then apply the forward transform. It's a bit clumsy, but I bet someone could easily create an extension script to do it. [0] https://jsfiddle.net/y7m16wa0/ https://jsfiddle.net/y7m16wa0/ [1] https://github.com/a-e-k/canvas_ity/blob/main/test/test.cpp#L399 https://github.com/a-e-k/canvas_ity/blob/main/test/test.cpp#..., https://github.com/a-e-k/canvas_ity/blob/main/test/test.html#L210 https://github.com/a-e-k/canvas_ity/blob/main/test/test.html...
- quitit 2y agoTo elaborate on the earlier point about Illustrator from amelius. Illustrator's stroke control is a touch more advanced than most people are aware in that there is full control over the width of the stroke at any point on the line and that includes the ability to independently adjust the width on either side of the path. That's especially useful for emulating handwork or script without forcing the object into a less editable format such as a filled shape. To visualise this, see this graphic: https://imgur.com/a/303dgSf https://imgur.com/a/303dgSf The black thin line is a basic stroke to visualise the path. The light blue area is the stroke with edits to the stroke width showing how each side of the path can be controlled independently. I have kept the tool selection active such that a wireframe overlay is visible to help demonstrate how the stroke width is different on either side of the line. The last area in the graphic is the pink area. The pink is another stroke applied to the same path. In fact all 3 strokes you see are all attached to one path. Illustrator allows a path to carry multiple strokes, and those stroke profiles be independent from one another. Side note: This stroke-width information can then be applied to other strokes, and also saved for later use. (Handy if you want a custom swash pack.)
- martin293 2y agoCould anyone please explain what stroke expansion actually is either on high school or math undergrad level?
- djoldman 2y agoA path is a line with zero or more curves, finite length, and zero width. A stroked path is a path with a non-zero width. Stroke expansion is going from a path to a stroked path. Turns out that the math is quite complex. I'm in search of a precise and consensus definition of a path with non-zero width... does anyone know where that is in the svg spec?
- scotty79 2y agoImagine basic graphics program. Stroke expansion is how you go from a line drawn with a pencil to the one drawn with some brush. It's how you go from drawing 1px width line to drawing paint covered area left by some brush following this line.
- helf 2y ago[dead]
- robinduckett 2y agoOnly last week I was trying to find out how to draw a dashed stroke on a path without needing a separate draw call for each dashed segment. I hope someone makes a library that uses this technique, it may be slightly beyond my abilities to implement myself.
- Simran-B 2y agoThere already is: https://github.com/linebender/vello https://github.com/linebender/vello Also see the comment by the author of the paper and library: https://news.ycombinator.com/item?id=40890270 https://news.ycombinator.com/item?id=40890270
- YmiYugy 2y agoIn the comparison it seems like Skia is quite a bit faster on the CPU than your solution, but at the cost of some robustness. Is this actually something that matters for typical applications like web browsers or UI toolkits?
- raphlinus 2y agoSo this is a little bit more complicated as a tradeoff. The main reason Skia is faster is that it's generating fewer primitives (quadratic Béziers instead of lines or arcs). Depending on the details of the renderer, you may also want to lower to a simpler primitive, and our method does both. If the goal is lines, then the additional cost of applying, say, Wang's method would make them take roughly the same runtime, though our method would produce fewer lines. If the goal is arcs, then I think our method comes out way ahead, as I'm not aware of anything else that generates arcs efficiently. But it does mean that for outline-to-outline applications running on the CPU, methods like Skia's are likely better (though ours is still faster than the Nehab implementation). I'm working on a cubic-to-cubic version also, but it's requiring some pretty deep math. See the Zulip thread to follow that work in progress[1]. [1]: https://xi.zulipchat.com/#narrow/stream/260979-kurbo/topic/Chebyshev.20perturbation.20for.20cubic.20B.C3.A9zier.20parallel.20curves https://xi.zulipchat.com/#narrow/stream/260979-kurbo/topic/C...
- YmiYugy 2y agoDo you have a rough idea whether doing this on the GPU is worth it on mobile devices with regards to energy consumption? I imagine many typical web and UI toolkit uses of this aren't limited by raw performance.
- refulgentis 2y agoYes, but only from first principles, and my first rule is always "measure it, then explain it, lest you look foolish". TL;DR: 100% worth it (claim to knowledge: from time on Android watches, incl. building an automated power testing framework at Google, left in October) - Power cost optimization is found by handwaving avoiding something spinning up, or due to very long actions (i.e. 5+ seconds) - The GPU is already running if a frame is due to be rendered. - If we're running drawing code that draws a stroke, a frame is due to be rendered. Therefore the additional cost to run the stroke render can be considered infinitesimal - Its unintuitive how much power savings can be achieved by "racing to zero" (i.e. doing something faster) - The algorithm is a better racer to zero because it runs in parallel
- raphlinus 2y ago+1 to always measuring. That said, we have done some experiments regarding power, including on Android, and it looks favorable. The general rule of thumb is that a GPU has about 10x the raw throughput per joule as a CPU (which, today, is basically the same metric as throughput per dollar). So if your GPU is only barely faster than the CPU because of overheads of the parallel algorithm, you might not win, but if it sails way past the CPU because it's work efficient and lean (as I believe this work is), you do win both on power and throughput (frames per second).
- DLoupe 2y agoOops, he did it again. Congrats Raph, and thanks - your work and your writing have been an inspiration to me for my entire career (~25 years).
- aappleby 2y agoGoogle Maps does stroke expansion in WebGL 1 vertex/pixel shaders. The vertex shader converts a linear path-segment "instance" into a quad with correctly beveled/extended endpoints, the pixel shader does some normalization and distance-field-esque math (there's no actual distance field texture) to produce analytically antialiased line segments with circular caps.
- a_e_k 2y agoIf you're interested in this, let me also plug the High Performance Graphics 2024 conference where this paper was accepted and will be presented at the end of the month. It'll be co-located with SIGGRAPH 2024 in Denver, CO. Come for HPG, stay for SIGGRAPH. Here's the full program: https://www.highperformancegraphics.org/2024/program/ https://www.highperformancegraphics.org/2024/program/ (Disclosure: I'm on the HPG conference committee.)
- nativeit 2y agoHonestly, at first I read that as “Come for the HPV, stay for SIGGRAPH,” and thought that this sounded like one hell of a conference.