3 ms·

Show HN: 3D Binpacking Algorithm Visualized

115 points by m3m3tic 3y ago

mrjasonh 3y ago
Looks like an implementation of: https://github.com/davidmchapman/3DContainerPacking https://github.com/davidmchapman/3DContainerPacking
- hojjat12000 3y ago
  From this repository: A 3D bin packing algorithm originally ported from https://github.com/keremdemirer/3dbinpackingjs https://github.com/keremdemirer/3dbinpackingjs, which itself was a JavaScript port of https://github.com/wknechtel/3d-bin-pack/ 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.
hamhock666 3y ago
On my phone, there seems to be a float issue where the boxes are too close together and they draw out of order.
- m3m3tic 3y ago
  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-problem/11553 https://discourse.threejs.org/t/threejs-and-the-transparent-...
jakelazaroff 3y ago
Slick demo but where is the algorithm visualized? Am I missing some way to see what's going on "under the hood"?
blobbers 3y ago
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!
- IE6 3y ago
  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).
zimpenfish 3y ago
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_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.
- matsemann 3y ago
  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.
hexo 3y ago
View rotation is laggy, doesnt really correspond to cursor movement and doesnt stop when cursor stops, it slows down for a second or so.
- matsemann 3y ago
  To me it feels smooth that way, I think it's intentional.
javiramos 3y ago
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/ https://inkbit3d.com/packing/
- latchkey 3y ago
  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?
- NoobPretender 3y ago
  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
danielvaughn 3y ago
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.
- dietr1ch 3y ago
  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
deleted 3y ago
[deleted]

115 points by m3m3tic 3y ago

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

hojjat12000 3y ago
From this repository: A 3D bin packing algorithm originally ported from https://github.com/keremdemirer/3dbinpackingjs https://github.com/keremdemirer/3dbinpackingjs, which itself was a JavaScript port of https://github.com/wknechtel/3d-bin-pack/ 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.

hamhock666 3y ago

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

m3m3tic 3y ago
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-problem/11553 https://discourse.threejs.org/t/threejs-and-the-transparent-...

jakelazaroff 3y ago

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

blobbers 3y ago

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!

IE6 3y ago
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).

zimpenfish 3y ago

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

matsemann 3y ago
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.

hexo 3y ago

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

matsemann 3y ago
To me it feels smooth that way, I think it's intentional.

javiramos 3y ago

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/ https://inkbit3d.com/packing/

latchkey 3y ago
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?
NoobPretender 3y ago
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

danielvaughn 3y ago

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.

dietr1ch 3y ago
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

deleted 3y ago

[deleted]