20200928

Algorithms for rendering quasicrystal tilings


Quasicrystals are aperiodic spatial tilings, and 2D quasicrystals have been used for centuries in Islamic art. I find these patterns beautiful, and I think more people should know how to render them.

You can render 2D quasicrystals as a sum of plane waves. They can also be constructed using aperiodic tilings (e.g. 4-fold Ammann-Beenker tiles and 5-fold Penrose Tiles), and there are fractal constructions that recursively subdivide a set of tiles using a smaller set of the same tiles (e.g. 5- and 7-fold tilings). Many more constructions can be found on the Tilings Encyclopedia

This post focuses on the "cut and project" construction, which is easy to implement in code. The routines shown here can be found in this iPython notebook on Github.

The cut-and-project construction

The simplest way to render crisp, geometric quasicrystals is the "cut and project" construction. This views the quasicrystal as a two-dimensional projection of a planar slice through a N-dimensional hyper-lattice. Let's implement this algorithm. 

A (hyper) lattice

First, we need to define the idea of a hyperlattice. This is a N-dimensional generalization of a cubic crystal lattice. It tiles ND space using ND hypercubes. We can represent the center of each hypercube (hypercell? hyperpixel?) as a N-D vector of integers
$$
\mathbf q_0 = [ x_1, ... x_N ],\,\,x_i\in\mathbb Z
$$
The associated N-cube, then, includes all points on a unit hypercube $\left[-\tfrac 1 2, \tfrac 1 2\right]^N$ offset to location $\mathbf q_0$:
$$
\mathbf q = \left[-\tfrac 1 2, \tfrac 1 2\right]^N + \mathbf q_0
$$

An irrational projection onto a 2D plane

To construct the quasicrystal, we cut through this ND lattice with a 2D plane. To get a aperiodic slice, this plane must not align with any periodic direction in the hyperlattice. 

A good choice is to project each direction of the hyperlattice onto an evenly-spaced set of basis directions, centered at the origin. We define a 2D $(s,t)$ plane $\mathcal P$ in terms of two N-D basis vectors, $\mathbf u, \mathbf v \in \mathbb R^N$.

$$
\begin{aligned}
\mathbf p &= \mathbf u \cdot s + \mathbf v \cdot t,\,\,s,t\in\mathbb R
\\
\mathbf u &= [ \cos(\theta_0), \dots , \cos(\theta_{N-1}) ]
\\
\mathbf v &= [ \sin(\theta_0), \dots , \sin(\theta_{N-1}) ]
\\
\theta_i &= \frac {\pi\cdot i}{N}
\end{aligned}
$$

5 comments:

  1. Beautiful.

    I wonder if one could color them in high-dimensional space. Usually I favor highly symmetric colorings. Presumably these would correspond to simple periodic patterns in N-D.

    ReplyDelete
  2. Very cool. I also found https://gglouser.github.io/cut-and-project-tiling/, which colors the faces based on their orientation in the hyperlattice.

    One thing I'm confused about is that the code draws edges between the centers q0. However, my intuition would be to find the intersections between each 2-D face of the cell and the cut plane. This would lead to an algorithm where one searched outward from an initial intersection, following adjacent faces each time a cell boundary was reached. Would this lead to the same result (perhaps shifted by 1/2 cell), or would it be some sort of dual quasicrystal?

    ReplyDelete
  3. So, if you actually render the cells in the location that the plane intersects them, you don't get a regular tiling. Instead, you get the colorful criss-cross image that you see at the start of algorithm 4.

    I think you are right that there is some intuition that I'm missing. I would have thought, for example, that the rhombi should be the 2D faces of the N-cube, since we're literally cutting and projecting N-cubes from the hyperlattice.

    I think this works because cubic lattices are self-dual. This means that identifying the centers of cubes intersecting the plane in the dual lattice is equivalent to finding the vertices on the cut surface on the original lattice.

    More generally, it does seem to me that there should be some sort of dual form of the projected 2D tiling, in much the same way that triangles and hexagons are dual for crystalline tilings. So far, the best I've found is rendering the Voronoi regions around the points. This looks like a mosaic, but is more irregular than I'd expect for the dual tiling. So there's probably some nicer way to do it.

    ReplyDelete
  4. That project is very cool. They seem to use Algorithm 3 in this post, but perhaps an optimized version of it. Their app is crazy fast. I suppose also that Rust → web assembly is substantially faster than Python with matplotlib.

    ReplyDelete