CompoundPath children are lost after a Unite

[ghenania]

@lehni I have an interesting use case for you ;-)

Sometimes, when I try to unite a CompoundPath with a Path, some subpaths are "lost".
Like here when I try to unite the CompoundPath in black with a Path in red. The resulting Path in blue is missing some subpaths.

[lehni]

Simplifed case

[lehni]

@iconexperience I believe this is an issue for you. I used the boolean-debug branch to display the determined winding contributions, and see what it shows:

Not surprisingly, the squares with winding 0 in all segments all disappear... But why do they get these values, while the others don't?

[lehni]

And with that information, here now an even more simplified case that has only one such square with wrong winding:

Further simplified case

[lehni]

@iconexperience so after looking a bit more into getWinding(), it turns out that this happens because of this line here:

https://github.com/paperjs/paper.js/blob/develop/src/path/PathItem.Boolean.js#L572

// TODO: Determine how to handle quality when curve is crossed
// at starting point. Do we always need to set to 0?
quality = 0;

It is time to address that TODO now. I don't understand things enough in that part of the code to do it. Could you help out?

I've tried just removing it, but that produces one failing test. I've also tried moving this code outside of its condition block:

https://github.com/paperjs/paper.js/blob/develop/src/path/PathItem.Boolean.js#L545

// Determine the quality of the winding calculation. Reduce the
// quality with every crossing of the ray very close to the
// path. This means that if the point is on or near multiple
// curves, the quality becomes less than 0.5.
if (a > pa - qualityEpsilon && a < pa + qualityEpsilon)
    quality /= 2;

That actually worked and produced no failing tests, but then the quality of all windings in that square is 0.25, which I don't think is right...

[lehni]

We should probably also look into why this happens on some of the squares and not on others? That's very bizarre...

[lehni]

@iconexperience I've spoken too quickly. By slightly rotating the square, I can get the approach described above to produce wrong windings too:

Updated Sketch

The problem with the slightly rotate square is that in propagateWinding(), one of the possible winding values I for the square is 0 with a quality of 0.5, and it happens to be the last one, so it ends up being used (all others have a quality of 0.5 as well)... I don't understand how it can be 0, and I don't really understand the quality factor, so it's hard for me to debug this part.

[iconexperience]

@lehni The quality factor should not be relevant in this case, because it is meant to handle cases where two curves are very close and detection of intersections is not reliable. It's quite possible that the quality factor causes this bug, but that only shows that the implementation is not correct.

In my opinion in the example we should get a correct winding result for all tested points. If that was the case, the quality factor should be irrelevant. But I agree, we should urgently settle this, or at least have a clear documentation for the quality factor.

But first I will try to find out why some points give an incorrect winding result.

[iconexperience]

Alright, this is the old problem with corners. Here is an example where the winding calculates incorrectly:

The grey line is the vertical ray. The winding left and right (here up and down) are zero, which is correct. But we need a special handling of these cases. For contains() we check if the point is on the path in these cases, but this will not be sufficient if we need the correct winding number.

I think long time ago we simple assinged 1 to these cases, but this is not always correct, because if you have two identical squares, the winding at that point must be 2. And if there are two identical squares but with opposite orientation, the winding must be 0. It's not that simple.

So how to determine the correct winding in these cases? I think by calculating the "on-path winding". This can still lead to incorrect results if the overlapping curves are not fully identical, but those cases should get a bad quality factor.

Welcome back "on-path winding"!

[iconexperience]

BTW, this is a perfect example to show why I selected odd values for propagateWindings(). If you check the windings at time values 0.25, 0.5 and 0.75 of a square, you will always check at a corner. This will not happen as easily if you use random looking values like 0.2341, 0.48732 and 0.76132 (or 0.1, 0.48, and 0.9).

[lehni]

@iconexperience thanks for looking into this! I agree with you, but I think we need an implementation that can handle these offsets because there will always be a shape that will be able to trigger this error otherwise. I was basically hoping to hit these errors eventually that you were addressing by shifting the factors : )

[iconexperience]

Yes, I agree, this should be our goal. There are several approaches that I thought of, but all have their problems.

1. If we encounter a corner, try again by casting the ray along the other axis (vertically instead of horizontally or vice versa). This approach would solve this issue, but fails if the squares are not rotated. Also, it would fails for corners with small angles, like the following case, which fails for both axes:

2. Add the winding to left winding and right winding if we are on a path. This does not help in this example, because we will be on the path twice and the windings would cancel each other.

3. Use 0.25, 0.5 and 0.75, but if we happen to be at a segment (t < winding epsilon || t > 1 - windingEpsilon) we will move the time value away from the segment. This may be the best approach. There could still be problems with corner with very small angles, but most of those would get a bad quality factor. Still no guarantee for a correct result, but the number of wrong winding values should be much, much smaller.

[lehni]

@iconexperience just quickly, regarding 3:

Aren't we already doing this in https://github.com/paperjs/paper.js/blob/develop/src/path/PathItem.Boolean.js#L718?

Your'e proposing to use windingEpsilon, but that's not for the curve-time space... And it's actually smaller than CURVETIME_EPSILON.

[lehni]

@iconexperience I've just brought the on-path winding handling back in 48e9ef6, and it looks like together with another change I made earlier, both rotated and not rotated squares are now handled correctly. I haven't addressed 1. & 3. of your suggestions above at all yet.

[lehni]

@iconexperience: Regarding suggestion 3: The problem is that we'd need to physically be windingEpsilon away from the segment (either horizontally or vertically, depending on
dir), but that does not translate to the same amount in curve-time, and there is no quick way translate one to the other. Do you think this is still required now that the on-path winding is back? I am not sure if I can close this issue after implementing a unit test for it, or if there is more to do now?

Regarding 1: How would we determine we're on a corner inside getWinding()?

[lehni]

This has been long fixed, since around v0.11.0