bezier-rs 0.4.0: `Bezier::euclidean_to_parametric` is imprecise, with a big discontinuity at 0.5

[Calsign]

In the current released version of bezier-rs, 0.4.0, the logic for approximating Bezier::euclidean_to_parametric is wrong. Specifically here:

// If the curve is near either end, we need even fewer segments to approximate the curve with reasonable accuracy.
// A point that's likely near the center is the worst case where we need to use up to half the predefined number of max subdivisions.
let subdivisions_proportional_to_likely_length = ((euclidean_t - 0.5).abs() * DEFAULT_LENGTH_SUBDIVISIONS as f64).round().max(1.) as usize;

This logic is supposed to use more subidivions the closer we are to 0.5. Instead, it uses only one subdivision at 0.5 and uses the most subdivisions near 0 and 1 where they aren't necessary. The consequence is that the approximation gets increasingly imprecise near 0.5. Additionally, since it picks which direction to estimate from based on which side of 0.5 it's on, there's a big discontinuity at 0.5 as it switches across two bad approximations.

I noticed this when I found some sample beziers that exhibited this sharp discontinuity at 0.5. It only seems to be noticeable for some beziers, I haven't figured out why. This test demonstrates that behavior:

#[test]
fn reproducer() {
    use assert_approx_eq::assert_approx_eq;

    let beziers = vec![
        Bezier::from_quadratic_coordinates(
            59.481598,
            -22.974262,
            -199.90213012695313,
            37.127464294433594,
            0.95370483,
            155.28082,
        ),
        // if the inequality is changed from < to <=, the above passes but this one fails:
        Bezier::from_quadratic_coordinates(
            287.4947204589844,
            314.4862060546875,
            283.2593688964844,
            111.31137084960938,
            168.7027587890625,
            297.6860046386719,
        ),
    ];

    const APPROX_ERROR: f64 = 0.01;
    const COMPARE_ERROR: f64 = 0.05;

    for bezier in beziers {
        let actual = bezier.euclidean_to_parametric(0.5, APPROX_ERROR);
        let before = bezier.euclidean_to_parametric(0.49, APPROX_ERROR);
        let after = bezier.euclidean_to_parametric(0.51, APPROX_ERROR);

        // the value at 0.5 should be roughly halfway between the values at 0.49 and 0.51
        assert_approx_eq!(actual, (before + after) / 2.0, COMPARE_ERROR);
    }
}

Output:

assertion failed: `(left !== right)` (left: `0.1875`, right: `0.4375`, expect diff: `0.05`, real diff: `0.25`)

Fortunately, this logic has changed completely in https://github.com/GraphiteEditor/Graphite/pull/1624, specifically https://github.com/GraphiteEditor/Graphite/commit/218e9675fd2751ac588a8a6995ec045e00539fcb. I am working around this by using the latest master version of bezier-rs.

I didn't see an existing issue for this so I thought it was worth posting in case others encounter the same issue. Also, a new release of bezier-rs with the refactor/fix would be appreciated.

[0HyperCube]

Thanks for the bug report @Calsign.

The algorithms in bézier-rs aren't particularly robust or performant. The original maintainers of the library implemented it as a university project and are no longer working on it. Therefore it is only maintained or improved if it is required for the Graphite editor.

If it would be useful I think @Keavon could probably create a new release with reasonable ease.

[pbrinkmeier]

Hi, could you provide an example document where this is visible to the naked eye? I am working on this and would like to have visual confirmation if it works :)

[0HyperCube]

Hello @pbrinkmeier, thanks for your interest in contributing. As mentioned in the original issue text, this is already fixed by https://github.com/GraphiteEditor/Graphite/commit/218e9675fd2751ac588a8a6995ec045e00539fcb. I think this issue was more pertaining to @Keavon publishing a new version of the library. Thanks anyway.

[Keavon]

I'll have more bandwidth beginning soon to start working towards a new version of the library, but there are some assorted blockers I need to pick through first.

[Keavon]

The 0.5 release will be forthcoming, so I will close this.