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:

Sierpinsky tetrahedron
Normalized 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:

Fully unfolded geometry
Tetrahedron MST on sphere. Folds (magenta) cuts (cyan)
slightly unfolded geometry

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.

Unfolded Platonic solid results

Unfolded Tetrahedron

Tetrahedron 1024 faces

Unfolded Cube

Cube 3072 faces
Octahedron 2048 faces
Icosahedron 5120 faces

Graticules

Gore’s Map (Cylindrical projection)

Conical projection

Azimutal projection

Azimutal two hemispheres

Polyconical

Bonus track

While trying to make sense of the paper, it was interesting to actually visualise some intermediate steps and structures.

Making sense of the MST nodes hierarchy

MST nodes hierarchy diagram.
MST nodes hierarchy diagram. 2. Close up

Visualising whether unfolding normals where correct

Some blatant errors, yet beautiful visualisations

Failed MST hierarchy view
Coronavirus ?? #facepalm

Failed unfolding process (wrong faces orientations)
Failed unfolding process (wrong faces orientations)

I am still fixing minor lots of stuff on the code. I pushed it as-is here.

Published by ibon

Chocolate engineer, software eater. Data visualisation at Workday. Past: Platochat, SdkBox, Chukong, Ludei.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: