Stroke expansion

[raphlinus]

This is a tracking issue for expanding strokes into fills, a common vector graphics operation. Among other things, it can be used to render strokes on top of a fill operation. That will be done as in intermediate step in Vello, before moving stroke expansion to a compute shader as described in linebender/vello#303.

The essence of stroking is offset curves, and that infrastructure is now in reasonably good shape, though there is a tail of robustness issues (tracked in #279). The main substantive work is computing the line caps and joins. See Nehab 2020 for a rather comprehensive discussion and many references. As discussed in the linked Vello issue, we will not target the most rigorously correct definition (which would require computation of evolutes) for performance reasons; perhaps that could be a future option.

The input is a path (discussion question: impl Shape is probably the friendliest approach, but it might be easier to have random access) and a stroke style. The latter is defined in peniko, in style.rs. I don't think it's appropriate to take a dependency on that. Rather, in the grand scheme, it might be better to move the authoritative source for that type into kurbo, and have peniko re-export it as needed. There is also a tolerance parameter. The output is a BezPath.

There are many references for this algorithm, including:

• In zeno, stroke.rs
• In Skia, SkStroke.cpp
• In Inkscape (livarot), PathStroke.cpp
• In FontForge, fontforge#3991

Of these, Skia should be considered a normative reference for compatibility and correctness. Perhaps some of the Skia tests can even be adapted.

See also the Paper.js issue requesting this feature, which I believe has not landed.

Discussion question: what is the best type for the input path? Choices include:

• impl Shape - probably the friendliest)
• impl IntoIterator<Item = PathEl> - same as simplify_bezpath
• &[PathEl] - random access might make life easier, especially for closed paths

A few more things. We may want to have some options guiding the optimization, analogous to SimplifyOptions. One of those may be whether each Bézier segment in the input path is offset independently, or whether curve fitting is applied to maximal G1-continuous ranges as is done for simplify. The latter may be fewer segments, but is also less editable.

[dfrg]

Moving the stroke styling types to kurbo and re-exporting from peniko seems like the right call to me. I expected we’d want to do this when adding stroke conversion to kurbo.

As for the signature, I’d like to suggest we follow the same pattern as flatten both for consistency and to simplify/optimize integration in vello.

[raphlinus]

One fun point of friction I'm encountering is that kurbo would rather types be f64, but the peniko type is f32. I'm just going to use f64 for now, and we'll sort this out during encoding.

[raphlinus]

One more requirement I'd like to add: generating only an inner or outer contour, which is essentially a dilation operator on a closed path. A particularly relevant application is stem thickening for font rendering, but there are others.

Trimming self-intersections is out of scope for this particular issue (in the Vello use case, it's up to the renderer to handle self-intersecting paths, in particular using multisampling when needed to avoid conflation artifacts), but will be useful for other applications. In that case, a separate pass would be used, and that feature is tracked in #277.

[raphlinus]

Here's a puzzling and difficult case (Skia fiddle link): it's a simple approximation of a circle, and the stroke width is more than twice the circle radius. Skia appears to get this wrong (and, for reference, there is a Skia bug though it isn't particularly conclusive):

By a Minkowski sum or swept-line definition, this should be a filled disc, as all points within that disc are within the line half-width of the source path. I had mistakenly believed that for closed continuous paths, tracing the parallel curves on either side, reversing the inner contour, would result in a shape with positive winding number everywhere in the Minkowski sum.

Because we're adopting Skia as a correctness reference, we're not trying to solve this, but it's very much worth being aware of.