New #resolveCrossing() does not handle 'nonzero' fill-rule properly.

[lehni]

Example:

var data = "M356.6,301.2L356.6,336Q356.6,343.2,353,351.4Q349.4,359.6,341.8,366.6Q334.2,373.6,322.2,378.2Q310.2,382.8,293.4,382.8Q285.8,382.8,278.4,381.2Q271,379.6,265.6,376Q260.2,372.4,256.8,366.6Q253.4,360.8,253.4,352.4Q253.4,339.6,259.2,332.2Q265,324.8,274.2,320.8Q283.4,316.8,295,315Q306.6,313.2,318,311.8Q329.4,310.4,339.8,308.2Q350.2,306,356.6,301.2Z M313,196.4Q295.8,196.4,280.2,200Q264.6,203.6,252.6,211.8Q240.6,220,233.4,233.2Q226.2,246.4,225.4,265.6L259.4,265.6Q260.6,242.8,275,234.6Q289.4,226.4,311,226.4Q319,226.4,327.2,227.6Q335.4,228.8,342,232.4Q348.6,236,352.8,242.8Q357,249.6,357,260.8Q357,270.4,351.4,275.4Q345.8,280.4,336.2,283Q326.6,285.6,314,287Q301.4,288.4,287.4,291.2Q274.2,293.6,261.6,297.2Q249,300.8,239.2,307.8Q229.4,314.8,223.4,326Q217.4,337.2,217.4,354.8Q217.4,370.4,222.8,381.4Q228.2,392.4,237.6,399.4Q247,406.4,259.4,409.4Q271.8,412.4,285.8,412.4Q307.4,412.4,326,405Q344.6,397.6,358.6,380.8Q358.6,397.6,366.4,405Q374.2,412.4,387.4,412.4Q403,412.4,411.8,407.2L411.8,380.8Q405.8,382.8,401.4,382.8Q393.4,382.8,392,377.2Q390.6,371.6,390.6,359.6L390.6,253.2Q390.6,235.2,383.8,224Q377,212.8,365.8,206.6Q354.6,200.4,340.8,198.4Q327,196.4,313,196.4Z";
var path1 = new CompoundPath(data);
path1.fillColor = 'red';
path1.resolveCrossings();

Result:

[lehni]

@iconexperience I am going to compare it with the old #reorient() now to spot the differences.

[lehni]

The change happened here: a3a3a2e

[lehni]

Interesting!

Your code does this:

path.setClockwise((counter % 2 === 0) === clockwise);

The old code was doing this:

path.setClockwise((counter % 2 === 0) && clockwise);

And that works! So the comparison is different based on the rule.

[iconexperience]

Yes, that seems to be a problem. My thought behind the change was that the rule will not work if the first child is anti-clockwise. I still think that this is a prolem, but it looks like my solution is not working well.

[lehni]

Yeah if I switch to the old way, then your example isn't working anymore. :/

[iconexperience]

But why isn't this example working? it's only two children, already alternating orientation, the first one is clockwise, nothing special at all. It should work.

[lehni]

I think the outer path is not clockwise, that's why...

[lehni]

Here some debug logging for the child:

counter % 2 === 0: false
clockwise: false

[iconexperience]

Wow, the interior point of the second child is not inside the first one:

The sketch

[lehni]

Watch out though, you're running on an old library... But I do get false too there. Odd!

[iconexperience]

Oh, the inner path is child zero, the outer child one.

[lehni]

yes, just realized the same : )

[lehni]

Here's what I propose: After sorting the children, we set the first one to clockwise always. We do the same already for normal paths anyway:

// TODO: Is this really required? We don't do the same for
// compound-paths:
// Paths that are not part of compound paths should never be
// counter- clockwise for boolean operations.

[lehni]

This works like a charm, with your example as well as all my other tests: Sketch

[iconexperience]

Hmm, what if we use the original orientation from before resolveCrossings()? Currently we sort the children, and then take the orientation from the first child. Should we take it before sorting?

[lehni]

I don't think that will improve the situation. With the example above, the first child is the inside of the path, which is completely strange. And we've always set #clockwise to true for simple paths.

If we allow the main path to be counter clockwise, then subtracting it will actually add it...

[lehni]

Or maybe I'm wrong about that last assumption.

[iconexperience]

It works with this example:smile: I see a problem if for two overlapping compound paths one of them changes orientation. I do not know how realistic this scenario is in a real world scenario.

[lehni]

I'm happy to preserve orientation if there's a way to actually make it work with this example. I don't think your suggestion would fix it.

[lehni]

Oh wait, yes the first child is clockwise... Hmmm.

[lehni]

Ok, I have it: Updated Sketch

I need to start with the winding number for the first child as the starting counter, and then just use counter % 2 in the end. Bingo!

[iconexperience]

Here is another sketch where the larger circles are stacked on top of the smaller ones. Your change works, but give me ten minutes to see if I find a way to keep the original orientation.

[lehni]

And actually, counter = clockwise ? 1 : -1 is wrong, since counter != winding. But counter = 1 works just as well : D

[lehni]

I'm sorry, I'm tired. I forgot to remove that line... Now here's the up-to-date version, with counter = 1 and no changing of the original orientation. And it works: Updated Sketch

[iconexperience]

There are some cases where it fails. Just press "run" several times and watch the circles at the bottom. This is tricky.

[lehni]

Yeah I just saw that too... I'm giving up for the day, brain fried. Setting clockwise to true on the main path would be the easy way out I guess.

[iconexperience]

Yes, but give me time until tomorrow afternoon to see if there is an easy way to keep orientation. You did some amazing work today.

[iconexperience]

Here is a version that keeps the orientation of the original first child. But does it make sense at all to keep the orientation of the first child? Or should we keep the orientation of the bottom child(ren)? I will think about it after some sleep.

[iconexperience]

And here is a version that keeps the original orientation of the bottom children (the ones that have no containing, larger child). Currently I like this one best, but let's sleep first.

Note that in the last two examples we iterate through all children (including the largest).

[lehni]

Very cool! What about this one, then?

[iconexperience]

If you start from index 1, you certainly have to add the first child to the items previously. Does it still not work?

And the difference now is that all the bottom children (the ones that are not contained in another child) will have the same orientation. Maybe that's the right way to go.

[iconexperience]

@lehni
There is still a bug in our algorithm. Look at this example:

var cp = new CompoundPath();
cp.addChild(new Path.Circle(100, 100, 50));
cp.addChild(new Path.Circle(100, 100, 30));
cp.addChild(new Path.Circle(200, 100, 20));
cp.fullySelected = true;

It looks like this (I have added the index that the children have after sorting in resolveCrossings():

What is happening is this:
child 0: no containing child, orientation will stay clockwise
child 1: child 0 is containing child, orientation will stay counter-clockwise
child2: no containing child found, but clockwise is still set to false from child 1, therefore it will be set to counter-clockwise.

To solve this, we have to set ``clockwise = first.isClockwise()` for each child, not only once at the beginning.

Solving this should also solve issue #877.

[lehni]

Yes that makes sense! But I discovered some other issues that are linked to this change, mainly: Sketch

Both paths have counter-clockwise orientation and now they both remain counter-clockwise. I wonder if that's the reason why the unite() command fails, before they used to be forced to be clockwise. What do you think?

[lehni]

Hmm but are you sure that solves it? Doesn't seem to a my end...

[iconexperience]

It works on my side. I pull the clockwise = first.isClockwise() into the for(i) loop, and my issue #877 works.

[lehni]

Not for me, on the develop branch. What am I missing?

[lehni]

Oh, I see now. Your example has an error and I fixed it wrongly. cp2 doesn't exist, so I replaced it with cp but it was meant to be replaced with p : )

[lehni]

Regarding the issue described in #869 (comment)

It turns out that this is simply a bezier clipping problem again, as some intersections aren't found when the paths are oriented the other way. And like with all the others, this one too gets fixed by #863

@iconexperience this has me wondering why we're not just merging that one in? I really haven't come across a situation that it doesn't handle yet.

[lehni]

I'm proposing that because I keep ending up in situations where I spend time debugging a case that would already be solved if this was merged in. And merging it in doesn't mean you can't keep improving fat-line clipping in parallel! : )

[iconexperience]

Yes, I was about to propose the same. I can then test with the new code.

Basically, what I expected to find were some edge cases that take extraordinarily long time to solve with fat line clipping. If you take any curve, divide it somewhere and then try to find the intersections, fat line clipping will theoretically iterate forever at the point where the curve was divided.

But there seem to be other cases that fill the whole tree (or a huge part of it), which is 2^24=16,777,216 calls to addCurveIntersections() this can cause an app to freeze for a few seconds, which is not nice at all.

Alright, let's merge the sucker and I will then try to find these elusive cases without pressure.

[lehni]

@iconexperience oh fuck merging #864 in seems to have messed tons of things up now. I get all these commit messages twice now, see above...

[iconexperience]

You broke the intenet!!! 😄 Unfortunately there is nothing I can do for you in this case. Creating a pull request is my highest achievement in Git so far.

[lehni]

I don't really understand it either... Now I'm worried something else is missing. Argh.

[lehni]

I think it's because I accidentally did a rebase instead of a merge. Oh well, should be all there.