Form Labs recently announced the launch of the Fuse 1, a desktop SLS printer that will print all your parts using nylon powder and a laser. This a fundamentally different method of 3D printing as compared to filament-based machines, and the best way to use a Fuse 1 is to fill the entire volume of the machine with 3D printed parts. [Michael Fogelman] decided to investigate the 3D packing problem, and managed to fill this printer with the maximum number of 3D printed tugboats. If you’re wondering, it’s 113, as compared with 82 tiny Benchies using naive bin packing.
The formal definition of this sort of problem is the bin packing problem, or simply calculating the maximum number of items can be packed into a finite volume. There is no general solution to this problem, and it’s probably impossible to create an algorithm that will solve this problem for any collection of 3D models. Nevertheless, it’s possible to create a solution that shows marked improvement over a naive solution.
[Michael]’s solution involves simulated annealing. This algorithm begins by randomly placing tugboats, then mutating the position or rotation of one of the boats for each iteration. The code is less than 1000 lines of Go and is available on GitHub if you already have an SLS printer at your disposal.
It should be noted this type of problem isn’t particularly new to the world of 3D printers. There have been a few tools to solve the bin-packing problem for filament-based printers, but the solutions to these problems are two-dimensional; since filling a bed is a problem that only uses the ‘shadow’ of the Z-axis of each part, it’s a slightly easier problem to solve.
Now that Form Labs’ Fuse 1 SLS printer has been announced, there is a new application for this type of problem in the space of 3D printers. It’s not a perfect solution — and it’s doubtful there will ever be a perfect solution — but if you’re looking for a way to fill the volume of your powder printer with parts, this is the best you’re going to do.
Can someone kindly create standalone exe? I do not know how to use go and compile it by myself
Ewww! Don’t you mean an ELF?
Well there is the Torquato solution, just best fit you 3D geometry to the nearest valid tetrahedra-octahedra pattern or super set of a valid pattern.
So it is impossible to to create an algorithm to do this, but Michael has created an algorithm to do this.
We need to get Michael working on more impossible tasks.
Not exactly. An algorithm to “solve” this problem means the algorithm finds the optimal solution, always. Michael’s algorithm finds a solution that is usually pretty good, but is not guaranteed to be optimal or even close. Not to take away from his work in developing a working tool to do this for the benefit of all of us, but simulated annealing is not new nor novel in being applied to this problem.
Spot on. As Fogleman states, “The Fuse 1 SLS printer can print at least 113 3DBenchy boats.” The Hackaday article misstates this as the maximum number that can fit. It’s entirely possible that 113 is in fact the maximum, but Fogleman does not show this nor does he claim to have shown this.
This is Benchoff’s superpower. He can find something to trigger us in pretty much every article he jolts down.
Hmmm… Mr. Benchoff said this, “— but if you’re looking for a way to fill the volume of your powder printer with parts, this is the best you’re going to do.” Emphasis on the word “best”. So he said that just to Wind-Us-Up? Maybe! Evil sometimes lurks where you least expect it ;-)
Well no it isn’t impossible. In fact finding the optimal packing is trivial – just extremely slow. In short: generate all possible packing patterns and select one that is optimal.
The problem is that the slowness is so extreme any non-trivial version of it isn’t likely to finish before the heat-death of the universe.
uv mapping runs into this constantly… seems to be a few good algorithms out there for a general-ish solution.
Chuck them in a barrel pf water and measure how much the level rises. There’s your minimum packing volume. :)
Just add One hydraulic press. :)
How well does it handle assorted input parts that dramatically differ in geometry and volume?
Short explanation: As this problem belongs to the family of https://en.wikipedia.org/wiki/Combinatorial_optimization problems, it is in the NP complexity class. Therefore, no efficient analytical solutions exists. Simulated annealing is a way to arrive at a very good, but most certainly not optimal solution in a timely manner.
If you really NEED the optimum solution you might not be doing it right. At that point it sounds like one is trying to use a 3d printer for manufacturing rather than one off prototypes or personal items. If you need to produce a lot of something you might be a lot better off just printing a few re-usable molds and using some sort of epoxy.
I believe the point is to demonstrate a proof of concept algorithm for maximizing build volume by packing rather than just mass manufacturing a single part. This is useful to maximize machine utilization if there are a lot of parts to print. Recoating on these type machines takes significant time, and reducing wasted space means you can print more efficiently.
Besides, 3d printing is sometimes the only practical manufacturing method for some geometries, and it’s then actually viable for mass manufacturing.
Great. Now instead of grey goo taking over the world, tugboats.
Is that not a problem the industry should have solved already? There are large manufacturers of huge powder sintering printers, service bureaus offering you some space in these printers for your little model… and there are more similar services, like the PCB manufacturers that take random boards from clustomers and try to fit them into a production planel and maximize profit by selling as much of that panel surface back to the customers as possible.
It seems strange to me that this is a problem that needs solving or has not been attacked and solved by now. Or are the solutions used i nthe industry all patented and locked down as trade secrets?
High end printers already come with software to handle the batch jobs. More exactly: expensive machines with expensive software and expensive contracts for maintenance, raw materials, etc.
But this code ignores one important thing: random orientation is only useful if you don’t care about the physical (elongation at break, flexural modulus, dimensional precision, etc) and cosmetic (surface roughness, layers, etc) properties of the print, or even the printability (failed vs successful batch caused by cooling, thickness, etc). Sometimes you really want something to be placed one way, and only that way or equivalent (you want something along Z axis, with some features at top and others at bottom, so rotating using that axis is fine, but the top-bottom must be respected). If you don’t care were is the worst of a print, fine, if you want to push the worst to the less important place, then you want to at least set some orietation constraints.
Basically this code is playing the 3d print lotto, like with certain 3d print services.
Just put it in a physics simulator and jiggle them around until you get the highest count density, clearances to keep them from merging. I call it the S.S. Benchy Chaos Theory.