Paper.js: Unite operation wrongly fills inner path 2

[iconexperience]

Here is another example that still fails:

The shape in the middle should not be filled.

Here is the code:

var p1 = new paper.CompoundPath();
p1.addChild(new paper.Path.Rectangle(200, 100, 200, 200));
p1.addChild(new paper.Path({segments:[[274.616046379547, 215.30654471841746, 0, 0, 0, 0], [296.47810618021146, 202.68940186127458, 0, 0, 0, 0], [297.0266776087829, 160.32607960213838, 0, 0, 0, 0], [260.5870762798793, 181.99677727655697, 0, 0, 0, 0], [260.5870762798793, 207.20554804067655, 0, 0, 0, 0]], closed:true}));
var p2 = new paper.CompoundPath();
p2.addChild(new paper.Path.Rectangle(210, 110, 180, 180));
p2.addChild(new paper.Path({segments:[[260.5870762798793, 207.2055480406766, 0, 0, 0, 0], [274.616046379547, 215.30654471841748, 0, 0, 0, 0], [296.47810618021146, 202.6894018612746, 0, 0, 0, 0], [297.0266776087829, 160.3260796021384, 0, 0, 0, 0], [260.5870762798793, 181.996777276557, 0, 0, 0, 0]], closed:true}));

p1.strokeColor = "green";
p2.strokeColor = "red";
var res = p1.unite(p2);
res.fillColor = "rgba(0, 0, 255, 0.2)";

And here is the sketch

I suspect that the reason why this fails is that the overlapping paths do not start at the same point.

[lehni]

Yeah that's definitely the issue here. The code currently just performs a really basic check:

if (Base.equals(segments1, segments2))

Note that this will also fail if they start with the same segment, but one of them has more segments than the other (e.g. through curve subdivision).

What we need is a way to geometrically compare the appearance of two paths that does not rely on comparing actual segments. I guess we could look through all curves of the first path and see if they fully overlap with path2, and also compare the total length?

What do you think? This would also be the better code to compare results of boolean operations in the unit test suite...

[iconexperience]

Hmm, if all the curves overlap, do we really have to compare the total length? Wouldn't that be identical automatically?

[lehni]

No because if we loop through the curves of path1 and compare with path2 and they all overlap it doesn't mean that path2 doesn't have some extra curves that don't overlap. So I'd do the length comparison first, then check for the overlaps.

Another approach could be to check for overlaps by looping through both paths one after the other, and see if all curves fully overlap with the other path. But that sounds slower?

[iconexperience]

Yep, doing a length check first is definately faster.

Sorry, I have to stop for today.

[lehni]

Me too. No need to for apologies! : )

[lehni]

@iconexperience I was just working on the mentioned path comparison, and it seems to work well! But then I realized that your changes in 916a712737bb155c676e94cee870cd4df9e5cc4a break the prerequisites for this to work. As a simple test for you to replicate, see this version of your sketch with the exact same cut-out path

It works on sketch, but stops working after the mentioned commit. Could you have a look and tell me why?

[iconexperience]

@lehni I am onto this and should be able to give you more information within the next half and hour or so.

[iconexperience]

Here are the windings and the propagation to the curves:

The dots show where the winding was calculated (green = 1, blue = 2) and the curves have the color of the winding.

As you can see the highlighted point has a wrong winding. It should be 2, but it is 1. Now let's find out why this happens.

[iconexperience]

And here is what is actually happening in detail: A vertical ray is cast, which intersects the outer square twice, which results in a winding of [-1,1]. Then the inner square is touched at the vertical right edge. The windings cancel each other, as intended (id 11 from the table in this comment).

[lehni]

Interesting! But where does it go wrong then? Is there a wrong assumption behind it?

[iconexperience]

_deleted this post, because it was totally wrong_

[iconexperience]

@lehni As you can see here I tried a solution before. This does not work in this case, because for vertical rays we have to use the opposite increment. So the correct code would be

var add = path.isClockwise() ? 1 : -1;
if (dir) add *= -1; // this can probably be combined elegantly with the previous line
windingL += add;
windingR -= add;
onPathWinding += add;

But I am not sure if this works for all cases or if this breaks something else.

[lehni]

Right! Let me try this out, and run the test suite.

[lehni]

Great, that was it! No new issues, and it does indeed fix that case. Do you wan to create a PR for proper trace of authorship? Would you mind writing adding an explaining comment to that part of the code? It's pretty cryptic otherwise.

[lehni]

As for keeping the code shorter, using the bit-wise-xor in this one-liner has the same result:

var add = path.isClockwise() ^ dir ? 1 : -1;

Update: Corrected to xor.

[iconexperience]

I will do that tomorrow (need to go to bed urgently), but here is already the explanation, so I don't forget:

_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, the windings are opposite._

And thanks for the one-liner, I love that one.

[lehni]

So how should we implement this mentioned path comparison feature? I'm thinking that PathItem#equals() is the right place for it, but we probably want an optional options argument that control what is being compared:

path1.equals(path2, {
    style: false, // default: true
    matrix: false, // default: true
    attributes: false, // default: true (things like `clipMask`, `guide`, and a couple of others that really should be in `Style`: `visible`, `blendMode`, `opacity`, ...)
    content: false, // default: true (compares the exact content, down to each segment)
    geometry: true, // default: false (compares the geometry of paths in the method described above)
});

But looking at this, I think options.geometry sticks out, and mostly you probably wouldn't need any of the other switches...

[lehni]

@iconexperience sounds great, go rest, and thanks again for the great work! You don't need to create a PR btw, you can just push it to the develop branch on your own fork and I can get it there. Just let me know here when it's ready, tomorrow.

[lehni]

Great, so all it takes is this new geometry comparison method. What if I simply call it PathItem#compare(path) and it returns true if the geometries are the same?

[iconexperience]

That sounds very good to me. Maybe there could be a second parameter for tolerance? Or would that be too complicated?

[lehni]

Good idea. It depends... Do you think Curve.getOverlaps() can handle different tolerances well? If so, we could default to GEOMETRIC_EPSILON, but allow different values?

[iconexperience]

Oh, so you would have to pass the tolerance to 'Curve.getOverlaps()'? In this case I would stick with the default tolerance.

[lehni]

Yes because that's where the actual comparing takes place...

[iconexperience]

In that case I would really stick with the current tolerance, a tolerance parameter would just be a gimmick.

[lehni]

@iconexperience so after thinking about this compare function for a few days, I've made an attempt now, and I'm really happy with how it turned out: ccac7ec7c5924b8a984addc4b3afde4ce8895f75

I realized it doesn't even need to compare path length, it just finds the start of the overlapping sequence and then loops through and makes sure it all joins and overlaps on both paths.

This should be pretty fast, I think! And it should also support paths with different amounts of curves, split curves, etc. It needs some thorough testing though. And probably I need to add handling of curves of length 0, since they wouldn't return overlaps.

For this, I am wondering, shouldn't we have a Curve#isEmpty() check that uses your optimization of checking start = end point first? The name is a bit strange, but we use this elsewhere for shapes and items... It could also be #isZero(), but that's misleading with zero coordinates. And curve sits weirdly between abstract data and content :)

[lehni]

Having said all that, your example now stops failing.

[iconexperience]

Great! I will test this soon.

isEmpty()isn't too bad. Alternatively you could call it isZeroLength(), which should be pretty easy to understand.

[lehni]

Yes... Maybe hasZeroLength() would be more correct?

[iconexperience]

Both are good, but isZeroLength wins the Google battle hands down :stuck_out_tongue_winking_eye:

[lehni]

@iconexperience I think I am on to a better solution here that will be able to live completely without my new compare() function, and doesn't require any additional code to handle fully overlapping paths. This would then also mean that we could probably implement compare() as path1.subtract(path2).isEmpty() : )

[lehni]

I think I was too quick in my previous commit... The current way of handling this seems the right way, after all.

[lehni]

@iconexperience while playing around with this, I stumbled on a version of the above sketch that fails with the recently merged in code from the new-winding branch, but works correctly in v0.10.2. I could track the error back to the merging of the two branches, before it worked. Is this a winding problem?

Here's the sketch

Please note that the two inner shapes aren't the same any more. One of them has a little spike. If i change the dimensions of this spike slightly, things start to work correctly again...

[lehni]

@iconexperience and this is the breaking commit: 916a712737bb155c676e94cee870cd4df9e5cc4a

[iconexperience]

It really looks like a winding problem. The spike has a winding of zero, which should not happen. The point where the winding is calculated is exactly at the peak of the spike (at t=0.5). I need to investigate why that is happening.

[lehni]

But these are only lines, so how can the spike be in the middle of a line?

[iconexperience]

I don't understand. The propagation chain at the spike consists of two lines, both have the same length. We test the winding at t=0.5, which in this case is where the lines touch.
t=0.5 is for the whole chain, not for one line.

[iconexperience]

Aha, Now I understand what is happening. Of course we are casting a vertical ray at the tip of the spike, because the slope is less than 45°. That's what we get an overall winding of zero, which is basically correct. But since the point is on the path, it should get a special treatment to get a non-zero winding, which obviously isn't working.

So we need to look into the handling of on-path points again. Something there isn't working as it should.

[lehni]

Oh I see what you mean. A chain doesn't really have curve-time, since curve-time runs non-linearly along one curve. For clarity it's better to speak of offsets and length there instead, I think.

What you describe makes sense. Is it worth comparing how you handled on-path points prior to the breaking commit, and see what's different?

[lehni]

FYI: If my changes since that commit of yours are confusing, you could branch off that commit instead, and fix it on that new branch? I could then forward-port the fix to the latest state of the develop branch.

[lehni]

@iconexperience I was just implementing the unit tests for this issue and realized that we still have this new breaking case. Is there anything I can do to help with this issue?

[lehni]

@iconexperience this one still needs looking into as well:

https://github.com/paperjs/paper.js/issues/1109#issuecomment-236147751

[lehni]

@iconexperience great news: 3c2588fdec1035d3960b46d5c7271d6ed5e2b7ff fixed the spike issue that I refer to above as well. Yet another issue we can close : )