Show HN: 3D Binpacking Algorithm Visualized | Hacker News Reader

Show HN: 3D Binpacking Algorithm Visualized

skusavvy.com

115 pointsm3m3tic16 comments

My company recently published a new 3D binpacking algorithm based on a spectral approach which is faster and produces denser packs. It is targeted for 3D printing where parts need to be packed within the build volume of the printer.

You can find out more about it here (including a technical paper): https://inkbit3d.com/packing/

This is really neat. I see you use a single GPU in the paper. Would it be possible to parallelize this across many GPUs to increase the speed?

Thanks for sharing the paper! <3 I've been meaning to implement something like this for organizing my tools in boxes and obviously I will choose the overkill solution for sorting screwdrivers and power tools

Slick demo but where is the algorithm visualized? Am I missing some way to see what's going on "under the hood"?

I once had to work on code to do this[2] (place had different sized boxes for shipping, they wanted them used efficiently) which had its own extra constraints (certain items had to be on top, in specific rotations; etc.) but that was based on [1]. Maybe it would have been easier using the EB-AFIT algorithm.

[1] Optimizing Three-Dimensional Bin Packing Through Simulation, https://www.researchgate.net/publication/228974015_Optimizin...

[2] It was not a fun time because there was no pipeline from the product database to this service which meant it was frequently out of date re: dimensions, weight, packing position requirements, etc. which drove the warehouse packers mad but after three months of my asking for, if nothing else, a daily CSV download being rebuffed, I quit.

Worked on something similar, with similar constraints as to products not being able to be placed freely, for instance something heavy could crush something brittle. Also, dimension data is forever a problem. Additionally, that data doesn't reflect reality even when it's fairly accurate, since things are seldom perfect cuboids. So assuming that leaves lot of unused room in reality = not optimal. For instance something in a similar packaging to a bag of ships or dog food, is thinner in the ends than in the middle, and possibly malleable in shape.

Also a real life constraint is that it has to be possible to actually pack. Expecting a packer to follow complicated instructions to a T for it to work, or else it wont fit, will never work. Additionally, things can arrive in a certain order, which needs to be accounted for if packing should happen before all items are ready.

I think it's a cool problem to work on. So much to think about outside just the algorithmic perfect world scenario.

Looks like an implementation of: https://github.com/davidmchapman/3DContainerPacking

From this repository:

A 3D bin packing algorithm originally ported from https://github.com/keremdemirer/3dbinpackingjs, which itself was a JavaScript port of https://github.com/wknechtel/3d-bin-pack/, which is a C reconstruction of a novel algorithm developed in a U.S. Air Force master's thesis by Erhan Baltacioglu in 2001.

I've had this startup idea rolling around in my head for a while. Basically a self-storage business but instead of individual units, customers drop off their items and they're all stored together in a backend warehouse that optimizes for space.

But I don't know anything about this particular set of algorithm problems; this is a neat resource.

You'd need to have a set of standard boxes and maybe also tiers of retrieval latency. I don't know if it'll compete with something further away were there's no complications on retrieving your stuff. It'd need to be really cheap

View rotation is laggy, doesnt really correspond to cursor movement and doesnt stop when cursor stops, it slows down for a second or so.

To me it feels smooth that way, I think it's intentional.

Seems like there's a bug in the implementation, mine has some boxes floating on top of each other with big gaps.

Neat idea though!

Yeah if you give it the dimensions of a standard gaylord (48x40) it tries to stack the boxes in a really strange way with smaller boxes occupying the space below larger boxes and causing some boxes to float. I wonder if additional metadata is needed such as (1) box weight (2) resistance to being crushed and (3) priority (not sure if this is relevant when shipping but it will decide which boxes don't "fit" on its own).

On my phone, there seems to be a float issue where the boxes are too close together and they draw out of order.

yeah the issue is on desktop too, I battled with it for awhile but ultimately gave up, it seems to be a notoriously difficult problem to solve with ThreeJS

https://discourse.threejs.org/t/threejs-and-the-transparent-...

Reply on news.ycombinator.com