Unexpected behaviour for combineSubtraction

[z93blom]

Loving this project so far - I'm planning on using this for my CNC-designs going forward. In order to do that I will need to understand the library, and I'm currently struggling with the combine methods. I'm trying to "cut out" a part from another part. but not all paths are removed.

See the example below. I'm trying to cut out one corner from the box, but the only paths that are removed are the ones from the corner, not from the box itself. Those two paths (ShapeLine2 & ShapeLine3 on the 'box') are instead split into two paths each..

I would have expected to end up with an "L" shaped model below. What am I doing wrong?

var makerjs = require('makerjs');

var lShape = {
  models : {
    toprightcorner: makerjs.model.move(new makerjs.models.Rectangle(50, 50), [50, 50]),
    box: new makerjs.models.Rectangle(100, 100)
  }
};

makerjs.model.combineSubtraction(lShape.models.box, lShape.models.toprightcorner);

var svg = makerjs.exporter.toSVG(lShape);

document.write(svg);

Thankful for any feedback.

[danmarshall]

I think it’s a bug, I don’t think you’re doing anything wrong. If you make your top right box bigger like 51, 51 then it seems to work. I’ll add this as a test case so that I can find out what’s going on, thanks for posting!

[z93blom]

There's a comment in combine.js (around line 400) that seems to point to the same behaviour as above - paths are left on modelA, but removed from modelB. However this is only enabled for the combineUnion path, not combineSubtraction.

I'm wondering how I can help with resolving this bug. How can I run everything from my local copy to test it out? How do I run the tests locally to make sure that an eventual fix does not break anything else? (Experienced .Net developer, but not super familiar with all the latest web programming concepts).

[danmarshall]

Thanks for the offer to help Fredrik! This may be the most complicated part of the entire project 🤓 so fair warning. First off, I'm not using the well known algorithms of traditional computational geometry - so if you have any experience with CG algos, please let me know. For the most part, this part of the code uses the naïve approach and is not yet optimized.

This problem is simlar to to the coincident faces / manifold problem in OpenSCAD: source: https://ihrchive.wordpress.com/2010/01/18/openscad-tip-manifold-space-and-time/ So, as you can see, in similar work, the advice is to "draw bigger" instead of "equal" before you subtract.

You are correct that I've only implemented it for union. If you can think of any easy solution for subtraction, please let me know. Otherwise my thoughts lead me to think that we need to find chains, and determine if the deleted links are needed to complete a chain.

A few months ago, I started another branch to try out a new algorithm based loosely on Bentley-Ottmann. I wasn't perfectly happy with the results, and, I still didn't get around to subtraction. I was going to get around to it after finishing some easier features ;)

[danmarshall]

Oh, and to run locally: Suggestion: use VS Code 👍

1. fork this project on GitHub.
2. git clone from your fork to your local machine.
3. npm install
4. npm run build

Now you can run tests:

1. npm test

Or you can run the playground:

1. npm run start

Then open a browser to http://localhost:8020

If you get this far, let me know. I also have some other shortcuts.

[danmarshall]

Here is a simple test to get you thinking of an algorithm: On the left, the top + right should be removed, but on the right, they should be kept: When subtracting the orange shape from the white square.

[z93blom]

I now see how the problem is much more complicated than I thought at first. I do not think that I'm the right person to help you out with the code, and I also understand why it might take some time to come up with a solution. I think I will try to extend the yellow box past the object that I'm subtracting from in order to make it obvious (the boxes are only placeholders for more complicated objects). That way I'm at least not waiting for a solution that might not come for some time. Thanks for helping out and pointing out why the workaround might be the correct solution at this point in time.

[jcomack]

Hey @danmarshall, I was curious if there's any update regarding this as I'm currently running into several situations where subtraction is leading to weird behavior.

Thanks in advance.

[danmarshall]

Hi @jcomack , no I haven't had a good block of time to solve some the fundamental issues behind this. If you're brave enough to try, see the https://github.com/microsoft/maker.js/tree/combine-sweep-expand-wip branch 🐉