3D Packing … for SLS Printing
How many 3DBenchy boats can the Fuse 1 print?
Formlabs recently announced the Fuse 1, a 3D printer that works via Selective Laser Sintering. This technique uses a nylon powder which conveniently supports the structures as they are printed. No scaffolding or supports are needed, so we can print as many objects as we can pack into the volume.
This begs the question - how many 3DBenchy boats can the Fuse 1 print in a single batch? As soon as the printer was announced, I immediately gravitated toward this algorithmic challenge.
The Fuse 1 SLS Printer has a printing volume of 165 x 165 x 320 mm. The 3DBenchy tug boat model has standard dimensions of 60 x 31 x 48mm. The printer volume is 8,712,000 mm3 and the boat's bounding volume is 89,293 mm3, so a very rough estimate yields 97 boats. Let's dig deeper...
Bin Packing
A bin packing algorithm can be used to pack as many boats into the volume as possible. All six distinct rotations are considered. With this approach, assuming a one millimeter spacing between boats, we can pack 82 boats into the printer. But this leaves a lot of empty space since we're just using the boat's bounding box for packing. How can we pack the boats closer together?
Bounding Volume Hierarchies
The first thing we need is a quick way to do collision tests between boats as we try packing them more closely. A Bounding Volume Hierarchy is the perfect data structure for this. As you can see below, even a small BVH with just 8 leaf nodes fits the shape of the original model fairly well. Constructing the BVH for a complex model may take a few seconds (3DBenchy is made up of 225,706 triangles!), but once built we can perform millions of collision checks per second.
3DBenchy
Bounding Volume Hierarchy with 8 leaf nodes
Simulated Annealing
Now we want to find some ways of arranging the boats to minimize wasted space. That is, we want to reduce the total volume of N boats packed together. This is an optimization problem, and I'm partial to Simulated Annealing for problems like these. The algorithm starts by randomly placing the boats. Then, each iteration, it randomly mutates the position or rotation of one of the boats. If a collision is detected, it tries something else. Then it computes a score based on the total volume occupied by the boats. Within seconds we can find some nice arrangements like those shown below.
2 boats packed to 83% of their unpacked volume
4 boats packed to 67% of their unpacked volume
4 boats packed in a more cubic shape
Bin Packing Plus
We could try the simulated annealing algorithm to pack the entire printer volume, but it doesn't work quite as well when the search space becomes so huge. Instead, we can use these tight arrangements found via annealing as options to choose from when performing the bin packing. The bin packing algorithm is modified to understand how many items are contained in each packed mesh and finds a packing that maximizes the total number of boats. With these new options in hand, the bin packing algorithm can fit 113 boats into the printer volume. Here's a video showing the packing.
With naive bin packing, 82 boats can be printed
With smarter packing, 113 boats can be printed - a 37.8% improvement
The Fuse 1 SLS printer can print at least 113 3DBenchy boats.
Multiple Meshes
As another example, this R2-D2 model is made up of 8 distinct parts. Simulated annealing is again used to pack these 8 parts into a small volume. We find a few different arrangements so that the bin packer has more options to work with. The algorithm is able to stuff 27 copies into the printer.
The Fuse 1 SLS printer can print at least 27 R2-D2 droids.
The Code
The code is written in Go (< 1000 lines) and consists of two binaries: pack3d for tightly packing objects via annealing and binpack to pack as many objects as possible into a specified volume (e.g. the volume of the printer).
https://github.com/fogleman/pack3d
Installation
First, install Go, set your GOPATH, and make sure $GOPATH/bin is on your PATH.
brew install go export GOPATH="$HOME/go" export PATH="$PATH:$GOPATH/bin"
Next, fetch and build the two binaries.
go get github.com/fogleman/pack3d/cmd/pack3d go get github.com/fogleman/pack3d/cmd/binpack
Usage Examples
Note that pack3d runs until stopped, writing its output to disk whenever a new best is found.
pack3d 2 3DBenchy.stl # tightly pack 2 boats pack3d 4 3DBenchy.stl # tightly pack 4 boats pack3d 1 *.stl # tightly pack various meshes, one of each # pack as many boats as possible into the printer volume, given a few different arrangements binpack 1 3DBenchy.stl 2 3DBenchy-x2.stl 4 3DBenchy-x4.stl