FlatFolder: A Crease Pattern Solver
FlatFolder is software written by Jason S. Ku to compute and analyze valid flatfoldable states of flatfoldable crease patterns, both assigned and unassigned.
How to use

Go to FlatFolder.
 Tested to run in Chrome, Firefox, and Safari.
 Chrome usually runs slightly faster than Firefox and much faster than Safari.
 You should see the following interface:

Press “Upload” to upload a crease pattern in FOLD, SVG, OPX, or CP file formats.
 Various example files can be found in the
./examples/
folder. You can download them by clicking here.
 If you have examples files that you’d like me to add (and you have the proper authorization of the creator), please email them to me!
 The software will probably have trouble if points in the input file are
not accurate to singleprecision. When importing any file that does not
already contain face information, FlatFolder will look at all the lines
imported and compute the length $L$ of the shortest one. Then:
 if any vertex of the input is closer than $\varepsilon = L/300$ to any other vertex, it will assume they are the same vertex; and
 if any vertex of the input is closer than $\varepsilon$ to any line, it will assume the vertex is on the line.
 For SVG format:
 the import assumes each imported line is an unassigned fold
(assignment
"U"
), unless its"style"
attribute contains a"stroke"
whose value is one of["red", "blue", "gray"]
corresponding to["M", "V", "F"]
assignments respectively;  will also accept values
["#FF0000", "#0000FF", "#808080"]
.
 the import assumes each imported line is an unassigned fold
(assignment
 For FOLD format:
 Import requires two properties:
vertices_coords
edges_vertices
 Import can also import two optional properties:
edges_assignment
(if missing, will assume all edges are unassigned"U"
)faces_vertices
(if missing, will construct its own set of faces from the provided edges) on import, will reorder faces to be increasing by area
 Import requires two properties:
 Various example files can be found in the

Once uploaded, FlatFolder will draw:
 the crease pattern on left of the display,
 an xray view of the folded crease pattern in the middle of the display, and
 a red circle behind any vertex of the imported crease pattern that
violates either Maekawa or Kawasaki’s theorems.
 For Kawasaki, it checks whether the ((sum of even angles) $ \pi$)
is greater than
0.00001
.
 For Kawasaki, it checks whether the ((sum of even angles) $ \pi$)
is greater than
 Selecting the “Text” option will draw index labels for all the vertices, edges, and faces in the crease pattern. Currently, there is no way in the interface to adjust the font size, so this is only useful for debugging small inputs or by manipulating the text later in an output SVG.

Press “Fold” to find flatfoldable states of the crease pattern.
 FlatFolder will break up the faceOrder variables into disconnected components of variables whose set of solutions are independently assignable from each other.
 You can limit the number of solutions to find per component by setting the
“Limit” option:
all
is defaut. This will attempt to compute all possible folded states. Alternatively, you can select a number from [1, 10, 100, 1000], which will correspond to the maximum number of solutions to find per component.

After computing the overlap graph:
 FlatFolder will replace the xray view with the overlap graph.
 Selecting the “Text” option will now also draw index labels for all the cells, segments, and points in the overlap graph.
 Clicking on a cell in the overlap graph will highlight:
 the faces of the crease pattern that overlap the cell (yellow), and
 the edges of the crease pattern that overlap the segments bounding the cell.

Clicking on a face of the crease pattern will highlight:
 the cells of the overlap graph that overlap the face (yellow),
 the segments of the overlap graph that overlap the edges bounding the face, and
 the other faces of the crease pattern that overlap the selected face in the folding (blue). Each blue face corresponds to a faceOrder variable (the yellow and blue faces overlap, so much be assigned an order).
 Clicking on one of the blue faces will highlight the
features of the corresponding faceOrder variable:
 its two faces (yellow),
 its tacotaco constraints (green),
 its tacotortilla constraints (red),
 its tortillatortilla constraints (orange), and
 its transitivity constraints (blue).

After computing solutions for all components:
 FlatFolder will display how many valid flatfolded states were found.
 If any states were found, FlatFolder will draw a rendering of the first one on the right of the display.
 Selecting the “Flip” option will redraw the folded state as seen from the other side.

A “Component” dropdown menu is added to aid in selecting other states.
 The “none” option hides all display of component information.
 The “all” option draws every component found on the overlap graph in a randomly assigned color.
 There is one numeric option (zeroindexed) for each component found.
Selecting a component will:
 draw that component on the overlap graph,
 display the number of states found for that component, and
 add a numeric input to enter which state to select for that component.
 Changing this number will redraw the flatfolded state based on the change.

You can change states of each component until you reach a desired state.

Press “Export” to generate export links to various outputs.
 Clicking “cp” downloads the crease pattern in FOLD format.
 Clicking “state” downloads the current folded state in FOLD format.
 Clicking “img” downloads a snapshot of the current display in SVG format.
 Clicking “log” downloads a text file of all console output since the most recent file was imported.
Algorithm
Existing software like ORIPA and Orihime/Oriedita find flatfoldable states by:
 constructing an overlap graph of cells, where each cell is a maximal regions of points in the folded image that overlap the same set of crease pattern faces, and
 finding an ordering of faces in each cell that avoids selfintersection of the paper.
FlatFolder takes a different approach for step (2) that makes it easier to compress the set of output states. In the following, we take $n$ to be the number of faces in the input crease pattern.

First, it finds each pair of faces
[f, g]
that overlap in the folding and identifies the pair as a Boolean variable that can have one of two possible assignments: eitherf
is overg
org
is overf
. There are at most $O(n^2)$ variables, which are computed by FlatFolder in $O(n^4)$ time. 
Next, it computes all constraints on those variables that must be satisfied to avoid selfintersection. There are four types of constraints:

TacoTaco: A tacotaco constraint occurs when two folded edges
[e1, e2]
of the crease pattern properly overlap along a segments
of the overlap graph, and of the two faces[f1, g1]
adjacent to edgee1
and the two faces[f2, g2]
adjacent to edgee2
, all of them lie on the same side of segments
in the folding. There are six variables associated with such a constraint:[f1, g1]
,[f1, f2]
,[f1, g2]
,[f2, g1]
,[f2, g2]
,[g1, g2]
 Out of the $2^6 = 64$ possible assignments of these variables, only 16 of them are valid (avoid intersection).
 There are at most $O(n^2)$ tacotaco constraints.

TacoTortilla: A tacotortilla constraint occurs when a folded edge
e
of the crease pattern adjacent to faces[f1, f2]
properly intersects the interior of a third facef3
along some segments
in the overlap graph. Alternatively,e
properly overlaps a crease edgee2
that is not folded in the folding (has assignmentF
), and we letf3
be the face adjacent toe2
that lies on the same side ofs
in the folding asf1
andf2
. There are are three variables associated with such a constraint:[f1, f2]
,[f1, f3]
,[f2, f3]
 Out of the $2^3 = 8$ possible assignments of these variables, only 4 of them are valid (avoid intersection).
 There are at most $O(n^2)$ tacotaco constraints.

TortillaTortilla: A tortillatortilla constraint occurs when two crease edges
[e1, e2]
(has assignmentF
) of the crease pattern properly overlap along a segments
of the overlap graph, and of the two faces[f1, g1]
adjacent to edgee1
and the two faces[f2, g2]
adjacent to edgee2
,f1
andf2
lie on one side ofs
, andg1
andg2
lie on the other side ofs
. There are two variables associated with such a constraint:[f1, f2]
,[g1, g2]
 Out of the $2^2 = 4$ possible assignments of these variables, only 2 of them are valid (avoid intersection).
 There are at most $O(n^2)$ tacotaco constraints.

Transitivity: A transitivity constraint occurs when three faces
[f1, f2, f2]
all mutually overlap the same cell of in the overlap graph. There are are three variables associated with such a constraint:[f1, f2]
,[f1, f3]
,[f2, f3]
 Out of the $2^3 = 8$ possible assignments of these variables, only 6 of them are valid (avoid intersection).
 There are at most $O(n^3)$ tacotaco constraints.
The variables and constraints form a bipartite constraint graph with one vertex for each variable and constraint, with an edge between a variable and a constraint if the constraint is associated with the variable. This graph has size $O(n^3)$ and is computed by FlatFolder in $O(n^5)$ time.


If the crease pattern is mountain/valley assigned, each edge assignments forces the assignment of one Boolean variable. FlatFolder makes these assignments, and assigns any variables that can be infered from those assignments according to the constraints. This step takes $O(n^3)$ time.

After removing any the variables that may have been assigned in the last step from the constraint graph, the graph may be disconnected into multiple unconnected components. If it is variables in one component cannot have any effect on variables in another component, so their assignments are independent. This step takes $O(n^3)$ time.

Lastly, FlatFolder finds valid solutions for each connected component of variables via a bruteforce search. This step can take exponental time $2^{O(n^2)}$ but if each component has only a polynomial number of solutions, solving each connected component independently can implicitly represent an exponential number of folded states in polynomial time.