Tracking issue for curve fitting robustness

[derekdreery]

This is a new tracking issue for fitting robustness. There shouldn't be too many problems once #269 lands, but if there are any, please post them here.

This issue also tracks curve offset, as that is a special case of curve fitting.

[raphlinus]

Achieving perfection here will take a lot of work, but there are two things I plan to do in the coming days which I believe will help a lot.

First, make the sample_pt_tangent() implementation in CurveOffset handle zero and near-zero derivatives in the source curve, as well as cusps caused by offsets. There's some logic for that in simplify_bezpath(), but that's at a higher level, before it gets into curve fitting.

Second, degenerate curves are manifesting as infinite recursion, it keeps subdividing (apparently sometimes to zero length) and you get either a hang or a stack overflow depending on the details. I'll add special case logic to handle the endpoints within the given accuracy of each other. You usually don't want to get there, but if you do, it should just draw a line, which is the simplest answer that meets the Fréchet bound.

[raphlinus]

There are a number of test cases floating around, but I'll start with this one from #269, as it's clearly documented. It hangs with the _opt variant, but also generates a stack overflow (indicating infinitely recursing subdivision) in the non-opt case. Just looking at the input, it's not obvious to me where the problem is, as the source curve has perfectly fine derivatives everywhere. I'll focus on that one first, then bring in more cases as needed.

[raphlinus]

Ok, for that particular failure it's now clear what's going on. There's some logic in CubicOffset::break_cusp called break_cusp_help which is supposed to detect the case that a cusp is near the endpoint, and it has some "magic" epsilon values (CUSP_EPS = 1e-8 is the most relevant one here) which in this case fail to trigger. Of course, this results in an extremely short segment, so I think handling that (before invoking cusp logic) will at least let the operation succeed, though the output will be less than ideal. It might also be worth thinking about more sophisticated logic for computing the epsilon - ideally you want a value large enough to avoid this kind of failure, but not so large you miss a cusp and generate incorrect output.

[valadaptive]

Not sure if this falls under the category of "robustness" or simply subpar results, but I'm trying to use kurbo's curve-simplification algorithm and there are some pretty large "bumps" in the resulting paths, of the sort described in your blog post:

These can be reproduced with this path, with an accuracy of 1.0 and an angle threshold of 10 degrees (not sure if that actually affects the algorithm in this particular case).

Tweaking the currently-hardcoded D_PENALTY_ELBOW and D_PENALTY_SLOPE values helps with this, but they need to be set to some pretty aggressive values.

This may require the development of a better metric, as you said in your blog post. There's also been a recent paper about simplifying Bezier splines that compares against kurbo's algorithm and claims an improvement; that may be worth looking into (sadly I am not smart enough to implement it).