Outline fails for very specific shapes

[raydog]

Hey there! I think I found a bug with the outline method, at least when telling it to generate a path on the inside. It's hard to explain, since it doesn't crash or anything. It just produces empty models with very specific inputs, and very specific outline distances. Here's some code that reproduces what I'm seeing:

import makerjs from "makerjs";

const points = [ 
  [ 36, 504 ],
  [ 540, 504 ],
  [ 576, 360 ],
  [ 756, 360 ],
  [ 864, 144 ],
  [ 864, 36 ],
  [ 36, 36 ]
];

const shape = new makerjs.models.ConnectTheDots(true, points);

const final = {
  models: {
    shape,
    a: makerjs.model.outline(shape, 30, 1, true),
    b: makerjs.model.outline(shape, 36, 1, true),
    c: makerjs.model.outline(shape, 42, 1, true),
  }
};

document.write(makerjs.exporter.toSVG(final));

The result ends up looking like:

Where shape, a, and c are all drawn correctly, but b is an empty model. Tweaking the outline distance, even by just a little (ie, changing the 36 into 36.1) seems to "fix" this, but that isn't a REAL solution. :)

Any help would be appreciated. Thanks!

[vespakoen]

@danmarshall Perhaps we should use ClipperLib for offsets & boolean ops, it seems to be faster and more reliable, I have got an example over here: https://github.com/makercam/makercam/blob/2e440e2d3cd93418233b89069cb46fdc009a4f23/src/clipperOffset.ts

[danmarshall]

@vespakoen nice implementation! For some applications, this may be the way to go if speed is a requirement and curves are not required - i.e. point-to-point is acceptable. As you have correctly concluded, the key to this is in the "tolerance" between points on curves.

ClipperLib uses some tried-and-true algorithms from the study of Computational Geometry. Most of these algorithms use irregular polygons based on point-to-point designation. So, here is where Maker.js is a little different and still underdeveloped in its algorithms. The cost is speed and some bugs. The upside is that you can retain true curve shapes (currently arcs & circles, planning for Bezier in the future).

For most CNC applications and manufacturing scenarios, it is helpful to know that a circle is a circle, and not a series of points. The algorithms are a work in progress, if anyone can help out here that would be appreciated! Also see comments in #377

[vespakoen]

I see, hats off to you for making that happen!
What is the algorithm you are using? is there any documentation on that (besides the code)?

I see that other people use "arc filtering" to convert the points back into arcs (where possible), but of course it would be cooler when this whole back and forth converting can be avoided.

I am quite interested in the topic of coding / algorithms for CNC, so if you have some recommended reads i'd love to hear =)

[danmarshall]

The "arc filtering" idea may have some merit. I do believe it may be worth an investigation. It could also be a useful function in and of itself for general purpose.

Currently, it is simply the naïve approach: expand every path and accumulate a boolean union for each iteration. Slow 😐. We do need to make sure that at least does not have bugs, like this issue's context.

I have experimented in another branch a sweep line algorithm, similar to the Bentley-Ottman but without the intersection logic, and adapted for arcs. Performance was better but still not as good as I'd like. One advantage was that many models could be unioned simultaneously without an accumulator. The code was nearly complete.

I would love to have documentation more than just the code. Ideally it would be awesome to have a visual algorithm similar to VisuAlgo.

[forresto]

Hey @raydog 👋! I found something similar (?) with expandPaths... starting with:

Expanding by 2 has some missing segments:

Interestingly, expanding by 2.0001 fixes the broken bits:

Live demo: https://observablehq.com/@forresto/maker-js-svg-path-expand

[jcomack]

Hi, I was wondering if there was any progress in regards to this issue as I'm currently running into the exact same issue, but am unable to find a reliable workaround.