“Dapper: decompose-and-pack for 3D printing” by Chen, Zhang, Lin, Hu, Lu, et al. …
Conference:
Type(s):
Title:
- Dapper: decompose-and-pack for 3D printing
Session/Category Title: Fabrication
Presenter(s)/Author(s):
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.
References:
1. Aho, A. V., and Corasick, M. J. 1975. Efficient string matching: An aid to bibliographic search. Communications of the ACM 18, 6, 333–340.
2. Cagan, J., Shimada, K., and Yin, S. 2002. A survey of computational approaches to three-dimensional layout problems. Computer-Aided Design 34, 597–611.
3. Chen, Y., and Medioni, G. 1992. Object modelling by registration of multiple range images. Image Vision Comput. 10, 3, 145–155.
4. Crainic, T. G., Perboli, G., and Tadei, R. 2012. Recent Advances in Multi-Dimensional Packing Problems. New Technologies – Trends, Innovations and Research.
5. 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.
6. Gogate, A. S., and Pande, S. S. 2008. Intelligent layout planning for rapid prototyping. International Journal of Production Research 46, 20, 560–563.
7. Hildebrand, K., Bickel, B., and Alexa, M. 2013. Orthogonal slicing for additive manufacturing. Computer & Graphics 37, 6, 669–675.
8. Hoffman, D. D., and Richards, W. A. 1984. Parts of recognition. Cognition 18, 65–96.
9. 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.
10. Lowerre, B. T. 1976. The harpy speech recognition system. PhD thesis, Carnegie Mellon University.
11. 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.
12. Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539–1556.
13. 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.
14. Wikipedia, 2014. 3D printing — wikipedia, the free encyclopedia. {Online; accessed 6-November-2014}.
15. Zhou, Y., and Wang, R. 2012. An algorithm for creating geometric dissection puzzles. In Proc. of Bridges Conf., 49–58.
16. 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.
