I’m continuing to develop integrated design + gcode generation in Grasshopper, and my latest bit of difficulty is ending up with a bunch of infill lines that work as a matter of geometry, but which are wildly unoptimized as a matter of actual machine movement.
Extrusion being extrusion, I can both reorder the lines and flip their start/end to optimize. But… is there any better solution than just brute force “try every permutation of order and direction”? I’m typically working with 5 - 15 lines per layer, so the brute force approach has to evaluate quite a lot of options.
Here’s a small test file to illustrate how the infill lines arrive and how I’m looking at measuring travel distance (for each layer, the sum of movement from the end of one line to the start of the next).
Sort the curve midpoints along a circle for each branch. (white group) The ‘path idx’ slider in the ‘Tree/List Viewer’ utility selects each branch to show the sorted curves, color-coded to show sequence. In some cases, it’s easy to see a short connection between adjacent curves. In other cases, it’s not so obvious.
Connect Curves joins the sorted curves in each branch, but because the curves are not flipped consistently, this makes longer jumps than one can see by visual inspection.
P.S. Here is a different idea (yellow group) for finding the shortest path from the end of each curve to the nearest start/end point (white segments). It works well sometimes and fails sometimes.
P.P.S. This version ‘c’ is a feeble attempt to avoid white segments between the end and start points of the same curve but it fails, probably because iteration (Anemone loop?) is required to avoid using the same point twice. I added a 'Travel distance’ indicator showing the sum of white segment lengths in each branch, which is a good enough idea that I retrofitted the same feature to version ‘b’ (now ‘bb’).
Thanks Joseph! All versions are interesting and it’s instructive to see your approach evolve. Lots to learn from here. Many thanks!
Exploring this more I think I have stumbled onto a variation of the traveling salesman problem, which is never a good sign. All of your solutions are improvements on what I’ve got and this isn’t a problem that has to be 100% solved; it’s about minimizing travel, not eliminating it. But it is very hard to let go of!
This is version ‘bb’ again from yesterday with two cosmetic additions:
Numbering the sorted curves by their midpoints (cyan group) and
Pipe added to the white segments to make them more obvious. (yellow group)
It’s interesting to note that branches 0 and 2 have six curves while branches 1 and 3 have 11 and 12 curves, respectively. Sorting is rather good except for where branches 1 and 3 start, which could be fixed. It’s also notable that in this image showing branch 0, the longest white “travel” segment isn’t needed at all since it merely returns to where it’s already been? Also true for branch 2.
Curve directions are mixed up, some need to be flipped to align end points with the start points of the next curve. Again, this looks like an Anemone loop would be useful. But another idea has occurred to me that might be addressed best earlier in the process…
I don’t know how these “infill lines” were created, particularly how the cross hatch lines were connected? Ii might work better to eliminate all the short connecting segments and use an Anemone loop to methodically connect them all in sorted sequence? Or maybe not.
There is a ‘ShortestWalk’ plug-in for GH that works very well, definitely worth a try.
Interesting work on the Seam – I still haven’t gotten that solution to work when generalized to other shapes without some hand-tuning.
But I did take a stab at adding additional information in the form of the center curve the shape is based around, and then using Anemone to iterate through each curve starting at the center and trying to sort/flip curves to minimize gaps, and finally closing small gaps between curves by just adding a little more infill.
It’s working decently, typically about a 50% reduction in travel. It really does call out @Joseph_Oster 's point that the real way to address this is probably in the infill generation code so it doesn’t produce backwards / separated curves. That is coming from Xylinus, which is fortunately open and modifyable, but I have not yet dug into that. It uses eerily elegant logic that is a little daunting.
P.S. Shortest walk is also interesting. I almost need the opposite – given a grid of points, what is the shortest path to cover them all? Which gets right back to traveling salespeople.
I don’t recognize any of my code in what you posted today, and don’t feel like working to understand what you are doing well enough to comment on it. Sorry.
What I can do though is copy/paste this new geometry into my Oct13b.gh version from two days ago and utilize the ‘Center curves’ for AlongCrv(Sort Along Curve), which is way better than the circles I was using, and doesn’t require any seam adjustment.
I realize mine is working on only one branch (layer) at a time and could probably change that, skipping the ‘Tree/List Viewer’, but I like being able to see and understand what the code is doing, which is difficult with all four branches visible at the same time.
Thanks @Joseph_Oster and sorry for being unclear – your code is super helpful and I’m still working with it; that Anemone sample is just an alternative I’m also exploring. And yes, I could stand to get a lot better at making code well-organized and self-documenting!
Well, it’s not so much that your code is unclear, it’s that my mind grasps for meaning at every step and I quickly got lost.
Your first group is labeled “Flip curves so start is closer to center curve” and my thought is “Why?”.
Your next group has the Anemone loop working on all four branches at the same time and my experience says “That won’t work!”. For one thing, the branches aren’t all the same length so the single value being passed to the ‘N’ (Repeat) input for Loop Start is questionable.
Etc. I stopped trying to make sense of it there.
My instinct would be to use TStat(Tree Statistics) to get the list of branches and work on each branch, one at a time, because I want to loop through the sorted list of curves in each branch. That would require two “nested” Anemone loops, the outer loop going through the branches and the inner loop going through the curves in each branch.
I’m just not in the mood today to work through this.
P.S. Adding the ‘Center curves’ as you’ve done is very useful, good idea!
Good stuff (as usual), But why struct? (since in a class assignments of large reference types are cheaper than assignments of large value types. - general case: 1Z curves etc etc)
A creative and interesting approach that, at first, appears to produce some minimal “Travel Distance” numbers. I can’t analyze the C# code but can study the results and compare them to my latest effort (in my next post). I added two linked ‘Tree/List Viewer’ widgets, one for the infill curves and one for the travel links, to view your results by branch:
I’m wondering if this really addresses the tool path travel distance issue? It appears to me that the infill curves and travel links are not integrated?
I’ve had luck using Anemone on multiple branches of varying length as long as I 1) set the loop count to the most that could be needed, and 2) ensure that the extra iterations on shorter branches do no harm. In this case I’m moving items from one list to another, so when the short branches run out the extra loops are a no-op. Seems to work, though maybe it’s a worst practice
Thanks for all of the insight, I’ve learned a lot from your approach!
The green group (upper right) weaves the “sorted” infill curves with the travel links to form one continuous toolpath per branch. The white group alternates start points by layer (branch) so in theory, the tool would minimize travel going from layer to layer.
OK, cool, though it means you can’t take shortcuts like ‘Flatten’, as I did inside the loop. The abridged ‘Tree/List Viewer’ in my code can be replaced by a second “outer” Anemone loop that would feed the “inner” Anemone loop shown. Again, best practice or not, I prefer to see what I’m doing so took this one-branch-at-a-time approach.
P.S. This (below) is branch zero, showing some wild long “travel links” to connect short segments of infill that were passed by when the tool was closer because of following infill curves to their ends. This appears to be correct, given the infill curves we have?
Out of curiosity, I culled the short connecting segments from the infill curves (pink group, top left - hope I didn’t lose anything?) and passed them through the same algorithm as before. The ‘Joined Tool Path Length’ is less for all branches except one, which is very close to the same.
Wow! That is really creative and interesting. Unfortunately I don’t have the source file at home, but either tomorrow or Monday I can post the infill lines as generated, before the connectors are created. But that looks right.
I do not understand what you mean with this quoted statement.
C# code connects Input curves (its ends) by lines and as result return these connecting-lines, which you call if I understand you well “travel links”. If we join Input-curves with connecting-lines we will get one curve.
I guess I’d like to see that one curve, the tool path for each layer? The code I posted today has a hidden side effect in the sense that the existing infill curves have a different sequence after the loop that allows Weave of the infill and ‘travel link’ curves.
Versions ‘16a’ and ‘16b’ use the identical algorithm.
