Re: [Origami] crease pattern data structure

[Robert Lang]

Apologies in advance for geeking out here. (But it's still
origami-related!). Comments below.

Thus spake "Hans Dybkjær"  on 2/13/16 10:52 PM:

>On 14 Feb 2016, at 02:12, Robert Lang  wrote:
>> 
>> -- a Crease is an object with pointers to its endpoint Vertices and
>> pointers to the 1 or 2 incident Polygons;
>a) In terms of folding sequences, many crease lines are often part of the
>same fold. 
>Is et meaningful to represent this, or is it better to let the program
>compute that?

Robby didn't ask about representing sequences, just CPs, but if we were
doing that, then I'd advocate a data structure of a Fold as being a
collection of creases that all move together. So the Fold would be a
collection of pointers to the affected Creases, and, perhaps, their
starting and ending fold angles. (And if the number of pointers exceeds a
certain threshold, we can call it a Collapse.)

Note, too, that now we'd probably now need to represent the folded state
as well, not just the CP. So, perhaps, a collection of either 2-vectors
(for flat folds) or 3-vectors (for 3D folds) representing the folded form.
(And, for flat folds, some further information specifying relative layer
ordering of Polygons, if we want to avoid self-interesection.)

>b) The assignment of Mountain, Valley, and Neutral, would that be part of
>the input?
>(Neutral are unfolded crease lines, ³unused² in the model, but either an
>artefact of the folding sequence or intentionally introduced for their
>decorative effects).

Almost certainly. For flat folds, the representations of crease status are
discrete values. In Tessellatica, creases can be Mountain, Valley,
Unfolded, or Border. (There are various algorithmic reasons why it's
useful to represent the edge of the paper as a type of "crease", but it
has to be its own type.)

For 3D folds, instead of (or perhaps, in addition to) discrete M, V, U, or
B, one would typically assign the crease a "Fold Angle" property, that
captures the continuously varying fold angle (between +180^\deg, for flat
folded valley, 0^\deg, for unfolded, and -180^\deg, for flat folded
mountain.)

>c) Having neutral creases, non-planar graphs become possible, since a
>neutral line may cross other lines in points which will not be a vertex
>of the final model.

While it is in principle possible to allow this, you'll find working with
the data model far easier if you enforce planarity of the graph and not
allow any creases to cross anywhere other than at a vertex. So unfolded
creases obey the same rules as folded ones. For one example: it's hard to
define and construct the Polygon objects (representing the facets of the
CP) if you allow crossings.

>Or is it better to represent them explicitly, and then derive the
>property that it does not affect the other crease¹s position in the final
>model?

I think explicitly is better. In TreeMaker, for example, there are M, V,
and U creases. When computing the crease pattern, one computes all of the
creases based on the tree conditions, but they are all initially U. Later
in the algorithm, once one has picked a specific arrangement of flaps, one
then assigns the creases; some become M, some become V, and others remain
U. If you pick a different flap arrangement, then the crease assignment
changes. So all the creases are always present; just not all of them
become folded.

HTH,

Robert

Re: [Origami] crease pattern data structure

[Hans Dybkjær]

On 14 Feb 2016, at 02:12, Robert Lang  wrote:
> 
> -- a Crease is an object with pointers to its endpoint Vertices and
> pointers to the 1 or 2 incident Polygons;
a) In terms of folding sequences, many crease lines are often part of the same 
fold. 
Is et meaningful to represent this, or is it better to let the program compute 
that?

b) The assignment of Mountain, Valley, and Neutral, would that be part of the 
input?
(Neutral are unfolded crease lines, “unused” in the model, but either an 
artefact of the folding sequence or intentionally introduced for their 
decorative effects).

c) Having neutral creases, non-planar graphs become possible, since a neutral 
line may cross other lines in points which will not be a vertex of the final 
model.
Or is it better to represent them explicitly, and then derive the property that 
it does not affect the other crease’s position in the final model?

Regards,
Hans


Hans Dybkjær
Site: papirfoldning.dk 
Society: foldning.dk 

[Origami] crease pattern data structure

[Robby]

Hello all,

a problem I'm trying to solve: what data structure to use to represent an
origami crease pattern in code

Graph - where I initially landed, but I can't seem to find a kind of graph
that depends on the vertices having a location in space, and my graph class
is quickly growing into a monstrous form since I'm calculating things like
the angle between two adjacent edges on a vertex. Does this kind of graph
have a name? Is there a formal approach to building what I'm trying to
build?

Thanks. Robby

Re: [Origami] crease pattern data structure

[Robert Lang]

Thus spake "Robby"  on 2/13/16 2:29 PM:

>Hello all,
>
>a problem I'm trying to solve: what data structure to use to represent an
>origami crease pattern in code
>
>Graph - where I initially landed, but I can't seem to find a kind of graph
>that depends on the vertices having a location in space, and my graph
>class
>is quickly growing into a monstrous form since I'm calculating things like
>the angle between two adjacent edges on a vertex. Does this kind of graph
>have a name? Is there a formal approach to building what I'm trying to
>build?

You could do worse than adopt the model used in Oripa (with the side
benefit that it would be easy to make your project I/O compatible):

http://mitani.cs.tsukuba.ac.jp/oripa/

Oripa is a Java app. Since it's open source, you might even be able to
build your thingamajig on top of it and reuse code.

If you're into C++, you could use the model that TreeMaker uses for crease
patterns:

http://langorigami.com/article/treemaker

And if Mathematica is your thing, there's Tessellatica, which has TGraph
and TGraph3D objects for representing crease patterns and their folded
forms:

http://langorigami.com/article/tessellatica

More generally, a useful way to represent a CP is to have Vertices,
Creases, and Polygon objects, where:

-- a Vertex is an object with x and y coordinates and a list of pointers
to its incident creases;
-- a Crease is an object with pointers to its endpoint Vertices and
pointers to the 1 or 2 incident Polygons;
-- a Polygon is an object with points to its incident Creases (and it's
also useful to maintain the corresponding list of its incident Vertices).

Of course, it's helpful to add additional objects and methods to
interrogate the relationships between the objects, cache useful
information, etc.

And even more broadly, if you start a Google search for "computational
geometry library ", you'll find stuff useful for
representing and manipulating planar graphs (which is what CPs are, at
least, from Euclidean paper).

HTH,

Robert