Optimization Inefficiency - Possibly line direction bias?

[chrsmlls333]

Hi there, I have been noticing some odd behaviour in the Axidraw Inkscape plugin 2.5.3 optimizing paths. I've attached an exaggerated example. Does the optimization hunt for the nearest endpoint of any kind or the nearest "a" in an "a->b" polyline or path. There could be great gains by adding an option to turn directionality(?) off in the optimization process.

If this has been fixed between 2.5.3 and 2.5.6 my apologies, didn't see it in the commit changes.

Length of path to draw: 3.05 m.
Pen-up travel distance: 1.93 m.

[oskay]

The current tool intentionally preserves the direction of paths. If you are seeing some "odd behavior" that does not appear to match this, please say so.

An option to turn that off -- to allow all paths to be reversed -- is a good idea, and one which has been discussed heavily elsewhere ( #4 ). We also have it on our internal issue tracker.

The number of ways to construct a path is nontrivial, and the tricky part of building a path reversal tool ensuring that we have correctly accounted for all of them.

[chrsmlls333]

Bookmarking this here as one basis of implementation: https://github.com/Pomax/svg-path-reverse/blob/gh-pages/reverse.js

(Apologies for my bias toward javascript.) I do remember that issue thread but I had forgotten that line-reversal was marked as a further improvement. Does Inkscape allow any API access to call its Path > Reverse function?

[oskay]

The link that I gave previously had another implementation, as well. (And again, this is something that is on our to-do list.)

Inkscape does not grant extensions access to internal functions. Some extensions get around this by calling a second copy of Inkscape as a CLI function to run a function, but it's a lot of overhead, especially if it needed to be called many times.

[masonium]

I was using my AxiDraw to plot a drawing that would definitely benefit from this optimization (to first-order it's a bunch of left-to-right lines, so it's basically the worst case without path reversal) so I decided to implement this myself.

I have a branch in plot_utils (https://github.com/masonium/plotink/tree/pathdata-reverse) and in axidraw (https://github.com/masonium/axidraw/tree/reordering-reversal) that together implement this. I opened a PR 31 in plotink already for a necessary bugfix that's a precursor to these branches. (Even without taking anything else though, the bug fix is relevant to improving the optimization as-is.)

One thing about my implementation is that it doesn't preserve <use> references. Those tags are correctly accounted for and plotted, but they are essentially de-referenced when reversed, rather than making a new <use> that refers to a reversed version of the original. If the original svg makes heavy use of <use>s, then the optimized version could be significantly larger, but I don't know how common this is in practice.

I don't know how far along you are ready, but if you're willing to take a look I'd be happy to open PRs for these branches to get them merged in. They are both based on 2.6.3.

[oskay]

We've had a couple of different versions that do basically what yours does for about three years (our own and one separately proposed that you can see here:evil-mad/EggBot#91 ).

The key reason that we haven't already added one of the existing ones is that it only works on some paths. A new feature needs to be (1) reliable and (2) effective. If the core attribute of a routine is that it makes our software less reliable, we are not adding it. Aside from the "use" element issue, your patch appears to skip a number of standard SVG path element commands.

We do have a path reversing solution that handles all path types and is added in our upstream code. It is tested, working, and is slated for release in an upcoming version of the AxiDraw software. However, this optimization will be available only during plotting, not as a separate tool. We may eventually add this feature to our "offline" separate Inkscape extension, or we may eventually remove the separate extension. If the integration within the AxiDraw plot process works significantly better, there may be little reason to maintain a separate tool.

[masonium]

Thanks for your feedback, @oskay . I'm a bit confused about the comment that "it only works on some paths". If you're referring to the <path> element specifically, I believe that ink_extensions.simplepath.parsePath returns a normalized, absolute path that only contains LCQMAZ commands, so my pathdata_reverse implementation is comprehensive . Otherwise, I believe that reverseNode handles all other drawing tags (<g>, <rect>, <polyline> ,etc.) that getFirstPoint handles, which seems to be the exhaustive set of plottable elements. <polygon>, <rect>, <circle>, and <ellipse> are all already closed paths, so there's no need to 'reverse' them for the purposes of the optimization algorithm.

Of course, if you have a tested and already merged implementation ready to go, then obviously there's no need for my branch. However, if you know of a specific deficiency offhand, either in concept or in specific implementation, I would appreciate any insight so that I could hopefully provide useful contributions in the future.

[oskay]

I believe that ink_extensions.simplepath.parsePath returns a normalized, absolute path that only contains LCQMAZ commands, so my pathdata_reverse implementation is comprehensive

Ah, that may indeed be so -- my error.

[haschdl]

Not a solution, but a suggestion. Due to the complexities of having that in the optimizer, one can dramatically improve the plotting times by handling the direction in the drawing (for example inverting the drawing direction in Processing).

I also tested scripts that invert “every other path” in Illustrator. Again, none of the solutions can be applied everywhere, but one should consider “starting a path close to where the previous one ended”.

[oskay]

Yes, if you're using Processing (or some other environment) to do the ordering, you can potentially get much better plotting efficiency versus a general algorithm that is concerned about execution time.

[oskay]

The feature has been implemented as of AxiDraw software release 3.0.