As a hobby, I design twisty puzzles. These puzzles are then printed by a 3D printing service. In order to bring down the cost of printing, I had to solve the problem of arranging all the puzzle parts as efficiently as possible inside a small bounding volume. PartStacker solves this problem: it takes as input a set of 3D model (STL file format) and attempts to place a specified number of copies of each in an as small as possible bounding box. PartStacker is free software, the program and its source code are available under the GNU General Public License.
Using PartStacker is simple. To begin, you need to import one or more STL files in to the program. Once this is done, at the very least you need to specify a part count for each individual STL file. A useful shortcut is to include the part count in the file name: both "part_name (XX).STL" and "part_name.XX.STL" are automatically recognized (substitute XX for the part count). The imported STL's are displayed in a list. After you click an entry from the list, you have the option of changing various settings which affect how the parts are stacked:
After importing STL files for your parts and selecting individual part settings, you can adjust the initial bounding box and maximum bounding box settings. The program will start stacking the parts in a cube with an edge length of the minimum bounding box size and will increase the bounding box size as needed until the maximum size is reached. These values are automatically selected to reasonable values but if you cannot quite get an optimal enough stacking then playing with these can help (increasing either or both values can actually work surprisingly well). Selecting a low minimum size or high maximum size will make calculating the stacking take a very long time.
The program also has an option for setting the minimum clearance between parts. Increasing the minimum clearance will make the program run much faster but the final stacking will not be as dense. Decreasing the minimum clearance will make the stacking denser but the program will take much longer to run. It is useful to play with this value if the default value does not produce a dense enough stacking.
Finally, you can press "start" to begin calculating the stacking. As the progress bar fills for the first time, precomputations (voxtelizing the parts) are done. When this is completed the bar will reset and start to fill again as a stacking is calculated. You may abort stacking by clicking "stop". If the stacking completes sucessfully (it fits within the maximal bounding box) you will be prompted to save the part. This prompt will also indicate the final stacking bounding box and density. If you do not save the stacking at this time you can later do so by selecting "Export result as STL".
It is possible to save the selected settings in a stacking configuration (.stk) file to save them for later use. This will save only the settings and references to the STL files (but not the STL files themselves). The file menu is used exclusively for .stk files and not for .stl files, .stl files can be loaded from the import/export menu.
The interface also has four buttons for (un-)loading STL files: Import/Delete/Change/Reload. "Import" loads an STL file in to the program while "Delete" removes the selected STL file(s) from the stacking (but not from the disk). "Change" allows you to replace one STL file with another and "Reload" reloads the selected file(s). This option is useful if you make adjustments to a file and want to use the new version.
Notice: PartStacker only works correctly with STL files that are in mm-units. It keeps a clearance of about 1mm between parts, if the files use any other units (inches or meters) then it will keep a clearance of 1 unit (1 inche or meter) which is probably not desirable.
This section describes briefly the algorithm that PartStacker uses. The magic happens mostly in PartStacker.cs PartStacker was not originally intended to be released to the public so comments in the source code are (still) sparse.
Rather than working directly with the triangulated models from STL files, the shapes of the parts are approximated with 1mm3 voxtels. If the option is selected, the part is first rotated to have a minimal axis-aligned bounding box (by looking at a random sample of points from the model and trying various rotations). Then (multiple) voxtelized verions of the part are generated, one for each rotation that will be tried. The parts are then sorted from largest to smallest and the largest parts are placed first. The stacking begins at the origin and tries to place the parts at points that are progressively farther away from the origin. The strategy is greedy: if a part fits it is immediately placed and the algorithm never backtracks. By considering larger parts first and then the smaller parts, the smaller parts will fill the gaps created between the larger parts. Up to 32 rotations of the part are considered at once (this can be done surprisingly efficiently using bitstrings). If it is not possible to place any more copies of the part inside the current bounding box then a new location for the part is selected that minimally expands the bounding box.