linebender / kurbo

A Rust library for manipulating curves
Apache License 2.0
716 stars 69 forks source link

`simplify_bezpath` panics on `LineTo` #342

Closed Ralith closed 7 months ago

Ralith commented 7 months ago

I'm attempting to use simplify_bezpath to approximate a large number of tiny line segments (generated by a tool I can't modify) with a small number of beziers for easier laser-cutting. My input consists of the concatenation of some number of sequences of PathEl where the first is a MoveTo and the remainder are all LineTo. As soon as simplify_bezpath encounters the first LineTo, it panics in SimplifyState::add_seg:

https://github.com/linebender/kurbo/blob/3ea8f6bf4c18688ce82bb7d105e962b8f204a484/src/simplify.rs#L250-L259

It's not clear why this is believed to be unreachable. Is my input malformed somehow?

xStrom commented 7 months ago

I don't know anything about the math here, but just looking at the code there seems to be a missing match arm.

The simplify_bezpath function has a case that handles PathEl::LineTo by creating a PathSeg::Line which is then fed into add_seg. However there is no match arm there to handle such a case, hence the panic.

To take a shot in the dark, perhaps the missing match arm would look like this:

PathSeg::Line(l) => self.queue.line_to(l.p1),
raphlinus commented 7 months ago

This was a logic error, based on confusion whether lines would be handled in simplify_bezpath or the method in SimplifyState. I have a patch for the panic, but it's not going to do what you want, because it will pass through lines unmodified; the code basically works on the logic that it should preserve G1 continuity, though the angle threshold is configurable.

I think the best way to do what you want in the current code is to degree-raise the lines to quadratic Béziers, and make sure to set the angle threshold to a value larger than the angles present in your input data which are intended to be smooth. However, looking at this, I'm wondering whether it might be better to apply the angle threshold logic to lines as well as Bézier segments.

raphlinus commented 7 months ago

I should add, the current implementation won't do a great job with degree-raised lines, as there is no lowpass filter. It tries to exactly match the area of the input (so a polyline will undershoot the area of a convex curve), as well as G1 continuity at each subdivision point, so noise there will degrade the results. It works best for mathematical curves where there is no noise in the input. The documentation should probably be revised to explain that.

So for this application, it's likely that you'll get better results by fitting a spline (a straightforward cubic spline should do pretty well) to the points and simplifying that. We don't have those methods but I'd be open to adding them (I was looking at a similar problem recently).

Ralith commented 7 months ago

I'm wondering whether it might be better to apply the angle threshold logic to lines as well as Bézier segments.

That seems intuitive to me. As a user, when I think "angle threshold", what I think about is the derivatives approaching both sides of a vertex regardless of the degree of the incident curves.

It works best for mathematical curves where there is no noise in the input.

My input is a few linearly approximated smooth curves connected at sharp corners, and I'm trying to reconstruct a more concise approximation of the underlying smooth curves, so I'm not certain if this is a problem for me or not. Clearer applicability docs and/or expanded capability would be great!

it's likely that you'll get better results by fitting a spline (a straightforward cubic spline should do pretty well) to the points and simplifying that.

That makes sense, thanks! I'll give that ago, and see about contributing it back if it works out.

Would it make sense to bake that behavior into simplify_bezpath, or expose a separate function and document its usefulness? It seems like an intuitive behavior for "simplify", and is naturally governed by a similar angle threshold, but seems a bit more ad-hoc and opinionated than the existing logic in that it doesn't preserve the specific properties you describe.

raphlinus commented 7 months ago

Ok I pushed a PR which will at least fix the panic. I did a small amount of experimentation trying to smooth lines and did not get good results. I'm not sure yet what's the best way to get this functionality, both in terms of the best algorithms to implement and how to surface that in the API, but am definitely open to further discussion.