Bézier path simplification

[raphlinus]

An update with work in progress. Sequel to Fitting cubic Bézier curves which was mostly fitting Euler spirals and Parallel curves of cubic Béziers which was about parallel curves. Scope of this is much more general: simplification of arbitrary paths.

Reflects code recently committed into kurbo, specifically ParamCurveFit and methods on that. Also discussion on Zulip in curve offsets and More thoughts on cubic fitting.

ParamCurveFit

ParamCurveFit is a general interface connecting an arbitrary curve to be fit with a curve fitting or path simplification backend. The key insight is to sample both the position and derivative of the source curve. Another feature is the ability to report cusps, which is especially useful for parallel curves.

Two main implementations: parallel curve of cubic, and arbitrary bezpath. Goal is to be open-ended, so you can go from many different curve representations (incl NURBS, piecewise spiral etc), or compute distortions on source curve (perspective transform etc).

Fun implementation technique: O(1) query of area + moment of arbitrary subrange of source curve using prefix sums.

Error metrics

Main error metric is Fréchet distance. This is hard to calculate directly, so we approximate.

Two main choices for approximation technique:

• Tiller-Hanson: for n samples of source curve, ray cast from normal and find intersection on approximation
• Arc length parametrized: for n samples, find corresponding points of equal % of arc length, measure distance

T-H metric fails when source curve is spicy and approximation has a loop (show!). Arc length metric is more robust but slower. Hybrid technique: detect when source curve is spicy (delta in normal angles above threshold).

Illustrations: the two techniques, and a failure case

Finding subdivision points

Simple technique: subdivide in half when error is exceeded. Not optimal; in the limit tends to produce ~1.5 as many curve segments as needed.

Fancy technique, based on 9.6.4 of thesis: try to find point that exactly produces error. This gives n. Last segment has too small error. Then try to find error target so all segments have equal error. Use ITP. Gives globally optimum solution when errors are monotonic. They won't be in general case, but it does give robust results.

Possible future work to improve this. Quite a bit slower (~50x the simple subdivision method). Possibly use generic optimization technique argmin.

Low pass filtering

This technique produces curves that are G1 continuous with source curve at endpoints of each segment. That's good if source curve is not noisy. When it is noisy (pen data, scans, etc), sampling gives noisy tangents.

Discussed in "more thoughts" thread, can probably adapt quite a bit of that.

A few approaches: explicit lowpass filtering, use optimization technique to also adjust tangents. Not tried yet.

Bumps

Frechet guarantees only distance, not smoothness. Discussed in section 9.2 of thesis. Optimizing solver can generate bumps. Show example. Not acceptable for eg fonts.

Sophisticated approach: fancy error metric that tries to model perception, including both angle and distance errors. Not done, but interesting future work.

Simpler approach: exclude Beziers that have cusps or nearly so. These are large d values (distance from endpoint to control point). Implemented, and produces smoother results.

Discussion

What's in kurbo now is likely useful and significantly better than anything in the literature. Exactly what you want to do depends a lot on the use case: an optimizer that gives a mathematically perfect result to minimize Fréchet distance might give undesirable bumps.

Scope for future work: make algorithms faster, figure out more perceptual error metric, optimizer for noisy data.

Point out that fit_to_bezpath assumes continuous input, other method should handle corners.

[raphlinus]

Below is an example of the bumps. This is the output of linebender/kurbo#269 using the test data in linebender/kurbo#268 and a tolerance of 0.18.