Pacific Graphics 2017
J. Barbic and O. Sorkine-Hornung(Guest Editors)

Volume 36 (2017), Number 7

Semi-Automatic Conversion of 3D Shape into
Flat-Foldable Polygonal Model
Emi Miyamoto

Yuki Endo

Yoshihiro Kanamori

Jun Mitani

University of Tsukuba

Abstract
This paper presents a method that can convert a given 3D mesh into a flat-foldable model consisting of rigid panels. A previous
work proposed a method to assist manual design of a single component of such flat-foldable model, consisting of verticallyconnected side panels as well as horizontal top and bottom panels. Our method semi-automatically generates a more complicated model that approximates the input mesh with multiple convex components. The user specifies the folding direction of eachconvex component and the fidelity of shape approximation. Given the user inputs, our method optimizes shapes and positions ofpanels of each convex component in order to make the whole model flat-foldable. The user can check a folding animation of theoutput model. We demonstrate the effectiveness of our method by fabricating physical paper prototypes of flat-foldable models.
Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry and Object
Modeling—Physically based modeling

Folding direction

1. Introduction
Folding objects flatly is an effective way to conserve storage
space. For example, packing materials such as card-board boxes
or gift boxes are devised to be flat-foldable and have their shapes
restored easily. In the field of origami engineering, folding mechanisms have been extensively studied and used to develop various products that require contractility and portability, from pop-up
cards to solar panels of satellites.
Although previous folding techniques are used in various fields,
they can handle only relatively simple shapes such as symmetric ones. Additionally, complicatedly-shaped objects consisting of
rigid materials are more difficult to fold than objects made of soft
materials such as cloth or rubber. Also, the more complicated theshape is, the more difficult it is to fold and restore its shape.
To tackle this challenge, Kase et al. proposed a system to assist
manual design of flat-foldable polygonal models [KKM15]. Figure 1 shows an example model designed by their system, which isdefined by the shapes of the top panel and cross-section polylines
specified by the user. The cross-section polylines define the sidepanels that are vertically connected each other and also connectedto the top and bottom panels. We can fold the model flat by pushing down the top panel because horizontally-adjacent side panels
are not connected and vertically-connected side panels are articulated at each horizontal edge that works as a hinge.
Unfortunately, their system has several problems. First, because
their system is basically for manual design, the user must undergo
submitted to Pacific Graphics (2017)

Top panel

Cross section
polylines

Side panels

Folding process

Figure 1: Flat-foldable component by Kase et al. [KKM15].
many trial-and-errors to design a desired shape. Second, the designing process is not intuitive because the user specifies the shapesof the top panel and cross-section polylines in 2D space, making
it hard to imagine the resultant shape of the whole model. Third,
although they suggested that a complicated model can be createdby designing and attaching multiple flat-foldable components eachother, the user must account for which faces to be attached while
adjusting the shapes and positions of faces and avoiding collisions
during folding.
In this paper, we propose a semi-automatic method for creating a multi-component, flat-foldable model that roughly approximates an input 3D mesh with rigid panels. Our method first divides the input mesh into multiple components and, in order tosimplify the shape optimization process, converts them into convex shapes. After the user specifies the folding direction of eachconvex component and fidelity parameters for shape approxima-

2

Miyamoto, Endo, Kanamori and Mitani / Semi-Automatic Conversion of 3D Shape into Flat-Foldable Polygonal Modeltion (e.g., the number of vertices in the top panel), our method calculates a flat-foldable shape for each component through optimization, while accounting for faces of inter-component attachment aswell as collisions between horizontally-adjacent side panels in eachcomponent. The user can check a folding animation of the resultant
model. To demonstrate the effectiveness of our method, we fabricate physical paper prototypes of flat-foldable models generated byour system.

Top-panel edge E j

Top panelvj
p0

Cross-section
polyline Pj

pij = ( uij , vij )Cross-section
polyline Pj

Polylinevertex pijzyxpMj -1

Cross section
Πj

u

j

2. Related Work
Techniques for folding objects flat have been used in various
fields. A research topic familiar for the computer graphics community is to design pop-up cards or books, which are paper artworks that are flat while closed and show their 3D shape when
opened [MS04, XTGH11, IEM∗ 11, JLYL14]. The target objects ofthese study form their shape when being expanded 90 or 180 degrees, whereas each flat-foldable component stands up after being
pulled perpendicularly to the top panel in our method. Additionally,
we can make a complex object by combining multiple objects thatare folded in different directions.
In the field of origami engineering, there are a number of techniques for designing flat-foldable shapes. Particularly, those forrigid-foldable shapes are the most relevant to our work. A rigidfoldable shape consists of rigid faces and mountain/valley creaselines, and the rigid faces remain rigid during folding, similarly tothe rigid panels in our flat-foldable models. However, existing studies focus on how to fold simple primitives, e.g., cylindrical or cellular structures [TM12, YYT∗ 13], unlike our work that handles general polygonal models using slits and multiple components.
For other foldable products, Li et al. presented a method for automatically generating foldable furniture [LHAZ15]. Koo et al. developed an interactive system to aid the design of work-alike
prototypes of products to explore possible mechanical architecture [SSCO08]. They optimize model geometry on the basis of afunctional relationship given by the user. While these studies focus
on avoiding intersections of each component of an object to design
foldable models, we focus on generating foldable objects that canbe flattened out.
3. Configuration of Flat-Foldable Component
Before explaining our method, we briefly review the baseline
method by Kase et al. [KKM15] to make this paper self-contained.
After introducing the basic definitions, we explain their method andthen describe our modification.
3.1. Basic Definitions of Flat-Foldable Component
As shown in Figure 1, a flat-foldable component is specified
with a horizontal top panel as well as cross-section polylines. Eachcross-section polyline is assigned to each top-panel edge; the crosssection polylines are as many as the top-panel edges. We can generate a vertical chain of side panels by extruding each cross-section
polyline infinitely in parallel to the corresponding top-panel edge,
followed by trimming with horizontally-adjacent side panels. The
side panels are folded outward during folding. The top panel is a

Figure 2: Basic definitions of a flat-foldable component.
planar polygon perpendicular to the folding direction. To avoid collisions of horizontally-adjacent side panels, the top panel must be
convex [KKM15]. The bottom panel is parallel to the top panel, andautomatically determined as a result of trimming with side panels.
Figure 2 summarizes the basic definitions. Suppose there are N
edges on the top panel. For each top-panel edge E j ( j = 0, 1, . . . , N −1), we consider cross section Π j of the flat-foldable component, andthen define cross-section polyline P j on plane Π j . Polyline P j conj
sists of vertices pi (i = 0, 1, . . . , M j − 1), where M j is the number ofjvertices in polyline P j . Each vertex pi corresponds to a horizontal
edge connecting vertically-adjacent side panels. Polyline P j is further examined in uv plane defined on cross section Π j . We denote
j
j
j j
j
pi = (ui , vi ) in uv plane. p0 and p M −1 contact the top and bottomjjjpanels, respectively. p0 must move only along v axis, p M −1 is fixedj
on u axis during folding. Hereafter we might omit subscript j forsimplicity.
3.2. Baseline Method by Kase et al.
Kase et al. [KKM15] examined the conditions that each polyline
must satisfy to generate a flat-foldable component (see Figure 3):
u0i ≥ ui ,∑
 = (u M−1 − u0 ) −δi li ≈ 0,

(1)
(2)

i

where ui and u0i correspond to u coordinates of pi before and afterfolding. li (i = 0, 1, 2, , · · · , M − 2) is the length of a segment S i connecting pi and pi+1 .  represents the gap between u coordinates of
the two endpoints in the flat-folded state. If gap  of the polyline issufficiently close to zero, the polyline is considered as flat-foldable.
δi becomes 1 if S i faces upward (i.e., the outward normal of a sidepanel corresponding to segment S i is oriented upward), and -1 if
downward. Each vertex has a folded or non-folded state, and thefolded state has two folding configurations, i.e., mountain fold or
valley fold. That is, the total number of possible folded configurations is 2 M−1 . To obtain a good folded configuration, their systemranks each folded configuration using a score function, and selects
the one with the best score. The system then optimizes the vertex
positions in the selected configuration in order to make the polyline
flat-foldable.
They also suggested to combine multiple flat-foldable components to create a more complicated model. Note that we must carefully select components’ faces to be attached in order to avoid colsubmitted to Pacific Graphics (2017)

Miyamoto, Endo, Kanamori and Mitani / Semi-Automatic Conversion of 3D Shape into Flat-Foldable Polygonal Model

v
p0

v

v

B

p0
u

A

u

p0

u

Figure 3: Folding sequence of a cross-section polyline.

v
p0

v

Before folding

A

3

B

After folding

Figure 5: 2D illustration of component attachment. The green segments in component B indicate a concave component where othercomponents cannot be attached to avoid collisions.
4. Proposed Methodv

Figure 6 illustrates the overview of our method, which involves
the following five steps. Namely, our method

u

ε p

0

Convex-foldvertexup0

uFigure 4: Folding of a cross-section polyline with our convexity
constraint. The gap  (middle) in the folded state is minimized via
optimization (right).
lisions during folding. Figure 5 illustrates an example. As their system allows concave shapes, component B in Figure 5 has a concave
component (with segments in green) where we cannot attach othercomponents to avoid collisions.

1. Divides an input 3D mesh model into multiple components andconverts them into convex shapes (Section 4.1),
2. Generates a top panel and optimizes its size and position foreach component (Section 4.2),
3. Generates cross-section polylines and adjusts the number andpositions of vertices of each polyline so that each polyline becomes foldable (Section 4.3),
4. Generates a 3D polygonal model from the top panel and crosssection polylines and then modifies the cross-section polylines
again as needed (Section 4.4), and
5. Connects foldable components with one another.
Our method generates a flat-foldable model automatically, except
for the user-specified folding directions and parameters for shape
approximation fidelity.

3.3. Convexity Constraint in Our Method
Unlike the manual design in their system, we determine thewhole shape of a flat-foldable component as automatically as possible while satisfying flat-foldability and shape fidelity. In order tomake the problem tractable, we introduce a novel constraint thateach polyline should have no valley fold and only one mountainfold in the flat-folded state, which ensures the resultant component
has a convex shape. The only vertex having a mountain fold will
move outermost in the flat-folded state, and we call it the convex
fold vertex (see Figure 4, right). This constraint simplifies the problem:
1. All unconstrained vertices in each polyline always move outward in u direction and thus Eq. (1) is always satisfied. What wehave to consider for flat-foldability is only Eq. (2).
2. When attaching multiple components, we do not have to consider concave components (Figure 5), unlike the manual designusing the system by Kase et al.
3. The number of possible folding configurations is greatly reduced from 2 M−1 to M − 2 (note that we cannot assign a mountain fold to p0 or p M−1 ).
This convex constraint also makes the manual folding process easier; if we allow a concave component and push it down vertically,
concave side panels will move inward and collide with adjacentside panels. To avoid such collisions, we have to manually pull out
each concave side panel outward during the folding. This is much
more troublesome in case of multiple concave components.
submitted to Pacific Graphics (2017)

4.1. Segmenting Mesh and Calculating Convex Components
To approximate an input 3D mesh with multiple flat-foldable
components, we apply the feature-preserving mesh segmentation
algorithm by Shapira et al. [SSCO08]. The top panel of each component must be convex (Section 3.1), and the cross-section polylines should not have valley folds causing inward move (Section 3.3), which makes the whole component shape convex. We
therefore replace each segmented mesh with its convex hull calculated using [BDH96].
4.1.1. Determining folding direction
An important step to generate each flat-foldable component is tospecify its folding direction, which determines fundamental factorsof shape design. First, the folding direction specifies the top panelso that the top panel becomes perpendicular to the folding direction. The top panel then determines not only top-panel edges but
also corresponding cross-section polylines, for which we have tominimize gaps in Eq. (2).
The shape of the top panel also affects inter-component attachment. Figure 7 illustrates the influence of the folding direction of aflat-foldable component, showing two resultant models with different folding directions specified for the teddy bear’s face. The modelin the upper row is created using the folding direction of the vertical direction from up to down. This folding direction specifies the
topmost face as the top panel, and the ears are attached flatly. On

4Miyamoto, Endo, Kanamori and Mitani / Semi-Automatic Conversion of 3D Shape into Flat-Foldable Polygonal Model

(1)

(2)

(3)

(4)

(5)

Top panel

Top panel

Input 3D
mesh model

Divide into multiple
Generate a top
Generate a cross Generate a polygonal
Combine eachcomponents and convert panel and optimize
section polylines model and modify component and output
them into convex shape it for each component and adjust vertices
the cross-sectionof each polyline polylines as needed

Figure 6: Overview of our method. We first (1) segment an input 3D mesh and replace each mesh segment with its convex hull, which will be
converted into a flat-foldable component. We then generate and optimize (2) a top panel and (3) cross-section polylines for each component.
Next, we (4) generate a flat-foldable component from the top panel and cross-section polylines and then modify the polylines again as needed.
Finally, we (5) combine flat-foldable components and output a foldable model.

Π AB

Convex parts

A

FA

B

FB

Top panels
Convertedfoldable models

Outline offoldable models

Figure 7: Influence of the folding direction of a flat-foldable component. The different folding directions (white arrows outlined inblue) yield different shapes of flat-foldable models.

Figure 9: Trimming B’s top panel to ensure a side panel parallelto the connecting plane ΠAB for attaching component A.
4.2. Generating Top Panel
Given the user-specified folding direction, we first generate theinitial shape of the top panel, and then optimize its size and position. The initial shape of the top panel is generated as follows. Our
method
1. Projects vertices of the convex component to a plane perpendicular to folding direction and convert them to points in 2D space,
2. Generates a 2D convex hull from the 2D points, and
3. Reduces vertices (and resp. edges) of the polygon up to the userspecified number, N min .

Figure 8: Folding direction with a larger top panel (right) yields
smaller spread after folding than that with a smaller top panel(right), resulting in less collisions during folding.
the other hand, the other model in the lower row is created using
the folding direction from back to front. In this case, the top panel
is not visible in front view, but the bottom panel is visible as the flat
polygon. Note that the ears are attached in different orientations.
As a criteria to determine the folding direction of each component, we consider the fact that a folding direction with a larger top
panel yield smaller spread in the flat-folded state (Figure 8), which
is beneficial to less collisions with other components during folding. We thus let the user specify a folding direction perpendicular
to the first principle direction of the component shape.

For the edge reduction in step 3, we use the algorithm by Dyken etal. [DDS09].
4.2.1. Trimming top panel for attachment
When designing the top panel, we trim the top-panel polygon to
generate side panels for attaching other flat-foldable components.
Figure 9 illustrates an example. Let A and B be mesh segments andΠAB be a plane fitted using least-squares to vertices located at theirinterface. To attach A to B, B should have a side panel parallel toplane ΠAB . Such side panel is defined by its cross-section polyline,
and such polyline is specified by the corresponding top-panel edge.
We therefore generate a top-panel edge parallel to plane ΠAB bytrimming the top panel. If one of B’s top-panel edges is almost
parallel to plane ΠAB , we do not trim B’s top panel but use such toppanel edge (and the corresponding side panel) of B. After ensuringsubmitted to Pacific Graphics (2017)

Miyamoto, Endo, Kanamori and Mitani / Semi-Automatic Conversion of 3D Shape into Flat-Foldable Polygonal Model𝑥𝑧

Top panel𝑦Polygon
model

×s0

×s0

Top panel

Top panel

Ej

Ej

5

Connecting
panel
Ej

×s0
×s0 Λ

p0

0

Λ2

v

Λ1

Configuration ofpolygon model

u

Πj

p1
p2

Cross-section polylines

Figure 10: Simplified model for optimizing the top panel. Polygons Λ0 ,Λ1 , and Λ2 are of the same shape as the initial top panel,jjj
and contain p0 , p1 , and p2 of cross-section polylines, respectively.
Scales s0 , s1 , and s2 as well as other parameters are optimized toobtain the polygon model shown in upper right.
B’s side panel for attaching A, we simply rotate and translate A to
attach A onto B.
Note that the attached bottom panel of A might be toolarger/smaller than B’s side panel. In that case, the user re-designs
the shapes by tuning the shape fidelity parameters (see Section 5.1).
4.2.2. Optimizing top panel
To optimize the size and position of the top panel, we also haveto consider how well the corresponding cross-section polylines(i.e., centerlines of side panels) approximate the initial component
shape. We simplify this problem by separating the optimizations
for the top panel and cross-section polylines; here we optimize
only the top panel with quite simplified cross-section polylines thatroughly approximate the component shape, and later, with the fixed
top panel, optimize cross-section polylines (Section 4.3).
Figure 10 illustrates the simplified model for optimizing the top
panel. In this model, each cross-section polyline has only three verj
j jtices and two edges, and vertex pi = (ui , vi ) (i = 0, 1, 2) in eachcross-section polyline P j has the same v coordinate. Let Λ0 , Λ1 ,and Λ2 be polygons that are parallel copies of the initial top panel
j jjand contain p0 , p1 , and p2 , respectively.
To roughly approximate the initial component shape with thissimplified model, we optimize the following eight parameters.
jjj

1. Scales s0 , s1 , and s2 for each u-coordinates u0 , u1 , and u2 (3parameters).
jjj
2. v coordinates v0 , v1 , and v2 (3 parameters).
3. x, y coordinates of the centroid of the simplified model (2 parameters).
Note that we omit the z coordinate of the centroid because theheight is already considered with the v coordinates.
Let V0 be the set of vertices in the initial component shape, andV be the set of vertices of the simplified model. We optimize theeight parameters by minimize the following energy function:∑∑E=
min dist(a s , b) +(3)
min dist(bt , a)
a∈VA

b∈VB

submitted to Pacific Graphics (2017)

b∈VB

a∈VA

Πj

Πj

Figure 11: Generating an initial polyline by connecting intersections (red) of the convex hull with cross section Π j corresponding
to the top-panel edge E j (left). To attach another component, we
insert an edge into the polyline (right), which is parallel to the component’s panel to be attached.
s.t. v0 >v1 > v2 ,

j

j

j

(4)

0 <si ≤ 1,

(5)

j
j
Hmin ≤ v2 , v0 ≤ Hmax .

(6)

Eq. (3) is the sum of the shortest distances between the initial component shape and the simplified model, approximating the exclusive OR of their volumes. Constraint (4) is to arrange vertices consistently in v direction. The condition 0 < si in constraint (5) prevents inversion in the simplified model. The condition si ≤ 1 is toshrink polygon Λi from its initial size; polygon Λi initially has thesame shape as the top panel and is expected to shrink. Constraint (6)is to keep the height of the simplified model within the specified
range, where Hmin and Hmax denote the lower and upper bounds ofthe heights of the top and bottom panels along the folding direction.
Note that foldability of cross-section polylines is omitted in this optimization because here we focus on appropriate size and positionof the top panel. We consider the foldability of cross-section polylines in the next subsection.
4.3. Generating Cross-section Polylines
Given the top panel optimized in the previous subsection, we obtain initial cross-section polylines as follows. For each cross section
Πi passing through the midpoint of top-panel edge E j , we calculateintersection points of edges on the convex component, and use themas the initial set of vertices of polyline P j (Figure 11, left). Because
we seek for convex components, vertices in the initial polylines are
removed if they do not contribute to convex hulls.
Additionally, we also have to consider inter-component attachments, similar to the discussion in Section 4.2.1. To attach a component, we need a side panel that is parallel to the target component’s
panel to be attached. We thus insert a line segment that defines suchside panel to the cross-section polyline P j . Specifically, we project
the vertices of the attaching panel onto cross section Π j , and insert
a segment covering the projected vertices (Figure 11, right). Note
that, if there are no projected vertices within the range of the top
and bottom panels, we do not insert a line segment, e.g., in the casethat the attaching panel is parallel to the top panel.
4.3.1. Optimizing polylines independently
This section describes how to optimize each cross-section polylines to be foldable independently, without considering other poly-Miyamoto, Endo, Kanamori and Mitani / Semi-Automatic Conversion of 3D Shape into Flat-Foldable Polygonal Model

6

Iterate
(1) v

(2) v

p0

p0

O p
M-1
Initialu

O pM-1
Simplify

(3)

u

O

v

v

O

v

(4) v

O

u

O
Adjust position of each convex
fold vertex and select best one

(5) v

u

O

Adjust position Select polyline withminimum εof blue vertices

Figure 12: Optimization of a cross-section polyline. pi (i = 0, 1, 2, · · · , M − 1) and p̂i0 (i0 = 0, 1, 2, · · · , k − 1) are vertices before and after
simplification. (1) We remove vertices of the polyline until the number of vertices becomes k (3 ≤ k < kmax ). We then (2) adjust the positionof the convex-fold vertex and select the polyline with the smallest gap , and (3) adjust the positions of all vertices. If k < kmax , we return toStep (3).

lines. The basic procedure is to generate candidate polylines bysimplification and optimization, and to select a simplified polylinethat has the smallest gap  among the candidates. The details areillustrated in Figure 12 and explained as follows.
1. We generate candidate polylines by simplifying the initial polyline P j with different numbers of vertices. Let k be the numberof vertices in a simplified polyline P̂kj . Note that p0 and p M−1
are fixed, and vertices belonging to the line segment parallel tothe connecting plane are only allowed to move in parallel to theplane. We iterate the following steps from k = 3 to k = kmax ,where kmax is the maximum number of vertices specified by theuser.
2. For each simplified polyline P̂kj , we pick each vertex ph (h =1, 2, · · · , k − 2) as a candidate of a convex-fold vertex, optimizeP̂kj , and then examine the gap . Here we optimize the uv coordinates of only ph using Eq. (7) with a constraint vh+1 < vh < vh−1
to avoid vertical flip. We then determine ph with the smallest
gap  as the convex-fold vertex of simplified polyline P̂kj .
3. For each simplified polyline P̂kj with different k, we optimize
the whole shape of P̂kj using Eq. (7) with the constraint (11) andexamine the gap . Again, p0 , p M−1 and vertices belonging to
the line segment parallel to the connecting plane are constrained
as Step 1. Finally, we select P̂kj with the smallest gap  as theoutput of this procedure.
To simplify a polyline in Step 1, we used the Douglas-Peucker
algorithm with a slight modification; we reduce vertices until thenumber of points becomes less than the specified number. The purpose of adjusting only one convex fold vertex in Step 2 is to choose
more appropriate folding configuration before optimization of allvertices, and to suppress the influence of the change of the shape asmuch as possible in only the convex fold vertex.
We define an energy function by considering foldability and fidelity of the simplified cross-section polyline to the initial polyline,
and adjust positions (i.e., u and v coordinates) of vertices by mini-

mizing the energy function as follows.
E = w s E s + wg Eg + wc Ec ,(7)

where E s , Eg and Ec are energy terms described hereafter, and w s ,wg , and wc are the weights. We empirically choose w s = 0.7, wg =1.0, and wc = 0.9.
Shape fidelity term. To prevent an adjusted polyline from differing from original shape during optimization, we add the following
term:
E s = dH ({pi }, {p̂i0 }),(8)

where dH (A, B) denotes Hausdorff distance between points set A
and B, and pi (i = 0, 1, 2, · · · , M − 1) and p̂i0 (i0 = 0, 1, 2, · · · , k − 1)
are the vertices before and after simplification.
Foldability term. We regard a cross-section polyline as flatfoldable if its gap  is less than a tolerance τ. Similarly to the baseline method [KKM15], we use τ = 0.001 × l, where l is the averagesegment length of the cross-section polyline. To minimize gap ,
we add the following term:
Eg = u M−1 − u0 −

h−1
∑
i=0

li +

M−1
∑

li ,

(9)

i=h

where h is an index of a convex fold vertex of the cross-section
polyline.
Convexity term. The cross-section polyline should be as convex
as possible so that it is flattened outward. To measure the convexityof the line, we define a new term that is the sum of distance between an edge pi−1 pi+1 . If it equals zero, the shape of the polyline
is convex to outward. The new term is:

M−2

∑

i f θi ≤ π
0
Ec =
di ,
di = 
(10)dist(p̂i−1 p̂i+1 , p̂i ) otherwise
i=1
submitted to Pacific Graphics (2017)

Miyamoto, Endo, Kanamori and Mitani / Semi-Automatic Conversion of 3D Shape into Flat-Foldable Polygonal Model
v

p j1
θ1

θ2

p1
p2

θ3

Lj1

1
Lj+1

p3

1
Lj-1

mj
Top panel

u

1
I j-1

1
I j+1

1
I j-1

1
I j+1

1
c j+1

p j1
mj

7

mj

1
c j-1

Top panel

1
Lj+1
1
c j+1

Lj1

Figure 13: Angles θi are calculated counterclockwise.

Figure 14: Top views of an invalid mesh (left) as well as top (middle) and oblique (right) views of a valid mesh.

where dist(E, p) is the Euclidean distance between edge E andpoint p. θi is a counterclockwise angle between vectors p̂i+1 − p̂iand p̂i−1 − p̂i (see Figure 13).

be the midpoint of top-panel edge E j , we can define I ij+1 as the

To avoid inconsistent ordering in the vertical direction, we minimize Eq. (7) with the following constraint:
vi+1 < vi < vi−1 .

intersection of a line pij m j and Lij+1 . This is shown in middle of
Figure 14.
The conditions under which collision occurs are described as:(11)

Note that there are cases where the gap  does not become lessthan τ. Thus, we iterate optimization while decreasing w1 and w3
until gap  becomes less than τ because foldability is more important than shape fidelity and convexity.
To solve this optimization problem, we use gradient descent withnumerical differentiation, starting from the initial shape that satisfies all the constraints. If we violate constraints during an iteration,
we halve the step size and re-evaluate the iteration. Particularly, if
we violate constraint (11) at vertex i, we replace vi with a valueslightly smaller than vi−1 . To keep the direction of the line segment
parallel to the connecting plane, the vertices consisting of the line
segment are constrained to move only along that direction. This isaccomplished by parameterizing the endpoint with a scalar value
and a unit directional vector, and by optimizing the scalar value
instead of u, v coordinates of the endpoint.
In the results shown in Section 5, our optimization always converged probably thanks to good initial shapes, and yielded flatfoldable models mainly because we choose a flat-foldable configuration among several candidates as in Step 2.

kpij − m j k − kI ij+1 − m j k > 0,

(12)

kpij − m j k − kI ij−1 − m j k > 0,(13)

where, because I ij+1 and I ij−1 are on the same line, the condition
under which collision does not occur is defined as:
kpij − m j k − min(kI ij+1 − m j k, kI ij−1 − m j k) ≤ 0.

(14)

The absolute value of the left side of Eq. (14) is equal tomax(kI ij+1 −pij k, kI ij−1 −pij k). Therefore, to generate foldable polygonal components properly, we modify the polylines by minimizing
the energy function with an additional objective function:
Ef =

N−1
∑ M−2
∑

max(kI ij+1 − pij k, kI ij−1 − pij k),(15)

j=0 i=1

and we update Eq. (7) to the following energy function:
E = w s E s + wg Eg + wc Ec + w f E f ,(16)

where we used the weights w s = 0.01, wg = 1.0, wc = 0.01, andw f = 1.0. We optimize Eq. (16) for each polyline until convergence.
5. Results

4.4. Optimizing Polylines While Avoiding Collisions with
Neighbors
In Section 4.3 we optimized each cross-section polyline separately. However, the side panels may collide with each other depending on shape of the adjacent cross-section polylines, and thus
we cannot generate foldable polygonal components sometimes.
Therefore, to generate a foldable polygonal model properly, thissection describes a method to modify the vertex positions of theentire polylines by considering relationship of vertices of the adjacent cross-section polylines.
Here, we explain the collision of the side panels by using Figj+1
ure 14. First, we define some symbols. Let ci in the P j+1 is ajpoint that have same v-coordinate as pi .
To explain the collision, we consider two lines; the one line Lij+1
includes cij+1 and is parallel to top-panel edge E j+1 , and the otherline Lij includes pi and is parallel to top-panel edge E j . Letting m j
submitted to Pacific Graphics (2017)

We implemented our algorithm using C++, and ran our programon a PC with an Intel Core i7 and 8GB RAM. We used the CGAL
C++ library for segmenting an input 3D mesh model and converting segments into multiple convex components.
Figure 18 shows the foldable polygonal models generated by using our system, and Figure 19 shows the animation of folding thesemodels. Figure 20 shows the fabricated physical paper prototypes
from development planes. For physical assembly, we used tapes
and bond for attachment. These results demonstrate that our system can convert input 3D models into foldable models, and theconverted models can be folded in the real world. Table 1 shows
the computation time. The segmentation includes a process of dividing and converting to multiple convex components. In addition,
the conversion of foldable model includes generation and optimization of the top panel, generation and optimization of cross-section
polylines. According to Table 1, the segmentation takes longer time
when the number of vertices is larger. This is because it takes time
to convert to convex shape rather than segmentation. On the other8

Miyamoto, Endo, Kanamori and Mitani / Semi-Automatic Conversion of 3D Shape into Flat-Foldable Polygonal Model

Before folding

After folding
Folding process

Figure 16: Comparison of our result (middle) created semiautomatically from the input mesh (left) and a manually-createdmodel (right) using the method by Kase et al. [KKM15].

Figure 15: Collision might occur if we fold multiple components
simultaneously (upper row) but we can usually avoid collision byfolding each component one by one (lower row).
hand, although the number of models and the number of vertices
affect calculation time, there is not much difference in calculation
time for each foldable component.
Some flat-foldable models require attention to avoid collisions
during folding. For example, when we fold the bunny’s head modelin Figure 15, the ears might collide with each other if we fold themsimultaneously (upper row). However, collisions do not occur if wefold each ear one by one (lower row). In case that self-collision is
unavoidable (we did not experience this situation in our results; collisions are usually avoidable as in Figure 15) or the resultant shapeis unfavorable, the user can re-design the model with additional interactions, as described in the following subsection.
5.1. Influence of User Interactions
Our method is automatic except for the following user interactions; the user specifies the folding direction of each flat-foldable
component (Section 4.1.1) and tunes the shape fidelity parameters,i.e., N min (Section 4.2) and kmax (Section 4.3.1). As GUIs, the user
specifies the folding direction by rotating it around the principle
shape axis using the mouse wheel, and N min and kmax using spinners, respectively. The folding direction can be specified for eachcomponent independently, as demonstrated in Figures 7 and 19 as
well as the accompanying video. If the user-specified folding direction is almost parallel to the current connecting plane (Figure 9), wequit using the connecting plane and instead use the top or bottom
panels as a new connecting plane.
Shape fidelity can be controlled by changing N min and kmax . Table 2 summarizes the Hausdorff distance as an error metric between
the resultant shape and the initial convex shape of each componentof Bunny. The Hausdorff distances are normalized by the diagonallength of Bunny’s bounding box. With larger N min and kmax , theHausdorff distance decreases but the difficulty in flat folding increases because of the more top-panel edges and more side-panel
hinges.
5.2. Comparison with Kase et al. [KKM15]
Figure 16 shows a comparison of our method and the method byKase et al. [KKM15] in terms of quality and time required for design. Our result (middle) was created semi-automatically from the

Input

Foldable

Figure 17: The hole in the input mesh (left) is lost in the flatfoldable convex component (right).
input mesh (left) while their result (right) was manually designedwith a moderate effort to make the result resemble the original. The
time required for designing the models with several trial-and-errors
are about 20 minutes and 50 minutes, respectively. In general, while
the method by Kase et al. [KKM15] provides much greater degreesof-freedom in the designing process, our method yields plausible
results in a shorter time.
Our design restriction that each flat-foldable component shouldhave a convex shape (Section 3.3) affects the resultant shapes. For
example, geometric details such as Bunny’s eyes or ears are lost in
Figure 18. Even worse, if the target polygonal model has a hole, thehole will be lost in its convex hull (Figure 17). This issue can be alleviated by increasing the number of segmented components, withincreased difficulty in the shape design and physical realization.

6. Conclusions and Future Work
We have proposed a system that converts input 3D shape into
foldable shape of polygonal models semi-automatically. The user
specifies folding direction of each divided convex component fromdirections perpendicular to a first principle component of the vertices of the convex component, and the minimum number of edges
of a top panel and the maximum number of cross-section polylines.
We demonstrated that our system can generate foldable polygonalmodels.
As the most interesting future direction, we would like to loosen
the convex shape constraint for each component (Section 3.3) in order to increase the shape approximation fidelity. Although allowing
concave components will increase the designing and folding labor,
the labor might be alleviated if we can actuate a foldable model
mechanically [KMM17].
submitted to Pacific Graphics (2017)

Miyamoto, Endo, Kanamori and Mitani / Semi-Automatic Conversion of 3D Shape into Flat-Foldable Polygonal Model

SnowmanTeapot

Bunny

Teddy

9

Armadillo

Input
Segmented
Foldable
Figure 18: Examples of input models and resultant flat-foldable models. Left column: Input models. Middle column: Convex hulls of segmented meshes. Right column: Flat-foldable components.

SnowmanTeapot

Bunny

Teddy

Figure 19: Example animation sequences of flat-foldable models.
submitted to Pacific Graphics (2017)

ArmadilloMiyamoto, Endo, Kanamori and Mitani / Semi-Automatic Conversion of 3D Shape into Flat-Foldable Polygonal Model

10

Table 1: Statistics of resultant flat-foldable models.

SnowmanTeapotBunny
Teddy
Armadillo# of input faces(# of components)
13,450 (6)6,543 (6)4,968 (5)3,192 (8)17,296 (15)Segmentation
(sec)
771
148
13
27
63

Conversion of
foldable model (sec)
234
193
194
174
449

Total time
(sec)
1,005
341
207
201
512

Table 2: Approximation errors of Bunny’s components w.r.t. N min and kmax .
N min
5
5
8
5
4

kmax
6
10
6
3
6

Left ear0.048 (5)0.046 (5)0.049 (8)0.044 (5)0.051 (4)Hausdorff distance (# of vertices of top panel)
Right ear
Head
Body
Foot
0.038 (5) 0.056 (5) 0.092 (5) 0.098 (5)0.034 (5) 0.063 (5) 0.087 (5) 0.097 (5)0.052 (8) 0.039 (8) 0.093 (8) 0.081 (8)0.047 (5) 0.062 (6) 0.097 (5) 0.101 (5)0.032 (4) 0.055 (5) 0.100 (5) 0.092 (4)average
0.066
0.065
0.063
0.070
0.066

foldable 3D polygonal models. In Mechanisms and Robotics Conference(2015), pp. DETC2015–46566. 1, 2, 6, 8
[KMM17] Kilian M., Monszpart A., Mitra N.: String actuated curved
folded surfaces. ACM Transactions on Graphics 36, 3 (2017). 8[LHAZ15] Li H., Hu R., Alhashim I., Zhang H.: Foldabilizing furniture. ACM Transactions on Graphics, (Special issue of SIGGRAPH Asia
2014) 34, 4 (2015), 90:1–90:12. 2[MS04] Mitani J., Suzuki H.: Computer aided design for origamic architecture models with polygonal representation. In Proc. of CGI 2004
(2004), pp. 1372–1379. 2[SSCO08] Shapira L., Shamir A., Cohen-Or D.: Consistent mesh partitioning and skeletonisation using the shape diameter function. The VisualComputer: International Journal of Computer Graphics 24, 4 (2008),
249–259. 2, 3
[TM12] Tachi T., Miura K.: Rigid-foldable cylinders and cells. The International Association for Shell and Spatial Structures 53, 4 (2012). 2[XTGH11] X.Li, T.Ju, Gu Y., Hu S.: A geometric study of v-style popups: Theories and algorithms. ACM Transactions on Graphics 30, 4(2011), 98:1–10. 2

Figure 20: Examples of physical paper prototypes of flat-foldable
models.

[YYT∗ 13] Yasuda H., Yein T., Tachi T., Miura K., Taya M.: Compression
behavior of tachi-miura polyhedra bellows. Proc. of the Royal Society A
469, 2159 (2013). 2

References[BDH96] Barber C. B., Dobkin D. P., Huhdanpaa H.: The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software
22, 4 (1996). 3[DDS09] Dyken C., Dæhlen M., Sevaldrud T.: Simultaneous curve simplification. Journal of Geographical Systems 11, 3 (2009), 273–289. 4[IEM∗ 11] Iizuka S., Endo Y., Mitani J., Kanamori Y., Fukui Y.: An interactive design system for pop-up cards with a physical simulation. The
Visual Computer (Proc. of Computer Graphics International 2011) 27,
6-8 (2011), 605–612. 2[JLYL14] Jr C. R. R., Le S. N., Yu J., Low K.-L.: Multi-style paper
pop-up designs from 3D models. ACM Trans. on Graphics 33, 2 (2014),
487–496. 2[KKM15]

Kase Y., Kanamori Y., Mitani J.: A method for designing flatsubmitted to Pacific Graphics (2017)