linebender / kurbo

A Rust library for manipulating curves
Apache License 2.0
716 stars 69 forks source link

Endless loop when trying to offset certain curve #344

Open RazrFalcon opened 6 months ago

RazrFalcon commented 6 months ago

Hello. I'm getting an endless loop when trying to offset the following curve:

let curve = kurbo::CubicBez {
    p0: (51.0, 0.0).into(),
    p1: (-0.0859375, 161.640625).into(),
    p2: (0.0, 164.0).into(),
    p3: (0.0, 164.0).into()
};
let offset = -8.0;
let accuracy = 0.01;
let offset_path = kurbo::offset::CubicOffset::new(curve, offset);
let path = kurbo::fit_to_bezpath_opt(&offset_path, accuracy);
println!("{:?}", path.to_svg());

CubicOffset::new_regularized doesn't help either.

Is this is a bug or am I using it wrong? fit_to_bezpath (no _opt) does finish, but produces some NaNs.

kurbo v0.11.0

raphlinus commented 6 months ago

It looks like this could be improved. Unfortunately, I'm swamped right now, so would only be able to dig in deeply after RustNL, but will offer a few thoughts.

First, this is exactly the type of case new_regularized is designed to handle, and I'm slightly surprised to hear it doesn't help, as we have run a lot of the "tricky strokes" examples from the Skia library through it.

Second, looking at the implementation of CubicOffset::sample_pt_tangent more closely, I think it might well be worthwhile to tweak it to handle near-zero derivatives of the cubic better. As it's written, it essentially assumes those derivatives are robustly nonzero, but does handle the cusps in the offset. The current robustness code in Vello is built on the premise of sampling from a perturbed point on near-zero derivative, and it seems to work pretty well.

Feel free to ping me in a few weeks if I haven't responded. It might also be worth bringing it up on the Zulip; there are a few other people who are familiar with this code.

RazrFalcon commented 6 months ago

Thanks for the explanation. I'm not in a rush and will test it more. I was able to trigger a couple more endless loops and I will try to figure out if they are caused by the same issue or different so we could have a better tests corpus.

dominikh commented 4 months ago

A trivial kind of input that triggers an endless loop I've found is singularities:

fn test_singularity() {
    let p = Point::new(0.0, 0.0);
    let c = CubicBez::new(p, p, p, p);
    let co = CubicOffset::new_regularized(c, 1.0, 1.0);
    fit_to_bezpath(&co, 1.0);
}