A while back, I implemented a paper that had showed up on HN for a course project (Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects).
Over the holidays, I cleaned up the implementation (with the help of Claude Code, although this is not an advertisement for it) and released it on GitHub.
If anyone needs fast 3D packing in python, do give this a shot. Hopefully I have attributed all the code/ideas I have used from elsewhere properly (if not, please feel free to let me know).
The problem sounds very interesting and a complex one to solve. Could give examples of use cases where dense 3d packing is needed? (Say, besides literal packing of physical objects in a box? )
> Could give examples of use cases where dense 3d packing is needed? (Say, besides literal packing of physical objects in a box? )
Not an answer, but something interesting on this topic:
In a warehouse/distribution center, a dense packing result can be too time consuming for most consumer products. As density increases, it takes the human longer to find their own solution rapidly that works. You can provide instructions but that is even slower than the human just doing their best via trial and error.
We had to dial back our settings from about a 95% volume consumption percent (initial naive setting) down to about 80% before they could rapidly fill the cartons. Basically it's balancing cost of labor vs capacity of system during peak (conveyor would start backing up) vs shipping costs.
Bin packing can be seen as an optimization problem. In 2D, consider a scenario where you need to cut shapes from a sheet of plywood or sheet metal while minimizing waste; finding the optimal orientation of these shapes reduces material loss. In 3D, you might imagine packing objects into a container or cargo space, or sculpting a collection of 3D shapes out of a known volume of material, where you'd optimize the arrangement and orientation to minimize waste.
One question I have, is when we say "interlocking-free", does this mean that the algorithm can still densely stack cups (with a draft angle), or is it instead guaranteeing that the convex hull of shapes are non-interfering?
Thanks. I'll link it in the first line in the README. I think the interlocking-free part can pack cups like you suggest. They propose a flood fill algorithm which computes all the reachable places for the voxelized shape. It doesn't put assumptions on convexity. I think it would be a great example to try it out on though.
Interesting, this is the first time I've come across using a FFT for collision detection, and now that I think about it it really makes sense. Thanks for the insight!
A while back, I implemented a paper that had showed up on HN for a course project (Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects).
Over the holidays, I cleaned up the implementation (with the help of Claude Code, although this is not an advertisement for it) and released it on GitHub.
If anyone needs fast 3D packing in python, do give this a shot. Hopefully I have attributed all the code/ideas I have used from elsewhere properly (if not, please feel free to let me know).
The problem sounds very interesting and a complex one to solve. Could give examples of use cases where dense 3d packing is needed? (Say, besides literal packing of physical objects in a box? )
> Could give examples of use cases where dense 3d packing is needed? (Say, besides literal packing of physical objects in a box? )
Not an answer, but something interesting on this topic:
In a warehouse/distribution center, a dense packing result can be too time consuming for most consumer products. As density increases, it takes the human longer to find their own solution rapidly that works. You can provide instructions but that is even slower than the human just doing their best via trial and error.
We had to dial back our settings from about a 95% volume consumption percent (initial naive setting) down to about 80% before they could rapidly fill the cartons. Basically it's balancing cost of labor vs capacity of system during peak (conveyor would start backing up) vs shipping costs.
The main one I could think of was maximising 3D printer utilisation, I.e if filling your print volume was something you wanted to optimise for.
Bin packing can be seen as an optimization problem. In 2D, consider a scenario where you need to cut shapes from a sheet of plywood or sheet metal while minimizing waste; finding the optimal orientation of these shapes reduces material loss. In 3D, you might imagine packing objects into a container or cargo space, or sculpting a collection of 3D shapes out of a known volume of material, where you'd optimize the arrangement and orientation to minimize waste.
Much too hard to find the original paper: https://dl.acm.org/doi/epdf/10.1145/3592126
One question I have, is when we say "interlocking-free", does this mean that the algorithm can still densely stack cups (with a draft angle), or is it instead guaranteeing that the convex hull of shapes are non-interfering?
Thanks. I'll link it in the first line in the README. I think the interlocking-free part can pack cups like you suggest. They propose a flood fill algorithm which computes all the reachable places for the voxelized shape. It doesn't put assumptions on convexity. I think it would be a great example to try it out on though.
Interesting, this is the first time I've come across using a FFT for collision detection, and now that I think about it it really makes sense. Thanks for the insight!
I'm old enough to remember when 2D packing was considered a hard problem.
2d packing is still a hard problem