Further numerical robustness issue in path rendering

[ChengCat]

Hello, I've quietly followed this project for quite some time, and thank you for this great work!

I am aware the path rendering algorithm is numerically tricky, and many numeric issues have already been resolved in the past. But unfortunately I still run into one issue here. The following incorrectly rendered image is produced by latest vello on the main branch (8a84a4a); the correct image should be a white filled square.

To reproduce, replace the function add_shapes_to_scene in examples/simple/src/main.rs with the following code:

fn add_shapes_to_scene(scene: &mut Scene) {
    use vello::kurbo::PathEl::*;

    let path = [
        MoveTo((0.0, 0.0).into()),
        LineTo((1000., 0.).into()),
        LineTo((1000., 1000.).into()),
        LineTo((0., 1000.).into()),
        LineTo((-1.87016292e-06, 923.848633).into()),
        LineTo((1.87016292e-06, 156.151367).into()),
        ClosePath,
    ];

    scene.fill(
        vello::peniko::Fill::NonZero,
        Affine::IDENTITY,
        Color::new([1.,1.,1.,1.]),
        None,
        &path,
    );
}

[waywardmonkeys]

Just so you know that we haven't forgotten or missed this, essentially everyone is on holiday at the moment.

[ChengCat]

Just so you know that we haven't forgotten or missed this, essentially everyone is on holiday at the moment.

Yeah, I am aware. So no hurry here :)

In the meantime, I write down some clues to fix the issue. A quick fix is to snap coordinates of all points to a uniform grid of fixed size (e.g. 1e-5), so that the two small numbers in my example would become 0. This approach probably wouldn't hurt render accuracy in practice, and can help to avoid many, if not all, issues in the currently implemented algorithm, but it nevertheless feels a hacky patch.

To better fix the issue, there are two references. One is this Zulip thread when Raph Levien last time worked on it. (https://xi.zulipchat.com/#narrow/channel/197075-gpu/topic/Path.20rendering.20numerical.20robustness) Another is the paper "Random-Access Rendering of General Vector Graphics", which Vello takes inspiration from. I haven't looked into these two references in detail though.

[raphlinus]

I'm on vacation now, but did want to mention I have a possible new approach to tile numerical robustness (this came out of the CPU implementation work).

Essentially, the current approach is to try to minimize the number of tiles when a line falls exactly on a tile boundary. So a line from 0, 0 to 16, 16 would be a single tile now (in the code, this is reflected in the span function going from the floor of min to the ceil of max, among other things). There is some tricky accounting, which I thought I had gotten right, but apparently not (though I haven't dug into this in detail).

The new idea is to be more relaxed about minimizing tiles, and basically promote any coordinate lying exactly on a tile grid line to grid + epsilon. The core idea is similar to what we do now, but it reduces the number of special cases. Of course the choice of "epsilon" is one of the things we have to figure out. Somewhere in the backlog is the idea of moving to tile-relative f16 coordinates, but I'm not sure that would be a big enough performance win to justify the effort.