unite() on self intersecting path creates wrong result

[iconexperience]

I found an example where unite() on a self intersecting path creates a wrong result.

Here is the Sketch

This is how it looks (magnified):

In the example the result in a Path, while one would expect a CompoundPath with two children. An interesting observation is that the original path is split at the intersection marked in the image below:

I will investigate further.

[iconexperience]

Here is a little explanation, why the result is wrong. In the image below I have added some arrows indicating the direction of the original path.

If we cast a ray (orange line) from any point P in the red area, it will intersect the path twice in the same direction. This means that the winding will be either 2 or -2, but in any case even and non-zero. Since the path uses 'non-zero' winding rule (you can check by p.windingRule), the point is inside the path. But after calling unite() the point P is outside the path.

Here is a sketch that shows how a point is inside the path before, and outside after calling unite().

[lehni]

I think our code currently assumes the "evenodd" winding rule, correct? Nowhere in the boolean code are we actually looking at path.windingRule, as far as I'm aware. So the real issue I believe is that we're not taking this into account currently.

[iconexperience]

I am not sure if this is the problem. If the result was a compound path with the red area as the second child (with clockwise orientation), both winding rules would give the correct result (for the winding rule). But the solution in this case is only correct if we assume even-odd.

Here is what I would have expected:

And here is what we get:

What I would like to know is why does the algorithm prefer the second, incorrect solution? Wouldn't it make more sense trying to stick to the original path's orientation instead of suddenly changing the orientation at point P below (the arrows indicate the original path's direction)?

[iconexperience]

I thought again about your idea regarding the winding rule and I am almost 100% sure that this is not the problem (here).

If you create a compound path from a path with self intersections (as in my example), the resulting compound path will be displayed identically to the original path if all curves have the same direction that they would have had on the original path. If you cast a ray from any point into any direction, the winding number will be the same as before, because the number of crossings and the direction of the crossed curves will be the same for the resulting (compound) path as for the original path. This again means that the resulting path will have the same holes and filled areas as the original path, regardless of the winding rule applied.

That on the other hand means that in my example the problem is that the direction of some curves are different on the resulting path from the direction on the original path.

[iconexperience]

I have found the cause of this bug.

When calling unite() on a path without arguments, the path is first "prepared", which calls resolveCrossings()and reorient()on the path.

resolveCrossings() (which finds the self intersections, divides at the intersections, and traces the paths) works correctly. This creates a CompoundPath with two children like this (green: first child, red, second child):

Both children have clockwise orientation, which is correct in this case.

But then reorient()decides that the orientation of the second child should be counter clockwise, and this is wrong. So we should take another look on how children of compound paths are oriented, because this still causes problems.

[iconexperience]

I tried something that could work. Instead of calling reorient() inside the preparePath() function, I call it at the very end of the computeBoolean() function. This solves my example and does not break the example at #541 . I will do more testing.

[lehni]

I think reorient() was added by @hkrish to handle hand-crafted compound paths. For example, this compound-path with both children having the same orientation wouldn't be handled correctly by the boolean code if they weren't reoriented.

Calling reorient() at the end of computeBoolean() would cause new issues there. But what we probably want to do is not call it again on paths that are already results of previous boolean operations... I shall look into how this can be achieved. We could for example only address orientation if it wasn't explicitly set through the _clockwise property on a path, like we're already handling it elsewhere, e.g. in CompoundPath#insertChildren().

[iconexperience]

I understand. This is quite new for me so I will have to experiment a little bit to understand what is going on and what should be the correct behaviour. But I am happy that we are on the right track.

[iconexperience]

This is just an idea, but what about using res.reorient().resolveCrossings() instead of res.resolveCrossings().reorient() in preparePath()?

[lehni]

The reorient() function can't handle self-intersection properly which is why it's called after resolveCrossing(). Tricky business...

[iconexperience]

I think I have an idea that may be worth trying. If we prepare a simple path (not a compound path) with self intersections, we reorient the children only if the path has an even-odd winding. If the path has a non-zero winding, we simply remove all children that are inside other children. This way we do not get any unexpected holes popping up when we perform boolean operations on paths with non-zero fill rule.

Here is a simple example how a path would be treated differently by preparePath() depending on its fill rule.

[lehni]

Yes, that sounds indeed like the way to go! I think resolveCrossings() should handle this internally, really. If the desired result of a resolveCrossings() call is to keep the children in place, then one would simply have to set the even-odd fill rule before. Sounds good?

[iconexperience]

Yes, sounds very good. Would you do this for all paths (compound or simple) or only for simple paths? Maybe it would be correct to apply this to all paths?

Oh, and of course the algorithms is not as simple as I wrote above. If a path has clockwise orientation and the child has anti-clockwise orientation, the child will not be removed. We will have to do something similar to the current algorithm in reorient() but we have to keep track of the winding sum if several children are on top of each other.

[iconexperience]

Here is a version of CompoundPath.reorient() that respects the fill rule. I found that we need to reorient the remaining children as we did before.

Of course, "reorient" may not be the preferred nomenclature anymore, because we may also delete a bunch of children.

Update: This code does not work

reorient: function () {
    var children = this.removeChildren().sort(function (a, b) {
        return b.getBounds().getArea() - a.getBounds().getArea();
    });
    if (children.length > 0) {
        if (this.getWindingRule() === 'nonzero') {
            // walk through children, from smallest to largest. The largest child
            // will never be removed, because it cannot be inside another child.
            for (var i = children.length - 1; i >= 1; i--) {
                // calculate the winding sum of child and all other children that
                // contain the child.
                var point = children[i].getInteriorPoint(),
                    windingSum = children[i].isClockwise() ? 1 : -1,
                    isContained = false;
                for (var j = i - 1; j >= 0; j--) {
                    if (children[j].contains(point)) {
                        isContained = true;
                        windingSum += children[j].isClockwise() ? 1 : -1;
                    }
                }
                // if winding sum is non-zero and child is inside other child, remove the child.
                if (windingSum != 0 && isContained) {
                    children.splice(i, 1);
                }
            }
        }
        this.addChildren(children);
        var clockwise = children[0].isClockwise();
        // Skip the first child
        for (var i = 1, l = children.length; i < l; i++) {
            var point = children[i].getInteriorPoint(),
                counters = 0;
            for (var j = i - 1; j >= 0; j--) {
                if (children[j].contains(point))
                    counters++;
            }
            children[i].setClockwise(counters % 2 === 0 && clockwise);
        }
    }
    return this;
}

[iconexperience]

Update: Here was a shorter version of the function above using only a single loop. This did not work, because the winding of the smaller curves would be wrong if containing paths are removed. It looks like we need two loops for nonzero fil rule.

[iconexperience]

BTW, I just found that getInteriorPoint()may not be fully reliable, at least for some points contains() returns false. I cannot link this to a bug, but let's keep this in mind for any future problems.

[iconexperience]

Update: Unfortunately this implementation will not work correctly in some complex cases, sorry

I found a way to handle both fill rules in one loop, adding very little overhead to the current code:

reorient: function () {
    var children = this.removeChildren().sort(function (a, b) {
        return b.getBounds().getArea() - a.getBounds().getArea();
    });
    if (children.length > 0) {
        this.addChildren(children);
        var isNonZero = this.getWindingRule() === 'nonzero',
            clockwise = children[0].isClockwise();
        // walk through children, from largest to smallest. The first child
        // will be skipped.
        for (var i = 1, l = children.length - 1; i <= l; i++) {
            var point = children[i].getInteriorPoint(),
                counters = 0;
            for (var j = i - 1; j >= 0; j--) {
                if (children[j].contains(point)) {
                    if (isNonZero && !counters &&
                        children[i].isClockwise() == children[j].isClockwise()) {
                        // remove child if fill rule is nonzero and child
                        // has same orientation as containing child
                        children[i].remove();
                        break;
                    }
                    counters++;
                }
            }
            // set correct orientation if child was not removed
            if (counters)
                children[i].setClockwise(counters % 2 === 0 && clockwise);
        }
    }
    return this;
}

[lehni]

@iconexperience:

• regarding getInteriorPoint(): Could you perhaps extract the SVG data of a path where this is the case? It would be good to find out more about that.
• isNonZero & co. Looks great! I need to compare it to the current version though : )

[iconexperience]

Aargh, forget the second implementation. It will fail if several children with the same orientation are stacked on top of each other and then more children follow with the opposite orientation. This is only a theoretical case, but the implementation should handle all cases correctly. Too bad, I really liked it.

[iconexperience]

Alright, I think I found a good implementation.

Here is a sketch with a little test case (click reload/run again for a new random example).

Here is the code:

reorient: function () {
    var children = this.removeChildren().sort(function (a, b) {
        return b.getBounds().getArea() - a.getBounds().getArea();
    });
    if (children.length > 0) {
        var isNonZero = this.getWindingRule() === 'nonzero',
            clockwise = children[0].isClockwise(),
            windingSums = new Array(children.length),
            removeFlags = new Array(children.length);
        // we have to determine the windings before adding the children.
        for (var i = 0, l = children.length - 1; i <= l; i++) {
            windingSums[i] = children[i].isClockwise() ? 1 : -1;
        }
        this.addChildren(children);
        // walk through children, from largest to smallest. The largest
        // child can be skipped.
        for (var i = 1, l = children.length - 1; i <= l; i++) {
            var child = children[i],
                point = child.getInteriorPoint(),
                counters = 0;
            for (var j = i - 1; j >= 0; j--) {
                if (children[j].contains(point)) {
                    if (isNonZero && removeFlags[i] === undefined) {
                        windingSums[i] += windingSums[j];
                        // remove child if fill rule is nonzero and
                        // winding sum changes from non-zero to zero
                        // or from zero to non-zero between
                        // containing child and child
                        removeFlags[i] = 
                            windingSums[i] != 0 && windingSums[j] != 0;
                        if (removeFlags[i])
                            break;
                    }
                    // increase counter for containing paths only 
                    // if path will not be removed
                    if (!removeFlags[j])
                        counters++;
                }
            }
            // set correct orientation
            child.setClockwise((counters % 2 === 0) == clockwise);
        }
        // remove all flagged children 
        for (var i = 1, l = children.length - 1; i <= l; i++) {
            if (removeFlags[i])
                children[i].remove();
        }
    }
    return this;
}

@lehni: In the original implementation there is the line children[i].setClockwise(counters % 2 === 0 && clockwise);

I think this is wrong. In my opinion it should be children[i].setClockwise((counters % 2 === 0) == clockwise);

in the original code all children will be anti-clockwise if the largest child is anti-clockwise. I think they should have alternating orientation.

[iconexperience]

And I managed to remove the removeFlags array, which made the code a bit smaller.

Here is the sketch

reorient: function () {
    var children = this.removeChildren().sort(function (a, b) {
        return b.getBounds().getArea() - a.getBounds().getArea();
    });
    if (children.length > 0) {
        var isNonZero = this.getWindingRule() === 'nonzero',
            clockwise = children[0].isClockwise(),
            windingSums = new Array(children.length);
        // we have to determine the windings before adding the children.
        for (var i = 0, l = children.length - 1; i <= l; i++) {
            windingSums[i] = children[i].isClockwise() ? 1 : -1;
        }
        this.addChildren(children);
        // walk through children, from largest to smallest. The largest
        // child can be skipped.
        for (var i = 1, l = children.length - 1; i <= l; i++) {
            var child = children[i],
                point = child.getInteriorPoint(),
                counters = 0,
                inOtherChild = false;
            for (var j = i - 1; j >= 0; j--) {
                if (children[j].contains(point)) {
                    if (isNonZero && !inOtherChild) {
                        windingSums[i] += windingSums[j];
                        // remove child if fill rule is nonzero and
                        // winding sum changes from non-zero to zero
                        // or from zero to non-zero between
                        // containing child and child
                        if (windingSums[i] != 0 && windingSums[j] != 0) {
                            children[i].remove();
                            break;
                        }
                    }
                    inOtherChild = true;
                    // increase counter for containing paths only 
                    // if path will not be removed
                    if (children[j].parent)
                        counters++;
                }
            }
            // set alternating orientation for nested children
            child.setClockwise((counters % 2 === 0) == clockwise);
        }
    }
    return this;
}

[iconexperience]

Here is an extended test where the compound has another stack of children that are not inside the first child. At the left is the compound path before, at the right after calling reorient().

[iconexperience]

@lehni Regarding getInteriorPoint() this seems to be the case only for very small paths with an area of almost zero. Here are five examples:

var pathsData = [
    "M214.48881,363.27884c-0.0001,-0.00017 -0.0001,-0.00017 0,0z",
    "M289.92236,384.04631c0.00002,0.00023 0.00002,0.00023 0,0z",
    "M195.51448,280.25264c-0.00011,0.00013 -0.00011,0.00013 0,0z",
    "M514.7818,183.0217c-0.00011,-0.00026 -0.00011,-0.00026 0,0z",
    "M471.91288,478.44229c-0.00018,0.00022 -0.00018,0.00022 0,0z"
];

for (var i = 0; i < pathsData.length; i++) {
    var p = new Path({pathData: pathsData[i]});
    console.log(i + ": " + p.contains(p.getInteriorPoint()));
}

Here is the sketch

[lehni]

Impressive work, @iconexperience! Is this ready for inclusion in the library? How does it handle partly overlapping children? Does the getInteriorPoint() check still work then, since it's not guaranteed to be inside another partly overlapping child? And I do wonder now if reorient() is the right name for it still, as it's also removing children, not just reorienting them. It's a kind of orientation clean-up, so far only used internally to prepare for boolean operations. Perhaps it's best to keep this internal, and not expose it through the API?

[iconexperience]

@lehni Yes, this should be ready. But I agree it should not be called reorient(), because it also removes children. Partly overlapping children are not handled (have not tested, actually), but this should not happen, as the code is supposed to be called after resolveCrossings(), which gets rid of partly overlaps. Maybe include the code into resolveCrossings()?

[lehni]

Well, a compound path can still have partly overlapping children though? I believe resolveCrossings() only resolves self-intersection within one child / path, not across children of a compound path...

[lehni]

Here the updated sketch with your code: Updated Sketch

[iconexperience]

The example with the new code does not work, because the CompoundPath.prototype.reorient does not override the original reorient() function. This was my mistake. I do not know how to override reorient() dynamically. In the updated sketch you are setting the winding rule to evenodd, so the result is correct. When using nonzero, the triangle is filled.

Regarding the partly overlapping children, I do not know, have to think about it. Maybe this is only the way to reorder children if resolveCrossings() created a CompoundPath from a Path?

[iconexperience]

@lehni Are you sure about resolveCrossings() on CompoundPaths? Here is a sketch Here is a better sketch where resolveCrossings() is called on a CompoundPath with two overlapping circles as children. The result is a CompoundPath with two "half moons" as children.

[lehni]

@iconexperience ha, you are right! And it makes total sense, because once the mono-curves from he full compound path are retrieved in one array, there is no distinction being made between the children anymore. My bad.... And good news! So yes, all in all I think resolveCrossings() and reorient() can merge and become one useful function. But what should it be called? It resolves both self-intersection and winding rules... Is resolveCrossings() still right?

[lehni]

Oh, and I adjusted my updated sketch to use the nonzero rule. I was toying with both to make sure that it works.

[iconexperience]

I would stick with resolveCrossings(). Makes sense to me. (BTW, last comment before Christmas. I am working on a great education demo on fat line clipping, hope to be finished this year).

[lehni]

I've been working a bit on simplifying and optimizing the code further. The windings only need to be calculated if the nonzero rule is set, for example: Updated Sketch

[iconexperience]

Nice. The one comment was wrong, though, so i changed it. Here is my updated sketch

[lehni]

Let's keep it open until https://github.com/paperjs/paper.js/issues/854#issuecomment-166631734 is resolved too? Or would you like to create a separate issue for that?

[iconexperience]

Alright, reopening.

[lehni]

@iconexperience regarding that other issue, it turns out all these paths have an actual area of 0, not just close to 0. I've normalized the path data a bit by moving the starting point to (0, 0), and then scale them by a massive amount, and I still get 0 for their area, and hence false for the contains() calls.

I don't think it's a bug though. It's just that these paths don't actually have an interior point since they don't have any area... Now we could of course return null in that case, but it would mean we'd have to always calculate the area first... But is that necessary?

Updated Sketch