faceOrders/edgeOrders inconsistency?

[origamimagiro]

There is something that has always felt off to me about the faceOrders/edgeOrders fields. Every other field in the FOLD spec maps to an array of primitives of the same type, or an array of arrays of primitives of the same type. The faceOrders/edgeOrders fields are the only exception, mapping to an array of triples of mixed type.

I propose we replace faceOrders, currently an array of triples triple [f, g, s], with two fields:

• faceOrders_faces, an array of ordered pairs of overlapping faces [f, g], and
• faceOrders_assignment, an array of order assignments s for each corresponding ordered pair of faces,

and similarly for edgeOrders. I think this would be more consistent with how the other data in FOLD spec are stored.

Thoughts?

We could then also consider replacing faceOrders with orders. Actually, perhaps we could replace both faceOrders and edgeOrders with orders? Are there situations where both faceOrders and edgeOrders would want to be used in the same frame?

[mayakraft]

faceOrders_faces, an array of ordered pairs of overlapping faces [f, g], and

"overlapping" only happens when faces are coplanar. currently, faceOrders can describe faces which are not coplanar too, I believe this functionality should not be lost. I propose removing the word overlapping.

---

edges_ or faces_ or vertices_ these prefixes all take part in multiple keys with different suffixes, each contributing a unique perspective to the graph. each of these prefixes have multiple reasons for existing. this proposal suggests inventing a new prefix, but without expanding functionality.

Q1: Are there any other pairings we can make with the faceOrders_ prefix to strengthen its case for existing?

Additionally, edges_vertices is an array which can exist independently of any other array, and make a meaningful contribution to the understanding of a graph on its own. This isn't the case with all of the arrays in the spec. However,

Q2: do either of these faceOrders_ keys contribute something on their own? If so this could support their case.

---

Re: the final paragraph, "orders" can refer to either faces or edges, correct? and what is the mechanism for inferring which one?

[origamimagiro]

I agree with the removal of the "overlapping" qualifier. Allowing non-overlapping can be useful when attaching faceOrders to a crease pattern for example.

The obvious answer to Q1 is the two pairings I already suggested, faceOrders_faces and faceOrders_assignment. Others could include a mapping from faceOrders to their adjacent constraints, e.g.,

• faceOrders_tacoTaco
• faceOrders_tacoTortilla
• faceOrders_tortillaTortilla
• faceOrders_transitivity

which is something I store in the solver I recently released. Decoupling faces and assignment would also make it cleaner for storing multiple assignments of the faceOrders. If I generate a new valid assignment for the FOLD object, I could just replace faceOrders_assignment instead of also rewriting the faces corresponding to each faceOrder.

[gkonjevod]

It seems to me that separating the information provided by the original array (relative ordering of face pairs) from the order in which it is specified (the sequence in which the face pairs are given in the array) leads to two arrays, each of which is not useful on its own. I think this is the point of Robby's second question, and the main reason I don't like the proposal to split up the single array.

On the "overlapping" issue, I agree that it sounds useful to have the relative order information even when the faces are not coplanar. However, I am not convinced it actually matters. The reason to specify the order information is because without it the folded state may not be uniquely specified. But, if the two faces are not coplanar, is it not the case that their relative positions in space (and thus the relative order information) can be inferred from the rest of the pattern? Right now I don't see either a simple proof of this statement or a counterexample, but intuitively it seems like it should hold.

[origamimagiro]

See my comment to Robby about decoupling faces and assignment. Having the two separated is useful when talking about multiple folded states. For example, one could store one FOLD format file that holds all valid folded states of a model over multiple frames, where each frame stores only the change in assignment without repeating the face pairs.

A reason why it can be useful to specify foldOrders when two faces do not overlap is on a FOLD format file representing a flat-foldable crease pattern. One can easily compute locations of the folded vertices from the crease pattern information, where faces will overlap in the folding and the foldOrders can apply.

[edemaine]

Definitely some good ideas here! Let me add one more:

If consistency were the only concern, then I think this design would make sense:

• faces_above_faces[f] is an array of all faces that are above face f (or that f is above? — not sure which, so maybe it needs a better name) relative to f's orientation.
• edges_above_edges[e] is an array of all edges that are above e (or that e is above?) relative to e's orientation.

This would satisfy the constraint that anything starting with faces_ is an array indexed by face id, and that anything ending with _faces has an array of face ids when indexed. The only unusual part is the above in the middle (needed because faces_faces has another meaning).

This design would be far easier to traverse: if I want to know the faces that are above f, I can access it directly. If I want to know the faces that are below f, we could easily compute an inverse mapping faces_below_faces. This feels very much in line with all our other data structures that let us jump from faces to incident information. For example, faces_faces

One argument against this proposal is that it's harder to flip between +1 and -1. (You've have to extract g from faces_above_faces[f] and add f to faces_above_faces[g].) I think this is why we didn't pick this design originally (but not sure I recall correctly that we considered it). Personally I like that it's all just face indices, no special ±1 data type, but perhaps Jason can comment on how this would feel to work with in his flat folder. (I forgot about 0, but that seems just as easy to represent by omitting faces in both arrays.)

The other issue is that Jason's proposal makes it really easy to specify multiple orders for the same folding using multiple faces. But this new proposal has some advantages too: if the orders different only in a few faces, you could just specify the faces that have any changed, leaving the rest of faces_above_faces at null to inherit from the parent frame (if I correctly recall how frames work). I feel like this might be a common result from an exhaustive search, and because many crease patterns only have a few faces that have ambiguity. What do you think, Jason?

---

Regarding "overlapping", I take it Jason and Robby are thinking about the transitive closure of the "above" relation? (Not sure what flat folding has to do with anything here... But it's quite relevant with map folding for example.) There are also two notions of "overlapping" which can be confusing: interior-overlapping and closure-intersecting. Direct above/below relations are only needed with positive-area interior overlap, and don't make sense e.g. with two faces that overlap on an edge, but sometimes there are transitive implications that could be useful (like in map folding).

I feel like the spec should at least mention the transitive closure issue. I take it folks are leaning toward not specifying whether things should be transitively closed (though I think we might want a helper to compute the transitive closure).

---

While we have this excitement, I'd also like to remind folks about a now 2-year-old proposal for FOLD 1.2. (#30) If there's in fact consensus for that, it'd be nice to merge it. (But please discuss in #30 or another discussion thread.)

[origamimagiro]

I have some concerns regarding faces_above_faces as you've defined it, not least of which is that it is incomplete. Specifically, if two faces properly overlap (in the interior-overlapping sense) and have normal vectors pointing away from each other, each would be below the other and their overlap would not appear in any faces_above_faces list. Such a pair would be indistinguishable from a pair of faces that do not overlap. In particular, faces_below_faces is NOT an inverse mapping of faces_above_faces and "overlapping" is NOT the transitive closure of the above relation you've defined.

(Less important is that there is inconsistency with the spec concerning naming conventions. Underscores should denote levels of array nesting, with camelCase being used for identifiers of each level. A more consistent naming for the thing you describe would be faces_aboveFaces.)

An alternative could be to define something like faces_overlappingFaces or faces_overlaps that maps each face index to an array of the indices of faces it properly intersects. This would be a restructuring of the same information as faceOrders_faces that I proposed previously, but I personally think faceOrders_faces would be more useful when you don't want to store all the possibly quadratic overlap information, and only want to store a sparse generating set of orders, that (together with edges_assignment) could be used to infer a unique assignment of all other orders. For most folded states, the generating set will be quite small.

If we do continue to discuss faceOrders_faces, I again am having more thoughts on naming. I think better terminology than orders_faces and orders_assignment I proposed previously would be something like overlaps_faces and overlaps_order. The things being indexed here are not orders; they're pairs of faces that overlap and need to be assigned, which could be useful to store in the absence of order information. For example, it could be useful to store overlaps_faces in a file for an unassigned crease pattern, so that a program could know which overlaps would need to be assigned to describe an actual folded state.

As an aside, I think we have slightly different philosophies on the FOLD format. I think Erik's perspective is that FOLD should store and define lots of information about a folded state that will make it easy to work with computationally. My perspective is that FOLD should be a useful storage and interchange format for faithfully representing a folded state; so while verbose representations can exist within the spec, I would like the format to include representations that are minimal, i.e., do not have to store information that could be derived from the other information stored. Storing derivable information can trade storage for reduced computational time later on, but may not result in any time savings if an importer wants to check redundant information for conflicts.

With respect to representations for exhaustive search, I would suggest that we not encourage the use of frames to list out the result of a large exhaustive search. Kind of the point of the solver I've been working on is that there are ways of compressing the output of an exhaustive search that can represent an exponential number of states in polynomial space. But I'll leave incorporating such compressed representations into FOLD spec to a separate discussion.

---

With respect to FOLD 1.2, I think we should deploy it (it is long overdue), and consider any changes to faceOrders in a future version.