Stroke tessellator seems to produce wrong results for some rounded path types

[patowen]

In the main branch (commit 2407b7f), running the following in the "cli" directory produces incorrect results:

cargo run show "M 69 -155 L 71 -158 74 -158" --stroke -w 100 --line-cap Round --line-join Round

Since the path has a bounding box of 5x3 and a stroke width of 100, it should end up producing a blob, which it does. However, the blob also has a spike protruding out of it, which I believe is a bug.

I don't have much familiarity with how the tessellator works, so I don't have a lead on what the root cause is or how feasible this would be to fix.

[nical]

Thanks for filing this and providing a test case. I'll have a look soon-ish.

[patowen]

I was able to find a potentially simpler test case where the bug is more apparent:

cargo run show "M 5 0 L 0 0 0 5" --stroke -w 100 --line-cap Round --line-join Round

The edge case in question seems to be when the segment lengths are short compared to the stroke width.

If I had to guess what was going on, it would be that, based on the fact that each path segment is effectively two circles joined by a rectangle, the tessellation algorithm may be assuming that the inner corner between two path segments is at the intersection between two line segments.

If so, I believe the bug would trigger if the inner corner is instead at the intersection between two circles (and possibly also at the intersection between a line segment and a circle).

[nical]

Yes indeed. With the cli app you can visualize the issue fairly easily by pressing w to show the wireframe and playing with the strpoke with using a and z. The problem is even more apparent if you set the line cap to Butt. When the stroke witdh becomes much larger than the segment length, the back join of the middle vertex sticks out because its position is computed by intersecting the two offset edges. If the edges are small enough, the intersection point may not be on the edges themselves. The stroke tessellator is a pretty naive algorithm that works with only some local information, so it has artifacts like that. For fully artifact-free stroking a different algorithm is needed (for example converting the stroke to a fill which is unfortunately much slower. That said it's probably possible to detect the worst cases and paper over them (there stroke tessellator already does a fair amount of that).

[patowen]

Thanks for the tips. I didn't realize those controls existed; that makes things a lot clearer!

I originally encountered this when playing around with a modified version of Lavagna (https://github.com/alepez/lavagna). It doesn't seem to come up that frequently in practice when using the program normally (rather than testing its limits), so I won't be disappointed if this takes a while to fix, especially given how tricky it is, and especially since I can work around it by just splitting the path if necessary (at the cost of some efficiency loss due to overlap).

Just to double-check, do you know if there are any workarounds that the Lyon library provides? For instance, is "converting the stroke to a fill" a feature that exists in Lyon, or is it just presented as a possible algorithm?

[nical]

Lyon doesn't provide a workaround currently. I have a work in progress stroke-to-fill implementation here: https://github.com/nical/misc/blob/master/path_renderer/core/src/stroke.rs#L134 which you can copy into your own project, the intent is that it will make it into lyon but it's not quite ready and I currently don't ave a lot of time to spend on it.