search

googlefonts / fontra

A browser-based font editor
https://fontra.xyz
GNU General Public License v3.0
510 stars 21 forks source link

Add "expand stroke" function (possibly as plugin) #1586

Open davelab6 opened 3 months ago

davelab6 commented 3 months ago

Raph has a new computer science paper out, which won 3rd place at the recent High Performance Graphics conference, and I think this is likely to be the best method for a Fontra 'expand stroke' function. The code is in rust which is wasm'able, and I guess amenable to an AI code port to Python if needed :)

https://linebender.org/gpu-stroke-expansion-paper/

justvanrossum commented 3 months ago

I do intend to use Kurbo at some point. I'm still really hoping they'll implement path ops one day.

I am fairly sure Kurbo contains stroke expansion functionality, presumably as described in the paper. I've heard Raph rave about it before :)

justvanrossum commented 3 months ago

That said, in type design one often needs strong predictability in terms of number of segments generated (possibly at the expense of precision and/or correctness), to keep the expanded stroke interpolatable across different stroke width settings. I'd be curious if Raphs algorithm offers parameters to do that.

raphlinus commented 3 months ago

Glad to weigh in here. There is stroke expansion functionality in kurbo (see stroke()), based on the quartic solver technique, but there are two things that are not perfect about it, for this application.

First (and probably not super important for this application), it's a bit on the slow side, compared with (say) Skia's stroke expansion. We have https://github.com/linebender/kurbo/issues/317 tracking that.

Second, because it selects the optimum Bézier for the stroke, it has poor continuity guarantees. To be clear, this is not a weakness of the kurbo algorithm, this is an inherent property of cubic Béziers, where the parameter space folds over itself when seen from a curve distance perspective. Fortunately, there is an answer. Instead of choosing a global optimum, use a perturbation approach to find a local optimum in the same basin as the source curve ("generatrix").

In fact, using a linear perturbation approach is ideal for this application, as the motion of the curve is purely linear as the offset is adjusted (this is good for grades as well as expanded strokes, where the offset can be both positive and negative). That means that the result of applying a perturbation approach to parallel curves will have essentially perfect interpolation compatibility.

I've done a lot of conceptual work in the past few weeks on the perturbation approach. There's an extensive Zulip thread on the idea, a draft blog post, and also a promising prototype in code (not yet released). My challenge is finding time to work on it, which is also the case for pathops.

davelab6 commented 3 months ago

shake'a'shakin' the points to produce a similar curve that is interpolation compatible, very cool :)