Inkscape Laser-Cutter Restack Plugin

I've mentioned before, in https://makerpunkbuzz.mywire.org/posts/new_laser_cutter_workflow/, about the Z-order, or "object stacking" order affecting the order that shapes are cut when converted to G-Code. I looked at revamping my code that post-processes the generated G-Code, but it seems the code produced by SvgToGcode is less amenable to that kind of text shuffling than that produced by Inkscape's GCodeTools, and I was always a little unhappy with the results too, because it only uses the "bounding box" of cuts to determine if they overlap, and this only truly works for rectangles: if a shape's contour is irregular, smaller shapes within its bounding box might not actually be inside its edges, like this:

A large equalateral triangle, with it's bottom side horizontal. Four small circles, labelled A, B, C and D, are arranged in a square pattern, with A and B either side of the triangle's apex, outside of its outline, but C and D are inside its bottom left and right corners.

Circles A and B are "outside" the outline of the triangle, but C and D are inside, but all of them are within its bounding box. It doesn't matter if A or B are cut before or after the triangle, but it does matter if C or D are cut after it, as the triangle could have dropped lower because it's no longer connected to the surrounding material, and the cuts for C and D would then be out of laser focus, and less effective. This can cause the cuts to not go right through, or burn or blur, resulting in a spoilt cut. Even worse, with very light material like card, the air assist could blow the triangle around, and the holes might even be done in the wrong place, or miss the material completely. So I'd want C and D to be cut before the triangle.

I had a look at the Python code of one of the "standard" Inkscape extensions, called "Restack", which I've already used, with only partial success, to try to alleviate this problem. From that, I was able to create my own version, which grouped smaller shapes by whether or not they were inside the bounding box of larger shapes, but that wasn't really any better than my old G-Code-juggler. I spent ages poring over the Inkscape Extensions documentation, and looking at other plugins to see how they tick, only to discover there was no way to "ask" Inkscape if two shapes overlapped. I had managed to get it to the point that it could order shapes by proximity, so that the laser head wouldn't have to jump round so much, but I couldn't work out how to check for contour overlaps, so I put up a post on Mastodon asking if anyone had any ideas how to do it. Somebody suggested I might be able to use Inkscape's "shell mode", and initially I thought this wouldn't work - one of the plugins I had looked at used it, and I didn't really understand what it was doing at that stage - but after I'd done some experiments with it, I realised I could make it answer, in a round-about-way, the question of whether two close-by shapes overlapped.

Inkscape has various operations you can do on paths which are really set logic operations: for example, you can compute the Union of two overlapping shapes, which creates a new shape which traces the outline of both the original shapes; Difference cuts away parts of the lower shape that are overlapped by the upper one; and so on. There is an Intersection operation, which produces a new shape which is just the area of overlap, and crucially, if they don't overlap, nothing at all.

These operations are all available in "shell mode" as commands. It took me a bit of time to work out how this text-based mode worked, because the documentation is a little sparse, and some things proved a bit counter-intuitive to me: most commands work on a "selection" of shapes, and there are subtle differences between how this works in the GUI and shell mode: the select-by-id: command destroys the current selection and replaces it with the named objects, if found. I had, for some reason, thought that I needed to "hide" all the other objects whilst doing path-intersection commands, but it turns out you don't. Once I'd figured that out, it didn't take too long to come up with the following steps to find out if two shapes overlap:

select-by-id: shape1,shape2
path-intersection
select-list

If shape1 and shape2 overlap, after path-intersection a new shape will be created; if not, nothing will be left of them, and crucially for my purposes, any new shape produced will now be the current selection. The select-list command will thus reveal if a new shape was created; if it output nothing, then the shapes didn't intersect.

I wrote a naive Python script to take an SVG file as input, and report on which shapes within it overlapped, and it worked. It used Inkscape shell mode to list all the shapes, and then created a script to do the operations above, then parsed the resulting output. However, it was fatally flawed, because it simply tested every shape against every other shape to see if they overlapped, and when presented with an even moderately complex SVG, it would basically never complete, because the number of tests performed is quadratic to the number of shapes present in the file.

My experimental extension already worked out which shapes were in the bounding-boxes of other shapes, so for the plugin, I was hoping this wouldn't be a problem, because I was only going to be checking a much smaller number of intersections. Initially, I only worked on getting the overlap information computed, and once I'd got that running on a test SVG I'd concocted, it was even able to handle files that the naive version had choked on.

It took me an embarrassingly long time to work out how to properly utilise the information I'd got back: eventually I had to write a recursive function to work out the final ordering, because if a small shape overlaps multiple larger shapes, I need to emit the most enclosed one first, and then work outwards through the enclosing shapes. Oh, and on top of that, I wanted the closest shape to be cut next. I found that an optimisation I'd made earlier, to reduce the number of comparisons, had actually shot me in the foot: I had decided to only consider the shape with the smallest enclosing bounding box for testing, but of course, a shape can be inside another's bounding box, but NOT overlapping, so this meant that I was missing a lot of overlaps in some situations. D'oh! Reminder: never try to prematurely optimise!

Eventually, what I had to do was create a "tree" of overlapping shapes, and then recurse the tree "depth first" so I could put the most enclosed shape at the lowest position, followed by its closest enclosing shape and so on, all the way up to the top. To do this, I ended up writing two recursive functions: one to build the tree from the shape enclosure test data, and another to output the shapes in the right order! Phew. Recursion is hard to reason about, and I've had a nasty brain fog of late, that has made it harder than it should be, and I also feel I'm rather out of practice too.

It's still not perfect, because it still sometimes puts shapes in a non-optimal order, resulting in the laser head jumping around a bit more than I'd like, but I think I can refine it to do what I want. I also have to take out an awful lot of debugging output, but I'm probably going to wait a bit before I do that - probably longer than I should, but that's how I roll!