Simple 3D Packing | Not Hacker News!

Discussion (1 comments)

Showing 10 comments

9 days ago

1 reply

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

9 days ago

3 replies

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

phil-martin

9 days ago

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.

RaftPeople

9 days ago

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

jordanarseno

3d ago

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.

avidiax

3d ago

1 reply

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

3d ago

Thanks. I'll link it in the first line in the README.

hermitcrab

3d ago

1 reply

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

Jarmsy

3d ago

2d packing is still a hard problem

Koffiepoeder

3d ago

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!

Resources