Dapper: Decompose-and-Pack for 3D Printing

ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2015)

Xuelin Chen1    Hao Zhang2    Jinjie Lin1    Ruizhen Hu3    Lin Lu1    Qixing Huang4    Bedrich Benes5    Daniel Cohen-Or6    Baoquan Chen1

1Shandong University    2Simon Fraser University    3SIAT    4Toyota Technological Institute    5Purdue University    6Tel Aviv University


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 powderand 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 packingand 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.

Fig 1: A 3D Inukshuk model (left) is decompose-and-packed (middle) for powder-based 3D printing. The fabricated pieces are assembled and glued together to form the final object (right). Figure 2: Decompose-and-pack polyonimoe shapes using pyramidal primitives (a) vs. box primitives (b). Both can pack perfectly without gap, but fewer pyramidal primitives are required.

Figure 8: A gallery of 2D results from DAP with the goal of height minimization. For each example, we show the input shape, the final decomposition, and the packing after local refinement. All results are obtained with the same default parameter setting except for the last row (a different setting α = 0:1 and η = 30 is used).
Figure 9: A gallery of 3D results from Dapper optimized for powder-based 3D printing (i.e., height minimization). For each example, we show (from left to right) the input shape, the final (virtual) decomposition and packing, and a photograph of the fabricated pieces. Part counts are shown in Table 1.

Figure 12: A few snapshots of powder-based 3D printing of pieces produced by Dapper, along with photos of assembled 3D objects from the 3D gallery after gluing the pieces.
Figure 14: DAP results optimized for powder-based vs. FDMbased 3D printing. For each example, we show the input shape, the final (virtual) decompositions and packings with respect to the two optimization objectives, as well as a photograph of the FDM fabrication result. Part counts, heights(cm) and total volume(cm3) of the vertical gaps are reported as well in vectors to show contrasts.


We thank all the reviewers for their insightful comments and valuable suggestions. We also acknowledge help from Sha He on video editing and early discussion with Ilya Baran on DAP. This work is supported in part by grants from National 973 Program (2015CB352500), NSFC (61232011, 61202147, 61332015), NSERC Canada (No. 611370), Guangdong Science and Technology Program (2015A030312015, 2014B050502009, 2014TX01X033), Shenzhen VisuCA Key Lab (CXB201104220029A), Israeli Science Foundation (No. 1790/12), and U.S.-Israel Bi-National Science Foundation (No. 2012376).

title = {Dapper: Decompose-and-Pack for 3D Printing},
author = {Xuelin Chen and Hao Zhang and Jinjie Lin and Ruizhen Hu and Lin Lu and Qixing Huang and Bedrich Benes and Daniel Cohen-Or and Baoquan Chen},
journal = {ACM Transactions on Graphics},
volume = {34},
number = {6},  

pages = {213:1-213:12}, 

year = {2015},

Downloads (faster for people in China)

Downloads (faster for people in other places)