Reading (or writing!) Hackaday, we find that people are often solving problems for us that we didn’t even know that we had. Take [Jack Qiao]’s SVGnest for instance. If you’ve ever used a laser cutter, for instance, you’ve probably thought for a second or two about how to best pack the objects into a sheet, given it your best shot, and then moved on. But if you had a lot of parts, and their shapes were irregular, and you wanted to minimize materials cost, you’d think up something better.
SVGnest, which runs in a browser, takes a bunch of SVG shapes and a bounding box as an input, and then tries to pack them all as well as possible. Actually optimizing the placement is a computationally expensive proposition, and that’s considering the placement order to be fixed and allowing only 90 degree rotations of each piece.
Once you consider all the possible orders in which you place the pieces, it becomes ridiculously computationally expensive, so SVGnest cheats and uses a genetic algorithm, which essentially swaps a few pieces and tests for an improvement many, many times over. Doing this randomly would be silly, so the routine packs the biggest pieces first, and then back-fills the small ones wherever they fit, possibly moving the big ones around to accommodate.
That’s a lot of computational work, but the end result is amazing. SVGnest packs shapes better than we could ever hope to, and as well as some commercial nesting software. Kudos. And now that the software is written, as soon as you stumble upon this problem yourself, you have a means to get to the solution. Thanks [Jack]!
42 thoughts on “Pack Your Plywood Cuts With Genetic Algortihms”
(apart from that, I think this is pretty darn awesome.)
Gets the job done.
could this be used to pack UV’s for 3d models?
OP here. I have’t thought about that application, but the underlying algo is the same. The major hurdle would be import/exporting of the UV data.
Jack you seriously need to sell this to pepakura!
i remembered that there is Flat iron that does something similar http://www.texturebaking.com/features-benefits/
i wonder how if your method worked for uv how it would compare to flat iron and other solutions.
i was thinking the same thing. uv mapping has always been a huge roadblock for my creativity. you make a model and know what you want to do for a texture, but you have this tediously long and boring task between the actual modeling and opening photoshop with a template and start spewing fourth pixels.
this would especially be useful if you need a second uv channel where every polygon has unique space, for example for normal maps (especially using baking techniques). the primary channel then lets you mirror and share areas to keep the pixel density up. you normally want large chunks of contiguous polygons there which have been pelted out to eliminate seams. but i usually map those out in sections before trying to get all those sections to fit. so the algorithm would help both of those situations.
Swaps 2 and tests? That doesn’t sound like a genetic algorithm, It sounds like a bubble sort.
You might want to do some more reading. It doesn’t “swap 2 and test”. Configurations are randomly mutated, and the mutations with the best scores are mated together to produce offspring for the next generation. None of that is in your bubble sort.
Laser cutters do distort a sheet while cutting. Small cuts tend to pull the plastic one way or the other. so a 1/4″ seems to be fine, and you really don’t waist too much material. Wood, not so much. But I do love this idea.
Rotating things on plywood isn’t that nice. Some connections start looking really bad when wood texture is turned in one part but not on the other. But great concept.
same goes for cloth
You can control the rotation. The default is 4 rotations (cardinal rotations), but if you set it to 2 you get only “up” or “down” orientations.
Why didn’t I think of that! Amazing.
On Fri, Jan 22, 2016 at 4:02 AM, Hackaday wrote:
> Elliot Williams posted: “Reading (or writing!) Hackaday, we find that > people are often solving problems for us that we didn’t even know that we > had. Take [Jack Qiao]’s SVGnest for instance. If you’ve ever used a laser > cutter, for instance, you’ve probably thought for a second or ” >
why not take a good 2d physics simulator, add some gravity, through all pieces into a box, and then shake the box a bit. Ok filling the hollow parts would be tricky then.
oh, i think to fill the hollow parts you would need some sort of tunneling effect
You mean something like quantum tunnelling??
Yes maybe, but why do you reply to your own comments
Me, Myself, and I all reply.
I use this technique when putting my kids playmo back in the box. First the large pieces like vehicles and stuff. Then pour figures and smaller over until filled to the brim and shake. Iterate as neccesary. Packs incredibly dense.
This is a bit like a simplistic form of simulated annealing…
Because of “particle packing”. If you put a lot of randomly shaped things in a box and shake, the smaller ones end up climbing to the top. You don’t get optimal packing that way. It’s been studied, and occurs in things like boxes of cornflakes. It’s actually a bit of a problem in some places.
The larger items actually end up rising because small items fall into the small gaps formed underneath the large items when they’re shaken about. The problems described are real.
THAT’S what I meant!
Actually OP’s idea might work in the absence of gravity, or absence of simulated gravity. But yup particle packing has caused problems in all sorts of real-world applications.
As far as simulations go though I’ve a feeling a genetic algo like this would do it in less calculations.
I thought of this, but could not get it done. My hat goes off to the programmer. Amazing.
I did a nesting algorithm at work once, although my constraints were rectangular parts with grain direction, and the potential for grain matching (parts that have to be next to one another). The beginning of the algorithm was the same, sorted by size and first fit placement, but without the extra genetic step (not likely to help much with rectangles, plus most parts couldn’t rotate).
Rectangles are easy though, collision detection is dead simple and you can just keep track of corners for insertion points. There’s a lot more to getting this to work with irregular shapes. This person did a heck of a job.
Yep, sounds familiar. Some time ago on HaD, I even made the comment about how the open-source slicer and toolpath software was a big step in giving rise to the DIY 3D printing explosion. Just a generic piece of software that allows the pipeline to exist, and gets the job done well. Since laser cutting is the other largest tool in this space of accessible and rapid building, a similar pipeline tool for 2D packing was clearly called for.
And then I just never did it, because I am lazy :P
Would this be useful in tackling the traveling salesman problem?
Well traveling salesman and 2d bin packing are both NP-Hard problems, so I assume you would be able to map solutions from on to the other.
It won’t solve the problem.
Genetic algorithms are good to find A solution, not THE solution.
The traveling salesman problem is difficult because one wants
THE BEST solution, rather than a good solution.
What about adding tabs to the parts to prevent them from moving?
you could feed the result back into you cam soft and have it tab it.
How can this be used for 3d printing with Slic3r and Repetier?
“uses a genetic algorithm, which essentially swaps a few pieces and tests for an improvement many, many times over”
No that is not genetic algorithm. That is maybe local search. Significant part of GA is having recombination!
GAs pick more fit mates with higher probability. It’s back-door hill-climbing on the objective function, IMO. I could have phrased it better in the article.
But I also refer to (single hidden layer) neural networks as “regression with logistic functions” so don’t listen to me. I put in a link for those who wanted to read more.
Calling it back door hill climbing is the same thing as calling it local search :) Anyway thanks for the response.
Good luck sorting your cuts.
Jack has made an update
Has anyone seen anything like this for 3D printing? It would be neat to use this technique to pack the build plate.
Please be kind and respectful to help make the comments section excellent. (Comment Policy)