Fitting cubic Bézier curves

[raphlinus]

This will likely be a blog post, but the work really should become a paper.

It's a follow up to the parallel curves blog post and Secrets of smooth Béziers revealed.

Motivation: simplifying existing shapes to make more concise fonts. Fitting mathematical curves but also solutions to the parallel curve problem. Rendering hyperbeziers (blog post upcoming).

There's a bunch of literature: de Boor High accuracy geometric Hermite interpolation, Graphics Gems chapter An algorithm for automatically fitting digitized curves. None are entirely satisfying. Closest thing is the more recent Fitting a Cubic Bézier to a Parametric Function, but ends up proposing an extremely expensive optimization approach.

The ideal would be a direct solution. It's not easy. Big issue is that there are multiple local minima (for error) in the parameter space. Show heatmap plot.

Difficult questions: how many local minima? How can we be sure we've got all of them? Why do they move so quickly sometimes in response to small perturbations of the source curve? Optimization techniques have risk of falling into one minimum.

Do need to set up the problem at some point. Endpoints fixed. Endpoint tangents fixed. Two parameters, the control vector magnitudes, to solve. Might be a good place to describe normalizing the chord to (0, 0) - (1, 0), which greatly simplifies math downstream.

Key fact about cubic beziers: C-shaped beziers come in triplets of very similar shape. With the techniques in this blog, we'll be able to identify exactly when that's the case and analytically go from any of the triplets to the other two.

Central idea: take two measurements of the source curve, and solve the parameters for a bezier so these two measurements match the source curve. Prior art: in de Boor paper, these two measurements are curvatures at endpoints (G2 geometric Hermite interpolation). de Boor shows that that there are up to 3 solutions. de Boor gives a system of two quadratic equations; numerically tractable. However, Penner paper shows evidence that the error is 5-10x times higher than optimum. Purely local techniques don't work well.

Our idea: these two measurements are signed area and x-moment. Present math (it's in the Penner paper, but I think the presentation can be slightly cleaner with the normalized chord).

Image: S shaped cubic bezier at center. Above it, one arm longer, one shorter, show "+" in interior to show change in area. Below it, opposite and "-". To right, both arms longer, one hump "+" one hump "-" to show no change in net area but change in x-moment. Similarly to left.

The simultaneous solution is a quartic polynomial. (Math details are messy but perhaps can be simplified).

Topic: beziers come in triplets, what about the fourth solution? It's a bezier with a loop.

Topic: near misses. Looking at solutions only may miss the optimum. Optimal solution is found in intersection of strips near area-match and moment-match lines. So need to look at regions where they approach but don't actually cross. That's a minimum of the derivative of x-moment when area is held constant. Probably good to show an image with the strip intersections in the 2D parameter space.

Maybe provide more intuition for argument that optimal solution has low error norm wrt any point in that intersection region, even when it's long and narrow. When curve is a parabola, perturbing the arm lengths while preserving signed area moves the points of the curve along the tangent; change to curve is minimal. For S-shaped curve, points move away from curve. I'm thinking this is best shown as an image.

Optional section: discussion of different metrics. Hausdorff vs Frechet. Cute story about walking the dog, Frechet distance is length of leash needed. Can introduce L2 norm by talking about exertion proportional to x^2. L2 is smoother. Can say: if you want an L-infty style norm, start with the L2 minimum and then optimize wrt the other norm. Not sure how important this is.

Can also talk about how exact area preservation is nice. Relevant to fonts especially, it means total ink of a stroke is exact.

General notes: doing this blog post well will be quite visually intensive, and requires a number of images. I think it's likely that near-optimality of the solution can be proven as a theorem, but that will require more work on the math.

[raphlinus]

@alvinpenner may find this interesting as it builds strongly on the work in the linked paper (and implemented in https://github.com/alvinpenner/Spiro2SVG)

[alvinpenner]

thanks for the link! I'm a really big fan of your Ph.D. thesis, which was awesome! fwiw, I once wrote up a bit of a qualitative description of the method I was using, at: https://www.codeproject.com/Articles/1160697/Spiro-SVG-Convert-Spirographs-to-SVG-Using-Bezier https://www.codeproject.com/Articles/1163857/Spiro-SVG-II-Roulettes-Lissajous-Figures-and-Farri unfortunately, the method relies heavily on the fact that I was fitting objects with a lot of symmetry.