Paper.js: New boolean operations issue.

[lehni]

@iconexperience this one's again from your test-case.

var path1 = new Path('M419.20344565830516,384.34607379092466c5.844713611412715,3.313058909545532 8.737629565616828,3.6008009941920136 9.663847696961,3.5457774486854987c0.4249875971154893,-0.23215482613579752 3.134401138218834,-1.9001699951828073 6.912521889816844,-9.027614775318739c33.358079343370036,-62.930193110079074 15.048818377810562,-263.53585410399967 14.89110904614597,-264.2035689431943l58.39331120497843,-13.792070421750992c0.38461989956749676,1.6284160973869177 24.314056080847877,221.98511298279283 -20.271816008415897,306.09659649109955c-7.779727674038611,14.676497403570863 -19.843728834889646,29.87171953249475 -38.60350857895327,37.0189975138764c-20.692089248499826,7.88346749760683 -41.830098370105475,3.183730282850888 -60.57334789311045,-7.440826188961864z');
var path2 = new Path('M450.6709242911992,114.66066752097116c-5.7317866225195075,-24.267422495749997 -2.0221968032280984,26.377626042706837 32.186077599051714,22.94975715794014l-5.982390225081872,-59.70101345199127c34.20913357233178,-3.427954978623788 37.91990661944476,47.22024138695528 32.18962383106816,22.95918587255207z');

path1.strokeColor = 'red';
path2.strokeColor = 'green';
path1.strokeScaling = path2.strokeScaling = false;

var res = path1.unite(path2);

res.fillColor = 'yellow';
res.fillColor.alpha = 0.25;

It works online but doesn't with the latest develop branch. It could be that I was a bit too eager removing my edge-case code...

[lehni]

The good news is that it's the only failing case.

[lehni]

So I've been looking into this error here, and it turns out that the removed edge-case handling code in isCrossing()was actually returning a false result here as well, which then in turn has prevented this issue form happening. But the origin of the issue must be elsewhere.

[iconexperience]

Here is a simplification of the issue:

var path1 = new paper.Path({segments:[
    [450.67092429122897, 114.66066752109714, 5, 5, 0, 0],
    [509.0642354962074, 100.86859709934615, 0, 0, 5, 5]], closed:true});
var path2 = new paper.Path({segments:[
    [450.6709242911992, 114.66066752097116, 0, 0, ],
    [482.8570018902509, 137.6104246789113, -34.20827440227981, 3.4278688847666956, 0, 0],
    [476.874611665169, 77.90941122692003, 0, 0, ],
    [509.0642354962372, 100.8685970994721, 0, 0]], closed:true});

path1.strokeColor = 'red';
path2.strokeColor = 'green';
path1.strokeScaling = path2.strokeScaling = false;
var res = path1.unite(path2);

res.fillColor = 'yellow';
res.fillColor.alpha = 0.25;

And the Sketch

[iconexperience]

And here are the found intersections. The red dots are crossings:

It's interesting that the sketch finds the same intersections and the crossings are the same, yet it does not fail on this example, while the current develop version fails.

[lehni]

I think what finally comes to bite us here is the fact that so far we consider all overlaps as crossings without any further checks. There's already a TODO about this, time to finally implement it, it seems:

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

[lehni]

Actually, I think I'm wrong here. it shouldn't be a problem in the boolean code that we potentially split in slightly too many places, as long as we do the right thing after. This is probably a bug in #isCrossing(). And that explains why you see different behavior on the different versions.

[lehni]

Hmm, I think we see multiple issues here. First of all, isn't it weird in your example that the left intersection is no crossing, and the right one is? The right one really doesn't look like one, or am I wrong?

But the actual issue is hidden: The green shape is split into two by #resolveCrossings(). The point where it intersects with itself produces two intersections with the other shape (because there are now two paths). And one of them is considered to be a crossing, while the other one is not. That is what I believe the source of the problem here.

Here the image from the original case, with the circles in the center slightly shifted. And here, the intersections on the side are reversed. The left one should be green, not red, I think.

[iconexperience]

Why is the red circle in the middle so far off the line? This is strange.

[lehni]

I tried to say: I moved it so you can see both : )

[iconexperience]

Ooops :blush:

[iconexperience]

@lehni Sorry can't concentrate today, there is too much going on around me. Hope that I can do a little work tomorrow.

[iconexperience]

I am trying again to solve this issue. As a first step here is a version with only straight lines that still has the same issue.

[iconexperience]

And here is a further simplification. I have split the green shape at the self intersection and removed the right part.

Here is the result

This does not actually fail, but it finds three crossings between two paths, which cannot be correct. In Firefox when zooming in on the left crossing it looks like this:

So it seems like there should be two crossings (or no crossing), but actually one crossing is reported. This is the root of all evil.

[iconexperience]

And some more details:

• CurveLocation.insert merges the locations of the two intersections to one, therefore only one intersection/crossing is found.
• isCrossing() returns true, because the tvalues are far enough from the end points (although just slightly), and the curves are not merely touching tangentially (obviously).

So there is an inconsistency between there two.

[iconexperience]

I think the problem is in CurveLocation.js line 529. We should probably not simply calculate the distance between the points, but check if they are on different curves and if so calculate the distance as the sum of the distances to the segment point between the two points. The same is true for CurveLocation.js line 328 _Not true, see next comment_

Here is what I mean for our test case. Currently we use the direct distance between the two intersections:

But we should be using the distances from the curve point:

[iconexperience]

Ignore my previous post, I was wrong. The distance is already calculated correctly at CurveLocation.js line 346/347.

This means the bug is probably in CurveLocation.isCrossing().

[iconexperience]

Here is why our algorithm currently believes the intersection is a crossing. For better understanding I have slightly changed the direction of the the lines (in the example above the top red and green lines are almost parallel).

• Both intersections are merged into one, because they are very close to each other. This is fine.
• Since the intersection is very close to P1 and P2, the algorithm in isCrossing treats the intersection as if P1 and P2 are the same. With this assumption the intersection actually becomes a crossing:

So the question is how to improve our algorithm to detect these cases correctly.

[iconexperience]

Here is a better visualization of the weakness in our current algorithm used in isCrossing() in cases when the intersection is very close to a curve point:

[iconexperience]

Here is a proposal for cases where straight curves are involved (this should be the majority of these edge cases). Instead of comparing the tangential angles to determine the order of the curves we could compare the side of the end point of one straight curve relative to the other straight curve. This would need a little refactoring in CurveLocation.js lines 444 to 480, but it could work.

[lehni]

@iconexperience this sounds good. But it wouldn't actually solve the example in this issue above, right?

[iconexperience]

@lehni Yes, this may be completely irrelevant for this issue and I will hav another look. Acutally I am quite deep into the the boolean code, so I should use this momentum.

Thanks for all the work that you have done today.

[iconexperience]

@lehni Interesting, 719392d fixes my simplification, but not your original example.

[iconexperience]

Here are the calculated windings for the curves. Red means 2, green means 1

I think the red curve where the arrow points at is wrong, it should be green.

[iconexperience]

And here is where the winding has been calculated. Again, red means winding 2, green means winding 1.

(there are no hidden red dots under the green ones, I checked).

The red curve marked before probably got it's winding through propagation. Since a propagation chain always runs from crossing to crossing, this belongs to the same chain as the inner red curves. Maybe a chain should only run from intersection to intersection, no matter if the intersection is a crossing or not?

[lehni]

@iconexperience I can't see any errors in my initial sketch here anymore either! You sure there still are issues? : ) I love when this happens. Although I'd prefer if I actually understood what solved it...

[lehni]

@iconexperience regarding the chains, where do you see the code that makes the distinction between crossings and intersections there? I can't see it in propagateWinding(), and I think it was always behaving the way you describe it.

[iconexperience]

The result looks fine, but there is still an "open path" error message. That's probably the red curves.

Regarding the chains, I was probably wrong. I thought the segment._intersection exists only for crossing, but of course it's also there is there is an overlap.

But in your original example the three red curves build one chain.

Why isn't there an intersection at the top right breaking the chaing?

[lehni]

I'm not sure... But I don't get that message. Are you sure you're working with the latest code? Which example are you testing with?

[iconexperience]

Oh dear, I had a second test in my code that cause the message (but still a correct result). Sorry.

Anyway, let's just close this.

[lehni]

Not so fast... This was apparently fixed by 648beb33e90821843f1b19143aaaf04f119bcc6d, but that's causing a shit-ton of new issues, see here: https://github.com/paperjs/paper.js/issues/1054#issuecomment-225354937

[lehni]

Ok, I feel this is safe to close now. I will add a unit test for it and then close. Woop!