Boolean Operations: Remove the need for #resolveCrossings()

[lehni]

As originally outlined here:

We are currently facing a problem in resolveCrossings() when resolving more complex cases with overlaps, where it cannot correctly resolve these cases because it doesn't perform any checks, it just crosses at each encountered intersection.

There is an idea for a solution that may better handle all these issues with overlaps and other edge-cases, while at the same time improve speed:

The problem is that resolveCrossings() doesn't correctly resolve the sub-paths that lie on top of each other (areas within the same path that are covering each other), because it doesn't have the intelligence to decide when to cross in a found intersection, and when to stay on the current path. tracePaths() has this intelligence when performing the actual boolean operation, thanks to the internal branching mechanism and calls to isValid() which tell it if any given encountered segment is valid (has a valid winding contribution) or not. If tracePaths() ends up in a place where there is no way forward, it rewinds back to the last crossing and tries other possible directions (other crossings if there are multiples in the same location, and also not crossing at all as a last resort).

The problem is that defining isValid() for resolveCrossings() isn't trivial.

So can't we get rid of the need for resolveCrossings() all together? What if we just subdivide all involved paths at all the encountered intersections, regardless of wether they are crossings, touching points or overlaps, and let the branching mechanism of tracePaths() handle the rest?

The problem here is that the way getWinding() is currently implemented, it assumes that there are no overlapping sub-paths, as it assumes that resolveCrossings() has been called before and has taken care of this already as part of preparePath(). In order for this to work as it should, we need to teach it how to handle those cases.

Here is what I have thought of so far:

• Instead of a global windingL & windingR, we have to count these values on a per operand basis (the left and right path or compound-path), based on the path owners of the curves in the curves array. We can do so by using the path id to group these values in an id based lookup table (for paths that are part of a compound-path, we need to use their compound-path parent to get the operands)
• These grouped values then need to be flattened on a per operand basis, taking into account each path's winding-rule.
• The flattened values then are combined again.

Once we have distributed corrected winding contributions to each segment in this way, we can simply perform tracePaths() and it should always produce the right result. No more need for resolveCrossings() (but we do need to check for self-intersection as well as intersection with the other path when searching for all intersections), and no more need to distinguish crossing points (another unstable part of the code), we simply split in every found intersection and let the branching code handle the rest.

Since this reduces the amounts of required passes to one, I believe the result should perform faster than our current implementation, while at the same time handle edge cases much better.

[lehni]

@iconexperience you can check out the status quo for this in the remove-resolve-crossings branch. There are currently 35 failing cases, and I am fairly convinced they are all linked to the missing intelligence in getWinding() now.

Using this does help address issues in my path offsetting code where CurveLocation#isCrossing() still produces wrong results in rare situations.

The great news is that once we have fixed getWinding(), we will not be required to rely on CurveLocation#isCrossing() anymore, at all!

[lehni]

@iconexperience I've made an attempt at this now in f6233a5028fe77c49d94cf09a7763a9060e6f747, but things are more complex for a reason that I did not consider. And since you're the winding specialist, it would be great to hear your opinion on this.

Look at this example:

Sketch 1

path1 is a squared turned into a shape of two facing triangles by swapping out two of the segments. This means that one of these triangles is oriented in clockwise orientation, while the other is counter-clockwise. With the current code, this gets split into two separate paths (two triangles), and both are reoriented to be clockwise. The winding code then has no trouble handling this.

The current code on the remove-resolve-crossings branch is struggling, because of the changing orientations. And I am not sure we can actually handle this correctly?

Attached the found winding contributions (wit L / R in parenthesis) for the boolean-debug and remove-resolve-crossings branches. (boolean-debug is the same as develop with added code for debugging, also merged into remove-resolve-crossings).

boolean-debug

remove-resolve-crossings

[adamdyson]

I keep finding myself coming back and checking on the progress of your Boolean operations. I came across Maker.js today which I'm going to also try and thought it may be off interest. https://github.com/Microsoft/maker.js/blob/master/src/core/combine.ts

[lehni]

@adamdyson interesting! I wasn't aware of this library yet. Please tell us your findings. For what it's worth, I think boolean operations work very well in Paper.js now, but still struggle with edge-cases involving almost-overlapping curves.

[adamdyson]

I'm testing it's capabilities right now. After testing in browser working with font glyphs, I can tell you the union/uniting paths appears to be accurate and efficient.

However I'm finding that expanding the united glyphs afterwards takes far to long to compute. Admittedly it is extremely accurate and no doubt complex to achieve, but 1m 30 seconds isn't acceptable for my purposes.

I'm not sure whether it's because the library is written in TypeScript, but the code seems really abstracted, clean and organised which suits my OOP style of coding coming a PHP background.

Below is a simple example of what I'm trying to achieve. Just replace the font with one of your own.

<!DOCTYPE html>
<html>
    <head>
        <title>Maker.js</title>
        <style type="text/css">
        html, body {
            height: 100%;
            margin: 0;
            padding: 0;
        }
        #container {
            height: 100%;
            margin: 10mm;
            position: relative;
            box-sizing: border-box;
            overflow: auto;
        }
        svg {
            position: absolute;
            top: 0;
            height: 100%;
            width: 100%;
        }
        #container #svgGroup {
            stroke: none;
        }
        #container #text {
            fill: #FF0000;
            stroke: none;
        }
        #container #outline {
            fill: #FF0000;
            stroke: #FFFFFF;
            stroke-width: 0.5mm;
        }
        </style>
        <script src="http://microsoft.github.io/maker.js/target/js/browser.maker.js" type="text/javascript"></script>
        <script src="https://pomax.github.io/bezierjs/bezier.js" type="text/javascript"></script>
        <script src="http://opentype.js.org/dist/opentype.js" type="text/javascript"></script>
    </head>
    <body>
    <script>
        var makerjs = require('makerjs');

        // Note: Change the font to something where glyphs overlap.
        opentype.load('/maker/fonts/cream/Cream.ttf', function (err, font)
            {

                if (err)
                {
                    document.getElementById('container').innerText = 'the font could not be loaded :(';
                }
                else
                {
                    var text = new makerjs.models.Text(font, 'Adam Dyson', 100, true);

                    var outline =  makerjs.cloneObject(text);
                    outline.layer = 'outline';

                    // Note: Expanding the model paths makes the CPU sky rocket
                    // and takes an extremely long time to compute.
                    text = makerjs.model.expandPaths(text, 3, 0);
                    text.layer = 'text';

                    var model = {
                        models: {
                            text: text,
                            outline: outline
                        }
                    };

                    var svg = makerjs.exporter.toSVG(model, {useSvgPathOnly: true});

                    document.getElementById('container').innerHTML = svg;
                }
            }
        );
    </script>
    <div id="container"></div>
    </body>
</html>

[lehni]

Offsetting / Expansion is a complex undertaking with bezier curves. Here the current state of things in paper.js: https://github.com/paperjs/paper.js/issues/371#issuecomment-285041094

It's not part of the library yet, but will be soon. This should be fairly fast!

[adamdyson]

Nice work! I'll be keeping an eye out for when it makes it's way into the library, will offsetting work with compound paths as well?

After testing Maker.js some more, there were cases where it failed to united certain paths correctly, even on paths that seemed quite trivial, so your algorithm is certainly better.

You might remember I opened an issue and we discussed a font API? Well, I have something functional but I'll need a bit more time to tidy things up. JavaScript isn't my preferred language, so you'll likely need to refactor things to suit your coding style but I'll submit a pull request soon and discuss it further.

[danmarshall]

Hi @adamdyson and @lehni, I stumbled on this thread and though I'd chime in about Maker.js :-)

Adam - I hope you were able to resolve your failure case, if not - please let me know and I can take a look.

The philosophy I've taken in Maker.js is to be a tortoise instead of a hare. I'd like things to work well even if they are slow, and then we can optimize later.

The algorithm for boolean operation in Maker.js is really simple, I call it the "sausage wrapper" which is to simply wrap every segment with an outline, then combine all the wrappers. Currently the combining is using the worst-case O(n squared) but I'm planning on trying out a sweep algorithm. Considering something similar to the Bentley-Ottman algorithm, but I need it to work with arcs also. I've been learning about the famous algorithms as I go along :-)

Jürg - great work here with Paper.js. Scriptographer was a real inspiration to me. Cheers!

[lehni]

@danmarshall thank you for writing, and apologies for taking so long to respond. Busy times here at the moment, unfortunately with other things than Paper.js... Maker.js looks very interesting, and I'm glad to hear that Scriptographer served as an inspiration!

Now if only I could get a company like Microsoft to support our efforts. Nudge nudge, wink wink 😉

[OpenGG]

@lehni @danmarshall Found something might be helpful http://jsfiddle.net/a0523o4p/3/

[OpenGG]

The equivalent paper.js getIntersections() returns incorrect result for certain CompoundPath , while Kevin Lindsey working good.

http://jsfiddle.net/bjat59f0/13/

http://jsfiddle.net/a0523o4p/3/

The path tested:

M124.999,202.856
    c-42.93,0-77.855-34.928-77.855-77.858s34.925-77.855,77.855-77.855s77.858,34.925,77.858,77.855S167.929,202.856,124.999,202.856z
    M125.003,245.385c-7.61,0-13.025-6.921-17.802-13.03c-2.79-3.559-6.259-8.002-8.654-8.638c-0.318-0.085-0.71-0.134-1.159-0.134 c-2.873,0-7.1,1.698-11.188,3.335c-4.929,1.973-10.029,4.021-14.774,4.021c-2.486,0-4.718-0.563-6.633-1.677 c-6.451-3.733-7.618-11.959-8.742-19.919c-0.646-4.571-1.45-10.261-3.292-12.096c-1.84-1.845-7.524-2.646-12.093-3.298 c-7.96-1.119-16.192-2.286-19.927-8.739c-3.682-6.358-0.614-14.005,2.35-21.404c1.829-4.563,3.904-9.735,3.201-12.352 c-0.638-2.392-5.073-5.861-8.64-8.648C11.539,138.025,4.618,132.612,4.618,125c0-7.61,6.921-13.025,13.027-17.802
    c3.567-2.79,8.002-6.259,8.64-8.651c0.702-2.614-1.375-7.789-3.201-12.349c-2.961-7.399-6.029-15.046-2.347-21.409 c3.733-6.451,11.962-7.618,19.924-8.742c4.569-0.646,10.253-1.45,12.096-3.292c1.84-1.84,2.646-7.524,3.29-12.093 c1.127-7.96,2.291-16.192,8.745-19.924c1.914-1.111,4.147-1.674,6.633-1.674c4.745,0,9.845,2.045,14.771,4.021 c4.085,1.639,8.312,3.335,11.188,3.335c0.446,0,0.836-0.045,1.161-0.131c2.392-0.641,5.861-5.079,8.654-8.643
    c4.782-6.109,10.194-13.03,17.804-13.03c7.612,0,13.025,6.921,17.804,13.027c2.782,3.565,6.259,8.002,8.654,8.643 c0.323,0.085,0.71,0.131,1.161,0.131c2.876,0,7.094-1.696,11.185-3.332c4.932-1.976,10.029-4.021,14.779-4.021 c2.478,0,4.715,0.563,6.627,1.671c6.448,3.733,7.618,11.962,8.739,19.927c0.646,4.569,1.453,10.253,3.292,12.093 c1.84,1.84,7.524,2.646,12.096,3.292c7.96,1.127,16.189,2.291,19.919,8.745c3.687,6.36,0.619,14.007-2.344,21.404
    c-1.824,4.563-3.898,9.735-3.201,12.347c0.641,2.395,5.079,5.864,8.643,8.657c6.104,4.774,13.025,10.189,13.025,17.799 c0,7.612-6.921,13.025-13.03,17.804c-3.559,2.788-8.002,6.264-8.638,8.654c-0.702,2.614,1.375,7.783,3.201,12.347 c2.964,7.399,6.032,15.046,2.344,21.409c-3.733,6.448-11.959,7.618-19.924,8.739c-4.566,0.646-10.256,1.453-12.09,3.292 c-1.845,1.84-2.646,7.524-3.298,12.096c-1.119,7.96-2.291,16.189-8.745,19.919c-1.909,1.113-4.147,1.677-6.627,1.677 c-4.745,0-9.839-2.048-14.768-4.021c-4.091-1.637-8.315-3.335-11.19-3.335c-0.446,0-0.836,0.048-1.161,0.134 c-2.392,0.635-5.861,5.073-8.648,8.638C138.027,238.464,132.615,245.385,125.003,245.385z