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: a3a3a2ec1ba4f3e77a7ad56d777c72df8f141469

[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]

What is the advantage of always calling setClockwise()?

[iconexperience]

Oh, and be careful. You forgot to remove the line // The first, largest child can be skipped. :wink:

[iconexperience]

I think mine calls it less often :smile:, please note the break statement. It only gets called once per child, and only if there is a containing, non-excluded child. But yours is probably better in the long run, because if clockwise then will be defined for all children and does not need to be caculated again the next time getClockwise() is called. And it is better to read.

[lehni]

Hmm but doesn't the break mean that the windings code isn't executed properly for all children then? I don't fully understand it all yet...

[iconexperience]

After a little sleep I am quite confident that we have found a nice solution here. And performance of the function should be considerable better that before, because for each child we only iterate up until we find the first containing, non-excluded child.

[iconexperience]

The break statement works, because we run through the children from largest to smallest. This means that for every child, all potentially containing childs have already been processed and their orientation has been fixed. Since we want to achieve alternating orientation, all we have to do is to find one non-excluded child that contains the current child, and we can simply set the orientation as the opposite of the containing child. (@lehni I know that you already understood this, but this is for future reference).

[iconexperience]

@lehni I noticed that we make a lot of calls to contains(), which always calculated the winding without checking if the point is inside the handle bounds. Adding bounds checking somewhere should yield in a performance improvement, because calculating the winding is quite an expensive operation (at least if the point is within the path's vertical bounds). Let's keep this in mind if we think that performance of the boolean code needs better performance.

[lehni]

I think the difference between mine and your versions is as you say simply that mine always calls setCockwise(), and this is currently a must, since insertChildren() on CompoundPath is trying to do something clever with the winding itself (first child = clockwise, all others = counter clockwise). That strategy is of course terrible, and should be fixed as well.

Would you like to help implement a strategy that's fast in CompoundPath#insertChildren() that is better than the current state of affairs?

And I believe insertChildren() has a hidden parameter that allows the deactivation of this process, but the used setChildren() doesn't. That's easy to fix though.

Regarding the optimizations, I think we should implement this straight away. There already are getters for handle bounds. I will look into it.

[lehni]

I'm going to add this comment to the code: https://github.com/paperjs/paper.js/issues/869#issuecomment-167509150

[iconexperience]

Great. I will try to help with the strategy, but give me some time today for the fat line clipping. I hope that I have some initial sketch finished tonight.

[lehni]

Super! No rush at all with the other stuff. Meanwhile I shall look into this one, a bit frightened: #870

[iconexperience]

I am sorry to bring this up again, but I just noticed that we can go back to start the iteration at index 1 again. This will save us one call to getInteriorPoint(), which can be quite an expensive operation.

[lehni]

Don't be sorry! So the same code works with index 1?

[lehni]

PS @iconexperience you'll be pleased by this: 3abffab5ebb47c1a328361c0382994e2dd161dab

[lehni]

Hmm the current implementation is still making trouble. Here an example

Used to look like this:

Now looks like this:

Going back to the version that always sets clockwise solves this issue though, so I guess that solves it! But I can't seem to start iteration at index 1, that doesn't work at all for me...

[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.