Boolean Intersections inside overlap ranges need special handling

[lehni]

That's why this special case is misbehaving: It has two intersections inside the overlap range, and currently deals with them wrongly:

var path1 = new Path({
    pathData: "M495.9,1693.5c-42.2-203.5-64.5-304.9-78-299.9 c-1.7,0.6-0.3,6.7,5.3,22.5l209.4-74.8l75.8,303.9L495.9,1693.5z",
    fillColor: 'red'
});
var path2 = new Path({
    pathData: "M632.6,1341.2l-209.4,74.9c95.4,267,135.6,201-60.1-144.5l202.9-85.7 L632.6,1341.2z",
    fillColor: 'blue'
});

view.center = project.activeLayer.position;

var res = path1.unite(path2);
res.fillColor = new Color(1, 1, 0, 0.5);
res.fullySelected = true;

[lehni]

@iconexperience I believe this is probably one of the reasons why you still see many edge cases failing.

[iconexperience]

Here is a visualization that may help understand how the graphs really look and overlap/intersect:

[iconexperience]

@lehni I am trying to understand what the algorithm should be doing and what it actually is doing. This could result in a small tutorial on the algorithm.

path1.getIntersections(path2) returns 4 intersections as seen below. At the right no intersection is found, which seems to be correct, becausel the point of path1 is slightly lower than the point at path2.

[iconexperience]

For both paths isClockwise()returns true. The winding of the path looks like this:

[iconexperience]

@lehni I have a question. In my paper-full.js I find code that reports intersections in splitPath() (starts with "if (window.reportIntersections) {"), but for some reason I cannot find this in the code repository. Can you tell me where that comes from?

[lehni]

That's debugging code only present on the boolean-fix branch. It allows me to turn on different types of reporting on the fly, in different places of scripts.

[iconexperience]

Here is a simple case that may be related to this issue:

var path1 = new Path({segments:[[291.7897242789684, 277.5989417824601, 0, 0, 13.316128368611714, 0.640602333086008], [327.3456172268099, 290.1359149875662, -10.196832025194396, -7.77472416139517, 0, 0], [290.966123770396, 337.8489368563888, 0, 0, 0.31321026490036274, 0.23881176115298786], [288.90662346713884, 337.5296328322788, 2.271007242607766, 0.10925191600728112, 0, 0]], closed:true});
var path2 = new Path({segments:[[327.3456172268098, 290.13591498756614, 0, 0, 19.811016870743288, 15.105200433449113], [360.2151963881203, 346.65852702489184, -5.176641576045313, -15.059210923779858, 0, 0], [303.474044239247, 366.16344058067085, 0, 0, -7.429072703960344, -21.61168996801632], [290.9661237703961, 337.84893685638883, 2.162840338313117, 1.649089344021263, 0, 0]], closed:true});

path1.fullySelected = true;
path2.fullySelected = true;

var result1 = path1.unite(path2);

[iconexperience]

@lehni I am trying to understand what is happening in my example above. While looking through the code if found in PathItem.Boolean line 367: // But since curves may contain more than one loop of curves

Is this a typo and the first "curve" should be "path"?. Or is this correct and can you explain with a short example what it means?

[lehni]

I can't remember exactly, but I think it refers to the monoCurves array, which may contain more than one loop of curves if it's produced by a compound-path. curve.next !== curves[i + 1]Detects the start of a new loop of curves in such an array. I need to improve the comment!

[iconexperience]

OK, thanks. No need to work on comments now, I will get along.

[iconexperience]

I have now simplified my simple test case to a very simple test case.

This fails with the current boolean-fix branch:

var path1 = new Path({segments:[[300, 290, 0, 0, 0, 0], [300, 340, 0, 0, 0, 0], [270, 310, 50, 10, 0, 0]], closed:true});
var path2 = new Path({segments:[[300, 290, 0, 0, 0, 0], [350, 320, 0, 0, 0, 0], [300, 340, 0, 0, 0, 0]], closed:true});

path = path1.unite(path2);

But interestingly this works:

var path1 = new Path({segments:[[300, 300, 0, 0, 0, 0], [300, 340, 0, 0, 0, 0], [270, 310, 50, 10, 0, 0]], closed:true});
var path2 = new Path({segments:[[300, 290, 0, 0, 0, 0], [350, 320, 0, 0, 0, 0], [300, 340, 0, 0, 0, 0]], closed:true});

path = path1.unite(path2);

This shows that my test case had nothing to do with the tiny loop or any tolerances.

[lehni]

That's a great test-case to see what might be going wrong, thanks! Will compare the two tomorrow if I find the time!

[lehni]

A quick inspection shows that when it goes wrong, it happens to start in a self-intersecting point, and probably doesn't discover that... When it goes right, it handles the self-intersection as it started somewhere else.

[lehni]

I couldn't stop looking for it... So it turns out that my getWinding() check in the handling of overlapping is not reliable. I check an arbitrary point along the curve (at t=0.5) to see if it's part of the boolean result or not, since the winding contributions for both overlapping points cannot be trusted. But the thing is, the way getWinding() is implemented right now, points along the curve might either fall inside or outside due to tiny imprecisions.

[lehni]

The other issue I am observing is that #clockwise of path1 is false, because it has a self-intersection... So the algorithm walks along it in the wrong direction after it crosses the self-intersection. I have a feeling we need to reintroduce the dir variable that controls direction, and find a way to determine the correct direction for each loop. Oh dear!

[lehni]

I think the whole self-intersection code needs more work. The paths / loops need to be reoriented once the intersections are resolved, not before. I'm now convinced this will solve many of the remaining issues that we're observing.

[lehni]

The issue described here appears to be solved with my latest commits.

[iconexperience]

Unfortunately I found more cases that fail. This one looks the same as the issue above, but still fails here.

var path1 = new Path({segments:[[380, 240, 0, 0, 0, 0],
    [365, 265, 0, 0, 0, 0],
    [331, 216, 0, 0, 0, 0],
    ], closed:true});
var path2 = new Path({segments:[[365, 265, 0, 0, 0, 0],
    [364, 269, 1, -5, 0, 0],
    [304, 264, 0, 0, 0, 0],
    [331, 216, 0, 0, 0, 0]], closed:true});
var result1 = path1.unite(path2);

[lehni]

How is it performing for you otherwise? Any improvements?

[iconexperience]

Sorry, not so much. The same or even a little bit worse. I cannot test much tonight and check if there are any new issues, but hopefully tomorrow.

But as I wrote before, I have the feeling that there are two kinds of issues. This type does not seem to be fully fixed yet, and the other one is the intersection on multiple curves. So no need to worry.

[lehni]

Good news: This will be fixed as soon as I implement handling of multiple intersections in the same location. I get this message here in the log:

Segment already has an intersection: { point: { x: 364.95511, y: 264.9353 }, index: 0, parameter: 0 }, { point: { x: 364.95511, y: 264.9353 }, index: 0, parameter: 0 }

And if I change the code to prefer the newer intersection over the older one, then this example works correctly, but others fail. That's why we need some code that chooses the right one. Looks to me like the two known failing cases are actually the same issues now: #787

You can change the behavior yourself simply by removing the else in this code:

if (segment._intersection) {
    console.log('Segment already has an intersection: '
            + segment._intersection + ', ' + loc._intersection);
} else {
    segment._intersection = loc._intersection;
}

->

if (segment._intersection) {
    console.log('Segment already has an intersection: '
            + segment._intersection + ', ' + loc._intersection);
}
segment._intersection = loc._intersection;

[lehni]

@iconexperience as described in https://github.com/paperjs/paper.js/issues/787#issuecomment-141706676, a lot of progress was made here. Time to do more testing!

[iconexperience]

@lehni OK, things look much better now than after your first attempt. I would say the number of cases where unite() fails are now roughly the same as before your work on multiple intersections on same point. So if you are aware of some remaining issues, you are on the right track. Is there anything special that I should look for, or should I post an example of a case that fails?

[lehni]

@iconexperience I will let you know when I finished the transition, for now I'm still smoothing out some edge cases. But I just got the edge case in #787 to process correctly!

[lehni]

@iconexperience since my last couple of commits, things look very good at my end now. There is one last issue I am aware of, but please feel free to start testing and filing issues!

[iconexperience]

Yes, that looks pretty slick. I can still see a few glitches, but this is the best version ever. Great!

Just let me know if I should send examples of the glitches, but maybe I should wait until everything works on your side.

[iconexperience]

@lehni Just noticed one case with an infinite recursion on getIntersection(). Should I try to reproduce and post it here?

[lehni]

Did you pull again? I just addressed an occasional infinite loop around the time you posted :)

[lehni]

Great to hear it works very well! We're getting there. So good!

[iconexperience]

Here is the (rather complex) case for the infinite loop that I am still getting. There seem to be two other problems occuring before, so maybe it is just a result of another issue.

var paths = [
new Path({segments:[[350.1904890845487, 161.3948069310073, 0, 0, 0, 0], [320.21009023604273, 156.37122769383404, 0, 0, -2.256368701042561, 13.46586376222993], [331.3310186359364, 137.39167890305538, -12.169783030983865, 9.56190639701586, 0, 0]], closed:true}),
 new Path({segments:[[349.8668755956758, 160.9829323756662, 0, 0, 0, 0], [331.3310186348609, 137.39167890390038, 0, 0, 3.756079303980414, -2.951184802256563], [352.0504449338527, 131.0603144476927, -9.765954340606129, -0.7126595175433295, 0, 0]], closed:true}),
new Path({segments:[[349.86687559362423, 160.9829324037806, 0, 0, 0, 0], [352.0504449334797, 131.0603144476655, 0, 0, 9.767001401257744, 0.7127359254925523], [371.63274390700997, 140.33415011123003, -3.287893443528219, -3.4657663927280566, 0, 0]], closed:true}),
new Path({segments:[[349.48527836926536, 161.3449449775435, 0, 0, 0, 0], [371.6327439082022, 140.33415011248672, 0, 0, 10.65314301848548, 11.229471297902506], [379.8790663653175, 160.7314423698879, 0.27562607274597895, 13.654905972180785, 0, 0]], closed:true}),
new Path({segments:[[379.8790663653175, 160.73144236988702, 0, 0, -0.08579547940030352, -4.250429548903014], [488.9393770928646, 335.3362523624572, -112.31068321628379, -124.17382623972674, 0, 0], [444.4406229071354, 375.5837476375429, 0, 0, -118.61580589781784, -131.1449458683842], [319.89128581744535, 161.94230360898052, 0.2939582701459358, 14.563108992527873, 0, 0]], closed:true})];

var result = paths[0];
for (var i = 0; i < paths.length; i++) {
  result = result.unite(paths[i]);
}

Update: simplified a bit by removing the first path.

[lehni]

Great, thanks! Almost all of these go away when I increase GEOMETRIC_EPSILON to 1e-7... What I wonder is if they would reappear again with smaller differences between the points.

One question that's probably easier for you to answer than me to inspect: Do these paths overlap precisely, or are there slight differences in the overlapping sides? Do they use the exact same coordinates or not?

[iconexperience]

@lehni No, the paths do not precisely overlap, the points are close, but not identical. They should be identical, which is a weakness in my algorithm. Seems like my current algorithm for getting the curve offset is not very good, but this makes it great to find edge cases for testing the boolean operations :smile:

[lehni]

Hehe, that's the perfect excuse for a sloppy algorithm 😛 No, it's really great we're putting it through such hard tests. The question also is: Should it actually merge these points, or not? Illustrator merges most of them... With 1e-8, paper.js doesn't. But I guess either way it should handle the resulting situation. I'll figure it out eventually, I'm sure. I got pretty good at understanding almost all aspects of the algorithm now (and hugely changed big parts of it), never thought that would happen...

[iconexperience]

Yes, I could feel how you got better and better. I was lost along the way, so I focused on testing and doing simpler things like my self intersection preprocessor, which I think is really good once it gets a little more polishing.

I don't know how much time you have at the moment, but if you can invest another week or two (or maybe three), the boolean operations will become perfect, I am sure about that.

[lehni]

I think this was and is great teamwork! I am hoping that my work on the algorithm and the added comments will improve understandability of it all. I think the code has become more readable already, but maybe it's just me learning about it.

Unfortunately I will have less time to work on things for the next 3 weeks or so, but will try to keep at it here and there. I will probably merge the current state into develop without the debugging comments and get a release out, since things have improved a whole lot already.

Thanks for all your help with things so far! I really appreciate the team work dynamics!

[iconexperience]

Maybe now is the right time to say what I did not dare to say the last days, because I did not want to make you upset:

There are seven non-breaking spaces in the boolean-fix code, that I had to remove after each build :grinning:

[lehni]

Hahaha for crying out loud! How do they keep sneaking in? And how is it not breaking my execution : ) Anyway, I'll run a search'n'replace right about now. And I need to figure out what I am doing differently than all these years. Or is it my OS 10.11 beta? : )

[iconexperience]

And why does it work on your system, but not here? It cannot be the build process, because I remember there was a distribution that had the nbsp in it. How do you even type a nbsp? ctrl + space?

[lehni]

I'm not building the lib while developing. I'm loading it directly from the separate files through prepro.js / load.js (my own little hack for fast development, it handles all the includes and other build-time statements at runtime). And for some reasons he nbsp don't cause issues on my system. I seem to by typing them with alt-space on the Swiss German Mac keyboard. And alt-7 writes the | sign. Which is why it always occurs before or-statements :) I need to turn that off!

[lehni]

Fixed in b68be09c879d1eb6ec8559198cc6f9825dd2422c!

[iconexperience]

@lehni Here is a very simple example that still causes an infinite loop.

The two touch points are identical:

var path1 = new Path({segments:[
[450, 230, 0, 0, 0, 0],  
[362.46932779553646, 264.4394368330295, 0, 0, 0, 0], 
[329.00715661950534, 214.6369961279195, 0, 0, 0, 0]
], closed:true});
var path2 = new Path({segments:[
[362.46932779553646, 264.4394368330295, 0, 0, 0.5029830904762775, -0.33795344231873514], 
[331.7750437531172, 267.3071389516512, 0.33347583635435285, -3.453534396532916, 0, 0], 
[329.00715661950534, 214.6369961279195, 0, 0, 0, 0]
], closed:true});

If I remove the handles from the non-touching point at the left, the problem disappears:

var path1 = new Path({segments:[
[450, 230, 0, 0, 0, 0],  
[362.46932779553646, 264.4394368330295, 0, 0, 0, 0], 
[329.00715661950534, 214.6369961279195, 0, 0, 0, 0]
], closed:true});
var path2 = new Path({segments:[
[362.46932779553646, 264.4394368330295, 0, 0, 0.5029830904762775, -0.33795344231873514], 
[331.7750437531172, 267.3071389516512, 0, 0, 0, 0], 
[329.00715661950534, 214.6369961279195, 0, 0, 0, 0]
], closed:true});

[lehni]

I've used my time on the airplane to New York to fix all kinds of things. The issue you reported above is already addressed. Give it another go, I think things should have improved once again quite a bit! But there is one more issue I became aware of that I have some ideas about how to fix... It's getting very solid all in all!

[iconexperience]

Thanks, things got better again, and I think there are a few new glitches. Should I continue posting examples of failed cases, or should I wait until you fixed the bug you already know?

In any case, don't spend too much time in New York with working on PaperJS, there are too many other things to do.

[lehni]

The bug is fixed, so yes please post the glitches. I won't work much on it here promised :)

[iconexperience]

I will send a few new examples over the next days. I have noticed two things:

1. There seem to be (almost) no CompoundPaths anymore. May cases that previously resulted in a compound path has a simple path as a result now. That's great, and much better for debugging.
2. There are no non-breaking spaces anymore :wink:

[iconexperience]

Here are the first two examples, both resulting in an infinite loop. I suspect that in both cases the handles of the two touching points are a problem, because they are collinear.

In the first case the intersection at the touch point is found twice. Is this the correct behaviour, or should Curve.getIntersections() only return one intersection. ` Example 1:

var path1 = new Path({segments:[
[211.76470809030513, 391.5530064242439, 0, 0, -1.1306561612996688, -11.284564044000547], 
[206.28516988159765, 416.3206370377553, 9.29930425192211, -12.510751934521268, 0, 0],
[142.17355611649077, 367.3087985311291, 0, 0, 0, 0]
], closed:true});
var path2 = new Path({segments:[
[152.06363005021922, 397.5347520600572, 0, 0, 0, 0],
[218.65631922872535, 332.74836297575644, 0, 0, -9.581012775680733, 10.097912103353224],
[211.76470809030513, 391.55300642424385, -1.8914123817368989, -18.8773252964819, 0, 0]
], closed:true});

var result = path1.unite(path2);

Example 2:

var path1 = new Path({segments:[
[138.3141655808707, 456.06810826237086, 0, 0, 1.6246548956081597, -1.188772469512287],
[103.70383447788026, 471.4426853592628, 15.914191732656704, 1.2415901505934812, 0, 0],
[147.64340975918196, 340.17263448268653, 0, 0, 0, 0]
], closed:true});
var path2 = new Path({segments:[
[102.88355437423151, 307.6462971693936, 0, 0, 0, 0],
[311.9175162439421, 379.75248280363354, 0, 0, -68.45789375971557, 0.5465997368099806],
[138.3141655808706, 456.06810826237097, 33.643258081480184, -24.617030422937262, 0, 0]
], closed:true});

var result = path1.unite(path2);

[iconexperience]

If the issues above are really caused by collinear handles, the solution provided by Cary Clark my be useful: https://youtu.be/OmfliNQsk88?t=1483 (Update: His solution may not be useful for us, since he seems to be using quadratic curves only).

Also using the curvature in addition to the tangent may be useful.

[iconexperience]

Here are two other example that still fail. These result in a Visited segment encountered, aborting message. As you can see all curves are straight, but in both examples two curves are partially overlapping. The cause for the problem is probably the same in both examples.

Example 3

var path1 = new Path({segments:[
[260.5630488345416, 240.11728335016855, 0, 0, 0, 0],
[230.82205831331396, 236.1805613638536, 0, 0, 0, 0],
[300.041224753361, 200, 0, 0, 0, 0],
[300, 300, 0, 0, 0, 0]
], closed:true});

var path2 = new Path({segments:[
[290.30323645974596, 244.0538990495128, 0, 0, 0, 0],
[320, 280, 0, 0, 0, 0],
[230.82205831199582, 236.18056137381197, 0, 0, 0, 0]
], closed:true});

var result = path1.unite(path2);

Example 4

var path1 = new Path({segments:[
[266.2339624919457, 249.28592706878334, 0, 0, 0, 0],
[236.42561910533144, 245.88969337410168, 0, 0, 0, 0],
[320, 240, 0, 0, 0, 0],
[280, 300, 0, 0, 0, 0]], closed:true});
var path2 = new Path({segments:[
[296.03993000559, 252.68189006496056, 0, 0, 0, 0], 
[320, 300, 0, 0, 0, 0], 
[236.42561910512714, 245.8896933758947, 0, 0, 0, 0]
], closed:true});

var result = path1.unite(path2);

[iconexperience]

Here are two examples, each with a nasty tiny loop. These throw a Visited segment encountered, aborting message, too, but I think the cause of the problem is different than in Examples 3 and 4.

Example 5

var path1 = new Path({segments:[
[109.2693308633721, 249.31916869409733, 0, 0, 0, 0],
[157.6368865573791, 284.8238100271277, 0, 0, 0, 0], 
[150, 329.3972954455561, 0, 0, 0, 0]], closed:true});
var path2 = new Path({segments:[
[109.26933086337212, 249.3191686940973, 0, 0, 0, 0],
[157.1468245594682, 224.11329044817836, 0, 0, 0, 0],
[161.745373658654, 283.93680878488584, 0, 0, -4.753441100107182, 0.365390282896783],
[157.63688655737909, 284.82381002712776, -0.5599416549340219, 0.7628019369743697, 0, 0]
], closed:true});

var result = path1.unite(path2);

Example 6

var path1 = new Path({segments:[
[249.53400844979302, 269.5706278725207, 0, 0, -5.202299838213264, 1.3434437726778015],
[243.02912232136828, 272.45353289318496, -0.02459817048722357, 0.029126503110205704, 0, 0],
[197.1892333604494, 233.7404268430289, 0, 0, 0, 0]
], closed:true});
var path2 = new Path({segments:[
[243.02912232136822, 272.453532893185, 0, 0, 0.44566136595048533, -0.527704170852985],
[242.66927041668393, 276.2408467361064, -0.16957999946740188, -3.971488536288973, 0, 0],
[197.18923336044946, 233.74042684302884, 0, 0, 0, 0]
], closed:true});

var result = path1.unite(path2);

[lehni]

@iconexperience thanks for the examples! Example 2 - 4 is partly fixed by 515d4ff93d99f5b0e3e0951d2a57968a47987320 (still producing some errors but the resulting shapes look good).