Towards Zero-Waste Furniture Design

Bongjin Koo∗ Jean Hergel∗ Sylvain Lefebvre Niloy J. Mitra

University College London INRIA Nancy INRIA Nancy University College London
arXiv:1604.00047v1 [[Link]] 31 Mar 2016

(a) input design (b) final design (c) fabricated design

Figure 1: We introduce waste-minimizing furniture design to dynamically analyze an input design (a) based on its 2D material usage (see
inset) and design specifications to assist the user through (b) multiple design suggestions to reduce material wastage (see inset). The final
user design can directly be exported for laser cutting and be assembled (c). In this case, wastage was reduced from 22% to 11%.

Abstract zero-waste furniture in an effort to reduce material wastage. A no-

table example being Maynard’s ‘Zero-waste Table.’ Computational
In traditional design, shapes are first conceived, and then fabricated. support for designing such waste-reducing furniture, however, is
While this decoupling simplifies the design process, it can result in largely lacking.
inefficient material usage, especially where off-cut pieces are hard
to reuse. The designer, in absence of explicit feedback on material Material considerations are typically appraised only after a shape
usage remains helpless to effectively adapt the design – even though has been designed. While this simplifies designing, it leads to un-
design variabilities exist. We investigate waste minimizing furniture necessary wastage: at design time, the user can at best guess to ac-
design wherein based on the current design, the user is presented count for how the shape will be physically realized, and can easily
with design variations that result in more effective usage of materi- fail to effectively adjust the design to improve material utilization.
als. Technically, we dynamically analyze material space layout to
determine which parts to change and how, while maintaining orig- In recent years, algorithms have been developed to economically
inal design intent specified in the form of design constraints. We 3D print given designs. For example, approaches have been pro-
evaluate the approach on simple and complex furniture design sce- posed to cleverly breakup a given shape into parts that better pack
narios, and demonstrate effective material usage that is difficult, if together in print volumes [Luo et al. 2012; Vanek et al. 2014; Chen
not impossible, to achieve without computational support. et al. 2015; Yao et al. 2015], adaptively hollow shape interiors to
save print materials [Stava et al. 2012; Prévost et al. 2013; Wang
et al. 2013; Dumas et al. 2014], explore parameter space variations
Keywords: computational design, fabrication, material usage, for manufacturable forms [Shugrina et al. 2015], or design con-
guided design nector geometry to remove the need for any secondary connector
parts [Fu et al. 2015]. However, improving material utilization by
1 Introduction explicitly allowing design changes has been less studied.

Furniture design is an exercise in form-finding wherein the designer In this work, we introduce the problem of waste-minimizing furni-
arrives at a final form by balancing aesthetics, object function, and ture design, and investigate it in the context of flatpack furniture
cost. Typically, design variations are manually explored by a mix- design (cf., [Brennan et al. 2006]) using laser cut wooden parts.
ture of guesswork, prior experience, and domain knowledge. With- Specifically, we study the interplay between furniture design ex-
out appropriate computational support, such an exploration is often ploration and cost-effective material usage. By directly coupling
tedious, time consuming, and can result in wasteful choices. the two, we empower the users to make more informed design de-
cisions. Note that this is fundamentally different from locking a
In furniture manufacturing, both for mass production and for cus- designed shape, and then trying to best fabricate it.
tomized designs, material wastage plays a deterrent role. This not
only leads to increased production cost (typically 5-15% wastage For example, in Figure 1, the user starts with an initial concept in-
due to off-cuts), but also hampers ongoing efforts towards green dicating design constraints (e.g., symmetry, desired height, etc.).
manufacturing [Daian and Ozarska 2009]. For an extensive report, Our system analyzes material usage by computing a dynamic 2D
please refer to the guideline from the British Furniture Manufac- layout of the parts and proposes design modifications to improve
turer [BFM 2003]. Hence, there has been a growing interest in material usage without violating specified design constraints (i.e.,
design intent). Note that such adaptations are often in the form of
∗ Joint first authors synchronous movement of multiple parts affected by both design
and material layout considerations, which are difficult to mentally Saakes et al. [2013] proposed an interactive system to allow the
imagine. The user can select any of the suggestions, either in its en- user to interactively layout parts for more personalized usage. Such
tirety or in part. She can further update the set of design constraints methods, however, do not explicitly modify the original designs in
by locking parts of the current design, and the process continues. order to improve material usage.
Thus, the user scopes out a design space via constraints, and our
algorithm refines the design to reduce material wastage while re- Fabrication-aware design. Recently, the growing popularity of
stricting changes to the indicated design space. personalized fabrication has motivated researchers to develop al-
gorithms to adapt existing shapes to make them better suited for
Technically, we achieve the above by using the current material lay-
physical construction. Examples include abstracting shapes as a
out to dynamically discover a set of relevant layout constraints. The
collection of slices to be laser cut [McCrae et al. 2011; Hildebrand
algorithm has a discrete aspect involving which part to change based
et al. 2012; Schwartzburg and Pauly 2013; Cignoni et al. 2014], as
on the current 2D layout, and a continuous aspect involving how to
foldable popups [Li et al. 2010; Li et al. 2011], developing toolkit to
adapt the part attributes based on the current material space layout
allow user to draft directly using a handheld laser pointer to control
without violating user-specified design constraints. Even for a fixed
high-powered laser cutters [Mueller et al. 2012], computationally
design, exploring the space of all possible packing is a combinato-
designing gear trains to support part movement for converting ani-
rial NP-hard problem. Instead, we locally analyze a set of candidate
mated characters to working physical automata [Coros et al. 2013],
packings to determine which parts to modify and how to change
introducing necessary joint geometry to create non-assembly artic-
them to optimize material utilization. We demonstrate that by dy-
ulated objects [Bächer et al. 2012; Calì et al. 2012], or supporting
namically analyzing a set of current packings, we can efficiently
an example-driven fabrication paradigm [Schulz et al. 2014]. To
and effectively couple the 2D layouts and the constrained 3D de-
simplify fabrication, Fu et al. [2015] suggest a method to gener-
signs. The user is then presented with different waste-reducing de-
ate a globally-interlocking furniture assembly that enables easy dis-
sign variations.
assembly/reassembly of furniture, without using glue, screws, etc.
We evaluated the system to create a variety of simple and complex Such methods, however, are chiefly used to adapt existing shapes
designs, and fabricated a selection of them. We also performed a after they have been designed, rather than to guide the user to re-
user study with both designers and novices to evaluate the effec- fine the designs to reduce material-wastage.
tiveness of the system. The performance benefits were particularly
obvious in case of complex designs involving different design con- Guided design. In the context of exploratory design, Xu et
straints. In summary, we: al. [2012] proposed a fit-and-diverse framework to allow users to
interactively guide model synthesis and exploration, while Talton et
• introduce the problem of material waste minimizing furniture al. [2009] exposed a parameterized shape space for model creation.
design; and These efforts, however, focus on aspects of digital content creation
• propose an algorithm that dynamically analyzes 2D material without fabrication and material considerations. Recently, Shug-
usage to suggest design modifications to improve material us- rina et al. [2015] developed a system that allows novices to easily
age without violating user-specified constraints. customize parametric models while maintaining 3D-printability of
the models. In a work closely related to our motivation, Umetani et
al. [2012] use stability and durability of materials to propose design
2 Related Work modifications, thus computationally guiding the users. With a sim-
ilar motivation, we investigate the impact of material usage in the
Material considerations. Physical materials play an important role context of guided design. We are unaware of prior attempts investi-
in 3D printing an object. Various approaches have been developed gating how material usage can be analyzed to refine the designs.
to economically and efficiently produce a designed object. For ex-
ample, adaptively hollowing out interiors and adding struts to create Constraint-based modeling. In the CAD community, constrained-
durable yet cost-effective 3D printouts [Stava et al. 2012], cleverly based modeling (cf., [Brüderlin and Roller 1998]) has long been
hollowing the shape interiors in conjunction with shape deforma- demonstrated as a powerful parametric way to design shapes and in-
tion to ensure stability of the final shape [Prévost et al. 2013], or teract with them. In the case of existing models, an inverse analyze-
perform FEM analysis to decide wall thickness and parameters to and-edit paradigm has been recently proposed to first discover the
ensure model endurance under known or unknown forces [Zhou constraints present in shapes, and then allow interactive editing [Gal
et al. 2013; Lu et al. 2014]. Techniques for designing scaffolds, et al. 2009; Xu et al. 2009; Zheng et al. 2011]. Such approaches dif-
both interior [Wang et al. 2013] and exterior [Dumas et al. 2014], fer on how model parts are abstracted (e.g., feature curves, model
have been developed for cost-effective 3D printing by reducing parts, or abstracted segments as primitives) and how the inter-part
wastage. Hu et al. [2015] propose to optimize the shape of a 3D constraints are conformed to. However, these methods have primar-
model to reduce support structures used during 3D printing. Al- ily focused on designing shapes for the virtual world where material
ternatively, methods have been developed to decompose and pack and fabrication constraints are irrelevant, and hence ignored.
3D models for reducing assembly cost, support material, printing
time or making big objects printable on small 3D printers [Luo
et al. 2012; Vanek et al. 2014; Yao et al. 2015]. Dapper [Chen 3 Design Workflow
et al. 2015] also employs a decompose-and-pack approach for min-
imum assembly cost, support material and build time when using Our goal is to propose design variations that minimize material
3D printers. It breaks 3D objects into pyramidal primitives, then wastage without violating original design intent. In this section,
finds good packing configurations to achieve the goal. we present the proposed system as experienced by the user, and de-
scribe the main algorithmic details in the subsequent sections. Here
In the context of laser cut fabrication, Hildebrand et al. [2012] we particularly focus on how the user encodes her design intent.
and Schwartzburg and Pauly [2013] explore how to rationalize a
given design for fabrication out of planar sheets. Further, material The user starts by choosing the desired material (i.e., thickness
wastage has been investigated by testing various packing strategies of wooden planks) and the number and dimensions of the mas-
from computational geometry community (cf., [Jylänki 2010]) to ter board(s). Our system considers rectangular master boards —
efficiently layout the parts in the material space. More recently, in practice these can represent new boards or left over rectangular
spaces in already used boards. The user starts by loading an initial it makes better utilization of material in the resultant design layout.
part-based 3D object design, either created in a modeling system or Note that this is the inverse of the design rationalization problem,
as a parameteric model. The parts can be rectangular or have curves i.e., instead of taking a design as fixed and best fabricating it, we
boundaries. The user also indicates a set of design constraints. In adapt the design so that the resultant rationalization makes better
our implementation, we support: equal length (e.g., li = lj ), sum utilization of available material. First, we introduce some notations.
of lengths (e.g., li + lj + · · · = lk + . . . ), fixed length (e.g., li = c),
equal position, symmetric parts, ground touching, and coplanarity 4.1 Parameterized designs
among indicated planks. The user can additionally specify that the
object should fit an indicated volume (e.g., in between two walls) The design is considered as a function D(X) that produces the ge-
and the internal space in the form of inner volume indicating mini- ometry of a fixed number of parts, given a configuration vector X.
mal shelf dimensions. The parts can be assembled into a final furniture design.
We make no assumption as to how D is implemented – we demon-
S2 M7 strate in Section 6 applications using both constrained based furni-
M6 ture design and parametric designs modeled by CSG. We however
expect a continuous behavior from D(X), i.e., small changes in X
M1 M5 result in small changes in the part shapes. Parametric modelers gen-
M2 erally offer such continuity to smoothly navigate the space shape.
During wastage optimization our algorithm will change the value of
M4
X so as to explore whether changes in part shapes reduce wastage.
M3
Since we focus on laser cut furniture construction, we assume the
S1 parts to have the same thickness τ . The parts are thus represented
as planar polygonal contours extruded orthogonally.
Figure 2: Our algorithm discovers design variations in shape The geometry of a part pi lies within a bounding box which we
space. The user starts from a design M1 along with indicated represent by a six dimensional vector encoding the box center pi
design constraints, and the algorithm seeks for wastage minimiz- and the lengths of its three sides lix , liy , τ – the Z axis being aligned
ing variations by interleaving between topologically different ma- with part thickness by convention.
terial layouts (indicated by changes in curved paths) or continuous
changes to the layouts (indicated by same colored curves). For ex-
4.2 Material space
ample, paths (Mi , Mj ) denote continuous design changes, while
points Mi denotes designs where new layouts are explored (i.e.,
branch points). The user can switch to another shape space by Since we focus on laser cut furniture, any 3D design given by a
picking an updated set of design constraints (shape M5 here). Note configuration vector X is realized as a layout (i.e., cutting plan) in
that by construction M5 belongs to both shape spaces S1 and S2 . the material space. Material space is characterized by the largest
See Algorithm 1. master board that the machine can possibly cut, a rectangle of size
W × H. In this space, each part i is associated with a position
(ui , vi ) and an orientation oi ∈ {0, π/2, π, −π/2}.
The algorithm suggests multiple design variations that all satisfy
the design specifications but achieve different material usages. We We use wi , hi as extent of a part bounding box in the material space
measure material usage based on the fraction of the master board(s) along the x- and y-axis, respectively. The part box lengths in mate-
utilized. The top suggestions are presented as thumbnails. If the rial space are given by the two plank dimensions other than thick-
user mouse-overs any thumbnail, the system animates the pro- ness. For a plank i, of orientation oi , we get one of the two cases:
posed design modifications. The user can preview the object- and
material-space views, and select her preferred design suggestion. oi = 0, oi = π ⇒ wi = lix hi = liy
Note that each thumbnail effectively represents a design exploration oi = −π/2, oi = π/2 ⇒ wi = liy hi = lix
path pursued by the algorithm. We provide a slider to move along
this path, which is particularly useful for making incremental up- The material space positions and orientations are variables in the
dates to the design (see Figure 2 and Section 4). layout optimization algorithm, alongside the design parameters X
The user either selects a suggested design variation, or picks part (see Section 5).
configurations from a suggested shape as additional design con- When wastage is not a concern and a design easily fits within ma-
straints (e.g., user can lock the proposed sizes of certain planks). terial space, the variables (ui , vi , oi ) are independent of the design,
Thus, effectively the user appends or updates the current set of spec- i.e., they simply adapt to changes in part sizes. However, as we seek
ified design. Note that the new constraints are trivially satisfied by to maximize utilization of the material space, the material space
the current design, which is critical for subsequent design space variables become tightly coupled with the design parameters. Our
exploration (e.g., M5 is in both shape spaces S1 and S2 ). layout optimizer therefore jointly optimizes for material space vari-
Once satisfied with a design, she requests for the cutting patterns. ables and design parameters to minimize wastage (see Section 5)
She can investigate the design, the material space usage and the We next discuss what makes a desirable layout from the point of
cutting patterns, and send the patterns directly for laser cutting. view of furniture fabrication.

4 Overview 4.3 Properties of a good design layout

Our goal is to analyze aspects arising from material considera- Rectangular master boards can be sourced in a large choice of sizes
tions, and investigate how design changes affect such considera- and thicknesses from resellers. Therefore, our goal is to achieve a
tions. Specifically, we ask how to adapt a furniture design so that full utilization of rectangular spaces, so that the user can use boards
 Figure 3: Evolution of shape variation across a run of our algorithm on the coffee-table (top) and low-chair (bottom) models.

of exactly the right size and minimize wastage. The machine di- a fixed set of design parts. The second factor is the set of parts itself,
mensions determine the maximum extent of a single board. which can be changed through the design parameters X.
We measure wastage as the fraction of the space not utilized by the In our approach we pack the parts using a deterministic docking al-
design in its material space bounding rectangle. Ideally, we want to gorithm that always produces the same result for a same ordering of
achieve full utilization, i.e., null wastage. the design parts. Therefore, a first optimization variable is the order
in which the parts are sent to the docking algorithm. The second
An ideal packing is one that tightly packs all the parts to per- optimization variable is the vector of design parameters X. These
fectly fill up one or more rectangular master boards (like a puzzle). two variables have different natures: finding an ordering is a com-
Our system helps the user achieve this by automatically exploring binatorial problem while the design parameters can be continuously
changes improving material space usage (see Figure 4). explored.

We therefore proceed in two main steps, first determining a set of

good orderings that then serve as starting points for continuously
evolving the design, reducing wastage. The overall approach is de-
scribed in Algorithm 1. The subroutine I MPROVE D ESIGN is de-
scribed in Section 5.1 while E XPLORE O RDERINGS is described in
Section 5.2. The process restarts for a number of iterations (we use
G = 3) to jump out of local minima reached by the continuous
design exploration. This results in the shape space exploration il-
lustrated in Figure 2. The process returns the K best found layouts
and designs and presents them to the user in thumbnails. She can
then select her favorite design, and if desired update the constraints
bad layout mediocre layout good layout and restart the exploration from this point — which simply calls
M IN WASTAGE again.
Figure 4: Examples of stages of layout refinement, from bad to
mediocre to good. A good layout is characterized by less area of Bitmaps. During optimization we regularly call the parameterized
material wasted (shown in green). design function D(X) to obtain a new set of parts after changing
parameters. The layout optimization represents parts internally as
bitmaps: each part contour is rasterized at a resolution τ , typically
5 Design Layout Optimization 0.5 mm per pixel. This enables fast manipulation of the parts within
the layout. Each part thus becomes a bitmap having either 1 (inside)
The wastage of a layout depends essentially on two factors. The or 0 (outside) in each pixel. The size of the bitmap matches the
first factor is the quality of the packing that can be achieved, given part extents in material space wi and hi . Every time the design is
refreshed a new set of bitmaps is computed for the parts. The master
board is similarly discretized into a regular grid of resolution τ .

Algorithm 1: M IN WASTAGE
Input: Design function D, starting design parameters Xs
Algorithm 2: I MPROVE D ESIGN
Output: Set of best layouts found L
1 Os ← identity ordering ; // 1,2,3,... Input: Starting design parameters X and ordering O
2 X ← {(Xs , Os )}; Output: Modified design parameters Xb with reduced wastage
3 for G iterations do 1 L ← D OCKING(D(X),O);
4 foreach (X, O) ∈ X do 2 Xb ← X, Lb ← L ;
5 O ← E XPLORE O RDERINGS (X, O); 3 Xc ← X, Lc ← L ;
6 foreach O ∈ O do 4 for N iterations do
7 X ← X ∪ {(I MPROVE D ESIGN(X, O),O)}; 5 Xb , Lb ←G ROW PARTS(Xb , Lb ,Xc , Lc , O);
6 Xc ←S HRINK PARTS(Xb , Lb );
8 X ← K EEP B ESTS(K,X ); 7 Lc ← S LIDE(Lb ,D(Xc ));
9 L ← ∅; // Check for improvement over current.
10 foreach (X, O) ∈ X do 8 if W (Lc ) < W (Lb ) then
11 L ← L∪ D OCKING(D(X),O); 9 Xb = Xc , Lb = Lc ;
12 return (L); 10 return (Xb );
5.1 Design optimization for wastage minimization Algorithm 3: SLIDE
Input: current layout C = (u0 , v0 , ...) and set of changed parts
The design optimization improves the design parameters X to min-
parts
imize wastage in the layout, keeping the docking ordering fixed. It
Output: updated layout L
appears as the subroutine I MPROVE D ESIGN in Algorithm 1. The
1 L←∅
pseudo-code for this step is given in Algorithm 2. Our objective is
2 foreach part pi ∈ parts in docking order do
to suggest design changes that reduce wastage, progressively im-
3 for N iterations do
proving the initial layout. The algorithm performs a guided local
4 ∆x ← −smallestLef tF reeInterval(L, pi );
search by changing the parts – through the design parameters – to
5 if ∆x = ∅ then
reduce wastage.
6 ∆x ← smallestRightDecollision(L, pi );
Prior to considering which parts to modify, we have to answer two 7 posx ← (ui + ∆x , vi ) ;
questions: First, how to drive the design parameters X to change 8 ∆y ← −smallestBottomF reeInterval(L, pi ) ;
only a given part (Section 5.1.1). This is achieved by relying on the 9 if ∆y = ∅ then
gradients of the part size with respect to X. Second, we have to 10 ∆y ← smallestT opDecollision(L, pi ) ;
decide on how to evolve the layout when parts are changed (Sec-
tion 5.1.2). We rely on a sliding algorithm that avoids jumps in 11 posy ← (ui , vi + ∆y ) ;
the layout configuration, thus producing only small changes in the 12 if posx = ∅ and posy = ∅ then
wastage function when small changes are applied to the part sizes. ; // cannot fit masterboard
13 return ∅ ; // W (∅) = 1
Overall strategy. Our approach changes the size of parts iteratively 14 if posx = pos and posy = pos then
with two different steps in each iteration: grow (line 5) and shrink 15 break;
(line 6). These steps progressively modify the design and keep track 16 if A(box(L Cposx pi ) < A(box(L Cposy pi )) then
of the design of smallest wastage encountered so far. 17 (ui , vi ) ← posx
The grow step (Section 5.1.3) attempts to enlarge the parts so as to 18 else if A(box(L Cposx pi ) > A(box(L Cposy pi ) then
reduce wastage. Each part is considered and its size is increased 19 (ui , vi ) ← posy
for as long as the growth further reduces wastage. When no further
improvement can be obtained, we create further opportunities by 20 else
shrinking a set of parts (Section 5.1.4). However, randomly shrink- 21 if ∆x < ∆y and |∆x | > 0 then
ing parts would be inefficient, as most parts would grow back im- 22 (ui , vi ) ← posx
mediately to their original sizes. Other parts are tightly coupled to 23 else
many others in the design D, and shrinking these would impact the 24 (ui , vi ) ← posy
entire design. Therefore, we analyze the layout to determine which
parts have a higher probability to result in wastage reduction. 25 L ← L C(ui ,vi ) pi
26 return (L);
5.1.1 Changing part sizes

During design space exploration the algorithm attempts to vary the

part sizes wi and hi individually. These dimensions vary as a func- problem is under-constrained and solved in the least-norm sense,
tion of design parameters X. In the remainder we use s(X) to minimizing ||∆||. We rely on a QR decomposition of the system
designate the vector of all part sizes assembled such that s2i = wi matrix to solve for both cases, accounting for possible rank defi-
and s2i+1 = hi . ciencies due to overlapping parameters in X.
Let us denote λ the change of size desired on si . Our objective is We implement this process as a subroutine
to compute a design change ∆ such that si (X + ∆) = si (X) + C HANGE PART S IZE (X,si ,λ), with X the current design pa-
λ. We denote the vector of changes as Λ = s(X + ∆) − s(X). rameters, si the part size to change and λ the change to apply. It
In this process only the size si should change with others remain returns the new design parameters X + ∆. A second subroutine
unchanged whenever possible, that is Λsj ,j6=i = 0 and Λsi = λ. C HANGE PART S IZES (X,Λ) allows to change the size of multiple
Parts are not independent in the design and therefore there is no parts at once.
trivial link between X and si (X). We therefore analyze the rela-
5.1.2 Updating layouts by sliding
tionship through the gradients ∂s∂x
i (X)
j
. These are computed by local
finite differencing (depending on the design analytical expressions As the shapes and sizes of the parts change the layout has to be
may be available). Each non-null gradient indicates that parameter updated. One option would be to restart the docking process after
xj influences si . Multiple parameters may influence si and param- each change. However, for a small change the docking process can
eters typically also influence other variables: there exists k 6= i produce large discontinuities in the wastage function. This makes
such that ∂s∂xk (X)
j
6= 0. a local search difficult. Instead, we propose to rely on a sliding
operation that attempts to continuously update the position of the
To compute ∆ we formulate the following problem. Let us consider parts after each change. Note that performing such an update while
the components of ∆ = (δ0 , ..., δ|X|−1 ). The change in part sizes optimizing for a given objective (i.e. wastage) is a very challenging
due to ∆ can be approximated in the first order through the gradi- combinatorial problem, as each part can move in four directions
ents as Λ = i δi · ∂s(X)
P
∂xi
. We solve for ∆ such that Λsi = λ and (left/right/top/bottom) and multiple cascading overlaps have to be
Λsj ,j6=i = 0. resolved. We propose a heuristic approach that works well for small
changes in the part shapes.
If there are less parameters than part sizes, the problem is over-
constrained and solved in the least-square sense, minimizing ||Λ − The algorithm is based on the following principle. After changing
(0, ..., λ, ..., 0)||2 . If there are more parameters than part sizes, the the part shapes, we reintroduce them in an empty layout in order of
docking. However, each time a part is reintroduced it may now have Algorithm 4: G ROW PARTS
empty space to its left/bottom or it may overlap with previously
Input: Best design parameters Xb and layout Lb so far, current
placed parts. Both cases can be resolved by a single horizontal or
design parameters Xc and current layout Lc being
vertical move. However a single move is generally not desirable as
explored, ordering O.
empty space may remain along the other direction. We therefore
Output: New best design and packing.
perform a limited sequence of horizontal/vertical moves. At each
1 improvement ← true;
iteration we select between vertical or horizontal by favoring moves
2 while improvement do
that result in the smallest layout bounding box. In case of a tie, we
3 improvement ← f alse;
favor moves to the left/bottom versus displacements to the top/right.
4 foreach part size si in random order do
This is illustrated in Figure 5.
5 We ← 1 ; // max wastage
6 Xe ← Xc , Le ← Lc ;
// Grow a first time and then continue as
long as it improves.
7 while true do
8 Xe ← C HANGE PART S IZE (Xe ,si ,1) ; // +1 pix.
9 Le ← S LIDE(Le ,D(Xe ));
10 if W (Le ) > We then
11 Le ← D OCKING(D(Xe ),O);
12 if W (Le ) < We then
Figure 5: Sliding a layout after a change of part sizes. Top: From 13 We = W (Le );
left to right, initial layout, same after change revealing overlaps, 14 else
layout after sliding. Bottom: Moves performed on the three first 15 break;
parts during sliding.
// Check for improvement over current.
16 if We < W (Lc ) then
The pseudo-code is given in Algorithm 3. In the algorithm we de- 17 Xc = Xe , Lc = Le ;
note by L the layout and denote by L Cpos pi the layout obtained 18 improvement ← true;
when adding part pi at position pos in the master board grid of
L. A(.) measures the area, box(L) is the bounding rectangle of
// Check for improvement over global best.
the layout. The algorithm iterates over all parts in docking order
(line 2). It then performs a fixed number of sliding operations on 19 if W (Lc ) < W (Lb ) then
each part (line 3) – we use N = 4 in our implementation. Lines 4-7 20 Xb = Xc , Lb = Lc ;
compute a horizontal move, favoring moves to the left that collapse 21 return (Xb , Lb );
newly created empty spaces. Lines 4-7 similarly compute a vertical
move. Lines 16-24 decide whether to select a horizontal move posx
or vertical move posy .
these chains prevent any further growth. We therefore detect lock-
The process may fail if parts can no longer fit in the masterboard. ing chains and select the parts to shrink among these. This often
This can happen either because there is not enough remaining area, results in a change of aspect ratio of the masterboard, and new op-
or because sliding cascades in large moves that prevent further in- portunities for other parts to grow.
sertion of parts. In such cases we return an empty layout which by
convention has a wastage of 1 (worst possible), line 13. The overall approach is described in Algorithm 5. It first deter-
mines which parts to shrink by calling S ELECT PARTS T O S HRINK
5.1.3 Grow step and then computes a change of parameters using the approach de-
scribed in Section 5.1.1.
The grow step is described in Algorithm 4. The algorithm iterates The core component is the S ELECT PART S IZES T O S HRINK subrou-
over all parts in random order (line 4) and progressively increases tine, described in Algorithm 6. The selection starts by gathering
the size of a part in a loop (line 7). Note that the first iteration of the all contacts between parts in the layout – this is done efficiently
loop determines the starting wastage for growing this part (lines 5 in the discretized layout grid. We first draw the part images into
and 12-13). The process continues until the growth results in an the grid and then check pairs of neighbors belonging to different
increased wastage (line 15). parts. This produces the set of left/right and bottom/left contacts
between part sizes (the involved part size is deduced from the part
After each change of parameters the design parts are recomputed
(line 9, D(Xe )) and sliding is called to adapt the current layout to
the change. The result is checked. If wastage decreases the process
continues (line 13). If not, we first attempt to dock the parts again Algorithm 5: S HRINK PARTS
(line 11). This can help continue the growth in cases were sliding Input: Best design parameters Xb and layout Lb so far.
fails to resolve overlaps by continuous changes. If wastage still not Output: Shrunk design parameters.
improves we stop the growth of this part size (line 15). 1 Xs ← X;
2 S ← S ELECT PART S IZES T O S HRINK(Lb );
5.1.4 Shrink step 3 Λ ← (0, ..., 0);
4 foreach si ∈ S do
The goal of the shrink step is to create further opportunities for de- 5 Λi ← −1 ; // -1 pixel
sign changes when no parts can further grow. The typical situation 6 Xs ← C HANGE PART S IZES (Xs ,Λ) ; // -1 pixel
is that a subset of parts are forming locking chains between respec- 7 return (Xs );
tively the left/right and top/bottom borders. The parts belonging to
 Algorithm 6: S ELECT PART S IZES T O S HRINK
Input: A layout L.
Output: Set of part sizes to shrink.
1 K ← ∅;
2 foreach axis a ∈ {X, Y } do
3 C ←G ATHER C ONTACTS A LONG A XIS(a) ;
4 K ← K ∪ F ORM C ONTACT C HAINS(C) ; Figure 6: Height-fields of the layout used to position the next part.
Left: Height-field for dropping parts from the right (red curve).
5 S ← ∅;
Right: Height-field for dropping parts from above (green curve).
6 while K 6= ∅ do
These height-fields are maintained every time a new part is added
7 si ← D RAW PART S IZE W ITH P ROBABILITY(K);
to the layout, and used for fast computation of the docking posi-
8 S ← S ∪ {si };
tions. Similar height-fields are pre-computed for the left/bottom of
9 K ← K \ K ILLED C HAINS(K,si );
the parts.
10 return S;

Docking algorithm. The docking algorithm places each part in

orientation and the considered axis). The contacts are oriented from order by ’dropping’ the next part on the current layout either from
right to left (respectively top to bottom). We similarly detect which the right, or from the top. It locally searches for the best placement
parts touch the borders. The contact detection is implemented in of each part, according to a criterion that minimizes wastage. The
the G ATHER C ONTACTS A LONG A XIS subroutine. result is a layout L including all parts.

Once the contacts are obtained we start from the right (respectively Given the layout so far our algorithm searches for the best orien-
top) border and form locking chains. Starting from the border, we tation and best position for the next part. We denote by Li−1 the
produce the set of chains iteratively. Each chain c is a sequence layout obtained for the i − 1 first parts, and by Li ← Li−1 Cpos pi
(lef t, sf irst , ..., slast ). At each iteration the chain spawns new the layout obtained by adding the next part at position pos. The
chains for each contact pair (slast , snext ) obtained by augment- docking position pos is computed from a drop location (s, x, o),
ing c as (lef t, sf irst , ..., slast , snext ). Potential cycles are easily with s ∈ {top, right}, x a position along the corresponding axis
detected as repetition of a same part in the chain and are ignored. and o ∈ {0, π/2, π, −π/2} an orientation.
The locking chain computation is implemented in the F ORM C ON -
TACT C HAINS subroutine.
The pseudo code for the docking algorithm is given in Algo-
rithm 7. The drop locations are ranked according to a docking
We next randomly select part sizes to shrink until all locking chains criterion that we denote D(Li−1 , pi , pos), explained next. The
are removed. The selection probability of each part is designed docking positions are computed from the drop locations by the
to avoid too large a jump in the design space. To achieve this ComputeDockingPosition subroutine. It is efficiently imple-
we consider two factors. First, we compute the number of oc- mented by maintaining the right/top height-fields of the current lay-
currences of each part in the locking chains, occ(pi ). A part with out as illustrated in Figure 6. Whenever evaluating a drop location
many occurrences is a good candidate as shrinking it will resolve we use the height-fields to quickly compute the docking positions
multiple locking chains at once. Second, we seek to avoid shrink- that bring the part in close contact with the current layout.
ing part sizes that are tightly coupled with others in the design D.
We compute the dependence of a part size by counting the num-
ber of non-zero entries in the Λ vector computed internally by Algorithm 7: D OCKING
C HANGE PART S IZE (Xe ,si ,−1). Input: Set of parts P , order O, master board dimensions W × H
Output: A layout L
We select part sizes with the following random process. First, 1 foreach part pi ∈ P following order in O do
we
P
select a number of occurrences o with probability P (o) = 2 best ← ∅ ;
occ(o)
pi ,occ(pi)=o
P . Then, among the parts such that occ(pi ) = o 3 bestscore ← 1 ;
pi occ(pi )
4 foreach drop location (s, x, o) do
we select a part size si with probability P (si |occ(si ) = o) = 5 pos ← ComputeDockingPosition(pi , (s, x, o)) ;
dep(si )
1− P dep(pi )
. This process is implemented by the 6 score ← D(Li−1 , pi , pos) ;
pi ,occ(pi )=o
D RAW PART S IZE W ITH P ROBABILITY subroutine. 7 if score < bestscore then
8 best ← pos ;
After each part size selection we update the set of locking chain by 9 bestscore ← score ;
removing all chains where the part size appears.
10 Li ← Li−1 Cpos pi ;
5.2 Exploring orderings 11 return Ln ;

The subroutine E XPLORE O RDERINGS in Algorithm 1 performs a

stochastic search of orderings resulting in low wastage layouts. The Docking criterion. The docking criterion considers wastage as the
process starts from a random order and iteratively considers possi- primary objective, where wastage is defined by the ratio of occu-
ble improvements by swapping two parts. At each iteration, we pied area divided by the bounding rectangle area of the layout. We
perform a swap and recompute a layout using the docking algo- denote W (Li ) the wastage of a layout including up to part i. It
rithm. If wastage is reduced the swap is accepted, otherwise it is Pi
A(p )
k
k=0
rejected. We apply the process for a number of iterations and keep is obtained as W (Li ) = A(box(L i ))
where A measures area and
the best ordering found as the starting point. We use |D(X)|2 iter- box(L) is the bounding rectangle of the layout. W is therefore the
ations, where |D(X)| is the number of parts. For each ordering, we ratio between the area of the parts and the area of the bounding
use a fast docking algorithm to compute a layout with low wastage. rectangle.
Figure 7: Designs created using our system. Each design is shown with initial shape, starting layout, optimized layout, and final design.
However, as the algorithm heuristically docks parts in sequence it
cannot foresee that some spaces will be definitely enclosed. In par-
ticular, for newly inserted concave parts there are often multiple
orientations of the part resulting in the same wastage: if the con-
cavity remains empty there is no preferred choice. However, some
choices are indeed better than others. If the concavity faces an al-
ready placed object, then further docking within the concavity will
never be possible. This is illustrated in Figure 8, left.

We therefore propose a second criterion that discourages these bad

choices. The idea is to estimate the space that will be definitely
enclosed when a part is added to the current layout. This is done
efficiently by considering the enclosed space between the height-
field of the current layout and the height-field of the added part,
along both horizontal and vertical directions.

Let H r (L) (respectively H t ) be the right (respectively top) height-

field of layout L and A(H r (L)) the area below it. The enclosed
area is then defined as:

E(Li−1 , pi , pos) =
max (0, A(H s (Li−1 Cpos pi )) − A(H s (Li−1 )) − A(pi ))
P
s∈{r,t}
Figure 10: Various material-driven design and fabrication exam-
with A(pi ) the area of part pi . Note the max that clamps negative ples. In each row, we show initial design (with material space lay-
values: this is due to cases where the part nests in a concavity below out inset), optimized design result (with material space layout in-
the height-field of the other direction. set), along with final cutout assembled model. Note that the design
changes are often subtle, but still leads to significant improvement
The enclosed space is used as a tie-breaker when docking positions in material usage.
produce the same wastage values; therefore D(Li−1 , pi , pos) re-
turns the vector (W (Li−1 Cpos pi ), E(Li−1 , pi , pos)). The effect
of the enclosed area criterion is shown in Figure 8. 6 Results
We used our system for various design explorations. As the com-
plexity of the designs grows beyond 4-6 planks, the utility of the
system quickly becomes apparent. Note that the design constraints
4
(see Figure 9), by coupling different object parts, make the opti-
mization challenging by preventing independent adaptation of part
1 3
2 4
sizes. By off-loading material usage considerations to the system,
2
1 3 the user can focus on the design. Note that even when changes to
the design are visually subtle, material utilization often increases
Figure 8: Two layouts obtained with the same docking order. Left: significantly.
Without taking enclosed area into account the first part is placed
with the concavity against the bottom packing border. This prevents Design examples. We used our system to design and fabricate
the second part to nest within and cascades into a series of poor a range of examples comprising rectangular and/or curved parts.
placements. Right: Taking into account enclosed areas results in We fabricated fullscale and miniature models of designed furni-
a placement of the first part that allows nesting of the second part ture. Models were made from MDF of 3 mm thickness and MDF
and produces a layout with lower wastage. of 30 mm thickness. The designs are easy to manufacture in
batches since after design layout optimization they typically fit mas-
ter boards completely: there is no need to attempt to reuse leftover
pieces of wood, and switching boards requires little clean up.
We directly output the cutting plan for the laser cutter (or CNC ma-
outer volume

chine) from the design layout, adding connectors for planks sharing
an edge, if needed. These are conveniently detected since planks
exactly overlap on edges in the 3D design. The connectors are ei-
ther finger joints, which are both strong after gluing and easy to
assemble; cross connectors for interleaved planks, or dowel-jointed
volume violation
for thicker materials (20 mm and 30 mm thickness).
inner volume

Figures 7 and 10 show various results. Table 1 gives an overview of

the complexity of each model, and the gains obtained by the layout
optimizer. The system performs at interactive rates on a laptop tak-
ing from a few seconds to 3-4 minutes for the larger examples. Note
initial with constraint without constraint that speed depends on how many exploration threads are pursued.

Figure 9: We show effects of designing with (middle column) or Figures 1 and 7 show results for objects with curved parts. Fig-
without (right column) the respective constraints activated. ure 3 shows some intermediate shapes as the design evolves for the
 1
Table 1: Statistics for cut design showing the number of planks, ours
(a) comparison of packing strategies
0.9
init
grow
(b) steps in an exploration run
baseline shrink
number of constraints, material wastage ratio before and after the 0.70 packing
0.8
final

design suggestions/optimization. 0.7

0.65 0.6

usage

usage
0.5
#planks #constraints ratio before ratio after
0.60 0.4

Figure 1 4 21 0.22 0.11 0.3

Figure 7a 7 33 0.34 0.08 0.55 0.2

Figure 7b 9 N/A 0.34 0.20 0.1

0.50
Figure 7c 8 N/A 0.24 0.17 0 100 200
different runs
300 400
0
0 5
exploration steps
10 15

Figure 7d 16 N/A 0.21 0.14 (c) usage improvements over different runs (coffee table) (d) usage improvement over different runs (parrot shelf)
Figure 10a 6 22 0.15 0.04 0.90

Figure 10b 11 41 0.15 0.03 0.85

Figure 10c 8 13 0.26 0.03 0.85

Figure 10d 16 29 0.11 0.02 0.80

usage
usage
0.80

0.75
0.75

coffee-table (Figure 1) and the low-chair (Figures 7-top) examples. ours ours

baseline baseline

Figure 11 shows alternate designs discovered by the algorithm for 0.70

0 4
different runs
8
0.70
0 4
different runs
8

the Parrot shelf. While they have slightly lower usage they offer
interesting variations that the user might prefer. Figure 12: Comparison of our algorithm against baseline alterna-
Figures 1 was fabricated using a CNC machine. The optimized de- tives. Higher is better. Please refer to the text for details.
sign achieved nearly 90% material usage, although one can achieve
null wastage by deciding to pick a rectangular top – a decision stylized chair, where both the chair seat height and chair width were
that can be made after layout optimization as this opportunity is constrained not to change beyond a margin. Figure 10d shows mul-
revealed. An allowable range was specified for the height and the tiple designs covering 2 master boards. The second master board
bases were marked as symmetric as input design constraints. In the is used as an overflow when docking can no longer fit a part in the
case of the parrot-shelf (Figure 7a), the user indicated minimum first. The layouts are slid independently.
and maximum range for the horizontal shelves along with desired
range for the shelf heights. Comparison. We now evaluate the relative importance of the key
As described, parameteric designs are easily supported and opti- algorithm steps. Figure 12a shows the importance of the docking
mized for in our framework. Figures 7b-d show three such exam- criteria introduced in Section 5.2. We ran 500 random runs of our
ples. In each case, additional constraints were provided to keep proposed packing algorithm with (‘ours’) and without (‘baseline’)
the objects within a given volume. The parts of the objects are all the docking criteria on the coffee-table example. We sort the runs
tightly coupled making these challenging examples to optimize for. based on resultant usage (no shape optimization is performed here)
and plot the two conditions. The docking criteria consistently re-
Figure 10a shows a L-shaped work table. The user specified a tar- sulted in 10-15% better usage.
get height for the design and a maximum work volume. Note that
the legs of the table were also constrained to not change more than Figure 12b shows usage improvement over one exploration run on
25% of original dimensions to prevent unwanted design changes. the coffee-table sequence. The legend explains which step (grow,
Figure 10b shows a coupled shelf and table design where height of shrink, etc.) is being performed. While this is the result from a
shelves and tabletop were similarly constrained. Figure 10c shows a single thread, many similar threads are simultaneously explored.
The few best results are then presented to the user as suggestions.
Figure 12c-d compare the importance of analyzing the material
space layout to decide which plank to change and how. As baseline,
we selected planks at random and perform either a grow or shrink
sequence with equal probability. Note that our method consistently
outperforms the alternative approach.

Design sessions. We asked second year art students (6 subjects)

from a design college to try our system. Figures 10b-d show a se-
lection of their designs. These particular students had performed a
very similar task as part of their first year assignment – ‘design fur-
niture of your choice making best use of the provided piece of MDF
board.’ Hence, they were very aware of the implicit link between
design and material usage. Previously, they had used commercial
3D modeling tool (Rhinoceros, Solidworks, Sketchup Pro) for de-
signing and mainly Illustrator for manually laying out the designs.
They recalled the frustration of having to switch between the dif-
ferent 2D-3D design representations. First, the students sketched
design concepts before using our system. Then, they used the ex-
ploration interface on their designs to reduce wastage. Note that
visually the initial sketch and final design can look similar, despite
the increase in material utilization, which is desirable in terms of
Figure 11: Two different design suggestions (green has ratio 0.86, preserving the original design.
blue has ratio 0.85) for the parrot-shelf. Original design with an-
other design suggestion is shown in Figure 7. Overall, the feedback was positive. They appreciated being able to
easily move between 2D↔3D, and not having to explicitly worry B RÜDERLIN , B., AND ROLLER , D., Eds. 1998. Geometric Con-
about material utilization. They appreciated the suggestions, in- straint Solving and Applications, vol. VIII. Springer.
stead of previous attempts using trial-and-error iterations between
various softwares to reduce material wastage. C ALÌ , J., C ALIAN , D., A MATI , C., K LEINBERGER , R., S TEED ,
A., K AUTZ , J., AND W EYRICH , T. 2012. 3d-printing of non-
assembly, articulated models. 130:1–130:8.
Limitations. Currently, the algorithm can only make topological
changes only for parameteric models. This will be an interesting C HEN , S. S., D ONOHO , D. L., AND S AUNDERS , M. A. 2001.
future direction to pursue for constrained models. Our docking ap- Atomic decomposition by basis pursuit. SIAM Rev. 43, 1, 129–
proach cannot nest parts into holes of other parts, a more advanced 159.
algorithm would be required. A more material-induced restriction
arises when the starting layout does not leave much space to opti- C HEN , X., Z HANG , H., L IN , J., H U , R., L U , L., H UANG , Q.,
mize over. This effectively means that the degree of freedom for B ENES , B., C OHEN -O R , D., AND C HEN , B. 2015. Dapper:
the design is low. Adding more planks does reduce this problem Decompose-and-pack for 3d printing. ACM Trans. Graph. 34, 6
(by providing additional freedom). However, beyond 25-30 planks, (Oct.), 213:1–213:12.
the exploration of the shape space becomes slow as there are too C IGNONI , P., P IETRONI , N., M ALOMO , L., AND S COPIGNO , R.
many paths to explore. One option is to limit exploration to only 2014. Field-aligned mesh joinery. ACM TOG 33, 1 (January).
a subset of planks at a time, but then again, very desirable design
configurations may be missed. C OROS , S., T HOMASZEWSKI , B., N ORIS , G., S UEDA , S., F OR -
BERG , M., S UMNER , R. W., M ATUSIK , W., AND B ICKEL , B.
2013. Computational design of mechanical characters. ACM
7 Conclusions and Future Work SIGGRAPH 32, 4, 83:1–83:12.
We investigated how design constraints and material usage can be DAIAN , G., AND O ZARSKA , B. 2009. Wood waste management
linked together towards form finding. Our system dynamically dis- practices and strategies to increase sustainability standards in the
covers and adapts to constraints arising due to current material us- australian wooden furniture manufacturing sector. Journal of
age, and computationally generates design variations to reduce ma- Cleaner Production 17, 17, 1594?–1602.
terial wastage. By dynamically analyzing 2D material space lay-
D UMAS , J., H ERGEL , J., AND L EFEBVRE , S. 2014. Bridging the
outs, we determine which and how to modify object parts, while
gap: Automated steady scaffoldings for 3d printing. ACM Trans.
using design constraints to determine how the proposed changes
Graph. 33, 4 (July), 98:1–98:10.
can be realized. This interplay results in a tight coupling between
3D design and 2D material usage and reveals information that usu- F U , C.-W., S ONG , P., YAN , X., YANG , L. W., JAYARAMAN ,
ally remains largely invisible to the designers, and hence difficult P. K., AND C OHEN -O R , D. 2015. Computational interlocking
to account for. We used our system to generate a variety of shapes furniture assembly. ACM Trans. Graph. 34, 4 (July), 91:1–91:11.
and demonstrated wastage reduction by 10% to 15%.
G AL , R., S ORKINE , O., M ITRA , N. J., AND C OHEN -O R , D.
Currently, we do not consider the stability of the produced furni- 2009. iwires: An analyze-and-edit approach to shape manipu-
ture nor the durability of the joints. This could be integrated as dy- lation. ACM Transactions on Graphics (Siggraph) 28, 3, #33,
namic constraints following previous work on structural reinforce- 1–10.
ment [Stava et al. 2012] and shape balancing [Prévost et al. 2013].
Another important future direction is to generalize the framework to G UENNEBAUD , G., JACOB , B., ET AL ., 2010. Eigen v3.
handle other types of laser cut materials, e.g., plastic plates that can [Link]
be easily cut and more interestingly bend to have freeform shapes. H ABBECKE , M., AND KOBBELT, L. 2012. Linear analysis of
Note that the packing problem will still be in 2D for such devel- nonlinear constraints for interactive geometric modeling. CGF
opable pieces. This can help produce interesting freeform shapes, 31, 2, 641–650.
while still making efficient use of materials.
H ILDEBRAND , K., B ICKEL , B., AND A LEXA , M. 2012. crdbrd
: Shape fabrication by sliding planar slices. CGF Eurographics
Acknowledgements 31, 2.

The work was supported in part by ERC ShapeForge (StG-2012- H U , K., J IN , S., AND WANG , C. C. 2015. Support slimming for
307877) and ERC SmartGeometry (StG-2013-335373). single material based additive manufacturing. Computer-Aided
Design 65, 1 – 10.

References J YLÄNKI , J. 2010. A thousand ways to pack the bin-a practical

approach to two-dimensional rectangle bin packing. Retrieved
from [Link] .
BÄCHER , M., B ICKEL , B., JAMES , D. L., AND P FISTER , H.
2012. Fabricating articulated characters from skinned meshes. L I , X.-Y., S HEN , C.-H., H UANG , S.-S., J U , T., AND H U , S.-M.
ACM Trans. Graph. (Proc. SIGGRAPH) 31, 4. 2010. Popup: automatic paper architectures from 3d models.
ACM SIGGRAPH 29, 4, 111:1–9.
BFM. 2003. Wood waste recycling in furniture manufacturing.
Tech. rep., British Furniture Manufacturer. L I , X.-Y., J U , T., G U , Y., AND H U , S.-M. 2011. A geometric
study of v-style pop-ups: Theories and algorithms. ACM Trans-
B OKELOH , M., WAND , M., S EIDEL , H.-P., AND KOLTUN , V. actions on Graphics 30, 4, 98:1–10.
2012. An algebraic model for parameterized shape editing. ACM
SIGGRAPH 31, 4, 78:1–78:10. L U , L., S HARF, A., Z HAO , H., W EI , Y., FAN , Q., C HEN , X.,
S AVOYE , Y., T U , C., C OHEN -O R , D., AND C HEN , B. 2014.
B RENNAN , G., B ROWN , J., D OCHERTY, M., AND T ULLETT, B. Build-to-last: Strength to weight 3d printed objects. ACM Trans.
2006. FlatPack/PlaskaPaczka. The Caseroom Press. Graph. 33, 4 (July), 97:1–97:10.
L UO , L., BARAN , I., RUSINKIEWICZ , S., AND M ATUSIK , W. Z HOU , Q., PANETTA , J., AND Z ORIN , D. 2013. Worst-case struc-
2012. Chopper: Partitioning models into 3D-printable parts. tural analysis. ACM Trans. Graph. 32, 4 (July), 137:1–137:12.
ACM SIGGRAPH Asia 31, 6.
M C C RAE , J., S INGH , K., AND M ITRA , N. J. 2011. Slices: A
shape-proxy based on planar sections. ACM Transactions on
Graphics 30, 6, 168:1–168:12.
M UELLER , S., L OPES , P., AND BAUDISCH , P. 2012. Interac-
tive construction: Interactive fabrication of functional mechani-
cal devices. In Proc. UIST, ACM, New York, NY, USA, 599–
606.
P RÉVOST, R., W HITING , E., L EFEBVRE , S., AND S ORKINE -
H ORNUNG , O. 2013. Make it stand: Balancing shapes for 3d
fabrication. ACM Trans. Graph. 32, 4 (July), 81:1–81:10.
S AAKES , D., C AMBAZARD , T., M ITANI , J., AND I GARASHI , T.
2013. Paccam: Material capture and interactive 2d packing for
efficient material usage on cnc cutting machines. In Proc. UIST,
ACM, New York, NY, USA, 441–446.
S CHULZ , A., S HAMIR , A., L EVIN , D. I. W., S ITTHI - AMORN , P.,
AND M ATUSIK , W. 2014. Design and fabrication by example.
ACM Trans. Graph. 33, 4 (July), 62:1–62:11.
S CHWARTZBURG , Y., AND PAULY, M. 2013. Fabrication-aware
design with intersecting planar pieces. CGF Eurographics 32, 2,
317–326.
S HUGRINA , M., S HAMIR , A., AND M ATUSIK , W. 2015. Fab
forms: Customizable objects for fabrication with validity and ge-
ometry caching. ACM Trans. Graph. 34, 4 (July), 100:1–100:12.
S TAVA , O., VANEK , J., B ENES , B., C ARR , N., AND M ĚCH , R.
2012. Stress relief: Improving structural strength of 3d printable
objects. ACM Trans. Graph. 31, 4 (July), 48:1–48:11.
TALTON , J. O., G IBSON , D., YANG , L., H ANRAHAN , P., AND
KOLTUN , V. 2009. Exploratory modeling with collaborative
design spaces. In ACM SIGGRAPH Asia, 167:1–167:10.
U METANI , N., I GARASHI , T., AND M ITRA , N. J. 2012. Guided
exploration of physically valid shapes for furniture design. ACM
SIGGRAPH 31, 4, 86:1–86:11.
VANEK , J., G ALICIA , J. A. G., B ENES , B., M ĚCH , R., C ARR ,
N., S TAVA , O., AND M ILLER , G. S. 2014. Packmerger: A
3d print volume optimizer. Computer Graphics Forum 33, 6,
322–332.
WANG , W., WANG , T. Y., YANG , Z., L IU , L., T ONG , X., T ONG ,
W., D ENG , J., C HEN , F., AND L IU , X. 2013. Cost-effective
printing of 3d objects with skin-frame structures. ACM Trans.
Graph. 32, 6 (Nov.), 177:1–177:10.
X U , W., WANG , J., Y IN , K., Z HOU , K., VAN DE PANNE , M.,
C HEN , F., AND G UO , B. 2009. Joint-aware manipulation of
deformable models. ACM Trans. Graph. 28, 3 (July), 35:1–35:9.
X U , K., Z HANG , H., C OHEN -O R , D., AND C HEN , B. 2012. Fit
and diverse: Set evolution for inspiring 3d shape galleries. ACM
SIGGRAPH 31, 4, 57:1–10.
YAO , M., C HEN , Z., L UO , L., WANG , R., AND WANG , H. 2015.
Level-set-based partitioning and packing optimization of a print-
able model. ACM Trans. Graph. 34, 6 (Oct.), 214:1–214:11.
Z HENG , Y., F U , H., C OHEN -O R , D., AU , O. K.-C., AND
TAI , C.-L. 2011. Component-wise controllers for structure-
preserving shape manipulation. In Computer Graphics Forum
(In Proc. of Eurographics 2011), vol. 30.