Multiple Partial Overlap Bug

[Vatvo]

Hello Flo_Curves Devs,

I found a bug with the marking of interior/exterior edges when subtracting complex shapes in a specific way in both v0.7.3 and v0.8.0.

It begins with a base shape created by merging four SimpleBezierPaths into a GraphPath:

And a cutout GraphPath like this:

The cutout path is then subtracted from the base shape using GraphPath::collide() and then GraphPath::set_exterior_by_subtracting(). This produces the incorrect path seen here:

Here is a recreation of what it should look like if it were correct:

The result of this error (when healed using the heal_exterior_gaps() function) looks like this:

When it should look like this:

The two black and white images were made using the original icons with which this bug was discovered, but I have written a test using the more minimal reproduction seen in the debug images.

The inner loop seen in the top right of the debug image seems to be important. When it is removed, the bug does not occur.

Also, if the top of the cutout shape, which intersects that loop, is moved higher (to around y=100) the bug does not occur.

When that point is at its normal position of y=160 it breaks.

I believe the bug is somewhere in the set_exterior_by_subtracting() function, or the function it calls, though I was unable to locate exactly where.

The subtract_multiple_partial_overlap() test I have proposed in pull request #29 creates these shapes, subtracts them, locates the edges of the inner arch, and checks their interior/exterior statuses. If they are correctly labelled as exterior, it passes. I believe that if this test passes, the bug would be fixed.

Also, I’m not sure if this is relevant, but maybe it will be useful information somehow. The edge indicated in the following image is actually two lines that partially overlap:

I would think that Flo_Curves should see the overlap and split the edge up appropriately.

I could be wrong about what this is supposed to look like, but maybe this information will be useful.

[Logicalshift]

Hi, thanks for the comprehensive report, I was easily able to reproduce the bug. I've got some first impressions for now, I should be able to try to figure out how to fix this this weekend.

I believe you've also identified the cause here: any overlapping lines should have caused a collision so there shouldn't be any of differing lengths. That will always cause incorrect behaviour, but precisely what happens depends on the ray that intersects the lines, hence why altering the shape seems to change the outcome. The longer line is inside the shape at the top, but outside at the bottom, so there are two possible results.

(Partially overlapping curves are the worst for figuring out collisions: apparently even when they are also lines)

There are some other possibilities: rays that run nearly exactly along a linear edge can cause glitches too, and rays that cross two overlapping edges have previously caused problems (v0.8 rewrote the algorithm for that last one so I'm hoping that's actually fully fixed now), and there's always the unexpected wildcard bug in some other part of the code.

I'll figure this out for sure this weekend, but this analysis has been really useful in narrowing down what could be going wrong.

[Logicalshift]

I believe I've fixed this as of d425e83 which is on the v0.8 branch.

There were a couple of problems: the main one was to do with overlapping curves. If you had a situation like this, where two overlapping lines are moving in opposite directions and the end points only :

   *------>
       <-------*

flo_curves would not recognise them as overlapping. This was the main reason the intersection wasn't being generated.

Then there was a filter being applied that was supposed to stop the last point of one path edge from intersecting with the first point of the next that also removed the intersection. That only makes sense when computing self-intersections so I've removed it.

Finally fixing the overlapping bug introduced a new bug where very small subdivided curves would be seen as overlapping, which would generate extra collisions. I've fixed that with a check that discards overlaps that are very close to the start and end of the curve (the points should snap together later on anyway)

[Vatvo]

Looks good. Thanks for the quick response. If it's not too much trouble, could the fix be added to the 0.7 branch too?

[Logicalshift]

Yep, no problem. I've copied the fix over into the 0.7 branch and released it with v0.7.3