bug in Engrave Process - Githubissues

SebKuzminsky commented 7 years ago

There's a bug with the Engrave Process. It affects the 0.6 branch (8ca7de23). I have not tested the master branch.

The bug is triggered when a 2D Model contains an arc, and the Tool diameter is near or above the diameter of the Model's arc.

Here's a human-readable view of the 2D model I've been using to reproduce the problem. Note that the arc dimensions are diameters, not radii (all units are millimeters). pycam-radius-bug

And here's the SVG, suitable for importing into PyCAM (I had to zip it to upload it to github...): pycam-radius-bug.zip

To reproduce:

Run pycam, open pycam-radius-bug.svg.
Model -> Model 1 -> Polygons -> Toggle Direction
Create a new Tool (Tool Diameter = 7).
Create a new Process (Strategy = Engraving, Trace model = Model 1,Radius compensation = True).
Create a new Bounds (default).
Create a new Task (default).
Task -> Generate Toolpath. A correct internal Toolpath is produced.
Tools -> Tool 1 -> Tool Diameter = 15.
Task -> Generate Toolpath. An incorrect Toolpath is produced.
Tools -> Tool 1 -> Tool Diameter = 8.

Task -> Generate Toolpath. An error window pops up with this content:

    An unexpected exception occoured: please send the text below to the developers of PyCAM. Thanks a lot!
    Traceback (most recent call last):
      File "/home/seb/pycam/pycam/Plugins/Tasks.py", line 316, in generate_toolpath
        toolpath = task_resolver(task, callback=draw_callback)
      File "/home/seb/pycam/pycam/Plugins/TaskTypes.py", line 61, in run_task
        path_generator, motion_grid = funcs["process"](environment["process"], tool.radius, box)
      File "/home/seb/pycam/pycam/Plugins/ProcessStrategies.py", line 153, in run_process
        callback=progress.update)
      File "/home/seb/pycam/pycam/Geometry/Model.py", line 582, in get_offset_model
        new_groups = group.get_offset_polygons(offset, callback=callback)
      File "/home/seb/pycam/pycam/Geometry/Polygon.py", line 970, in get_offset_polygons
        group.append(line)
      File "/home/seb/pycam/pycam/Geometry/Polygon.py", line 234, in append
        raise ValueError("This line does not fit to the polygon")
    ValueError: This line does not fit to the polygon

At this point PyCAM is crashed and you have to kill it.

SebKuzminsky commented 7 years ago

I chased this bug a little bit tonight. pycam.Geometry.Polygon.append() gets called a couple of times after the polygon is marked "closed". I modified append() to just return if self is closed instead of throwing an exception, and to log the polygon and the passed-in line:

line: Line<9.50246,9.9808,0>-<9.49957,10.0238,0>
Polygon self: Polygon (open) [(9.49957, 10.023755980472334, 0.0), (9.49957, 34.97639651679649, 0.0), (9.502457182932396, 35.019368020534095, 0.0), (9.515573833336923, 35.10524446866709, 0.0), (9.527000177412619, 35.149694161999456, 0.0), (9.542374168896634, 35.19168721561594, 0.0), (9.56238918154408, 35.233226373434654, 0.0), (9.587180707563952, 35.27403270083675, 0.0), (9.616369151310678, 35.31306417193011, 0.0), (9.649918380461184, 35.34996925935412, 0.0), (9.687025988276115, 35.383696799274325, 0.0), (9.72582392505001, 35.41271185498569, 0.0), (9.766311192581432, 35.4372983898595, 0.0), (9.808346625958412, 35.457547857513994, 0.0), (9.850947452753502, 35.47314494740523, 0.0), (9.895225754181963, 35.48453626037314, 0.0), (9.980181380546219, 35.497506846254566, 0.0), (10.023349035613245, 35.5004, 0.0), (34.97658664020646, 35.5004, 0.0), (35.019807642397026, 35.49750357299531, 0.0), (35.10468877889262, 35.484544881864664, 0.0), (35.14887254083956, 35.47317623026187, 0.0), (35.191387539569384, 35.45761022506737, 0.0), (35.23350201483283, 35.43731896793975, 0.0), (35.2742447014048, 35.41258092546249, 0.0), (35.31281981737043, 35.383734754328714, 0.0), (35.35006684878531, 35.34987572380007, 0.0), (35.3839956833647, 35.31256346254536, 0.0), (35.41267588575218, 35.27422360865933, 0.0), (35.437436279317794, 35.23344411063034, 0.0), (35.45775419311276, 35.19129432363565, 0.0), (35.472833648316985, 35.15010822541437, 0.0), (35.484288051617696, 35.1055095617098, 0.0), (35.49752305323669, 35.01891533504323, 0.0), (35.5004, 34.97616256802571, 0.0), (35.5004, 10.023989886825614, 0.0), (35.4975243508227, 9.981248600390801, 0.0), (35.48431516089819, 9.894844139076964, 0.0), (35.47283741299973, 9.850158310824996, 0.0), (35.45768498066828, 9.808770189623836, 0.0), (35.437436709052754, 9.76675814927186, 0.0), (35.41282137601592, 9.726224442118989, 0.0), (35.383938787031816, 9.687617045309228, 0.0), (35.349926520918864, 9.650206712597319, 0.0), (35.31276422143213, 9.616424706755819, 0.0), (35.273732581583424, 9.58723512300195, 0.0), (35.232962358093474, 9.562466520205703, 0.0), (35.19134821497085, 9.542415377027812, 0.0), (35.149287112819195, 9.527015556866932, 0.0), (35.10491024349481, 9.51560647860991, 0.0), (35.01889223983069, 9.502465561031013, 0.0), (34.975884971999825, 9.49957, 0.0), (10.024050776519855, 9.49957, 0.0), (9.981096862595038, 9.502462270530275, 0.0), (9.895004356488387, 9.515615099623469, 0.0), (9.8505329321647, 9.527046817604312, 0.0), (9.808385946048737, 9.542477746545138, 0.0), (9.76685089856769, 9.562487116484254, 0.0), (9.726336060621739, 9.58710414975529, 0.0), (9.687081588694687, 9.616462664853184, 0.0), (9.650058714946802, 9.650113188986136, 0.0), (9.616426035559979, 9.68711632523044, 0.0), (9.587035197240997, 9.72641538058683, 0.0), (9.5623887695681, 9.766975993328263, 0.0), (9.542443357272347, 9.808377331789563, 0.0), (9.52699641076229, 9.850572412561991, 0.0), (9.515546718448373, 9.89510921589264, 0.0), (9.502455888129878, 9.980795905892979, 0.0)]

line: Line<9.49957,10.0238,0>-<9.49957,10.0005,0>
Polygon self: Polygon (closed) [(9.49957, 10.023755980472334, 0.0), (9.49957, 34.97639651679649, 0.0), (9.502457182932396, 35.019368020534095, 0.0), (9.515573833336923, 35.10524446866709, 0.0), (9.527000177412619, 35.149694161999456, 0.0), (9.542374168896634, 35.19168721561594, 0.0), (9.56238918154408, 35.233226373434654, 0.0), (9.587180707563952, 35.27403270083675, 0.0), (9.616369151310678, 35.31306417193011, 0.0), (9.649918380461184, 35.34996925935412, 0.0), (9.687025988276115, 35.383696799274325, 0.0), (9.72582392505001, 35.41271185498569, 0.0), (9.766311192581432, 35.4372983898595, 0.0), (9.808346625958412, 35.457547857513994, 0.0), (9.850947452753502, 35.47314494740523, 0.0), (9.895225754181963, 35.48453626037314, 0.0), (9.980181380546219, 35.497506846254566, 0.0), (10.023349035613245, 35.5004, 0.0), (34.97658664020646, 35.5004, 0.0), (35.019807642397026, 35.49750357299531, 0.0), (35.10468877889262, 35.484544881864664, 0.0), (35.14887254083956, 35.47317623026187, 0.0), (35.191387539569384, 35.45761022506737, 0.0), (35.23350201483283, 35.43731896793975, 0.0), (35.2742447014048, 35.41258092546249, 0.0), (35.31281981737043, 35.383734754328714, 0.0), (35.35006684878531, 35.34987572380007, 0.0), (35.3839956833647, 35.31256346254536, 0.0), (35.41267588575218, 35.27422360865933, 0.0), (35.437436279317794, 35.23344411063034, 0.0), (35.45775419311276, 35.19129432363565, 0.0), (35.472833648316985, 35.15010822541437, 0.0), (35.484288051617696, 35.1055095617098, 0.0), (35.49752305323669, 35.01891533504323, 0.0), (35.5004, 34.97616256802571, 0.0), (35.5004, 10.023989886825614, 0.0), (35.4975243508227, 9.981248600390801, 0.0), (35.48431516089819, 9.894844139076964, 0.0), (35.47283741299973, 9.850158310824996, 0.0), (35.45768498066828, 9.808770189623836, 0.0), (35.437436709052754, 9.76675814927186, 0.0), (35.41282137601592, 9.726224442118989, 0.0), (35.383938787031816, 9.687617045309228, 0.0), (35.349926520918864, 9.650206712597319, 0.0), (35.31276422143213, 9.616424706755819, 0.0), (35.273732581583424, 9.58723512300195, 0.0), (35.232962358093474, 9.562466520205703, 0.0), (35.19134821497085, 9.542415377027812, 0.0), (35.149287112819195, 9.527015556866932, 0.0), (35.10491024349481, 9.51560647860991, 0.0), (35.01889223983069, 9.502465561031013, 0.0), (34.975884971999825, 9.49957, 0.0), (10.024050776519855, 9.49957, 0.0), (9.981096862595038, 9.502462270530275, 0.0), (9.895004356488387, 9.515615099623469, 0.0), (9.8505329321647, 9.527046817604312, 0.0), (9.808385946048737, 9.542477746545138, 0.0), (9.76685089856769, 9.562487116484254, 0.0), (9.726336060621739, 9.58710414975529, 0.0), (9.687081588694687, 9.616462664853184, 0.0), (9.650058714946802, 9.650113188986136, 0.0), (9.616426035559979, 9.68711632523044, 0.0), (9.587035197240997, 9.72641538058683, 0.0), (9.5623887695681, 9.766975993328263, 0.0), (9.542443357272347, 9.808377331789563, 0.0), (9.52699641076229, 9.850572412561991, 0.0), (9.515546718448373, 9.89510921589264, 0.0), (9.502455888129878, 9.980795905892979, 0.0)]
closed Polygon, ignoring line

line: Line<9.49957,10.0005,0>-<9.49957,10.0238,0>
Polygon self: Polygon (closed) [(9.49957, 10.023755980472334, 0.0), (9.49957, 34.97639651679649, 0.0), (9.502457182932396, 35.019368020534095, 0.0), (9.515573833336923, 35.10524446866709, 0.0), (9.527000177412619, 35.149694161999456, 0.0), (9.542374168896634, 35.19168721561594, 0.0), (9.56238918154408, 35.233226373434654, 0.0), (9.587180707563952, 35.27403270083675, 0.0), (9.616369151310678, 35.31306417193011, 0.0), (9.649918380461184, 35.34996925935412, 0.0), (9.687025988276115, 35.383696799274325, 0.0), (9.72582392505001, 35.41271185498569, 0.0), (9.766311192581432, 35.4372983898595, 0.0), (9.808346625958412, 35.457547857513994, 0.0), (9.850947452753502, 35.47314494740523, 0.0), (9.895225754181963, 35.48453626037314, 0.0), (9.980181380546219, 35.497506846254566, 0.0), (10.023349035613245, 35.5004, 0.0), (34.97658664020646, 35.5004, 0.0), (35.019807642397026, 35.49750357299531, 0.0), (35.10468877889262, 35.484544881864664, 0.0), (35.14887254083956, 35.47317623026187, 0.0), (35.191387539569384, 35.45761022506737, 0.0), (35.23350201483283, 35.43731896793975, 0.0), (35.2742447014048, 35.41258092546249, 0.0), (35.31281981737043, 35.383734754328714, 0.0), (35.35006684878531, 35.34987572380007, 0.0), (35.3839956833647, 35.31256346254536, 0.0), (35.41267588575218, 35.27422360865933, 0.0), (35.437436279317794, 35.23344411063034, 0.0), (35.45775419311276, 35.19129432363565, 0.0), (35.472833648316985, 35.15010822541437, 0.0), (35.484288051617696, 35.1055095617098, 0.0), (35.49752305323669, 35.01891533504323, 0.0), (35.5004, 34.97616256802571, 0.0), (35.5004, 10.023989886825614, 0.0), (35.4975243508227, 9.981248600390801, 0.0), (35.48431516089819, 9.894844139076964, 0.0), (35.47283741299973, 9.850158310824996, 0.0), (35.45768498066828, 9.808770189623836, 0.0), (35.437436709052754, 9.76675814927186, 0.0), (35.41282137601592, 9.726224442118989, 0.0), (35.383938787031816, 9.687617045309228, 0.0), (35.349926520918864, 9.650206712597319, 0.0), (35.31276422143213, 9.616424706755819, 0.0), (35.273732581583424, 9.58723512300195, 0.0), (35.232962358093474, 9.562466520205703, 0.0), (35.19134821497085, 9.542415377027812, 0.0), (35.149287112819195, 9.527015556866932, 0.0), (35.10491024349481, 9.51560647860991, 0.0), (35.01889223983069, 9.502465561031013, 0.0), (34.975884971999825, 9.49957, 0.0), (10.024050776519855, 9.49957, 0.0), (9.981096862595038, 9.502462270530275, 0.0), (9.895004356488387, 9.515615099623469, 0.0), (9.8505329321647, 9.527046817604312, 0.0), (9.808385946048737, 9.542477746545138, 0.0), (9.76685089856769, 9.562487116484254, 0.0), (9.726336060621739, 9.58710414975529, 0.0), (9.687081588694687, 9.616462664853184, 0.0), (9.650058714946802, 9.650113188986136, 0.0), (9.616426035559979, 9.68711632523044, 0.0), (9.587035197240997, 9.72641538058683, 0.0), (9.5623887695681, 9.766975993328263, 0.0), (9.542443357272347, 9.808377331789563, 0.0), (9.52699641076229, 9.850572412561991, 0.0), (9.515546718448373, 9.89510921589264, 0.0), (9.502455888129878, 9.980795905892979, 0.0)]
closed Polygon, ignoring line

Now the toolpath is successfully generated, and the path looks like this (8mm tool): pycam-radius-working

SebKuzminsky commented 7 years ago

Ignoring lines appended to closed polygons lets it generate toolpaths with tools up to the diameter of the arcs in the model, 10mm in this case.

But any larger tools than that and it makes those weird inverted arcs in the toolpath like I showed in the original bug report.

SebKuzminsky commented 7 years ago

The problem is with the sequence of points that Geometry.Polygon.get_offset_polygons() gets from Geometry.Polygon.get_shifted_vertex().

The corners display the kind of "inverted arcs" shown in the original bug report with the 15 mm tool.

The size of the inverted arcs depend on the size of the tool, and with an 8mm tool the buggy corner happens to trigger the "closed polygon" detection in Geometry.Polygon.append().

So I think the real problem is that get_shifted_vertex() gets the corners wrong. In this model, the SVG's arcs get converted to short line segments (either in the SVG to EPS step, or in the EPS to DXF step, or in the DXF importer, I'm not sure), that may be related too.

SebKuzminsky commented 7 years ago

My previous comment was hasty. I now think the points that get_shifted_vertex() returns make sense, and the problem is in the post-processing of those points that get_offset_polygons() does.

get_offset_polygons() does this:

generate the list of offset points
make lines from adjacent pairs of those points
identify intersections among the generated lines, produce separate polygons from each non-intersecting sequence of lines (simplify_polygon_intersections())
discard any polygon that has other polygon(s) inside it
return the remaining list of polygons (ie, the polygons that do not have any polygons inside of them)

That's my reading of the code, if I've misunderstood any part of that I welcome corrections.

In the "tool diameter = 15mm" example in the original message of this bug report, that should result in five separate polygons: one for the inside square, and one for each of the four little incorrect corners. Clearly the inside square is the expected result, and the four corners are errors of this algorithm. They have no polygons inside of them, so they are not excluded by the pruning at the end of the function.

I think some other or some additional pruning needs to be added.

I note that there is ample literature on polygon offsetting. Is the pycam polygon offsetting algorithm derived from a published algorithm someplace, or is it a new invention of this project?

zancas commented 7 years ago

'Attempting to replicate on master.

zancas commented 7 years ago

Can you please make me one of this issues assignees? Or, better, configure the fork such that I can assign myself?

SebKuzminsky commented 7 years ago

@zancas That screenshot looks like it's of a version of pycam from after the gtk3 transition, is it from the master branch maybe?

The "Path parameters" area has a field called "Trace models (2D)", which shows the upper left part of an "M" in your screenshot. That field should say "Model #something", and you should select it. I think you've found a bug in the gtk3 port of pycam (that the Engrave/Trace Model field is displayed too small), if so, please open another Issue to track that.

I've been doing all my work on the "stable/0.6" branch, which uses gtk2, which does not have this display problem.

sumpfralle commented 6 years ago

@SebKuzminsky: your great preparations (including the test code for a minimal example) helped me tremendously. I think I found a proper condition for pruning plugins that are too close to the original polygon.

But sadly there are more problems (instabiltities) lurking within that part of the code: when I tried to use a different DXF model, I failed to use polygon offsetting with some tool diameters. For some other diameters, it is working.

Thus I think, I as was able to improve the offsetting a bit - but it is still not working reliably. @SebKuzminsky: please try if the current state of the 0.6-offset-polygon-bug-79 branch works with your model. I assume that it is behaving a bit better.

After putting another few hours into this part of pycam's code, I have to admit that I won't be able to bring it up to a level of quality, that would be acceptable for long-term maintenance. It was a bad idea from the start to create a custom polygon offsetting code. And it went worse with every debugging session that added another clumsy workaround for the next corner case.

I propose, that we should merge the current state of the 0.6-offset-polygon-bug-79 branch and try to avoid working on that code until we found an (external) replacement, that is worth the effort. Or do you have other ideas?

Neon22 commented 6 years ago

Have you considered turning the lines into connected SVG - then using an SVG library to do the offsetting. There is also the approach openSCAD uses which does offsetting of curves well. In my experience the DXF entities tend to be the cause of teh problem as exporters substantially vary in the quality of their oputput for DXF. REFs:

http://tavmjong.free.fr/blog/?p=1257
https://pypi.python.org/pypi/svgpathtools
https://stackoverflow.com/questions/28731506/svg-path-manipulation
OpenSCAD source in C (alas) - complex... https://github.com/openscad/openscad/blob/master/src/polyclipping/clipper.cpp

sumpfralle commented 6 years ago

Yes, this would be indeed a good approach for solving this nasty problem for real.

clipper: there is already a (short) discussion regarding the clipper library: #26
SVG library: this also sounds good to me

I would be happy to merge code proposals in this direction.

SebKuzminsky commented 6 years ago

I think moving from dxf to svg is a step in the right direction.

SebKuzminsky commented 6 years ago

@sumpfralle We should not merge the 0.6-offset-polygon-bug-79 branch as is, because it does not pass "make test".

https://travis-ci.org/SebKuzminsky/pycam/builds/300475223

If the changes you made are an improvement we could merge just those, but the test should not go in until it passes.

SebKuzminsky commented 6 years ago

@Neon22 I like the idea of using an external library of geometry functions when possible. I didn't see polygon/path offsetting in the svgpathtools feature list, but maybe it's available without being enumerated there. Or maybe we can construct our own polygon offsetting code from their simpler primitives.

It would be very much preferable if whatever external libraries we use were available as debian packages on our supported platforms. We currently ship pycam debs for Ubuntu Trusty, Debian Jessie, and Debian Stretch, and none of them seem to have svgpathtools packages. We could package it ourselves, or include it in our repo as a git submodule, but both of those are worse options than just installing pre-existing packages.

Other external geometry libraries we might consider are OpenVoronoi (see #42 and #44) and Boost Geometry.

sumpfralle commented 6 years ago

We should not merge the 0.6-offset-polygon-bug-79 branch as is, because it does not pass "make test".

My bad - I did not check it. It is fixed now.

@SebKuzminsky: regarding the technical merge details: which flow would you prefer for the stable branch?

step 1: merge the 79-branch as-is into stable or do a fast-forward merge with the rebased 79-branch?
step 2: merge the updated stable branch into master

It would be very much preferable if whatever external libraries we use were available as debian packages on our supported platforms.

This would be a priority for me, too.

SebKuzminsky commented 6 years ago

Great! Thanks for fixing that.

As for the work flow, the normal github way would be to merge 0.6-offset-polygon-bug-79 into stable/0.6 with a merge commit (for example by clicking the Merge button in a PR, or by running "git merge --no-ff"). Then merge stable/0.6 into master "by hand".

SebKuzminsky commented 6 years ago

Hmm, when I try to reproduce the problem originally described above, with the 15mm diameter tool I get this output:

No valid moves found

That's maybe better than an incorrect tool path, but it's still not quite right ;-)

SebKuzminsky commented 6 years ago

I guess I should have added that model to the test suite...

Neon22 commented 6 years ago

@SebKuzminsky "I like the idea of using an external library of geometry functions when possible. I didn't see polygon/path offsetting in the svgpathtools feature list, but maybe it's available without being enumerated there. Or maybe we can construct our own polygon offsetting code from their simpler primitives." Actually bottom of this page is enumerated some code for offsets. (may not be complete enough) Will it do ?

https://pypi.python.org/pypi/svgpathtools

sumpfralle commented 6 years ago

Indeed it looks like the svgpathtools package would simply just do that without a lot of effort.

Thus I am tempted to add it as an optional provider for the offsetting functionality. The builtin method would be used as a fallback and announce a hint regarding the manual installation of svgpathtools in case of a no valid moves found situation.

What do you think?

SebKuzminsky commented 6 years ago

I'm generally opposed to having multiple ways of doing the same thing, within a package. It's twice as much code to test and support (for us devs), and it's twice as much to understand how to use (for users). I'd prefer to identify the best solution, and put all effort into making that work well for all users.

I believe svgpathtools is developed here: https://github.com/mathandy/svgpathtools

I don't yet know if svgpathtools is the external libaray we should use. If it is, i think we have two options:

Package svgpathtools as a debian package and have pycam Depend on it, or
Include svgpathtools as a submodule in the pycam git repo and include it in the pycam package.

sumpfralle commented 6 years ago

I'd prefer to identify the best solution, and put all effort into making that work well for all users.

Agreed.

I really need to find a more precise way of saying "Personally I do not plan to put much effort into this specific topic" :)

sumpfralle commented 6 years ago

I summarized the state of the polygon offsetting algorithm and referred to the above thorough analysis in #114.

SebKuzminsky / pycam

bug in Engrave Process #79