search

svenhb / GRBL-Plotter

A GCode sender (not only for lasers or plotters) for up to two GRBL controller. SVG, DXF, HPGL import. 6 axis DRO.
https://grbl-plotter.de/
GNU General Public License v3.0
696 stars 176 forks source link

Merge and Sort slow for some imports #347

Closed heurist1 closed 1 year ago

heurist1 commented 1 year ago

I am close to having a solution for this bug, so expect a pull request in the next few days.

My usual use case is to load .svg files that were created in Inkscape, and create an .nc file, which is written to an SD card to transfer it to an Atomstack laser cutter. The files that cause the most problems are ones that I have cross hatched areas using Inkscape. I know I can get GRBL-Plotter to do some of the cross hatch, but sometimes I need the extra control that I have in Inkscape

I have attached an example file below.

The problem appears to be because of the way the searches are performed in the merge and sort stages of loading. I understand that some of this can be omitted using settings, but the resultant file takes a lot more time to cut, because the paths have not been optimised.

The aim is to profile the code and provide small changes to improve the times. Currently I have a test that takes >24min on 1.7.0.0 and 1min27 with the optimisations. It has a small change in the sort, and a mechanism to speed up the tests of being the same type/group. I will check that the output in unchanged using my test file, but would be interested in any other test files for different use cases that I should also test.

I think I could make it even more efficient by storing bounding boxes for each element, but maybe that should be saved for a separate issue.

TestMergeSort1

svenhb commented 1 year ago

This is really an unusual graphic. I'm curious about your algorithm. But I wouldn't call this issue a bug, rather an improvement as it works in most cases.

heurist1 commented 1 year ago

I am happy for you to re-categorise this issue as an improvement. I'm not sure if I have the permissions to change it myself. I guess it had felt like a bug before I looked into it because I had an even larger graphic and it hadn't completed in hours, so felt like it had locked up, but you are correct that it did work and would in theory have completed eventually.

The graphic is the lid of an 8 sided box. The outer lines are cut, the other lines are etched in plywood, using the tool tables in GRBL-Plotter and grouping based on layers. The cross hatching was applied in Inkscape using an extension extensions->Generate from path->Hatch Fill. see https://inkscape.org/~Moini/%E2%98%85hatch-fill+1. I probably haven't though too deeply about the paths and elements that were written to the .svg, I just used Inkscape and its tools and trusted that they were reasonable.

I had some issues using the cross hatching in GRBL-Plotter a while back (I was also going to look into this), but I have noticed that a recent build mentions the fixing of some issues in the hatch fill, so maybe I need to try again with a new version first.

svenhb commented 1 year ago

Yes, I uploaded my latest changes, because you wrote about a pull request, where you should use my latest files... About hatch-fill changes: there was a request to inset the fill in both directions - not just shorten the lines. To solve this, I shrink the enveloping path, before generating the hatch-fill.

heurist1 commented 1 year ago

Have added #348 pull request with my changes. Sorry I don't know an official way of tying an issue to a pull request in github.

svenhb commented 1 year ago

Sorry, I also have no idea how it works and what to select for a pull request - and I don't want to deal with it. I will check and insert your code locally. I will accept the pull request, so you will become a "contributor" After that I will upload my local code, to be synchronized. And probably make a new release.

svenhb commented 1 year ago

Made a new release with your changes - thanks