Pack Your Plywood Cuts with Genetic Algortihms

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]!

40 thoughts on “Pack Your Plywood Cuts with Genetic Algortihms

    1. JavaScript is very capable on modern PC’s. I use it all the time – just open a .htm on my desktop and send it to a text editor.

      While my JavaScript is guaranteed to fail on any machine or browser other than the ones I used to develop the code – it still gets the job done.

      My HDL synthesis PC is a 2.6 GHz quad core so It is really surprising what it can do with plain old JavaScript.

      Of course I only use JavaScript for the more simple and quick things – anything harder and I will use something like Lua.

      I find JavaScript useful for graphics or other rendered outputs – cos that’s what a browser is made for.

    1. 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.

    1. 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.

  1. 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.

  2. 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 ” >

    1. 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.

    2. 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.

      1. 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.

        1. 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.

    1. 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.

    2. 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

    1. 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.

  3. “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!

    1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s