Wrong intersections found on two touching curves

[lehni]

See here: Demo sketch

Two intersections are found. On develop, one of them is considered to be a crossing.

[lehni]

I am starting to think that this is unavoidable and just part of the numeric imprecisions that we're dealing with. But what's problematic is that this intersection doesn't identify as a crossing...

@iconexperience what do you think about this? We could increase TRIGONOMETRIC_EPSILON to 1e-7 and it would catch most of these as not-crossings...

[lehni]

Some more information: I am seeing such cases even when a straight line is involved, meaning the problem is not only in the fat-line clipping code. Since our cubic root solver that is involved in line-curve intersections is numerically sound, I tend to think that these results are just part of the game.

[iconexperience]

@lehni I agree that we will not be able to solve all edge cases, but at the same time I will not give up :)

Regarding the isCrossing() method I still think that my approach was very good, but it does not work currently, because it requires that all intersections must be divided before it can propertly distinguish between crossings and non-crossings.

As a reminder, here is a brief description of my approach. First I search for the shortest distance dmin from the intersection point p to the curves's end points. Then I take the point on each curve at dmin/2 from the intersection point p. These points are then used to determine if the intersection is a crossing.

The problem is that it fails in cases like these:

BUT if we divide the curves at each intersection and apply the algorithm afterwards, it would work in all cases. But this requires to divide the curves at all intersections, not only at crossings and overlaps. The intersections that are neither crossings nor overlaps are quite rare in my test cases, so maybe the performance difference would be small.

[lehni]

@iconexperience welcome back :)

The false positive that I describe above isn't produced by my code that determines the directions to be used to identify a crossing. It is produced by this line here:

 if (t1Inside && t2Inside)
            return !this.isTouching();

The intersection is "inside" both curves (not at the ends), and therefore the checks further down aren't even performed. And from the tangents it looks like they're not touching, but crossing.

I am weary to change all the code to dividing first before checking. I also think it would be nice to find an approach that could reliably tell us this information not just for boolean operations, but as part of the CurveLocation API.

What we could try next is this: When the location is inside a curve, then the curve is subdivided and the two parts are used as the curve before / after the location. Then the same checks are performed as so far, with which in the latest iteration seems to work very well for all kinds of edge cases.

[lehni]

Some more thoughts: I am still seeing a lot of boolean issues when shapes are overlapping, or almost overlapping. When it does not see the curves as overlaps, then a somewhat random number of crossings is found, sometimes producing wrong boolean results. I start thinking that our approach may always bee too fragile for such edge cases, no matter how much more we improve the approach. It may be wiser to invest this time and energy into implementing the approach that @hkrish recently described to me.

[iconexperience]

Ok, I understand, so my approach would not help.

I agree that overlapping similar paths is still a weak spot of the algorithm. A more fault-tolerant algorithm would certainly help here.

What does implementing the new algorithm imply? Is it only a complete overhault of tracePaths() or is there much more to do?

[lehni]

Unfortunately it's a complete different approach. We'd have to through everything out that we've done so far... :/

[iconexperience]

Ooooh, that's awful.
I can still see problems with the current code popping up here and there (the worst case is when tracePath fails to close a path and everything gets lost, which means that the result of a unite operation is empty), but I am quite happy in general. Is it really worth all that effort?
Having said that, if you there is code that works better than the current one, let's throw the old junk out. We should not keep if for nostalgic reasons:)

[lehni]

I know... I think I want to work on some other bits first though. I will probably wrap up offsetting and then finally release v1.0.0 (!). But we should keep this other approach on the radar, for sure. In the offsetting, I can probably work around the issues that I am encountering for now, but I also feel that it's maybe time to stop zooming in and trying to solve every single edge case we're encountering.

If you have a test-case for a situation where the whole path is lost, I'd be interested in seeing it.

Oh, and let's close those pending issues where we can, so I can find back to a sense of overview here. : )

Would you be interested in being part of the effort to implement this new approach?

[iconexperience]

I would like to be part of that, but I have very busy weeks ahead of me. All the work on Paper.js had a purpose, and I hope that I can soon show what that is :) So please do not count too much on me before summer.

But let's try to get the pending issues closed. I will look into them.

And a test case (or two) will arrive soon.

[lehni]

That makes sense. I am still thinking that if we could teach getOverlaps() to be more relaxed about what's considered an overlap, we could probably handle these edge-cases better. This is perhaps worth looking into before throwing away all the work we've done so far?

[lehni]

Oh, and I'm very curious to see what you've been working on!

[iconexperience]

I have created a new issue with an example for a unite operation that results in an empty path, as mentioned above.