I'm currently working on a program that takes a bunch of STL files as input (and metadata on how many copies of each file are wanted) and returns a single new STL file that contains all of the input STL files, nicely stacked for 3D printing. My goal is to minimize the volume of the bounding box.
My current heuristic approach is to take each input file, and rotate it so the bounding box volume is minimal. Now I treat the parts as if they are cubes. I then sort the parts by volume and place the largest first, then the smaller ones (the idea being that any gaps left by the larger ones will be filled up by the smaller parts). I try to place each part (in positive space) as close the origin as possible. I fill up three arrays with x,y,z coordinates of the corners of the boxes already place and then consider any combination of these as location for my new box. If it does not fit in the current bounding box, I pick the location that leads to the smallest increase of the bounding box.
However, this does not always give satisfactory results. The algorithm is more than fast enough, but most often the placement is just really bad and I could do far better by hand.
Maybe treating the parts as boxes is just not good enough. Another option would be considering convex hulls for the parts but that would be a lot more difficult to implement and I've got no idea what kind of algorithm you would use for packing convex polyhedra.
Maybe I need to consider different orientations of the boxes I am currently using. Maybe just rotating each 90 degrees will help?
However, this leads to the time becoming non polynomial (not good, since I usually need to consider over 100 parts) and I can't use dynamic programming either since there is no good way to measure how much space is still available.
Perhaps another option is just to pick a random orientation (rotated about 90 degrees), each time a part is inserted?
This is a really complicated topic but I'm interested if anyone here can tip me off to some resources.
This is just a sample output:
Density is 9% which is not good enough to get the Shapeways discount. Manually I can easily make it to over 10%. It's really annoying because the computer stacking looks much more dense than the one I made myself, but it's not.