7 ms·
Show HN: 3D Packing for 3D Printing
- throwaway2016a 9y agoThis looks really cool but I have a naive question... I've heard desktop printers are prone to failure. Like the print becoming detached from the plate. Would this increase the units / material you lose if there is an error? Or do the errors happen early enough in the print you can catch them before much damage is done.
- silasb 9y agoYou are referring to FDM printers. The OP is talking about SLS printers which don't have this issue.
- ortusdux 9y agoThis demo/ad? from Tested does a great job explaining how this printer works. It really is amazing for the price-point. https://www.youtube.com/watch?v=IrFYt3uUdrI https://www.youtube.com/watch?v=IrFYt3uUdrI
- throwaway2016a 9y agoThank you. As I said naive question. I don't know much about 3d printers.
- deleted 9y ago[deleted]
- daenz 9y agoLove the visualizations and the explanations Question: Is this more of an unbounded multi-dimensional knapsack problem? With bin packing, you have multiple bins and you're minimizing the bins used. With knapsack, you're maximizing the value (in this case, count) of the objects fit into the finite knapsack.
- fogleman 9y agoI guess it isn't exactly bin packing or knapsack. Usually knapsack doesn't deal with dimensions but just a cost/weight. Consider it a variant.
- obeid 9y agoI came here for the visuals and the visual explanation and OP delivered. Disclaimer: OP is a friend of mine.
- evanlivingston 9y agoWheres the print?
- yellowapple 9y agoThe printer in question hasn't been released yet, so I'm guessing there's no physical print yet.
- deleted 9y ago[deleted]
- ClassyJacket 9y agoIt's a ten thousand dollar printer and isn't out yet. The OP probably doesn't have access to one.
- delhanty 9y agoOr possibly OP has access via his employer Kitware? Kitware could be doing software consultancy for Formlabs. They already have expertise in 3D slicing [1][2][3], which is just what you need for 3D printing. This is pure uninformed speculation: Formlabs look like they have great hardware. On the other hand they could be under competitive pressure on the software front. Firstly there's Autodesk who launched Ember as an "Open" design [4] in roughly the same market as Formlabs Form 1/2. This is straight out of the Joel Spolysky playbook [5] "Smart companies try to commoditize their products’ complements." Autodesk's (MCAD) product is Inventor now transitioning to Fusion 360. 3D printing is the complement. That's why Ember's "electronics are shared under a Creative Commons Attribution-ShareAlike license, the same license under which we've shared Ember's resin and mechanical designs; the firmware is licensed under GNU GPL (see the source code itself for the full details)." [4]. You can bet that it will be a cold day in hell before Autodesk releases Inventor and/or Fusion 360's source code under any sort of FOSS license. Secondly, there's Stratasys that bought GrabCAD mainly to acquire there MCAD software team, several of whom are ex Solidworks / Siemens PLM (Unigraphics/Parasolid/D-Cubed). Expect in the next few years for slicing of STL to be replaced by slicing of native MCAD file formats. That's a step up in development effort and probably needs Modeling kernel (Parasolid, Acis ...). Thirdly, there's 3D Systemes who decided to compete with lawyers rather than software developers - but eventually that got settled [6]. Possibly strategies for Formlabs: Either, invest heavily in their software. That's wny they might contract Kitware. Maybe they license a modeling kernel. Or, get acquired by one of the other (not Autodesk) big three MCAD vendors: (1) Dassault, (2) Siemens PLM, (3) PTC. [1] https://www.kitware.com/platforms/#3d-slicer https://www.kitware.com/platforms/#3d-slicer [2] https://www.slicer.org https://www.slicer.org [3] https://github.com/Slicer/Slicer/ https://github.com/Slicer/Slicer/ [4] http://learn.ember.autodesk.com/blog/ember-open-source-electronics-and-firmware http://learn.ember.autodesk.com/blog/ember-open-source-elect... [5] https://www.joelonsoftware.com/2002/06/12/strategy-letter-v/ https://www.joelonsoftware.com/2002/06/12/strategy-letter-v/ [6] http://jolt.law.harvard.edu/digest/3d-systems-and-formlabs-settled-two-year-patent-dispute http://jolt.law.harvard.edu/digest/3d-systems-and-formlabs-s...
- 2dollars27cents 9y agoVery cool! This is a bit of a naive optimization, though. Thermal properties have to be considered when planning SLS builds. Very dense cross sections will result in long laser scan times, and the quality of those benchies will suffer significantly.
- fogleman 9y agoI had a feeling there might be physical limitations!
- worldburger 9y agoCould this be optimized for the SLA Form2? I.e. No flat sides oriented horizontal?
- fudged71 9y agoAlso there are constraints with regards to specific part orientations in the build chamber and angles of specific parts of a print
- fogleman 9y agoA couple performance optimizations I made that weren't covered in the article: - When I profiled my initial implementation of the annealing, I found that it was spending a lot of time just rotating bounding boxes to test for intersection. So I precompute all possible rotations of the BVHs (24 rotations) and then only need to deal with translation when checking for intersection - way faster: https://github.com/fogleman/pack3d/blob/master/pack3d/bvh.go#L54-L64 https://github.com/fogleman/pack3d/blob/master/pack3d/bvh.go... - Even more interesting, for the bin packing code, I used a recursive algorithm with memoization, like you do. But I realized an improvement can be made. Say you search for the optimal packing for a box sized 10x10x10 and the optimal packing comes back, say, 9x8x9. Now I do another query for a box sized, say, 9x9x9. I should just reuse the result for my 10x10x10 query because 9x9x9 falls between 9x8x9 and 10x10x10. Basically instead of requiring an exact match in the memoization, I want to query a range. I implemented this using a spatial hash and it made things WAY faster. https://github.com/fogleman/pack3d/blob/master/binpack/spatial.go https://github.com/fogleman/pack3d/blob/master/binpack/spati...
- StavrosK 9y ago> So I precompute all possible rotations of the BVHs (24 rotations) 24 times faster, or, as we say in algorithm analysis, no times faster!
- awirth 9y agoI read it as though the rotations were expensive, so they were memoized. In this case, it really could be much more than 24 times faster.
- vortico 9y ago>Note that pack3d runs until stopped, writing its output to disk whenever a new best is found. I wish more software operated like this. It makes it convenient because your concrete constraint is usually time, instead of number of iterations, which is an abstract value.
- fogleman 9y agoSomehow it seems less polished of a command line tool that way, but it was perfect for my needs. I actually ran it over night to pack a model of a deer, packing 8 of them together. It produced this histogram of scores: http://i.imgur.com/VENTeIa.png http://i.imgur.com/VENTeIa.png So it could easily find arrangements that scored around 65% while the best it found was like 52% (lower is better and basically anything under 100% is better than naive packing).
- fogleman 9y agoHere are the 8 deer by the way: http://i.imgur.com/RDwzbD8.png http://i.imgur.com/RDwzbD8.png
- deleted 9y ago[deleted]
- sitkack 9y agoI could see other heuristics for termination Delta improvement / delta time X minutes or y percentage Does it parallelize?
- fogleman 9y agoIn general, simulated annealing is hard to parallelize. But in this case we also tend to get stuck in local minima a lot, because they are very deep troughs in the search space. (Annealing does still perform much better than hill climbing though, so it's still worthwhile.) So we can run multiple annealings in parallel and pick the best result.
- andrenotgiant 9y agoGreat write-up on a really interesting topic! Last year I needed the same thing for packing 2-dimensional shapes on a piece of plywood (for CNC.) You would think it's fairly simple and common but I failed to find any FOSS tools. Any pointers for a good 2d shape-packing algorithm?
- fogleman 9y agoThanks! Have you seen this? http://svgnest.com/ http://svgnest.com/
- Kliment 9y agoI hacked a crude one together for generating build plates for FFF/FDM printers. https://github.com/kliment/simarrange https://github.com/kliment/simarrange
- mrec 9y ago> Any pointers for a good 2d shape-packing algorithm? Googling `open source texture packer` finds a few projects. Do the requirements change significantly when dealing with a physical sheet of plywood rather than pixels?
- andrenotgiant 9y agoI'm sure Shapeways [1] already optimizes the heck out of its own printing, but if not you should consult for them. They print using laser sintering and I'd imagine a 37% improvement in efficiency would be pretty nice for their bottom line. [1] https://www.shapeways.com https://www.shapeways.com
- fudged71 9y agoMy understanding is Shapeways uses an advanced/custom version of Netfabb for their 3D packing. Yes they have some insane optimizations/automation already, and I believe they also use human input for certain requirements/limitations
- slavik81 9y agoWhile packing problems are pretty cool in general, I'm afraid I don't understand why this is useful for 3D printing. Does this increase printer throughput?
- andrenotgiant 9y agoTo a certain extent, yes it increases printer throughput. With selective laser sintering there's a fixed overhead time required to remove the last print from the machine, clean up the workspace, and reset it. See: https://youtu.be/9E5MfBAV_tA?t=50 https://youtu.be/9E5MfBAV_tA?t=50
- syntaxing 9y agoCan anyone explain how the STL manipulation works? I never really understood how the program reads a STL file and how it processes the geometry. Is there something similar in Python as well?
- fogleman 9y agoAn STL file is literally just a list of triangles. Each triangle has three vertices, each vertex has X, Y, Z floating point coordinates.