Weird combination results

[mrzealot]

Howdy!

I'm using this excellent lib to generate keyboard layouts, but combining (unioning) shapes only seemed to work on one side, not the other. Attached is a fairly reduced JSON example of the expected behaviour and the error as well (the objects are the same, only the bad is mirrored and translated a bit). makerjs_debug.zip

The error happens when trying to combine the a and b parts of the models like so:

const json = <read json>
const combined = makerjs.model.combineUnion(json.models.a, json.models.b)

Everything is fine for the "good" input, while the result of the "bad" seemingly disappears. After making sure that it's not due to my code, I rolled up my sleeves and went deep. Turns out that the disappearance is because a line is incorrectly left out, and all the rest is then discarded as "dead ends". It all leads back to isSlopeEqual is equal.ts, where both the slopes and the yIntercepts are checked to be within .00001 of each other. The problem is that while slopes are always on the same scale, the differences of the yIntercepts can vary drastically with distance from the axis. So even if the slopes are well within .00001 of each other, the intercepts might not be after a certain distance.

My very simplistic, quick&dirty fix was to scale the yIntercept comparisons to a constant range, thereby making it independent of position. Wdyt about this addition? Should I open a pull request or would another solution be more fitting long-term?

[danmarshall]

Howdy @mrzealot ! Thanks for digging deeply into the issue. Boolean combinations are definitely turning up many issues here. Does your fix work against the unit tests? npm test

[mrzealot]

Good point, forgot to run those. What's worse, it revealed that I also forgot about division by zero (my arch nemesis) yet again!

All fixed now, tho, and I even added a new test to check for approximate slopes. It manages to fail the old version of the function by creating two lines whose slopes are within precision of each other and then translating them far far away. You can check out the changes here. Lemme know what you think...

[mrzealot]

Sadly ran into another issue, which is not connected to (nor solved by) my previous fix, but it's a "weird combination result" regardless...

Code to reproduce on the demo site:

var m = require('makerjs');

function f() {

const base = new m.models.RoundRectangle(10, 10, 1)
const a = m.model.move(new m.models.Rectangle(10, 10), [5, 5])
const b = m.model.move(new m.models.Rectangle(10, 10), [5, -5])

const base_plus_a = m.model.combineUnion(base, a)

const error = m.model.combineUnion(base_plus_a, b)
return error

}

module.exports = f;

Attached are three images, one for how these shapes look stacked, a second for how base and A combines well, and a third showing how unioning base+A to B messes things up.

Will try to do another round of digging, but let me know if you have any ideas @danmarshall !

[mrzealot]

Phew, found this as well. Turns out the automatically generated farPoint was a really poor choice, as it accidentally lead to the exact angle where the lineToFarPoint was tangential to the second rectangle, and therefore isPointInsideModel considered it to be inside when it wasn't (in the case of the bottom left corner arc). When I manually specify a farPoint among the combination options, it works like a charm.

This is just a workaround, tho, as I don't have a general solution... Maybe the confidence could be increased by checking against multiple farPoints and seeing if they agree, but I don't see how it ever gets certain. Anyways, the point is that isPointInsideModel should be thinking about tangents as well. Hope this helps...

[danmarshall]

Thanks for digging into the issue @mrzealot . I've been working on a new algorithm, but it's not yet complete. If you're feeling bold, you can try it out from source: https://github.com/microsoft/maker.js/tree/combine-sweep-expand-wip

[mrzealot]

Sounds really promising! I assume my previous PR won't be needed, then.

To be honest, tho, the layout generator I'm writing is itself a side-quest, and the makerjs debug it introduced was a side-side-quest :D So I'm very much looking forward to getting back on track (if the combination results choose to support me going forward)... But do let us know when the new internals are ready!

[mrzealot]

Hey @danmarshall , any news on this front? Just noticed that my generator utility still has to depend on my "pirated" fork of makerjs and thought I'd ask if the new algorithm is coming anytime soon? Or if not, could my above fix be incorporated into an interim release so that I can just say "makerjs" in my package.json? :slightly_smiling_face:

[danmarshall]

Hi @mrzealot , thanks for checking in :) I haven't progressed with my solution yet. At this point I have been considering a substantial change - introducing a new mild bezier path, and that is taking some thought.

[mrzealot]

Ah, gotcha. No rush on the big stuff, I get how time-consuming such a refactor can be. Just wondering whether a bugfix release to npm would be possible in the meantime? It's a minor change, it's tested, and also a third reason I can't think of right now. :)

[danmarshall]

I can take a PR. Looking at your code, and revisting the comparison of y-intercepts, I wonder if it makes more sense to just compare a to b with the rounding (remove the factor altogether?)

[mrzealot]

I'm not sure what you mean... I introduced the factor here explicitly because of scaling issues (see first comment). The subsequent commit just makes it more robust and adds tests. Or am I missing something?

[danmarshall]

Given the original line:

return round(slopeA.yIntercept - slopeB.yIntercept, .00001) == 0;

It seems like changing the factor is effectively the same as changing the .00001 to something less.

[mrzealot]

Well, we could just multiply the precision by the factor as opposed to the difference on the left side, if that's what you mean. Or calculate a separate precision value. But we have to calculate it somehow, as the point is having a "dynamic precision" and not allowing large yIntercepts to knock matches out of range. For example, we could write precision = .00001 / Math.max(Math.abs(slopeA.yIntercept), Math.abs(slopeB.yIntercept), 1));, if it'd make more sense to you. Which is functionally the same, but it's a functionality we need. Am I getting closer to what you mean?

[danmarshall]

How about if precision was an option that you could pass in? We'd have to thread it through the options for combine, etc.

[mrzealot]

Sure, that would be an elegant addition (which I've also thought about). But I think that would only be relevant in addition to this dynamic scaling, not instead of. There's no sense in being able to set the precision if it can be messed up by having your objects be (or move) further away from the y axis.

I mean, it could work with just the option, sure, but then precision doesn't mean what it should mean to the users. They can adjust it lower to accommodate far away objects, but then their near objects might theoretically suffer from an increased imprecision.

[danmarshall]

@mrzealot I've been digging into your test cases and understanding the issue with the slopes. Thanks for adding the test cases, that was really helpful. Also thanks for debugging the farPoint issue (which will not be used in the new algorithm). Does using your farPoint solution fix the issue you are having? Because I'm starting to believe that these two lines:

        var line1 = new makerjs.paths.Line([1, 0], [2, 2]);
        var line2 = new makerjs.paths.Line([1, 0], [2, 2.000001]);

Should not be considered as having the same slope. It is true as you say, the further translated away from the y axis, the bigger the problem gets.

[mrzealot]

@danmarshall Thanks! And yes, the farPoint stuff turned out to be completely unrelated, and can be circumvented by using a random value within the combination options.

As for the slopes, the optimal solution would be doing both. As in, allowing the user to set within what precision they consider two lines as having the same slope, but also dynamically scaling said precision so that distance from the y axis doesn't affect it. Both are justified, but the dynamic part is way more important (as the default precision of .00001 is fine for most cases). If you don't want my test case to be considered equal, tho, then the additional precision option is also needed.

Imho, let's just merge the dynamic stuff for now, and leave the parametric precision to the refactored codebase (if still relevant). Wdyt?

[danmarshall]

I would say, if you have a workaround, and we don't need the slope stuff, then let's not change it.

[mrzealot]

But we do need the slope stuff! I'm probably not explaining this right... Lemme try again:

The farPoint stuff is a separate issue. I had just initially thought it was related, but it wasn't. I have a workaround for that, no need to do anything there.

The slope stuff is a bug, and my use-case depends on it working correctly. I don't have a workaround for that, this is why I'm pestering you to merge my fix. :slightly_smiling_face:

[danmarshall]

@mrsealot, thanks again for the thoughtful discussion, and great find of this bug. Please see PR #485 which I hope solves this.