GPU-Friendly Stroke Expansion | Hacker News Reader

GPU-Friendly Stroke Expansion

arxiv.org

180 pointsraphlinus39 comments

Gotta 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.

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.

Here's the full program: https://www.highperformancegraphics.org/2024/program/

(Disclosure: I'm on the HPG conference committee.)

Honestly, at first I read that as “Come for the HPV, stay for SIGGRAPH,” and thought that this sounded like one hell of a conference.

Oops, 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).

Happy to see the neverending fruits of using Euler spirals in place of Béziers. Very few people can boast of such influential phd work.

I'm curious whose phd work you are referring to?

By the same author https://levien.com/phd/phd.html

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.

[0] https://jsfiddle.net/y7m16wa0/

[1] 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...

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.

To visualise this, see this graphic: 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.)

> 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.

There already is: https://github.com/linebender/vello

Also see the comment by the author of the paper and library: https://news.ycombinator.com/item?id=40890270

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.

[1]: https://github.com/linebender/gpu-stroke-expansion-paper

Impressive! Thank you for the pointer

I heard that text rendering on GPU is hard, can the proposed approach pave the road to a reliable and widespread solution?

Have a look at line bender’s projects

https://linebender.org/

They are based on this work, Vello is the vector graphic rendering library and Xilem a high level ui framework.

just 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)

Fonts are defined as filled curves, not stroked curves, so this approach is not directly applicable to most text.

I believe metafont, created by Knuth for Tex, is an exception here in that it does use strokes.

Yes, 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....

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.

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.

1: https://hhoppe.com/proj/ravg/

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].

[1]: https://xi.zulipchat.com/#narrow/stream/260979-kurbo/topic/C...

Could anyone please explain what stroke expansion actually is either on high school or math undergrad level?

A 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?

Imagine 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.

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).

Does anyone know of ways to expand this towards 3D paths with consistent screen-space stroke width?

Look at the quadratic bezier fragment shader in https://hhoppe.com/proj/ravg/ might generalize well zo 3d.

Much simpler than the paper, but I have a 3D screen space implementation here[1].

[1] https://mattdesl.svbtle.com/drawing-lines-is-hard

I 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 is also nice.

Reply on news.ycombinator.com