Failing boolean operation with near-collinear lines

[lehni]

After 4a10fe33d39cdc19e7286efb1556288085d04630, this is the last failing unit test in the test suite:

Sketch

I think it boils down to the two lines running down and up in the inside of the red shape being almost collinear, but having handles in the range of -1e-8 to 1e-10, leading to isStraight() returning false, and hence isCollinear() too. I think this also relates to #838, but am not quite sure how to best handle this. @iconexperience, what do you think?

var path1 = new Path("M570,290l5.8176000300452415,33.58556812220928l-28.17314339506561,-14.439003967264455l31.189735425395614,-4.568209255479985c-5.7225406635552645e-9,-3.907138079739525e-8 -59.366611385062015,8.695139599513823 -59.366611385062015,8.695139599513823z")
var path2 = new Path("M575.8176000300631,323.58556812217466l-15.81760003006309,-23.585568122174664l-37.57818885419795,-3.7802815709635524z")
path1.strokeColor = 'red';
path2.strokeColor = 'blue';
path1.strokeScaling = path2.strokeScaling = false;
var result = path1.intersect(path2);
result.fillColor = new Color(1, 0, 0, 0.25);

[lehni]

And here the isolated lines, with some logging of isStraight() and handles:

Sketch

[iconexperience]

This is just an idea, but it might work. Right now when checking for overlaps, we permit a tolerance of GEOMETRICAL_EPSILON, but only for for straight curves. But we could extend the algorithm to non-straight curves like this:

• Take the line through the end points of the curve that has the larger distance between It's end points
• If the curve's handles and the other curve's end points and handles' distances to that line is less than GEOMETRICAL_EPSILON, we have an overlap.

Or in other words, we create a fat line with the width 2*epsilon for curve 1 and check if the handles of curve 1 and the whole curve 2 is within this fat line.

[lehni]

That's an interesting proposal! But just to be clear, I wasn't speaking about the overlap checks yet, just the current removal that happens through reduce() and the isStraight() and isCollinear() checks.

But indeed, right now no overlaps are found on these two curves:

Sketch

[lehni]

...And as stated in #874, in the future this removal shouldn't be handled by reduce(), and should include such overlaps as well. But what do we expect isCollinear() to return in the case above? what about the tolerances?

[iconexperience]

I think that we should not change isStraight() because of one failing edge case. This has been working well so far, so my opinion is to keep it as it is right now.

Regarding isCollinear() I am not so sure. But of course one would expect the curves to be straight is isCollinear() returns true, no?

[lehni]

Yeah, I agree.

I've made some first tests and it turns out it's rather easy to get getOverlaps() to detect and handle these properly, without braking any existing edge cases. I think this can be rather easily solved together with #874 now... Can't wait for all this to be off the table.

[lehni]

@iconexperience check here, I implemented your suggestion and it works like a charm:

https://github.com/paperjs/paper.js/commit/0d172a74f42fa3cb6e0d5b5b985a2b0f24808baa#diff-6393c249dbbb25dc0e510bd9d91b268dR1875

I thought I would have to modify the curve values when deciding that they are straight (projecting them onto the line they are tested against), but it turns out at least in this example here that's not required, due to the tolerances in the Curve.getParameterOf() call further down. I think we might get away without doing that :)

[iconexperience]

Nice. Here is my implementation just for comparison:

/**
 * Code to detect overlaps of intersecting based on work by
 * @iconexperience: https://github.com/paperjs/paper.js/issues/648
 */
getOverlaps: function(v1, v2) {
    var abs = Math.abs,
        timeEpsilon = /*#=*/Numerical.CURVETIME_EPSILON,
        geomEpsilon = /*#=*/Numerical.GEOMETRIC_EPSILON,
        straight1 = Curve.isStraight(v1),
        straight2 = Curve.isStraight(v2),
        straight = straight1 && straight2;

    function getEndDistSquared(v) {
        var x = v[6] - v[0],
            y = v[7] - v[1];
        return x * x + y * y;
    }

    var flip = getEndDistSquared(v1) < getEndDistSquared(v2),
        l1 = flip ? v2 : v1,
        l2 = flip ? v1 : v2,
        line = new Line(l1[0], l1[1], l1[6], l1[7]);
    var straightOverlap = line.getDistance(new Point(l1[2], l1[3])) < geomEpsilon &&
        line.getDistance(new Point(l1[4], l1[5])) < geomEpsilon &&
        line.getDistance(new Point(l2[0], l2[1])) < geomEpsilon &&
        line.getDistance(new Point(l2[2], l2[3])) < geomEpsilon &&
        line.getDistance(new Point(l2[4], l2[5])) < geomEpsilon &&
        line.getDistance(new Point(l2[6], l2[7])) < geomEpsilon;
    if ((straight1 || straight2) && !straightOverlap)
        return null;

    var v = [v1, v2],
        pairs = [];
    // Iterate through all end points: First p1 and p2 of curve 1,
    // then p1 and p2 of curve 2.
    for (var i = 0, t1 = 0;
         i < 2 && pairs.length < 2;
         i += t1 === 0 ? 0 : 1, t1 = t1 ^ 1) {
        var t2 = Curve.getParameterOf(v[i ^ 1], new Point(
            v[i][t1 === 0 ? 0 : 6],
            v[i][t1 === 0 ? 1 : 7]));
        if (t2 != null) {  // If point is on curve
            var pair = i === 0 ? [t1, t2] : [t2, t1];
            // Filter out tiny overlaps
            // TODO: Compare distance of points instead of curve time?
            if (pairs.length === 0 ||
                abs(pair[0] - pairs[0][0]) > timeEpsilon &&
                abs(pair[1] - pairs[0][1]) > timeEpsilon)
                pairs.push(pair);
        }
        // If we checked 3 points but found no match,
        // curves cannot overlap.
        if (i === 1 && pairs.length === 0)
            break;
    }
    if (pairs.length !== 2) {
        pairs = null;
    } else if (!straightOverlap) {
        // Straight pairs don't need further checks. If we found
        // 2 pairs, the end points on v1 & v2 should be the same.
        var o1 = Curve.getPart(v1, pairs[0][0], pairs[1][0]),
            o2 = Curve.getPart(v2, pairs[0][1], pairs[1][1]);
        // Check if handles of the overlapping curves are the same too.
        if (abs(o2[2] - o1[2]) > geomEpsilon ||
            abs(o2[3] - o1[3]) > geomEpsilon ||
            abs(o2[4] - o1[4]) > geomEpsilon ||
            abs(o2[5] - o1[5]) > geomEpsilon)
            pairs = null;
    }
    return pairs;
}

[iconexperience]

Very similar, but yours is a little bit cleverer, doing the handles check only on non-straight curves.

[iconexperience]

I think renaming getLineLengthSquared to getEndDistSquared (or similar) is a good idea. (maybe to old name is alright) Also, the whole comment about handling the straight cases should be updated.

[lehni]

Yes I agree : ) As for the comments, does this cover it? a7fc04a9b119324cca8ec6955e430d678484d8e1

[iconexperience]

Two tiny suggestions:

Note that the the picked line-> Note that the curve for the picked line set them all straight -> treat them as straight

[lehni]

Yes, that's better. I'm getting sluggish : )

[iconexperience]

That was quite a big change in a very short time :) Did this actually solve the last failing unit test case?

[lehni]

No not yet, but it sets the base for it. With this in place, the "self-overlaps" get properly detected in the example in https://github.com/paperjs/paper.js/issues/887#issuecomment-168965587. What's left to do is to implement their removal, as outlined in #874.

And thanks to all the boolean unit tests that cover many of the known edge cases now, I can now much more confidently change things in such a way.

[lehni]

I also finally understood my hack for 'adjusted' winding contributions last evening, when realizing that these 'adjusted' numbers were only in use anymore when picking the starting segment. And it turned out that their sole use was to avoid segments that are part of overlaps as starting points : ) So that lead to the nice simplifications in https://github.com/paperjs/paper.js/commit/4a10fe33d39cdc19e7286efb1556288085d04630#diff-83b0f841b43dce90324008de0d976e25R593

I feel more and more confident about understanding all aspects of the boolean code now, including my own hacks that are nearly gone now.

[iconexperience]

This all sounds very nice. Do you want me to do anything at the moment? I am a bit packed with other things, but will keep listening.

[lehni]

No I think we're nearly there. The ball is in my court now : )

[lehni]

So the above commit 5a16d0cd01648bb369b21d95802560dec258caf3 just closed #887 and #874. It was a huge pain to get there, about a full day in the making, probably has slowed down things a little, but appears to work beautifully. : ) Proper testing is required...

[lehni]

It looks rather simple in the end, but to remove overlap range segments first and then perform tracePath(), all based on the same set of found crossings and overlaps was a daunting task, due to path mutation.

[lehni]

And it's so nice to finally have decent boolean operation tests in place that I trust!

[iconexperience]

Congratulations! I have my automated test up and running, and so far not problems were found. Super cool!

[lehni]

So I just did a quick performance comparison, and have good news: I could not measure any slow-downs resulting from 5a16d0cd01648bb369b21d95802560dec258caf3! That's really great, and not what I expected. It's solid code, all through!