Ben Gordon

I recently "never graduated" from the Recurse Center, a self-directed, community-driven educational retreat for programmers in New York City. The Recurse Center promotes a self-directed approach to learning, where there are no teachers or curriculum, rather, each student works on what interests them most, with the support of a community of other highly motivated students.

During my time at the Recurse Center (which I'll now refer to as "RC"), I committed to self-study a list of technologies, languages, and concepts:

• A compiled high-performance programming language (Rust)
• Low-level computer hardware through the Nand2Tetris course
• Gaining a preliminary understanding of Distributed Systems from Martin Kleppman's Designing Data Intensive Applications
• Learning more about 3D graphics through rasterization and rendering techniques

Background and Motivation

When I started this project, I had just finished an OBJ file renderer using WebGL, Rust, and WebAssembly. That project was a webpage that rendered a complex 40,000 vertex 3D model, and allowed to user to rotate that model with mouse controls. I had taken on that project with the intention of learning more about Rust and WebAssembly. After finishing, I felt much stronger on the core principles of Rust and WebAssembly using Wasm-Bindgen, but I felt I hadn't taken full advantage of WASM's performance or Rust's type system.

For my next project, I set out to take full advantage of Rust and WebAssembly by generating geometries in real-time. The only question was "What geometry was both visually interesting and industrially useful enough to build a project around?" My answer is Hilbert Curves.

So what is a Hilbert Curve?

A Hilbert Curve is a fractal space-filling curve. In essence, it is one of many possible ways to fold a line segment such that it passes through all points in a unit square, where the resulting curve forms a fractal pattern.

Hilbert Curves have some special properties that make them stand out in term of industrial use. Specifically, they have good locality preservation, meaning that any two points on the line segment that are near each other in 1D space will continue to be close to each other once the curve is folded into a 2D arrangement. This property makes these curves useful for a wide variety of applications including data storage, data visualization, 3D graphics, image processing, etc...

How do I make one?

If you want a deep dive into the math of Hilbert Curve generation, keep an eye out for part 2 of this series where I dig into math behind the Skilling Transform. For now, I'll be approaching the topic of Hilbert Curve construction purely visually using the recursive approach.

To get us started, here is the base unit of a Hilbert Curve. This "U" shape is a first-order Hilbert Curve. All of our higher-order Hilbert Curves in the future will be built from many copies of this first order curve, so you can think of this as our building block.

To construct our second order Hilbert Curve, we will clone the first order Hilbert Curve 4 times, rotate each curve, then connect the segments together:

We can repeat this pattern once more, cloning the second order curve, rotating the copies, and then connecting each copy with a small line segment. This generates the third order Hilbert Curve:

Since the pattern is recursive, we can repeat this operation indefinitely to keep generating higher order curves. I'll spare you more boring exposition and just render the 4th, 5th, and 6th order curves:

Hungry for More?

And that's all for now! If you are interested in seeing how this recursive method carries over from generating 2D Hilbert Planar Curves into 3D Hilbert Spatial Cubes, check out Part 2 of this series!