[HN Gopher] GPU-Friendly Stroke Expansion
___________________________________________________________________
GPU-Friendly Stroke Expansion
Author : raphlinus
Score : 162 points
Date : 2024-07-02 13:27 UTC (4 days ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| mehmetoguzderin wrote:
| 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.?
| raphlinus wrote:
| 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
| mehmetoguzderin wrote:
| Impressive! Thank you for the pointer
| montroser wrote:
| 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.
| azeirah wrote:
| 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!
| Klaster_1 wrote:
| I heard that text rendering on GPU is hard, can the proposed
| approach pave the road to a reliable and widespread solution?
| iTokio wrote:
| 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.
| homarp wrote:
| 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)
| mkl wrote:
| Fonts are defined as filled curves, not stroked curves, so this
| approach is not directly applicable to most text.
| marhee wrote:
| I believe metafont, created by Knuth for Tex, is an exception
| here in that it does use strokes.
| WillAdams wrote:
| 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....
| raphlinus wrote:
| 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.
| erwinh wrote:
| Does anyone know of ways to expand this towards 3D paths with
| consistent screen-space stroke width?
| posix86 wrote:
| Look at the quadratic bezier fragment shader in
| https://hhoppe.com/proj/ravg/ might generalize well zo 3d.
| mattdesl wrote:
| Much simpler than the paper, but I have a 3D screen space
| implementation here[1].
|
| [1] https://mattdesl.svbtle.com/drawing-lines-is-hard
| amitp wrote:
| 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.
| enriquto wrote:
| Happy to see the neverending fruits of using Euler spirals in
| place of Beziers. Very few people can boast of such influential
| phd work.
| spencerchubb wrote:
| I'm curious whose phd work you are referring to?
| enriquto wrote:
| By the same author https://levien.com/phd/phd.html
| posix86 wrote:
| 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/
| djoldman wrote:
| 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.
| amelius wrote:
| 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.
| a_e_k wrote:
| 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...
| martin293 wrote:
| Could anyone please explain what stroke expansion actually is
| either on high school or math undergrad level?
| djoldman wrote:
| 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?
| scotty79 wrote:
| 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.
| robinduckett wrote:
| 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.
| Simran-B wrote:
| 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
| YmiYugy wrote:
| 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?
| raphlinus wrote:
| 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 Beziers 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...
| YmiYugy wrote:
| 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.
| refulgentis wrote:
| 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
| raphlinus wrote:
| +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 wrote:
| 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).
| aappleby wrote:
| 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.
| a_e_k wrote:
| 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.)
___________________________________________________________________
(page generated 2024-07-06 23:00 UTC)