Stroke dash patterns and animations

[foobar27]

I'm currently considering to use lyon for an open source tool to create animations like the YouTube channel 3blue1brown, who wrote a python framework.

I have two use cases which I'm not 100% sure yet how to implement them on top of lyon.

The first use case is to render dashed strokes, the second is about animating strokes (like you would draw them on a sheet of paper by moving your pen).

These use cases are more related then they seem at the first sight:

• I would also like to animate dashed paths (and ideally reuse as much of the tesselation as I can between the frames).
• The use cases probably boil down to split the paths, either at the places where the dash stops, or at the place where the path is supposed to stop at the current frame.

As for the implementation (for both use cases) I would see several high-level options for implementing cubic or quadratic curves (linear strokes should be simple):

• Split the cubic curve mathematically, maybe with Segment.split_range. In order to implement dash patterns or animations, I would need to approximate the length, and also the control points. This seems like a numeric nightmare. For dash patterns it might still work, but for animations the curve will probably jump around all the time.
• Flatten the path, then implement the dash patterns or animations on the linear segments (probably with the Segment.split* methods?).
• Use a completely different library, which does not use tesselation. Draw the path by parametrizing it over time.

I tend to go for the flattening approach. Do you concur?

Finally, would this somehow fit into lyon? I see two options:

• Encode the dash pattern in the PathEvent, then let the tesselator split it after flattening it.
• Add it to lyon_algorithm (like hatching). Then the user can implement a path iterator which returns multiple PathEvents for every dashed segment. This would probably be less intrusive and more efficient when I want to animate dashed strokes (I can reuse a part of the tesselation between the frames), but it might couple the animation code with the dash patterns.

What do you think?

If you believe this would be a valuable addition to lyon, I could give it a try.

[nical]

In lyon_algorithms there is a walk module that lets you do something close to dashed patterns (not quite but close): it lets you invoke a callback at predefined intervals along the path using distance instead of curve parameter. You can see it in action if you run the wgpu example which uses that to position arrows along a path using instancing. the dashes don't get to bend along with the curves but they are positioned properly.

See https://docs.rs/lyon_algorithms/0.17.4/lyon_algorithms/walk/index.html and also an example of how it is used here https://github.com/nical/lyon/blob/43df8bade5fe7e8e444ce0d763897fd0527ca822/examples/wgpu/src/main.rs#L564

The stroke tessellator also has a crude approximation of the distance along the path (crude in the sense that the value you get on either side of the stroke is the distance of the center of the stoke). you can pass that to a shader and use it to hide/reveal parts depending on the distance. I suspect that it is not enough to render nice looking dashes close to sharp joins but it is likely enough to animate the stroke convincingly.

If you want really good looking dashes for arbitrary path I think that the most reasonable option is to implement a function that generates the contour of the dashes and tessellate it with the fill tessellator. I think that skia does that.

[nical]

Answering a bit more precisely

I think that you can already get away with using the vertex advancement to animate the stoke in the shader, but otherwise you could write an algorithm that takes a path event iterator and generates a path event event iterator that go from distances d0 to d1 of the imput. In fact if you do that you might be able use it for dashes as well.

Encode the dash pattern in the PathEvent, then let the tesselator split it after flattening it.

Having dashes in the path events would make everything more complicated, including algorithms that consume path events but for which dashing doesn't make sense. Path events, path data structures and tessellators should be independent from the notion of dashing, and dashing should be implemented in its own routines that leverage paths, tessellators, etc.

Add it to lyon_algorithm [..]

Yeah. Let me know if walk_path which is already there fits your purpose. Otherwise you could write a more general dashing algorithm that not only provides the start and end of the dashes, but also the curve segments within each dash. It would be great if it could be implemented without allocating a path for each dash. For example a callback invoked for each dash, that provides an iterator of path events, and that iterator walks the edges within the dash of the original path but splits the first and last edge to only show the right parts. or even something that takes an iterator and dashing parameters and produces an iterator of iterators of path events so that you could write:

for dash in path.iter().dashed(DashOptions { .. }) {
    for path_evt in dash {
        // ...
    }
}

It's super nice from an API point of view but it can be harder to write. If you can implement something like that without allocating memory I'll gladly add it to lyon_algorithms.

Once you have your dashes you can either write an algorithm to turn the path of a stroke into a fill countour and tessellate it with the fill tessellator for maximum quality, or tessellate it directly with the stroke tessellator.

I'd very much like to have a stroke-to-fill conversion in lyon (cf. #564).

[foobar27]

Thanks for the extensive explanations. I will try to implement the nested iterator approach and come back to you once I have a first prototype.

[Dollab]

Hi, if you need to draw a lot of dashed lines with high performance and good antialiasing I recommend this approach : http://jcgt.org/published/0002/02/08/ You would need to implement a different stroke tessellator to output the correct information per vertex but it works quite well.

[nical]

@Dollab The tessellation in this paper looks close to what lyon's stroke tessellator produces. I'm keen on adding to the stroke tessellator to make this work but it's not clear to me a first pass on the paper how the "texture coordinates" (texcoord in their shader code) are produced in a way that looks good with angles. Have you implemented something like that?

Edit: Ah nevemind, the joins with overlaping segments are how they handle angles that are not close to linear. The question is then how do they deal with transparency when segments overlaps.

[Dollab]

@nical I've implemented a variation of this approach. I've replaced the baked angles by the coordinates of the four vertices surrounding the join, in order to directly compute the needed cos and sin in the shader. I've also replaced the attributes with the total length of the path with a bit flag on the vertices coordinates indicating if we are at the end or the start of the path, this enables the path to be scaled / sheared via a matrix transform in the shader without breaking the joins. Finally, I've added the changes needed to handle edge cases such as when a path segment is smaller than the width of the stroke. This makes the stroke tessellator very simple.

The remaining problems of the approach in my experience are :

• self intersecting path will overlap and show if you apply transparency
• dashes do not handle shear / non uniform scaling transformation (as it will break uv continuity). I do not see a way to fix this unfortunately.
• on some GPU I've experienced pbs with the dashes system (probably due to a bug with float precision on my part, which should be fixable).
• path need a lot of data per vertex on the gpu

For my use case, a CAD web app, these trade offs are ok.

I'll be happy to share the code if you are interested.

[nical]

The path sampler makes it easy to create dash patterns by using the split_range method with each range a..b being a dash from distance a to distance b along the path.