![](https://csdnimg.cn/release/download_crawler_static/18574044/bg3.jpg)
3D Packing. In engineering and manufacturing domains, some
methods pack 3D parts for efficient layered fabrication [Dickinson
and Knopf 2002] and rapid prototyping [Gogate and Pande 2008].
The general packing problem has many variants in many appli-
cation settings, including packing/loading, scheduling, and rout-
ing [Crainic et al. 2012]. Most instances of the packing problem
are NP-hard, hence heuristic-driven exhaustive or stochastic search
including branch-and-bound, simulated annealing, and genetic al-
gorithms are frequently adopted [Cagan et al. 2002].
The key difference between Dapper and these previous works is
that in our problem, the shapes to be packed are not given a priori;
they are the result of a simultaneous shape decomposition and are
modified on-the-fly. The coupling not only changes the nature of
the problem but also increases the search space significantly.
Decomposition for 3D printing. The problem of decomposing
3D objects into solid parts for efficient fabrication has drawn inter-
ests from graphics researchers recently. Perhaps the first attempt
was made by Luo et al. [2012], where they develop a tool to parti-
tion a 3D model so that each part can fit in the printing volume. Fac-
tors including low part count, assemblability, and aesthetics of the
cuts are taken into consideration, but the method is oblivious to sup-
port material or build time. The work by Hildebrand et al. [2013] is
motivated by the direction bias of additive manufacturing. It poses
the interesting problem of decomposing a 3D shape into few pieces
so that each piece can be consistently sliced with small geometric
error along one of three orthogonal slicing directions. Recent work
by Hu et al. [2014] decomposes a 3D object into a small number
of approximately pyramidal parts so that each can be printed by an
FDM printer with low cost in time and material.
Dapper also computes solid decompositions in 3D and seeks low
part counts. However, we add packing, a new dimension, to the
decompose-to-print problem. Smart packing strategies allow print-
ing multiple parts at a time, leading to better utilization of the print
volume while incurring small time and material cost.
Boxelization. Recent work by Zhou et al. [2014] “boxelizes” a
3D shape by voxelizing it, computing a tree linkage structure over
the voxels, and folding the linkage structure into a box. There is
slight resemblance between boxelization and Dapper: voxelization
and unlinking of voxels can be seen as a special form of decompo-
sition; folding into a box is a special form of packing. The resem-
blance would stop there though as the two problems have different
goals and operate on completely different primitives (linked voxels
vs. discrete set of polycubes) and constraints.
Discrete scissor congruence. More closely related to DAP is
the intriguing Scissoring Congruence problem, which disects two
shapes into identical sets of segments. Note that this problem is
identical to DAP if its target container has the same area/volume as
the input shape. Zhou and Wang [2012] discretize the problem on
a grid and solve Discrete Scissoring Congruence (DSC) by recur-
sive co-disection of the two input shapes. Our DAP problem has a
different goal: it decompose-and-packs an input shape into an open-
ended volume as tightly as possible while minimizing part count. In
contrast, DSC works with a fixed target container and seeks exact
congruence without setting an objective to minimize the number of
segments. Both problems require difficult global optimization. To
counter local minima, the DSC solution applies random exploration
of hundreds of pairs of initial seeds for the co-disection.
PackMerger. PackMerger [Vanek et al. 2014] appears to be the
first work which considers improving a decomposition for better
packing. The method first converts an input 3D object into shells,
while Dapper works with solid decomposition. Moreover, Pack-
Merger works with terahedralized input and imposes additional re-
strictions on the input object, possibly leading to uneven gluing
boundaries. Dapper, on the other hand, only makes planar cuts.
Algorithmically, while Dapper follows a top-down search, Pack-
Merger is bottom-up. In PackMerger, the initial set of segments is
obtained with packing in mind, e.g., larger cut areas are preferred.
However, the consideration of packing is only implicit, the decom-
position is not coupled with any packing process. After the initial
decomposition, PackMerger executes a merge-and-pack step which
again decouples the two tasks; it corresponds to a “merge-and-then-
pack” process. Specifically, this step randomly explores mergings
between segments, and for each merging, recomputes a tight pack-
ing with a fixed set of segments. The search merely amounts to
a random sampling of packing solutions. The final solution is se-
lected as the merging configuration leading to the best packing.
In our work, we adhere to the true spirit of DAP, emphasizing the
strong coupling, rather than interleaving the solution by solving a
decomposition and then a packing, independently.
The main potential advantage of PackMerger over our algorithm is
that it searches over arbitrary rotations of the shape pieces during
packing. Dapper could allow this as well. However, the coupling
of decompose and pack significantly increases the search space
over any decoupled approach, making a refined discretization of the
space of rotations prohibitive. As the experimental comparison re-
sults would later reveal, the quality and computational advantages
afforded by Dapper with only axial rotations appear to outweight
any gains offered by PackMerger with the consideration of arbi-
trary rotations. Indeed, the difference is mainly in the optimization
or search strategy, not the discretization of search spaces.
3 Decompose-and-pack pyramidal shapes
Our goal is to optimally decompose-and-pack a 3D input object into
a container, the printing volume, for efficient fabrication. The input
to the Dapper algorithm is a solid 3D object, along with a target
container which is a rectangular cuboid. In our coverage, to ease
understanding of the algorithm, we mainly illustrate it in 2D. We
assume that the container has sufficient height to admit a packing
of all the decomposed parts. However, the horizontal dimensions of
the container are limiting, so that the input shape cannot fit inside
without being cut into smaller pieces. The challenge is to efficiently
pack the input using a small number of pieces.
3.1 Overview
Dapper starts with an initial partitioning of the input shape into few
pyramidal parts. The parts are voxelized into pyramidal polycubes.
Dapper then applies a global DAP optimization over the polycubes.
After packing the polycubes into the container, the positions of the
enclosed shape parts are locally refined to obtain a lower and tighter
packing. Figure 3 outlines the major steps of Dapper.
In the global optimization phase (Section 4.1), we decompose and
pack pyramidal polycubes. We pictorially regard the container as a
pile of packed polycubes. Each pile corresponds to a partial DAP
solution and a complete solution is reached when all polycubes are
packed. Our solution search is top-down and iterative. At each iter-
ation, we generate a set of candidate moves, each of which involves
packing a part onto the pile, possibly after a part decomposition.
Iterative selection of candidate moves advances the DAP solution
and forms a search tree. Expansion and pruning of the search tree
are based on a priority score we define for each candidate move and
a global objective function we define for each DAP solution.
Dapper: Decompose-and-Pack for 3D Printing • 213:3
ACM Transactions on Graphics, Vol. 34, No. 6, Article 213, Publication Date: November 2015