Speed up stroke expansion

[raphlinus]

Stroke expansion is pretty slow. One aspect of this issue is doing some measurements to see how it compares to other solutions, and also where the time is going. There may be some low hanging fruit.

That said, even without measurement there are some ideas. A lot of time goes into error measurement after fitting to see whether the resulting offset is within tolerance. I bet we could do an analytical error metric (likely based on estimates of min/max curvature) that would predict upper and lower bounds on error. If the upper bound is within tolerance, it can be based on just the fit, no need to measure. If the lower bound isn't, then we subdivide without needing to do the fit and measure.

Additionally, fitting based on "balanced Béziers" (Zulip thread) is likely to be faster. The numerical integration of the curve to be fit (the parallel curve of the source Bézier) needs to compute only area, not also moment. The solver is quadratic, not quartic, which should be much faster. The only trick is that it might need more subdivisions; fitting the source curve even with infinitesimal offset is not guaranteed, while it is for the quartic-based solver. It's trivial to detect the imbalance of the source curve. Perhaps we apply the analytical error metrics to see whether it can still be fit by a single cubic. If it needs to be subdivided, then perhaps the quadratic fit for the subdivisions is good enough.

This would be a great project for someone who's handy at math.

[raphlinus]

One other thing to add: an error metric based on curvature (and, now that I think about it, possibly parametrization balance as well) would no doubt also be useful in setting the number of samples needed for numerical integration. That's currently hardcoded at 16, not based on any kind of rigorous analysis, it just seemed like a reasonable value.

[raphlinus]

I've written up lots of ideas in the Zulip thread Fast, precise cubic curve offsetting. I believe those ideas are extremely promising. There's also a conceptual framework for error metrics. I'll likely get to it later this year, but it's potentially a good issue for someone who's good at math. There should also be a paper describing the approach, as I believe it would be a significant research contribution over what's state of the art.

I should also mention that shape control is a plausible approach, and could be made to work. Part of the research effort (and why it really deserves a paper) is carefully comparing the shape control and error metric approaches.