Edge River Method Part 1 of ???: Introduction (and some Theory)

Fundamentals

Yes, there’s already a blog post about ERM, but there’s¹ only one blog post about it and apparently ERM resources are obscure. So here’s another one, since I recently delved into some specific aspects of ERM.

The edge river method (ERM) is a method that’s pretty similar to the axial method, but meant to extend to general 2D polygons. Let’s take a look at a classic axial packing map.

The map. Dotted black lines are ridge lines.

Yep, just a regular axial map. It has some rivers, and they turn. One thing you can do here is to place edges of the tree directly onto the axial packing.

The map after placing edges onto the packing. Flap F has been turned into a middle flap for illustration purposes.

Notice that each river comes out of an edge and flows and turns until it reaches the boundary of the paper or the same edge from the other side (as in river F).² This concept can be generalized to the case where the “tree” is actually a shape made of 2D polygons (and from now on will be called an abstraction³) Let’s take a look at a sample ERM map that I made.

From each edge comes a river, which flows until it reaches the boundary of the paper or another edge that ends up in the same position. For example, the bottom middle river coming from region A flows until it reaches the top edge of region B, which ends up at the same position. In general, an ERM map has several components (names given by Mu-Tsun Tsai)

Lakes (blue). These are the blocks that make up the abstraction and need to be packed into the map.
Backside Lakes (dark blue). These are lakes that end up on the back side. They can be explicitly planned, or they can just show up when rivers intersect, as in this case, where the bottom-right river and the right-side river from region A intersect. (Regular lakes will be called frontside lakes if they need to be distinguished from backside lakes.)
Rivers (striped green). These are similar to rivers in an axial packing. They enforce the condition on the distance between the corresponding endpoints on the lake, and are mostly not allowed to cross each other (though sometimes they can, creating more lakes. We’ll get into that later.) When folding the crease pattern, the entire river gets folded onto roughly the same edge.
Lands (background color). Any area that’s not a lake or a river.
Peninsulas⁴ (diamond red). A type of land that’s a feature unique to ERM. In general, rivers that come out of a concavity (e.g. the concavity between the bottom-left of region A and the left of region B) cannot share an edge (we’ll get into why later). Peninsulas are explicitly marked as a reminder of this constraint, as it is one of the most important facts about ERM and easy to forget when constructing a packing.
the Sea (outside the diagram). This is the paper boundary.

One of the most important differences between regular axial packing and ERM is literally just that, ERM is not axial. In axial packing, the “abstraction” lies on a single axis, so all rivers collapse to the same direction. But in ERM, rivers can collapse to different directions, which is responsible for basically all the complications of ERM compared to axial packing.

So, now you’re ready to start packing with ERM! (on a basic level):

Come up with an abstraction.
Pack the abstraction into a map, forming lakes.
Send a river from each lake edge and make sure it goes to the sea or to a lake edge that will end up in the same place (like in axial packing).
Make sure the rivers don’t intersect (unless you know what you’re doing)
If two rivers form a concavity, make sure there’s space between them.
??? (draw a crease pattern)
Profit!

Okay, but if you want to use ERM at a higher level, we need to talk about ERM theory.

Theory

Lakes, Rivers, and Lands

Fundamentally, ERM is a way of telling the paper where to go to construct the target shape without stretching it or tearing it. In the ideal version of ERM, where you can make infinitely dense folds, there are only 3 types of regions: lakes, rivers, and lands. Let’s take a look at the following example, which shows an abstraction with 3 flaps.

The abstraction, with a region and 3 points labelled.

The ERM map, which shows where those points go.

Let’s look at what lakes, rivers, and lands do in this ideal model:

Lakes are regions that map directly to the abstraction and don’t collapse. A point inside a lake (e.g. point $P$) turns into a point in the abstraction.
Rivers are constant-width regions that collapse onto an edge in the abstraction. A line inside a river that is parallel to the river (e.g. line $Q$) turns into a point in the abstraction (specifically a point on some edge). Rivers contain infinitely dense creases, each one perpendicular to the flow of the river.
Lands are regions that collapse onto a single point in the abstraction. An entire land (e.g. region $R$) turns into a point in the abstraction (specifically a vertex).

When you make the infinitely dense crimps on the rivers and the double infinitely dense all-directional crimps on the lands required to collapse this ideal ERM map, you get exactly the target abstraction. If you could actually do infinitely dense crimps, then this would be the end of it. Lakes! Rivers! Lands! The fundamental regions of ERM!

Unfortunately, on real paper, you can’t make infinitely dense creases, and all the complications of ERM past the fundamental regions come from this fact.

Sometimes, you get lucky and you can just make the infinitely dense creases finite, and it will fold as intended:

The 3-flap crease pattern, with the ERM map in the background

Waffle walls

Unfortunately, you usually don’t get so lucky. Consider the following ERM map, which represents a 540° angle made of 6 axis-aligned squares.

The ERM map. Note land $$P$$ in the middle.

Now let’s try to draw a crease pattern for this map. The outer lands and rivers are easy, but land $P$ looks tricky. Instead of using Origamizer since I’m not Tomohiro Tachi, let’s try to do it more manually. A first attempt is shown below⁵:

A first attempt at the 540° angle. Faded lines are folded less than 180°.

But now let’s actually try to fold it.

The back side. Hmm, there's something sticking out of the vertex...

Most of the paper on the back side is aligned with the abstraction, but there’s a 6-sided-star-shaped wall sticking out. This is what I like to call a waffle wall, named after the waffles used in the Origamizer algorithm. Thankfully, we can apply some force and twist the waffle walls (kind of like a hexagon twist) and try to get it on the abstraction.

A second attempt at the 540° angle, after twisting the vertex. (I encourage you to fold this, it looks pretty and locks awesomely)

The waffle walls got much smaller, but they're still there.

We can keep twisting and twisting these waffle walls, and they’ll get smaller and smaller, approaching 0, but as long as we make only finitely many creases, there will be waffle walls (proof in the footnote⁶). I’ll leave this section off with a beautiful picture.

A coloring of the faces after an infinite number of waffle wall twists, where faces of the same color end up on the same face of the abstraction, and faces of different colors end up on different faces of the abstraction. Every point where a solid white line turns (except the boundary and the 6 turning points close to it) maps to point $$P$$ (the center point).

In fact, whenever there’s a vertex with negative curvature (an angle greater than 360°), there is a risk of needing waffle walls. Note that I said a risk, not a guarantee, because in some cases you can avoid them. For example, in the 3-flap discussed in Lakes, Rivers, and Lands, there is a vertex with a 540° angle (90° front and back × 3 flaps), but no waffle walls are needed⁷.

Peninsulas

Another situation where waffle walls are not needed is when the vertex in question is on the boundary of the abstraction. However, we need to be careful here. Consider the following ERM map, this time of an L.

The abstraction, with some points labelled.

The abstraction again, with forced positions for $$P'$$ and $$R'$$. The shortest distance from $$P'$$ to $$R'$$ within the abstraction is greater than 2.

Now let’s try to make a (finite!) crease pattern based on this ERM map. Let’s mark points $P_1$ and $P_2$, which both map to $P$, and do something similar for points $Q_1$, $Q_2$, $Q$, $R_1$, $R_2$, and $R$. Let’s assume that there is only one crease strictly between $Q_1$ and $Q_2$ (otherwise bring $P_2$ and its corresponding points closer to $P_1$. Eventually you’ll meet the assumption because there’s only a finite number of creases. Also, note that the crease has to be vertical because creases should be parallel to rivers.), and say that it goes through $Q'$. We also mark points $P'$ and $R'$ where the crease would cross through lines $\overline{P_1P_2}$ and $\overline{R_1R_2}$, respectively. Note that the distance between $P'$ and $R'$ on the paper is 2. However, consider where $P'$ and $R'$ would end up. Line $\overline{P_1P'}$ on the paper must end up perpendicular to line $\overline{PQ}$ on the abstraction, and similar for $R$. If we restrict the entire paper to the abstraction (so no waffle walls), $P'$ and $R'$ have their positions forced, specifically to be inset into the abstraction compared to points $P$ and $R$. This causes the distance between $P'$ and $R'$ to stretch, which is illegal, so this ERM map won’t work.

As an aside, if we do allow waffle walls, the above ERM map will work. Here’s an example crease pattern:

The crease pattern for the above ERM map. Note that it has 90° folds; these form the waffle walls.

This one’s even worse than that orthogonal 540° angle vertex, because here you can’t twist the waffle walls into the abstraction at all. You’d have to sink them, meaning that you can’t limit the waffle wall zone to just small areas around vertices. As another aside, Soichiro Uchida made a software called Orixa that can compute ERM maps and crease patterns for arbitrary polyominos (ones with holes are split first; abstractions must be “trees”!), but assumes that waffle walls are allowed. In the output, lakes are gray, rivers are blue, and lands are green.

Thankfully, this time there’s an easy fix that gets rid of the waffle walls completely. The problem is that the rivers corresponding to segments $\overline{PQ}$ and $\overline{QR}$ touch, causing a problem with stretching the paper. If we just make them not do that, the problem goes away. Behold:

The fixed ERM map. The rivers that shouldn't touch now don't touch. We add a reminder region to remind ourselves not to accidentally make those rivers touch.

A crease pattern for the ERM map. All folds are 180°, so there are no waffle walls.

Now the rivers don’t touch. The diamond-patterned red region in the middle, as mentioned in the Fundamentals section, is a peninsula, and it serves as a reminder to not make those rivers touch. Note that it is still a land. In general, if two rivers are attached to edges that form a concavity, and you want the paper to stay inside the abstraction, those rivers should not touch. You can make the space as small as you want, but the smaller the space, the less distance the paper is allowed to travel into the abstraction before it stretches, and thus the greater the number of creases.

There’s rivers that shouldn’t touch, but there’s also…

Overlapping Rivers

Consider the following packing challenge, involving making an L-tromino.

We want to pack the abstraction with the lakes in the specific places shown above. (Perhaps it’s part of a bigger model and due to tight constraints these lake positions are pretty much forced.) When we draw rivers from each edge, we have a problem: there’s seemingly no space for river $\overline{QR}$. Is this challenge impossible?

No. Notice that river $\overline{PQ}$ and river $\overline{QR}$ here can be seen as one big river of width 2. But it doesn’t particularly need to have width 2. The distance from $P$ to $R$ in the abstraction is $\sqrt{2}$, so as long as the edges of the big river stay $\sqrt{2}$ apart, things should be fine. But river $\overline{PQ}$ and river $\overline{QR}$ must have width 1, so how do we resolve this?

Fixing the map with overlapping rivers. The overlap is marked with double-striped teal.

We can just make the rivers overlap! We overlap the rivers so that the shortest distance between $P$ and $R$ on the paper is $\sqrt{2}$, satisfied by $P_1$ and $R_1$. To understand how overlapping rivers work, let’s think back to the ideal model discussed in Lakes, Rivers, and Lands, with infinite creases. The path of the river dictates what direction the creases should go (or you could say that the creases turn the river), but at the overlap these crease directions disagree, except along segment $\overline{P_1R_1}$, which seemingly leads to a contradiction: the rivers can’t turn the way that they’re drawn! However, the resolution here is simple: we don’t draw any creases that would go through the overlap, except the one where they agree. A region that cannot have creases through it is a lake. This simplifies to the diagram on the right, where the overlap is replaced with two new lakes we didn’t draw in the abstraction (but those lakes will just be hidden, so it’s fine). A more formal proof that the overlap simplifies to those lakes is in this footnote⁸.

ERM diagrammers⁹ show overlapping rivers for simplicity, but in reality, overlapping rivers are just forced lakes.

By the way, I don’t recommend this specific packing in real life. Here’s a resulting crease pattern:

A crease pattern for the ERM map. Note that the creases around the peninsula are dense.

As discussed in Peninsulas, the narrower the peninsula, the denser the creases have to be, and this is a good example of that. And this particular example has a complicated reverse fold, so you either have to deal with it or increase the density even more.

Now for another example of the use of overlapping rivers. This pattern often shows up in my designs:

Let’s say that all the lakes are fixed, and that due to the greater context, river $\overline{RS}$ is also fixed (for example, segment $\overline{RS}$ could just be long, and thus even if it turns, you get an annoyingly narrow peninsula). The fix, is of course, to use overlapping rivers, but you can’t just push river $\overline{QR}$ closer to river $\overline{PQ}$¹⁰. Instead, you have river $\overline{PQ}$ and river $\overline{QR}$ cross, effectively switching their positions!

Fixing the map with overlapping rivers. There's a peninsula between river $$\overline{QR}$$ and $$\overline{RS}$$ but it's not drawn to avoid confusion.

This river-switching technique is basically my favorite way to get around peninsula constraints. You add a (backside) lake that eats up a concavity-forming river, and then the river that it spits out is allowed to touch the other concavity-forming river. (And yes, the river overlap must become one big lake because there is absolutely no agreement on crease direction.) You can even make a nice sparse crease pattern since the peninsula (not drawn) is nice and wide, but let’s leave that as an exercise.¹¹

In the case where the rivers cross instead of simply overlapping, you do have to be careful about correspondences. In the diagram above that uses a backside lake, note that $O'$ and $O$ map to the same point, and $R'$ and $R$ map to the same point. When river $\overline{QR}$ “crosses” $\overline{PQ}$, the result is a backside lake that then spits out new rivers $\overline{O'R'}$ (not $\overline{PQ}$) and $\overline{O'P}$ (not $\overline{QR}$). This is important because of the rule that rivers must go to either the sea or a lake edge that ends up in the same position as the one it came out of.

In summary, if two rivers form a convexity, you can make them overlap a bit (or even have them cross), but it forces lakes to appear.

Other Geography

Mu-Tsun Tsai mentions some other terms in their blog post about ERM, so let’s go over them quickly.

Waterfalls. Those are just a representation convenience for overlapping rivers (I prefer to show the overlap or draw lakes instead.)
Swamps. Those are just a representation convenience for split backside lakes. (I haven’t gotten into a situation where I needed to draw a swamp yet. Probably because I usually just use rectangles. I’d probably just math out the backside lakes and draw them because I like to see where the rivers are flowing for crease pattern creation purposes.)

If I had to solve Mu-Tsun Tsai’s swamp puzzle, I’d probably do it something like this:

The swamp puzzle abstraction. The puzzle is to pack this in an 8×8 grid.

Let's just plop in the backside lake for now and fill in what we can.

The backside lake eats up too much space, but if we split it and rotate it just right, it works out.

Then from there, I’d probably figure out how that river overlap turns into lakes, and then draw a crease pattern.

Theory Summary

So, now you’re ready to start packing with ERM! (on a more theoretical level):

Come up with an abstraction. Keep in mind that waffle walls are inevitable if there’s an internal point that must be winded more than 360° around.
Pack the abstraction into a map, forming lakes.
Send a river from each lake edge and make sure it goes to the sea or to a lake edge that will end up in the same place.
If two rivers form a concavity, make sure there’s space between them. Use a peninsula as a reminder.
If two rivers form a convexity, they can intersect as long as distance constraints are still satisfied. If they cross, beware the river mapping!
Calculate the lakes for river overlaps.
??? (draw a crease pattern)
Profit!

Drawing a (Finite!) Crease Pattern

After you’ve worked long and hard creating that ERM map, you still need to fold it. I’ll talk about this briefly.

Discretize the ERM map, because you’re not getting smooth circle rivers with a finite number of folds. This can be done by sharpening the circles at specific places called ridge line. In box pleating, for example, rivers turn 90° at a time, except at Pythagorean stretches.
Fill each land with belts (rivers that just loop on themselves)
Fill in the rivers with parallel creases alternating mountain and valley¹², like in axial design.
Add in the missing creases. (This is the hard step, and requires some crease manipulation. If a situation looks impossible, it could be because you forgot to separate concavity rivers with a peninsula.)

Discretizing the map so that it can be folded with a finite number of creases. Thin white lines are ridge lines.

The End

Well, that’s all for now. Next time I’ll probably talk about the special case of box pleating, especially when the abstraction consists of just rectangles.

there was ↩
I like to affectionately call a river that completes a loop without crossing the paper boundary a belt. ↩
I almost wanted to call it a fat tree instead because it still needs to be a tree (in a sense), just with thickness. ↩
If it were up to me I’d call it a buffer zone. Peninsula is a weird name for something that usually ends up being an island. ↩
I had to manually figure out the angles and such here with the help of Blender. Wouldn’t it be cool if we had something like Oriedita, but 3D? ↩
To see why, assume that every point on the paper ends up on the abstraction with a finite number of creases, and that every point on the abstraction is mapped to. Also assume that the paper boundary gets mapped to a closed curve around abstraction point $P$ and has winding number 1 around $P$. (Otherwise you can cheat by strip folding. Also, I wanted to avoid using the word Fréchet distance because it can be arbitrarily big since the paper is allowed to back up.) Now consider the set $\mathcal{P}$ of paper points that map to abstraction point $P$ (the 540° vertex). $\mathcal{P}$ must be finite, because there are only finitely many creases (and thus faces between them), and each face between creases can contain only one paper point mapping to $P$. The angle around each point in $\mathcal{P}$ is 360°, so no point in $\mathcal{P}$ can cover all 540° of $P$ by itself. Since it is impossible to wind around point $P$ without leaving the abstraction or going through all 540°, the winding number of the neighborhood of each point in $\mathcal{P}$ around $P$ is 0. Now take the convex hull of all the points in $\mathcal{P}$ (which has winding number 1 around $P$), and shrink that hull until there are no more points in $\mathcal{P}$ inside it. Every time you cross a point $x$ in $\mathcal{P}$, the winding number stays the same (that is, 1), because the neighborhood of $x$ has winding number 0. But now you have a region with winding number 1 around $P$ and no points that map to $P$, which means you cut the paper, a contradiction! (Note: if $\mathcal{P}$ was infinite, you could have an infinite number of $\mathcal{P}$ crossing events and never get to that contradiction.) ↩
This escapes the proof because the 540° vertex in the 3-flap is structured in such a way that you can wind around it and skip some faces without leaving the abstraction. For example, if the faces are ordered $F$, $G$, $H$, $I$, $J$, $K$, you can go $F\to G\to H\to I\to F$ (360°) without leaving the abstraction. ↩
First, note that $P_1$ on the paper maps to $P$ in the abstraction, $Q_1$ and $Q_2$ both map to $Q$, and $R_1$ maps to $R$. $\triangle P_1Q_1R_1$ is congruent to $\triangle PQR$, so no creases are allowed through it. Similarly, no creases are allowed through $\triangle P_1Q_2R_1$. Since $Q_1$ and $Q_2$ map to the same point, there must be a crease on the perpendicular bisector of $\overline{Q_1Q_2}$, which happens to be right between $\triangle P_1Q_1R_1$ and $\triangle P_1Q_2R_1$. Thus, we get the lakes. ↩
Well, I don’t think there’s that many, especially ones that use overlapping rivers ↩
Well, technically you could, but it makes things inconvenient, and you either get a narrow peninsula or lots of lakes. ↩
I guess it’s an unfair exercise, since I didn’t explain how to turn an ERM map into a crease pattern. ↩
They technically don’t need to alternate, but if you don’t know what you’re doing you’ll run into self-intersection hell. ↩