Optimize boolean operations when there are no crossings.

[lehni]

When there are no crossings, the result can already be known ahead of tracePaths(), probably leading to a massive speed-up:

• intersect: return null
• unite: return a compound path with both operands
• subtract: return the first operand
• exclude: same as unite.
• divide: no change needed, since it redirects to the other methods.

[iconexperience]

Hmm, I just implemented it in the way described above, and there are six new issues in the unit tests.

[lehni]

Could you share the new code in a commit added to the PR?

[iconexperience]

@lehni All I did was to copy the code from non-crossing boolean op and modify it a bit. Here it is:

        reorient: function(nonZero) {
            var children = this._children,
                length = children && children.length;
            if (length > 1) {
                // collect paths and create an id-path lookup
                var paths1 = this.removeChildren(),
                    lookup = Base.each(paths1, function (path, i) {
                        this[path._id] = {
                            clockwise: path.isClockwise(),
                            index: i
                        };
                    }, {});

                // Builds a tree structure from the specified paths. Each node of the
                // tree is an array of length 2, with the path itself at index 0 and
                // the paths that it directly contains as an array at index 1.
                var buildTree = function (paths) {
                    var sortedPaths = paths.length == 1 ?
                            paths :
                            paths.sort(function (a, b) {
                                return Math.abs(b.getArea()) - Math.abs(a.getArea());
                            }),
                        rootNodes = [];
                    // insert all paths to the tree.
                    for (var i = 0; i < sortedPaths.length; i++) {
                        var path = sortedPaths[i],
                            interiorPoint = path.getInteriorPoint(),
                            levelNodes = rootNodes,
                            containingPathFound;
                        do {
                            // iterate through all nodes on the level. If the path of
                            // one node contains the new path, recursively iterate
                            // through the children of the node.
                            containingPathFound = false;
                            for (var j = levelNodes.length - 1; j >= 0; j--) {
                                if (levelNodes[j][0].contains(interiorPoint)) {
                                    containingPathFound = true;
                                    levelNodes = levelNodes[j][1];
                                    break;
                                }
                            }
                        } while (containingPathFound);
                        levelNodes.push([path, []]);
                    }
                    return rootNodes;
                };

                // Sets the orientation of the paths and alternates the orientation
                // for all descendant levels.
                var normalizeOrientation = function (nodes, windingSum, exclNonzero, reverse) {
                    for (var i = nodes.length - 1; i >= 0; i--) {
                        var node = nodes[i],
                            entry = lookup[node[0]._id],
                            winding = 0;
                        if (!entry.exclude) {
                            winding = entry.clockwise ? 1 : -1;
                            if (exclNonzero && windingSum !== 0 && windingSum + winding !== 0) {
                                // if the winding sum of the containing path is nonzero
                                // and the winding sum for the path is nonzero, we
                                // can exclude the path in case of nonzero fill rule.
                                entry.exclude = true;
                            } else {
                                // alternate orientation
                                entry.clockwise = reverse ^ (windingSum === 0);
                                winding = windingSum > 0 ? -1 : 1;
                            }
                        }
                        normalizeOrientation(node[1], windingSum + winding, exclNonzero, reverse);
                    }
                };

                // build trees for paths and normalize the orientation
                var rootNodes1 = buildTree(paths1);
                var clockwise = rootNodes1[0][0].isClockwise();
                normalizeOrientation(rootNodes1, 0, nonZero, !clockwise);
                // collect result paths and create overall result.
                var resultPaths = [];
                for (var i = 0; i < paths1.length; i++) {
                    if (!lookup[paths1[i]._id].exclude) {
                        paths1[i].setClockwise(lookup[paths1[i]._id].clockwise);
                        resultPaths.push(paths1[i]);
                    }
                }
                this.setChildren(resultPaths);
            }
            return this;
        },

[iconexperience]

Also, apologies for not having delivered more during the last days. I had big plans, but there were so many other things that I had to do that I just didn't make the progress as I was hoping. I hope in two weeks I will be more productive.

[lehni]

@iconexperience I've lost the overview a bit over the pending works from your end... So there is #1131, #1073, and what you've outlined here but what I have yet to see. Is there anything else? Now that I've fixed the commit / push issue, could you create PRs for the things you've been working on? I'm having a hard time keeping an overview...

[lehni]

To bring this discussion back to one place again: @iconexperience has since described his new approach in the comments here onwards: https://github.com/paperjs/paper.js/issues/1215#issuecomment-267755710, and has created a new branch with this code: https://github.com/iconexperience/paper.js/tree/improvedReorient Here the commit with all the current work: https://github.com/iconexperience/paper.js/commit/61df327bc2d9dd019eb9d4d1f6ef9ec94c8025f9

[lehni]

@iconexperience I have started looking through the code. It looks good! I think we should merge this in despite your concerns mentioned here https://github.com/paperjs/paper.js/issues/1215#issuecomment-267776686 and then work more on it together.

I have one question already. Could you describe the reason for this?

if (paths2 && operator.exclude) {
    for (var i = 0; i < paths2.length; i++) {
        paths2[i].reverse();
    }
}

We do the opposite further above, and it's a bit weird to reverse a path twice:

// Give both paths the same orientation except for subtraction
// and exclusion, where we need them at opposite orientation.
if (_path2 && (operator.subtract || operator.exclude)
        ^ (_path2.isClockwise() ^ _path1.isClockwise()))
    _path2.reverse();

[iconexperience]

Hmm, I am not really sure why I did that, probably to undo the path reverse. Reversing the path may be necessary for the standard algorithm (for cases with crossings), but I think it should not be required for non-crossing boolean operations.

In any case, the following example does not work correctly without my undoing of reversing of the paths:

var createCircle = function(radius, clockwise) {
    var circle = new Path.Circle({center: [100, 100], radius: radius});
    if (!clockwise) {
        circle.reverse();
    }
    return circle;
}

var p1 = new CompoundPath({children: [createCircle(90, true), createCircle(50, false)], fillColor: "rgba(0, 255, 0, 0.3)"});
var p2 = new CompoundPath({children: [createCircle(70, true), createCircle(30, false)], fillColor: "rgba(255, 0, 0, 0.3)"});

var res = p1.exclude(p2);
res.fillColor = "rgba(0, 0, 255, 0.3)";

But it does work if we set the permitted windings for exclude to [-1, 1]. Maybe that would be the correct approach.

[lehni]

Yes that sounds like the better approach! Do you think it's always the correct one?

[iconexperience]

I think so. preparePath() ensures alternate winding for compound paths, therefore the only possible winding numbers with two combined paths are [-2, -1, 0, 1, 2]. And here is what these numbers mean for a given point:

winding	meaning	include in result for exclude
-2/+2	inside both paths, which have the same orientation	no
-1/+1	inside one path and outside the other path	yes
0	outside both paths or inside both paths, where paths have opposite orientation	no

I would certainly prefer reversing path2 after checking if there are any crossings. This way we could keep the orientation of the paths in more cases, but that may not be easy to do.

[iconexperience]

Instead of adding the negative values to the accepted winding numbers we should simply compare to the absolute value of the winding number. This way we will have unite/intersect/subtract have covered as well.

So we could remove the reorientation for the èxclude`operations and this would become:

            var reorientedPaths = reorientPaths(
                paths2 ? paths1.concat(paths2) : paths1,
                function(w) {return insideWindings.indexOf(Math.abs(w)) >= 0;}
            );

[lehni]

I tried exactly this earlier, but I it caused issues with some test-cases, e.g.:

var p1 = new Path.Circle(175, 405, 15);
var p2 = new Path.Circle(260, 320, 100);
p1.fillColor = "green";
p2.fillColor = "red";
var res = p1.subtract(p2);
res.position.y += 250;

[iconexperience]

That's right, for subtract paths winding number -1 means that the area is not in path1 but in path2, therefore it must not be included in the result.

[lehni]

I was thinking about the change of direction. I could probably improve the tracePath() algorithm so that flip isn't necessary, but it would add complexity in getWinding() and propagateWiding() and a few other places, not sure it's worth the effort. If we don't do this, then I think it's better if the code that handles boolean operations without intersections matches the code where intersections occur in behavior, in which case leaving the path reversed is actually the desired behavior. Do you know what I mean?

[iconexperience]

I fully agree. The hehaviour should be the same for the code with and without the non-crossings shortcut.

Here is a simple example that shows how cases with non-clockwise orientation are handled by the old code, which is still used by Sketch. unite reverses the orientation, exclude keeps the anti-clockwise orientation.

Maybe one day we will decide that the orientation of the result paths is very important :)

[lehni]

@iconexperience I've merged your changes from https://github.com/iconexperience/paper.js/commit/61df327bc2d9dd019eb9d4d1f6ef9ec94c8025f9 into the develop branch now. Please have a look and test with your own code.