> 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.
If 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.
I'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.
There'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.
To 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.
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.)
> This is something that Adobe Illustrator could do 20 years ago
... and Metafont could do over 40 years ago. Part of the problem might be that finding a good class of curves closed under convolution (that’s the general term for this kind of thing) remains a research problem, thus not really something you see in open formats (including e.g. PostScript—part of why converting Metafont to more conventional vector formats is difficult). But it’s the first time I (an amateur) am seeing Levien’s thesis mentioned in this context, so I’ll have to check that out.
Stroke 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.
Only 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.
Fascinating, 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.?
Good 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.
The 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.
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....
Looks 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.
If 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!
Google 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.
In 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?
So 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].
Do 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.
Yes, 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
+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).
> 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.