Myriahedral projections

It’s recently been the 10th anniversary of this paper. It is such a fantastic example of data visualisation that have always feel the need of making an implementation of it. Finally I gave it a try with more or less successful results.

Unfolding a Myriahedron. Tetrahedron, 4096 faces.

How I reached this point, was a bit of a rollercoaster of failure and success, but intuition always works. Unfolding the myriahedron is composed of three different yet related steps, each one a problem in itself:

Create the myriahedron.
Calculate a maximum spanning tree (MST).
Unfold the geometry based on the spanning tree.

Myriahedron

Myriahedron, refers to a ten-thousand-face polyhedron. To start with, I selected a regular tetrahedron and then recursively subdivide its edges. During subdivision, process I chose to generate new edges for 4 new triangles, though 9 could be generated as well.

Recursion level 6 leads a 4096 faces polyhedron. We just need the edges for this subdivision process. At the same time we recursively subdivide the edges, we generate a numerical parameter for each of them, which gets modified on edge split, or edge generation, during the recursion process. This allows us to label edges as folds or cuts. After subdivission process, we get a Myriahedron with indexed geometry: 2050 vertices, 4096 faces, 6144 edges.

This process does not offer any remarkably interesting visualisation result, just the edges of a recursively subdivided tetrahedron. If for instance during this process we decided not no include the edges for the central triangle (remember we subdivided each triangle in four new ones), we’d get a Sierpinsky tetrahedron:

Maximum Spanning Tree (MST)

This step is a bit tricky, but the results pay off by themselves.

During the recursive subdivision, we ended up with a graph composed of vertices, and undirected links between a pair of points (Edges). We need to generate another graph, which instead of connecting vertices, it connects myriahedron faces. I basically use a dual structure here which keeps track of the original Edge (connecting vertices) with its new information (what faces this edge is shared by).

I apply Prim/Kurskal algorithm to this faces-connecting graph to obtain a maximum spanning tree. These nodes have the same weights as the Vertices set. In my case I did the most naive Prim’s implementation, with a full search per iteration instead of using a priority queue (more on my laziness on future posts). This subgraph will be the set of folds, over the final geometry. One side note: during our recursive subdivision process, we set edge weights to increment when new edges are created. We expect higher values to be a fold in geometry, and lower values to be a cut, so I needed to negate the weight to obtain a Maximum instead of a minimum spanning tree.

Another MST needs to be calculated, for the geometry cuts. It turns out, we don’t need to calculate another MST. Since we know, for each face-connecting edge, what the original vertex-connecting edge it was created from, we can just substract from the set of all vertex-connecting edges all the faces-connecting edges.

The MST offers outstanding visuals by itself.

Recursively subdivided tetrahedron. Folds (magenta), Cuts (cyan)

Cuts/Folds over normalized recursive subdivided tetrahedron (4096 faces)

In these pictures we can observe a few things:

Each triangle in the geometry, has at least one cut and one fold.
Folds (magenta) are edges connecting faces. Folds have a direct relationship with cuts (cyan). The unfolding edge will be an edge on the triangle which is not a cut.

Unfolding the geometry

Despite being quite intuitive, unfolding the geometry took me the most time to figure out. First, I needed to re-triangulate the geometry. From list of edges to polygons. Each polygon has its own vertices (non indexed geometry).

Though not necessary. I decided to generate a connecting graph for every fold, just to get strips of connecting faces.

The only needed structure for unfolding, is the folds MST. This is a recursive process starting by the terminal nodes MST nodes. Each node connects two faces. We calculate the angle between these two faces (cross product over their normals). Then rotate accordingly all adjacent faces’ geometry. I tested rotations using Rodrigues and Quaternions to obviously obtain the same results. I ended up using quaternions since the maths involved where a bit less allocative.

After repeating this process for every MST node (connecting faces), we’d get the following results:

Tetrahedron MST on sphere. Folds (magenta) cuts (cyan)

See how cuts (cyan on the left image) will be followed by the unfolding geometry process (result on the right). See how Europe and Africa are unfolded following exactly the cuts path.

Tetrahedron MST on sphere. Geometry + folds view.

This is a capture of the un/folding process. Beautiful imo.

This exercise just covers recursive subdivision of Platonic solids and graticules. Unfortunately, no maps of earth’s coastline, or land/water like in the original paper.