Render vector mesh fills correctly as separate subpaths

[Keavon]

This is a Help Wanted issue we are hoping may be solved by a motivated and experienced new contributor with a reasonable background in graphics, graph theory, or math. It is not suitable for newbie programmers, but it does not require existing experience with the Graphite codebase or even necessarily a long history with Rust. You can set up the Graphite project with these intro instructions if you are interested in getting involved.

---

Our vector meshes extend the traditional SVG-style paths by allowing for branching topology, where an anchor can connect to 3+ segments instead of a maximum of 2. Our render code doesn't handle this very well when it is generating the fill for vector mesh layers, like grids created with our Shape tool's grid shape mode:

Here is how a grid is drawn

Open https://dev.graphite.rs, click New Document, and then draw a grid like this:

capture_13_.mp4

We want all the grid cells to be filled red if this was behaving correctly. It should do that by producing a separate non-branching SVG subpath for each cell area by computing a traversal of each bounded area.

There is also a special case where the algorithm will need to detect if a contiguous island of vector geometry (a subpath, but potentially a mesh) is actually a mesh or if it is just a non-branching SVG-compatible subpath.

If it is non-branching, we want to use SVG's behavior of drawing a fill even if the shape is open (not closed) by pretending a straight line connects the open endpoints. The following (currently implemented) behavior is desired:

If it is branching, we want to disable that behavior and fill only closed regions of the mesh. The following behavior is not desired:

Instead, it should look like this:

These meshes are created using the Pen tool, but the experimental Vector Meshes feature has to be enabled in File > Preferences.

Download these test cases, remove the .txt file extension, and drag it into your localhost Graphite editor (or https://dev.graphite.rs for testing against the latest master commit):

Vector Mesh Rendering.graphite.txt

The renderer should produce separate SVG elements for the fill subpaths (based on the graph traversals described above) compared to the strokes (which already are implemented in a way that isn't quite so buggy so they aren't in scope for being changed in this issue).

The algorithm needs to be implemented and then reused for both the SVG and Vello versions of our renderer. The code is located here:
https://github.com/GraphiteEditor/Graphite/blob/master/node-graph/gsvg-renderer/src/renderer.rs#L703-L1114

You should research "minimal cycle basis" as the type of graph traversal. It is described in the sections titled "Filing the Holes" and "Curvy Edges" of https://alexharri.com/blog/vector-networks.

[iamthenoname]

I've managed to render grids properly now, but I'm still figuring out why exactly it's not following the desired behavior for other meshes. I'll continue working on this later.

[Keavon]

Here is the file with the three test cases (remove the .txt extension after downloading):

Vector Mesh Rendering.graphite.txt

I also recommend enabling File > Preferences > Vector Meshes which allows the Pen tool to create/edit branching paths.