Unite operation results in empty path

[iconexperience]

Here is an example of a unite operation that results in an empty path:

var p1 = paper.PathItem.create("M933.13,1023.97l-516.19,-171.71l607.1,-101.57z");
var p2 = paper.PathItem.create("M933.13,1023.97l-516.19,-171.71l67.33,-11.27l337.49,112.27c16.7,-50.22 71.03,-77.36 121.34,-60.63l45.23,-135.96l35.71,-5.98z");
var res = p1.unite(p3);

Here is the sketch, but note that in the sketch everything works as expected.

[lehni]

Ok, thanks.

Here the sketch with the view zoomed onto the shapes

[iconexperience]

What I find irritating here is that the intersections at the bottom corner actually results in splitting the curves there, although the distance of the points there is tiny (p1 = [1024.04, 750.69] and p2 = [1024.04, 750.6899999999999]). Since the curves are lines, t is smaller than tmax (t=0.9999994022573444) and as a result curves that are far shorter than our geometrical epsilon are created. Not sure if this is the reason why the unite operation fails, but I find it very strange.

[lehni]

Interesting indeed!

Here the sketch with intersections marked

More analysis soon.

[lehni]

And here the updated sketch keeping the circle size independent of the zoom level

With this you can see what the problem is:

On the right hand side, the green path appears to cross the red one, but when you zoom in, you can see that it doesn't seem to. The left part of the right "beam" is not crossing at all, and the right part appears to barely touch (no matter how much I zoom in, I can't see the two lines separately, before the rendering goes crazy because of too much zooming). So why is this not an overlap? It may just be another case of not finding an overlap. I would guess that this is the reason why it's not doing the right thing.

[lehni]

I found a way to adjust this and make the code not see it as a crossing, but the unite operation still fails. Could it be that this is a problem of the new winding code? I have to bring back my boolean debug code to look into the involved winding numbers, but it could be the source of the problem.

[iconexperience]

Here is the sketch using the "segment" form. I find this more useful for fiddling around.

Regarding the "not found overlap": I do not think this is the problem. If I move the green corner down a bit as in this sketch the problem persists.

Regarding your idea with the winding code: I think this is not the problem, either (but not sure), because I am using another version of the winding code and still see the same problem.

[iconexperience]

Maybe we are doing it still wrong when collecting the intersections. First we should look if end points of curves are close, using geometrical epsilon. If so, these intersections should get t=0 or t=1. Then we can look for more intersections using the curve/curve, curve/line and line/line algorithms. Doing it this way would at least prevent the creation of those super tiny curve fragments.

[iconexperience]

If I put the following code snipplet into getCurveIntersections() (just before addCurveIntersections()) this test case works:

      var c1p0 = c1.point1,
          c1p3 = c1.point2,
          c2p0 = c2.point1,
          c2p3 = c2.point2;
        if (c1p0.isClose(c2p0, epsilon))
          addLocation(locations, include, c1, 0, c1p0, c2, 0, c2p0);
        if (c1p0.isClose(c2p3, epsilon))
          addLocation(locations, include, c1, 0, c1p0, c2, 1, c2p3);
        if (c1p3.isClose(c2p0, epsilon))
          addLocation(locations, include, c1, 1, c1p3, c2, 0, c2p0);
        if (c1p3.isClose(c2p3, epsilon))
          addLocation(locations, include, c1, 1, c1p3, c2, 1, c2p3);

[lehni]

There is a reason why we don't look at these points first: Remember when we had a case where a line-line case would produce 2 intersections instead of only one, because one pair of start-/ end-points where closer to each other than GEOMETRIC_EPSILON? I think this case would be back now if we did it i the way proposed above.

BTW, in the code you're proposing, which values is epsilon?

And finally the question: Is there a reason for you to still use your own version of the winding code? Does the one in the library not work as well? And if not, could you provide cases where it fails?

[lehni]

@iconexperience I just tried your suggestion of adding the code snippet, but it doesn't change the behavior at my end (and the same code is already performed after addCurveIntersections(), just in different form).

Did you also change the epsilon?

[lehni]

Oh, and #1174 is the issue that breaks if I add this code and increase the epsilon... But the sketch above still fails for me on develop. Not sure how you managed to get it work?

[lehni]

@iconexperience the strange corner is not at the bottom, btw, it is at the top right. The distance between the found intersection and the actual corner is 6.597945674741107e-10, the curve-time of the found intersection is 0.9999994022573444. I just compared with the code that works, and there too this intersection was found. It had the same amount of intersections, the same curve-times, and the same winding contributions. The only difference is that it started in a different segment, and was lucky to not fail. I think this bug would occur in other similar constellations on the old code though, it's just that another case has "unlocked" this particular case on the new code. More investigation needed...

[lehni]

Oh, btw: The problem is that the tracePath() algorithm now starts exactly in this corner, and somehow doesn't manage to close the path because of the proximity...

[lehni]

I now found out that my tracePath() branching code isn't actually correctly trying all possible intersections, as well as not crossing, in all intersections. This is sort of huge, it may well mean that many of the other issues that I am seeing could be resolved as well. The fix is fairly trivial!

[iconexperience]

Sorry for again another useless proposal. I am currently working on so many things, so I tried to find a quick solution, but doing fundamental things in a hurry is just a bad idea. And I noticed later that the strange corner is at the top right, too.

Anyway, your observation is really interesting. It sounds like this could really be the breakthrough.

[lehni]

@iconexperience I have just pushed all the changes that fix this issue here. But it also introduced some new failures with unit tests. After analyzing the first problem, it turned out that this error was caused by the reintroduction of the following snippet (see https://github.com/paperjs/paper.js/issues/1073#issuecomment-270897288):

if (onPath && !windingL && !windingR) {
    // If the point is on the path and the windings canceled
    // each other, we treat the point as if it was inside the
    // path. A point inside a path has a winding of [+1,-1]
    // for clockwise and [-1,+1] for counter-clockwise paths.
    // If the ray is cast in y direction (dir == 1), the
    // windings always have opposite sign.
    var add = path.isClockwise(closed) ^ dir ? 1 : -1;
    windingL += add;
    windingR += add;
}

I have then removed it, but now another test case is failing, and I am not sure why yet. I am fairly certain that the snipped above is wrong though, as it leads to wrong winding numbers. I am tapping a bit in the dark with all this though, perhaps you can help me out? Also, I am still waiting for feedback on the winding changes outlined in #1073...

[lehni]

Here the newly failing sketch.

Note that it works alright on v0,10,2.

[lehni]

When zooming in on the bottom part o Firefox (all other browsers crap out due to very high zoom level), you can see the situation there:

What's interesting is that if I scale the active layer up by factor 10, everything works. Looks like winding imprecisions to me, but it's really hard to debug:

project.activeLayer.scale(10);

[lehni]

I just found that it appears to be OK to reduce windingEpsilon to 1e-9, and it solves this new issue here (see 4d3ca746aba7f965257e0eede2b5a93e9fca0616). All tests pass again, but I am not super comfortable with this solution. I really would appreciate to hear your opinion on these open winding questions, @iconexperience... And it would be good to reach a state where we're working with the same code base again, as otherwise we're just tapping more and more in the dark.

[iconexperience]

I started looking at our winding code and already found one, albeit unrelated part that can be improved.

In addWinding() if the curve is completely left or right of the abscissa's tolerance range, we simply use t=0.5 to calculate the abscissa's value, because it does not matter which point on the curve we use. This is not wrong, but we should select t=0, because this makes the calculation of amuch easier and faster.

[iconexperience]

One part of the code that I find suspicious is this line in addWinding():

} else if (a3Prev < paL && a > paL || a3Prev > paR && a < paR) {

I have my doubts that this only handles thoses cases that it is supposed to handle. It may handle other cases, too, which could cause trouble. I will have to think this though again.

[iconexperience]

Yes, I am pretty sure that part of addWinding() is not fully correct. It should probably be

                } else if (a0 != a3Prev) {
                    // A horizontal curve is between current and previous
                    // non-horizontal curve
                    if (a3Prev < paR && a > paR) {
                        // Right winding was not added before, so add it now
                        windingR += winding;
                        onPath = true;
                    } else if (a3Prev > paL && a < paL) {
                        // Left winding was not added before, so add it now
                        windingL += winding;
                        onPath = true;
                    }
                    // TODO: Determine how to handle quality when curve is crossed
                    // at starting point. Do we always need to set to 0?
                }

I have not tested if this fixes any of the remaining issues, but at least it passes all unit tests.

[iconexperience]

Here is an explanation of the code above. It is supposed to handle cases in which the winding of the path does not change (from upwards to downwards or vice versa) and there is a horizontal curve between two non-horizontal curves. The blue area is the range between paL and paR.

In case 1 the winding of the previous curve was not added, so we should add the winding of the current curve.

In case 2 the winding of the previous curve was added, but it is on the opposite side of the blue range, therefore we should add the winding of the new curve.

In case 3 the winding of the previous curve was added. The start point of the new curve is in the blue range, therefore the winding of the new curve will not be added.

In cases 4 and 5 the winding of the previous curve was added. In order to not add the same winding twice, the winding of the new curve will not be added.

[lehni]

@iconexperience great, thanks! That's very useful. I will look into it shortly and get back.

[lehni]

@iconexperience this looks reasonable. But we still need to figure out what to do with quality in these cases? At the moment, it is set to 0

[iconexperience]

@lehni The correct approach for the quality factor would be like this: In all these special cases we have two abscissa values, a3Prev (the end point of the previous curve, and a0, the start point of the current curve. We should find which of these is closer to pa and then adjust the quality factor as if we only had this one point. I will try to figure out how this looks in detail tomorrow.

[lehni]

@iconexperience thanks for the PR! This doesn't address the proposed way to handle quality yet, correct?

[iconexperience]

Unfortunately not. This only addresses the simple stuff. And the addressed cases are quite rare, therefore we should not see any changes at all, but it had to be done. Sorry for being late on the quality handling, I still have some other things to do first.

[lehni]

Another question: Should we use 1 for t here also?

Curve.solveCubic(v, io, po, roots, 0, 1) === 1
        ? roots[0]
        : 0.5,

[iconexperience]

If I see it correctly, if we arrive there something has gone wrong in solveCubic() and do not think this happens anymore. The 0.5 is just a fallback, and I think it is alright to take the average here.

[iconexperience]

Or maybe we should use

    Curve.solveCubic(v, io, po, roots, 0, 1) > 0
        ? roots[0]
        : 0.5,

But honestly, I do not think this makes any difference.