Dapper: Decompose-and-Pack for 3D Printing

Xuelin Chen1 , Hao(Richard) 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 at Chicago, 5Purdue University, 6Tel Aviv University
(SIGGRAPH Asia 2015)
Input

Figure 1: A 3D Inukshuk model decompose-and-packed (middle) for 3D printing. The fabricated pieces are assembled and glued together to form the final object (right).

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

Video:

 

Downloads:

BibTex:

@article{Chen:2015:DDP:2816795.2818087,
  author = {Chen, Xuelin and Zhang, Hao and Lin, Jinjie and Hu, Ruizhen and Lu, Lin and Huang, Qixing and Benes, Bedrich and Cohen-Or, Daniel and Chen,   Baoquan},
  title = {Dapper: Decompose-and-pack for 3D Printing},
  journal = {ACM Trans. Graph.},
  issue_date = {November 2015},
  volume = {34},
  number = {6},
  month = oct,
  year = {2015},
  issn = {0730-0301},
  pages = {213:1--213:12},
  articleno = {213},
  numpages = {12},
  url = {http://doi.acm.org/10.1145/2816795.2818087},
  doi = {10.1145/2816795.2818087},
  acmid = {2818087},
  publisher = {ACM},
  address = {New York, NY, USA},
  keywords = {3D printing, decompose-and-pack, pyramidal shape},
}