A file has no paper

The field’s interchange format is a small thing and it is the right small thing: an array of vertex coordinates, an array of edges given as pairs of vertex indices, and an array of letters — mountain, valley, boundary, flat, unassigned — one per edge. Faces are optional. Everything else in a file is metadata.

That is exactly the object this collection computes with. Not a translation of it, not a serialisation: the same three arrays under the same names, which is why exporting a pattern here is nine lines of metadata and no converter. The format is a description of what the subject decided a crease pattern is.

Which makes it a good place to ask what that decision left out.

A list cannot forbid a crossing #

Two edges in the list cross when the segments they describe meet at a point that is not an endpoint of either. Nothing in the format prevents it, and nothing could: the arrays record which vertices an edge joins, and a crossing is a relation between two edges that neither of them mentions.

So a file containing a crossing is well-formed. It parses, it loads, its vertices can be checked against every theorem the subject has — and it describes a pattern that has no flat folded state, for a reason no reader of the arrays will find.

This is not hypothetical. Four of this collection’s own tessellation patches exported exactly that: valid files, every vertex satisfying developability, Kawasaki, Maekawa and the big-little-big lemma, and 12, 18, 12 and 5 crossings between them.

Why a validator would not have caught it #

The natural response is that a file format should come with a validator, and that a validator should reject a pattern whose edges cross. Both are reasonable and neither would have helped, for two separate reasons.

A crossing is expensive relative to the rest of validation. Checking that indices are in range, that arrays are the same length, that letters are from the vocabulary — all of that is one pass. Checking that no two edges cross is a comparison of every pair. It is not a large cost in absolute terms, and it is a different kind of check: the others are about the file and this one is about the geometry the file denotes.

And a crossing is sometimes what was meant. A drawing may legitimately contain lines that cross: a construction diagram, a figure showing two candidate patterns superimposed, a file that is a stage in a pipeline before subdivision. A format that refused them would refuse things people want to store.

So the right place for the check is not the format. It is whoever is about to claim that a file folds — which is to say, it is here, and it took years.

What a file has no place for #

Two things about a sheet of paper have no representation at all, and they are the two this collection has needed most recently.

Where the paper is. The format marks an edge as boundary, which says this edge is on the outline, and that is all. A pattern whose edges are all creases makes no statement about where the sheet stops — and the checks that decide whether a vertex is interior read the boundary edges, so a pattern without them treats every vertex as interior. That is exactly what happened to the tessellation patches: their crease lists carry four boundary edges for the sheet’s rim and nothing else, so the patch’s own outline is invisible to every question about it.

A cut. The letters describe how an edge folds — up, down, flat, unknown — or that it is on the boundary. None of them says that the paper is separated along an edge with paper on both sides. That distinction turns out to matter: a cut removes an adjacency, which is the only operation that can break a cycle in the panel graph, and this collection had to add a sixth letter to its own patterns to express it.

Both omissions have the same character. The format records what a crease pattern is made of, and the two missing things are facts about the paper the pattern is drawn on.

The two arrays that are the same length #

There is a quiet structural fact in the format that is worth pulling out, because it is where the crossing hides.

The list of edges and the list of letters are parallel arrays: the nth letter belongs to the nth edge. That pairing is the whole of what an assignment is, and it means a crease is defined by its two endpoints and nothing else. Two edges are related only if they share a vertex index.

So the file’s notion of adjacent is shares an index, and the paper’s notion is meets on the page. Those agree exactly when the pattern has been subdivided — every meeting given a vertex — and they come apart otherwise, in two directions at once: two edges can share an index and be drawn as one straight line, and two edges can cross and share nothing.

The first case is harmless and common: a crease drawn as several collinear edges is the same crease. The second is the fault. And the reason the format cannot legislate either is that both are questions about coordinates, and the coordinates live in a third array the assignments never look at.

The cost argument does not survive the arithmetic #

One of the two reasons given above is worth checking rather than accepting, because it is the kind of claim that sounds like engineering and is not.

Comparing every pair of edges on the largest patch here — 282 creases — is 39,621 segment tests, and a sweep line does the same job in about 2,300 steps. Either figure is far below what the vertex conditions already cost: 126 interior vertices, four conditions apiece, each reading a sorted list of sectors.

So a crossing check is not expensive relative to the rest of validation. It is cheaper. The first reason is wrong, and the second one is doing all the work: a format has to be able to store what people mean, and people sometimes mean crossing lines.

That matters because it changes where the check belongs. It is not omitted from the format as a performance compromise; it is omitted because it is not a question about the file at all.

And the face count is decidable from the array lengths #

Which turns the third step of the procedure into arithmetic. For a connected planar graph, Euler gives

$$F = E - V + 2,$$

so the number of faces a file’s own arrays imply is fixed before any geometry is computed. A file listing a different number of faces is inconsistent with itself, detectable in the time it takes to read two array lengths.

Better, the discrepancy is diagnostic. Each crossing subdivides two edges at one new point — $V + 1$, $E + 2$ — so it adds exactly one region to the drawing while the file’s arrays know nothing about it. The regions a reader can count on the page, minus $E - V + 2$, is the number of crossings, without finding any of them.

That is the cheapest form of the first step: a count against a count, before a single pair of segments is compared.

What a reader of a file should do first #

The practical conclusion is a short procedure, and it is the one this collection now runs.

Subdivide before believing anything. Cut every edge at every point another meets it, and count the vertices that had to be invented. If the count is not zero, the file’s list and the file’s drawing are different objects, and every question asked of the list is being asked of the wrong one.

Then read the boundary. A file with no boundary edges has no statement about where the paper is, and every vertex condition applied to it is being applied to a pattern with no edge — which passes more readily than it should.

Then ask for the faces. If the file has them, check that they cover the region the boundary encloses; if it does not, compute them and find out whether they can be computed at all. A pattern whose graph is in two pieces has no face structure to read, and that is a fact worth knowing about a file before folding it.

Three steps, none of them expensive, and all three about the geometry rather than about the syntax. A file that passes them is a file whose list and drawing agree.

The faces are the interesting optional #

One field in the format is optional and almost every consumer wants it: the faces. Without them a pattern loads into a folding tool as a drawing rather than as something that can be folded, so a file with no faces is one the recipient has to repair before using.

They are optional for a good reason. Reading them off requires planarising the pattern — subdividing every edge wherever another meets it and walking the result — which is a computation the format’s authors were right not to require of a writer.

That computation is the one that finds the crossings. So the file format’s optional field and this collection’s newest check are the same operation, arrived at from two directions: a consumer wants faces because it wants to fold the thing, and the walk that produces them cannot proceed past a crossing without inventing a vertex.

Of the eight patterns printed here, seven export faces. The fold-and-cut triangle exports edges only, because the outline being cut is not a crease and does not reach the sheet’s edge, so the pattern’s graph is in two pieces and containment cannot be read out of adjacency. The file says so rather than exporting faces that are wrong.

What the format got right #

It would be easy to read all of this as a complaint, and it is not one. Three decisions in that format are worth naming as good ones, and the first is the reason this collection has no converter.

The arrays are the natural representation. Vertices, edges, letters: a program that computes with crease patterns wants those three arrays, and a format that stores anything else would impose a translation on everyone.

The letters distinguish four things, and the distinction between flat and unassigned is the one that shows care — “not creased” and “not decided” are different statements, and a consumer averaging over assignments needs to be able to tell them apart. This collection’s export writes a fold angle of zero for the first and nothing for the second, which is only possible because the format kept them separate.

And faces are optional rather than required. A format that demanded them would demand a planarisation, which would have made a writer’s job much harder and would have pushed everybody toward writing the field wrongly.

The omissions are of a piece with those decisions rather than against them. A format defined by what a program needs will not carry facts that only paper has.

The unit that has nowhere to go #

One more omission is worth naming because this collection ran into it immediately and had to work round it in the only place available.

The format has no length unit. Coordinates are numbers; whether a unit means a millimetre, a metre or a sheet width is not stated anywhere in a file. For a format describing a mathematical object that is correct — a crease pattern is scale-free, and a Miura is a Miura at any size.

For a collection whose whole proposition is that a reader can print a pattern and fold it, it is a problem. The stated size has to be on the sheet, because a printer set to fit-to-page rescales silently and a reader deserves a way to notice. So the size is a fact about the artefact that the artefact’s own format cannot hold.

Where it goes here is the file’s description: coordinates are in sheet widths, and one unit is so many millimetres on the printable sheet. That is a sentence in a human-readable field, which is to say it is a comment. A consumer will not read it, and nothing checks it.

That is the honest state of the thing, and it is a fair example of how a format’s silences propagate. The subject decided a crease pattern is a graph; a graph has no size; so the one number a folder needs before touching the paper is stored as prose.

What a file is good for anyway #

None of the omissions makes the format a poor one, and the demonstration is that this collection publishes a file for every pattern it prints and would not do so if the files were useless.

A file loads into a folding tool and becomes an object that can be turned, coloured and folded on a screen. It can be diffed, so a change to a pattern is legible as a change rather than as two pictures. It can be checked by somebody else’s checker, which is the only real test a claim of foldability gets — an assertion that only its author has run is an assertion nobody has checked. And it is the same arrays the code computes with, so nothing is lost in the writing.

Against that, the omissions are the ordinary cost of a format being about one thing. What they require is that a claim about a file be made somewhere the file cannot make it — which is what an essay is, and why every pattern here has one.

What a notation records is what its makers thought the object was #

This collection has now met the same shape three times in three notations, and the three are two centuries apart.

The diagram notation — the arrows and dashed lines that made the subject cumulative — records a sequence, because its makers thought a model was a series of moves. It says nothing about the crease pattern, which is why a diagram can be followed and not analysed.

The crease pattern records a drawing, because the designers who published patterns thought a model was its creases. It does not decide the folded object, which is why a pattern needs a layer order the notation has no place for.

And the file format records a graph, because the people who wrote it were writing software. It cannot say where the paper is, cannot say that paper is separated, and cannot forbid two edges crossing — three facts about a sheet rather than about a graph.

None of those is a mistake. Each notation records the thing its makers were reasoning about, and each is silent about the things they were not. What follows for anybody reading a file is that the silence is not an absence of the fact, it is an absence of the question — and the question has to be asked somewhere else.

The letters are a vocabulary, and vocabularies are political #

A last observation, which is history rather than geometry.

Five letters is a decision about what kinds of line exist, and the five chosen are the ones a folding tool needs: two folds, a boundary, a line that is drawn and not folded, and one for “not yet decided”. They are the vocabulary of somebody rendering and simulating a pattern.

A different community would have chosen differently. A manufacturer would want a letter for a score line that is pressed and not folded; a paper engineer would want one for a slit; a teacher would want one for a line that is only a guide. Each of those exists in somebody’s practice, and each would have to be smuggled into this format as an unassigned edge with a note.

So the format is not neutral about what a crease pattern is, and could not be. It encodes the set of distinctions its authors needed, which is the same thing every notation in this subject has done — the diagram symbols encode a sequence of moves because their inventor needed to transmit a model, and they are correspondingly poor at describing a pattern.

Where this leaves the collection’s own files #

Every printed pattern here exports cleanly and has done since the export was written: valid arrays, faces where the graph permits, a stated length unit — which the format has no field for, so it goes in the description — and coordinates in the pattern’s own units.

None of them contains a crossing, and that is now checked rather than assumed, on every build, by the reading that plans the faces.

And the sixth letter stays local. A cut is expressed in this collection’s own patterns and is not written into an exported file, because the vocabulary a file uses belongs to the format rather than to any one writer. A file that invented a letter would be a file that only its author could read, which is the one thing an interchange format exists to prevent.