Wrong hit result

[aureole82]

I got the hit result { type: 'fill', item: Path@1 } where definitely no hit result should be.

http://jsfiddle.net/x5t1v10e/

[iconexperience]

Oh dear, that seems to be a side effect of the new boolean code. We probably get two intersections at the little horizontal line left to the point, which then results in a winding number of 1, which means we are inside the path.

[lehni]

Hmm but we didn't change the winding code, did we? The contains() code doesn't check for intersections. But that's easy verified by comparing with an older version of the library...

[iconexperience]

You are correct @lehni, this also happens in older versions, but it is a bit difficult to compare, because in previous versions the curve values were totally wrong (including a few NaN).

As I see it, there are a two strange things happening here:

• If I set the stroke width to zero, we still get a hit, because for both vertical lines at the right (the one from [840, 0] to [840, 20] and the one from [860, 20] to [860, 110] the winding numbers are counted in getWinding(), so the algorithm thinks we are crossing the path twice there. This is probably what causes the incorrect hit result.
• Curve.solveCubic has not a very good precision for a vertical linear curve in the example below. This is probably not a problem, because we are withing our curve time tolerance. But I find it odd.

var values = [0, 0, 0, 0, 0, 20, 0, 20];
var roots = [];
paper.Curve.solveCubic(values, 1, 20, roots, 0, 1);
console.log(roots[0]; // should be "1", but actually is "0.999999988079071"

[iconexperience]

What causes the double counting of the winding is the condition in getWinding() at line 361, that only omits double counting if there are no horizontal curves with winding == 0 inbetween.

@lehni Do you know any cases where this condition is required? I commented it out and in my test suite it caused no new glitches.

[iconexperience]

I think an easy solution would be the following, but it is a bit of a hack, because prevT does not refer to prevCurve after this special case. But they are not used in combination, so it may be alright.

In getWinding() line 396 add this:

} else if (winding === 0 && py === values[1]) {
    prevCurve = curve;
}

(we only have to check against values[1], because winding === 0 means that the curve is absolutely horziontal or values[1] === values[7])

Or maybe this, which I think is more correct:

} else if (winding === 0 && prevT > tMax) {
    prevCurve = curve;
}

(Update: I think the second solution is not more correct, because the problem occurs only if there is an absolutely horizontal curve (v[1] === v[7]) AND the end point of the previous curve is exactly at py AND the start point of the next curve is exactly at py. This means that my first solution already covers all possible cases).

[lehni]

@iconexperience the code in question was implemented to solve #736, so any changes to it should probably be tested against that case as well. Could you have a look?

[iconexperience]

Yes, I will do. Also, I think the issue is a little bit more complicated than I thought and there could be other cases that still fail. It should be solveable, but it's a bit tricky.

[iconexperience]

I found some inconsistencies with precision in getWinding(). In this Sketch you can see that points are counted as being on the path if they are horizontally just outside the path (epsilon = 2e-7 is used), but we do not allow this tolerance vertically. We may want to take a look at the vertical tolerance after this issue has been solved.

[iconexperience]

I have created a small test case based on @aureole82's example that produces six wrong results.

For the points outside the path contains() returns true, for the points inside the path it returns false

Here is the Sketch

I have set the winding rule to "evenodd", which causes the points inside the path to be counted as outside.

I think I have found a solution, but I need to test it agains some edge cases.

[iconexperience]

@lehni I have a question. In getWinding()line 357 there is a check for an "end" of loops, but this is not done by checking if this is the last curve in the array of curves but by curve.next !== curves[i + 1]. I do not understand why it is done this way. Do you have any example where there can be several "loops" and where simply checking for the last curve will fail? If there can be several loops I find it strange is that startCounted is never reset to false, so if the start of one loop is counted, all starts of the following loops are marked as counted.

What I need to do is to find out the first and the last curve that has winding !== 0. For these two curves I then need to make sure that for the start of first and end of last the winding is only added once.

Update: Maybe the "loops" are a relict from the old boolean code when paths could have self intersections?

[lehni]

The reason why it's done this way is simply that the curves array of a CompoundPaths can contain more than one loop (all curves of the first child-path = loop 1, followed by all curves of the second child-path = loop 2, etc).

[lehni]

@iconexperience your observation about startCounted is probably correct. I need to look into this when I find the time, very busy at the moment unfortunately...

[iconexperience]

@lehni I will try to do this. I think I understand the whole algorithm and I know where the problems are. Also, your information about the compound paths was very helpful. But I need some time, too.

[lehni]

@iconexperience great, thanks!

[lehni]

@iconexperience I've rewritten your sketch a bit to give visual feedback.

[iconexperience]

@lehni I though I had a good solution, but then I found new cases that caused problems. Therefore I will present some intermediate results for discussion.

The problem with the current implementation of getWinding() is that it completely ignores curves with winding==0 (I call them horizontal curves). As a result the merging of intersections if one intersection is at the end point of one curve and another intersection is at the start point of the next curve can fail. Here is an example:

The two red intersections should be merged, but this fails in the current implementation, because due to the horizontal curve the two vertical curves are not regarded as being neighbors.

I have found a way that fixes merging of these intersections, but my apporach fails if the point is directly on a horizontal curve. Actually, I do not even know what the correct result should be. Below are four examples, red intersections indicate a winding contribution of -1, green ones indicate a winding contribution of 1.

Here is a quick summary of our algorithm which should help to understand the examples: We calculate the sum of the winding contributions for all intersections right and left of the point (windLeft and windRight). From these sums we calculate the absolute value and use the maximum of both values as the overall winding (winding = max(abs(windLeft), abs(windRight)).

A point is inside a path if the winding value is non-zero (when using the non-zero rule) or odd (when using he even-odd rule).

The following four examples illustrate the problem. With the current implementation in examples 1, 2 and 4 the point will be counted as being inside the path, in example 3 the point is counted as being outside of the path.

Example 1 windLeft = -1, windRight = 0, winding = 1

Example 2 windLeft = 0, windRight = 1, winding = 1

Example 3 windLeft = 0, windRight = 0, winding = 0

Example 4 windLeft = -1, windRight = 1, winding = 1

I am tempted to simply return 1 in these cases, as we are inside the path if we are on the stroke by definition.

[iconexperience]

For testing my first proposed solution, I have made the test case a little bit nastier.

Here is the sketch

And this is how it looks:

As you can see, the results look quite random.

[iconexperience]

@lehni Do you have a proposal what the correct return value of getWinding() for the numbered points below is?

For 1, 2 and 6 it is probably 1, but what about 3, 4 and 5? Would it be sufficient if we returned 1? This would mean inside the path for even-odd and non-zero winding rules.

[iconexperience]

Here is another Sketch which shows the results if we switch x and y corrdinates in the example above. This is how it looks:

I will try to get the same results for the original example.

[iconexperience]

I have finished an implementation that seems to work well.

After some testing and cleanup I hopefully can create a pull request next week.

[lehni]

@iconexperience sounds great! Apologies for my silence on all fronts, I've been constantly absorbed, and will be for another two weeks until things are finally cooling down. Will be back more around here after that!

[iconexperience]

No problem, I know that you are busy. I will just keep on working and see how far I can get.

[lehni]

So I'm finally coming out of my work tunnel. What's the state of affairs here now? Is #852 fully solving this? And could you outline the approach you've settled for in the end? Just trying to understand it.

[lehni]

The reason why I am asking: I wonder if a part of the work that you're doing in getWinding() now could be moved to _getMonoCurves() curves and cached instead?

[iconexperience]

As far as I can see this issue is fixed with my proposed changes at #852. I have not found any negative side effects and performance should be about the same. But since the change is rather complex, I would like to do more testing.

And I will add more details on my new implementation here.

[lehni]

This is now merged in, but I am keeping this issue open until I've implemented unit tests for it too.