Boolean path operations

[Kethku]

I noticed a link in the wiki referring to skia path operations.

Is this a feature that is being considered for the library? I'm working on a creative coding environment which relies on lyon for much of the rendering pipeline, and having boolean operations available would be an awesome addition.

I did some looking into what it would require to implement such a feature, and I think it may be pretty doable especially if the first version just operates on flattened paths and paths which assume no intersections. Doing union, intersect and difference operations on these paths would be a matter of scanning down the intersection list and comparing winding values as described in this presentation: https://www.youtube.com/watch?v=OmfliNQsk88

After that initial feature is provided, handling intersections and curves would be extensions on the initial version.

I'm just spitballing here. Does this make sense? What am I missing. Do you (the maintainers) have any hints for where I might look first to implement something like this? Thanks in advance.

[nical]

It would be great to have path boolean operations in lyon. It's mostly a matter of me or someone else spending the time to do it I don't have a lot of spare time right now but these come and go, I might some time later in the future. I would definitely love to receive pull requests for features like this! Path ops are not too complicated in principle but making them robust is a bit tricky because of numerical stability, but you gotta start somewhere, and an imperfect implementation can be improved upon.

If you want to implement something like this, my advice would be to look for some online or book references that explain the algorithm and look into open-source libraries (like skia) fill the gaps.

[Kethku]

I have no idea if I will have the time or know-how to do it, but I'll do some digging around and see whats up. Can you elaborate on the numerical stability issue?

[nical]

These issues mostly come from having to deal with intersections: When you find the intersection between two edges, a lot of these algorithms (the tessellator, boolean ops, etc.) need to insert a vertex at the intersection position and connect that vertex with vertices of the original edges. The finite precision of floats means that the intersection point will not be exactly at the on the two intersecting edges. As a result the new edges produced around the intersection are not exactly collinear with their original intersecting edges, so it introduces a slight change to the geometry.

Depending on the invariant of the algorithm this slight change might put you into an invalid state that is more or less complicated/expensive to detect and recover from. For example, if you rely on a certain sorting of the edges and vertices, that sorting could be compromised, etc.

In practice as far as I know, there aren't magical solutions to these, other than building the algorithm in a way that it can recover from breaking its own invariant which can be tricky since these algorithms by definition rely on them.
Anyway, that shouldn't discourage you. After years of bug fixing, lyon's tessellator still fails in some hard cases due to this type of issue, yet a number of people find it useful.

[Stumblinbear]

Has there been any progress on this? I'm needing polygon intersection, but the only crate that offers it utilizes geo which I'd rather not use just for the boolean op. I'm also not even sure how I'd prep a Lyon Path for use in it.

[nical]

Nope. Robust boolean operations is a lot of work and I don't have the bandwidth to implement it at the moment.