Abstract
We pose the decompose-and-pack or DAP problem, which tightly combines shape decomposition and packing. While in general, DAP seeks to decompose an input shape into a small number of parts which can be efficiently packed, our focus is geared towards 3D printing. The goal is to optimally decompose-and-pack a 3D object into a printing volume to minimize support material, build time, and assembly cost. We present Dapper, a global optimization algorithm for the DAP problem which can be applied to both powder- and FDM-based 3D printing. The solution search is top-down and iterative. Starting with a coarse decomposition of the input shape into few initial parts, we progressively pack a pile in the printing volume, by iteratively docking parts, possibly while introducing cuts, onto the pile. Exploration of the search space is via a prioritized and bounded beam search, with breadth and depth pruning guided by local and global DAP objectives. A key feature of Dapper is that it works with pyramidal primitives, which are packing- and printing-friendly. Pyramidal shapes are also more general than boxes to reduce part counts, while still maintaining a suitable level of simplicity to facilitate DAP optimization. We demonstrate printing efficiency gains achieved by Dapper, compare to state-of-the-art alternatives, and show how fabrication criteria such as cut area and part size can be easily incorporated into our solution framework to produce more physically plausible fabrications.
- Aho, A. V., and Corasick, M. J. 1975. Efficient string matching: An aid to bibliographic search. Communications of the ACM 18, 6, 333--340. Google ScholarDigital Library
- Cagan, J., Shimada, K., and Yin, S. 2002. A survey of computational approaches to three-dimensional layout problems. Computer-Aided Design 34, 597--611.Google ScholarCross Ref
- Chen, Y., and Medioni, G. 1992. Object modelling by registration of multiple range images. Image Vision Comput. 10, 3, 145--155. Google ScholarDigital Library
- Crainic, T. G., Perboli, G., and Tadei, R. 2012. Recent Advances in Multi-Dimensional Packing Problems. New Technologies - Trends, Innovations and Research.Google Scholar
- Dickinson, J. K., and Knopf, G. K. 2002. Packing subsets of 3D parts for layered manufacturing. International Journal of Smart Engineering System Design 4, 3, 147--161.Google ScholarCross Ref
- Gogate, A. S., and Pande, S. S. 2008. Intelligent layout planning for rapid prototyping. International Journal of Production Research 46, 20, 560--563.Google ScholarCross Ref
- Hildebrand, K., Bickel, B., and Alexa, M. 2013. Orthogonal slicing for additive manufacturing. Computer & Graphics 37, 6, 669--675. Google ScholarDigital Library
- Hoffman, D. D., and Richards, W. A. 1984. Parts of recognition. Cognition 18, 65--96.Google ScholarCross Ref
- Hu, R., Li, H., Zhang, H., and Cohen-Or, D. 2014. Approximate pyramidal shape decomposition. ACM Trans. on Graph 33, 6, 213:1--213:12. Google ScholarDigital Library
- Lowerre, B. T. 1976. The harpy speech recognition system. PhD thesis, Carnegie Mellon University. Google ScholarDigital Library
- Luo, L., Baran, I., Rusinkiewicz, S., and Matusik, W. 2012. Chopper: Partitioning models into 3D-printable parts. ACM Trans. on Graph 31, 6, 129:1--129:9. Google ScholarDigital Library
- Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539--1556.Google ScholarCross Ref
- Vanek, J., Garcia, J., Benes, B., Mech, R., Carr, N., Stava, O., and Miller, G. 2014. PackMerger: A 3D print volume optimizer. Computer Graphics Forum 33, 6, 322--332.Google ScholarDigital Library
- Wikipedia, 2014. 3D printing --- wikipedia, the free encyclopedia. {Online; accessed 6-November-2014}.Google Scholar
- Zhou, Y., and Wang, R. 2012. An algorithm for creating geometric dissection puzzles. In Proc. of Bridges Conf., 49--58.Google Scholar
- Zhou, Y., Sueda, S., Matusik, W., and Shamir, A. 2014. Boxelization: Folding 3D objects into boxes. ACM Trans. on Graph 33, 4, 71:1--71:8. Google ScholarDigital Library
Index Terms
- Dapper: decompose-and-pack for 3D printing
Recommendations
Fundamental characteristics of printed gelatin utilizing micro 3D printer
Gelatin is useful for biofabrication, because it can be used for cell scaffolds and it has unique properties. Therefore, we attempted to fabricate biodevices of gelatin utilizing micro 3D printer which is able to print with high precision. However, it ...
3D printed PEGDA microstructures for gelatin scaffold integration and neuron differentiation
Three dimensional (3D) printing techniques can be used for scaffold fabrication but the most of them are limited by resolution and material choice. To bypass these limitations, we developed an approach by combining conventional 3D printing and freeze-...
LuBan: Low-Cost and In-Situ Droplet Micro-Sensing for Inkjet 3D Printing Quality Assurance
SenSys '17: Proceedings of the 15th ACM Conference on Embedded Network Sensor SystemsInkjet 3D printing is a disruptive manufacturing technology in emerging metal- and bio-printing applications. The nozzle of the printer deposits tiny liquid droplets, which are subsequently solidified on a target location. Due to the elegant concept of ...
Comments