Simple 3D Packing

[matroid]

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).

[jukea]

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? )

[avidiax]

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?

[matroid]

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.

[Koffiepoeder]

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!

[hermitcrab]

I'm old enough to remember when 2D packing was considered a hard problem.

[Jarmsy]

2d packing is still a hard problem