Hilbert curves are cool

Hilbert curves are cool.  They’re a form of fractal comprised entirely of 90 degree angles. It’s a way to make a single continuous line fill up any given space (2D, 3D, and beyond).

The background to this blog is a hilbert curve I rendered myself (code).  Above is a simpler version of the curve, blown up so you can see it, with the color of the line changing so you can see how it flows.

It has a some cool properties.  For example, if you subdivide the image width-wise and height-wise by a power of two, you get squares that also contain one contiguous part of the line.  It turns out this is important in computer simulations.  Because of how CPU caching works, it’s faster to read a bunch of bytes next to each other than ones far apart. So if you’re simulating weather patterns or particle physics or whatever, you have to map memory (which is one-dimensional) to 2D or 3D space.  If you use a hilbert curve to do that mapping, then when you divide the space up to work on it, each little square or block will live on a continuous piece of memory, and your program will run much faster.

Also, I just think they look cool.  I played with a few filters and came up with some cool images of the 2D hilbert curve:

Also, they work in 3D too.  I wanted to see this, so I wrote a program to build a 3D hilbert curve in Minecraft:

The code to render these is here.  This code is two years old (Jan 2011), and it’s based on the pymclevel Python module, which may be dead or different by now.  Also, it outputs schematic files, which was a format you fed to a Minecraft map editor to plop the object into an existing world.

I also rendered another cool fractal, the Menger sponge:

Code to generate that is here.