Post #2332239

2026-05-08 14:37 UTC

Recently, Sébastien Labbé and Peter Selinger posted a preprint (https://arxiv.org/pdf/2604.20964) that describes a sophisticated construction for the hat tiling, based on what&#39;s called a Markov partition (see the thread by @pieter at https://mathstodon.xyz/@pieter/116484517078239617 for more details). One nice side effect of their construction is that it provides a means of rendering the hat tiling on the GPU using a fragment shader. That&#39;s cool, because it requires a constant amount of work per pixel, regardless of how many tiles you&#39;re drawing, and you can pan around forever without ever worrying about running out of information about the positions of tiles (as you would with a drawing algorithm based on substitution). I have a slightly glitchy prototype written up in Shadertoy. I&#39;ll make the code available, but I want to clean it up first.

Replies (4)

@csk@mathstodon.xyz 2026-05-08 14:46

The construction involves defining a fractal colouring of the plane, and sampling from the fractal using points in a lattice (the vertices of a tiling by equilateral triangles). @pieter@mathstodon.xyz asked about visualizing the result of sliding the lattice relative to the fractal, which should cause whole sections of the tiling to "flip" from one configuration to another as collections of sample points move from one region of the fractal into another (like Conway Worms in the Penrose tiling). Here's a visualization of that on a very zoomed-out tiling. It's neat! (It also looks slightly glitchy, which might be an inevitable consequence of floating-point error.)

Open ##2454875
@simontatham@hachyderm.io 2026-05-08 14:48

@csk@mathstodon.xyz @pieter@mathstodon.xyz with my computer-arithmetic hat on, I want to quibble with the 'constant work' and 'never run out of information' parts. I think those things would be true if your GPU had _true real numbers_ as a data type. But all it has is finitely large floating-point approximations. And this whole technique relies on the translation symmetry lattices of the grid points and the fractal pattern being irrational multiples of each other. That irrational multiplier will be imperfectly represented in floating point, so sooner or later as you pan away from the origin you'll reach a point where rounding errors start to affect the results. (If nothing else, from first principles, even within a single hat tiling of the whole plane, the non-periodicity implies that every tile in the plane must be distinguishable, and therefore there's no way a finite amount of information could even tell you where you are within _that_ hat tiling – and that's before considering the uncountable number of distinct tilings of the whole plane.) But perhaps you have to get 2^52 tiles away from the origin before this becomes a problem!

Open ##2454876
@pieter@mathstodon.xyz 2026-05-08 18:57

@csk@mathstodon.xyz Nice to see this implemented, Craig. I'm curious how you determine which fractal shape, if any, a control point lies in. Is it anything like the iterative process I describe here: https://mathstodon.xyz/@pieter/115951754157537975?

Open ##2454886
@tiotasram@kolektiva.social 2026-05-09 11:09

@csk@mathstodon.xyz @pieter@mathstodon.xyz dunno where I'll find the time, but this makes me want to apply my fractal coordinates method to the turtle and/or hat tilings, since that would allow you to use a substitution-based construction while efficiently paying log (distance-from-origin) memory+time complexity no matter where you go, and only calculating what's necessary for what the user actually scrolls across...

Open ##2454888