Better cubic to quadratic

[rsheeter]

https://docs.rs/kurbo/latest/kurbo/fn.cubics_to_quadratic_splines.html, added in #193 as a port of https://github.com/fonttools/fonttools/tree/main/Lib/fontTools/cu2qu, allows us to convert a set of cubics to an interpolation compatible quadratic b-spline. This is invaluable in font compilation of variable fonts that use cubic sources as the https://learn.microsoft.com/en-us/typography/opentype/spec/glyf table currently only supports quadratics.

Per discussion with @raphlinus, we could improve on the current algorithm:

• Conversion from curve → quad b-spline is similar flattening
  • So, the density of points you need to retain is proportional to cube root of curvature
• An optimal cu2qu would be looking at the cube root of curvature along the curve and evenly sampling, and that will determine how to split things up.
• This would take two steps
  1. How many quads do we need? - based on cube root of curvature as above
  2. Fit N quads to the cubic, much as cu2qu does already

The improved version would be expected to outdo cu2qu for S curves and cases where there's an extremely highly curved region, e.g. the notch under a ball at the end of a font shape.

A better cu2qu would be of immediate value to https://github.com/googlefonts/fontmake-rs.

[behdad]

The reason cu2qu works the way it is, is that it wouldn't need to encode any of the interior on-curve points.

So to beat it with non-uniform t values, you need to be able to use ~half the quads, which I have a hard time imagining you can do. You will only start seeing benefits if for a curve that cu2qu uses 5 quad segments, you can use 2 segments...

[ctrlcctrlv]

Why not cucoqu?

[ctrlcctrlv]

I based cucoqu heavily on Skia's converter, so it is your optimal solution.

https://github.com/MFEK/cucoqu.rlib/blob/main/src/cu2qu/mod.rs

impl CurvesToQuadratic for Vec<Cubic> {
    fn curves_to_quadratic(&self, max_errors: Vec<f32>) -> Result<Vec<QuadSpline>, ApproxNotFoundError> {
        debug_assert_eq!(self.len(), max_errors.len());
        let l = self.len();
        let mut splines = vec![None; l];
        let mut last_i = 0;
        let mut i = 0;
        let mut n = 1;
        loop {
            let test_spline = self[i].approx_spline(n, max_errors[i]);
            if let Err(_) = test_spline {
                if n == MAX_N {
                    break;
                };
                n += 1;
                last_i = i;
                continue;
            }
            splines[i] = match test_spline {
                Ok(a) => Some(a),
                Err(e) => return Err(e),
            };
            i = (i + 1) % l;
            if i == last_i {
                //done
                return Ok(splines.into_iter().map(|maybe| maybe.expect("Should not get a None")).collect());
            }
        }
        Err(ApproxNotFoundError)
    }
}