## Tutorial: Hilbert Curve Coloring

Text and Images © 2001 Kerry Mitchell

### Hilbert's Space-filling Curve

German mathematician David Hilbert discovered the curve that bears his name in the early 1900's. It is an example of a "space-filling" curve: it literally covers every point in a square. Like all good fractals, it is generated in iterations. The first few are shown below:

 iteration 0 iteration 1 iteration 2

The beginning state is on the left. Hilbert designed his curve as connecting the centers of 4 sub-squares, which made up a larger square. To begin, 3 segments connect the 4 centers in an upside-down U shape.

In the middle is iteration 1. Each of the 4 squares has been divided into 4 more squares. The U shape from before is shrunk to half its original size and copied into each sector of 4 squares. In the top left, it's simply copied. In the top right, it's flipped horizontally. In the bottom left, it's rotated 90 degrees clockwise, and in the bottom right, it's rotated 90 degrees counter-clockwise. The 4 pieces are connected with 3 segments, each of which is the same size as the shrunken pieces of the U shape. They are shown in red.

The right panel shows iteration 2. Each of the 16 squares from iteration 1 has been divided into 4 more squares, and the shape from iteration 1 is shrunk and copied. Again, 3 connecting segments (shown in red) are added to complete the curve. The iteration proceeds in this fashion. At each stage, the previous curve is reduced to half its size and copied 4 times. In the upper left, it's just copied, flipped in the upper right, rotated one way in the bottom left, and rotated the other way in the bottom right. At each stage, the curve starts in the lower left corner and ends in the lower right corner, never touching or crossing itself.

### My Version

Here, we see the first 3 iterations from the Hilbert curve coloring formula (click on the images to see the uprs):

 iteration 0 iteration 1 iteration 2

The colored backgrounds have been added to visualize the construction. In each 2x2 block of squares, the curve starts in the lower left (red), moves to the upper left (green), upper right (blue), and exits from the lower right (white). In the cases for iteration 1 and 2, grid lines have been added to break up the 2x2 blocks. You can see how the basic shape is just copied, flipped, and rotated many times. The formula adds the connecting lines, so that the curve always starts in the lower left corner and ends in the lower right.

### Center Coordinates

The curve is just a series of lines connecting the centers of each of the squares. There's no reason why the point in the square has to be the exact center, and choosing other points can lead to interesting results. Each "center" point can be specified within its own sub-square. The normal curve has the points right in the center of each sub-square, with coordinates of (0.5, 0.5). The coordinates can vary from 0 to 1 in both dimensions.

 normal points moved in points moved out iteration 0 iteration 3 center coordinates lower left/red (0.5, 0.5) upper left/green (0.5, 0.5) upper right/blue (0.5, 0.5) lower right/white (0.5, 0.5) (0.75, 0.75) (0.75, 0.25) (0.25, 0.25) (0.25, 0.75) (0.25, 0.25) (0.25, 0.75) (0.75, 0.75) (0.75, 0.25)

### Enter/Exit Point

Instead of drawing connecting lines between the last point of one 2x2 block and the first point of the next 2x2 block, the formula draws a line from the last center to the edge of its sub-square, and another line from the edge of the first sub-square to its center. By design the 2 stubs connect, because the point on the edge of the last sub-square always matches up with the point on the edge of the next first sub-square. Exactly where along the sides of the sub-squares is up to you. The default is halfway along the side (enter/exit parameter value of 0.5), but it can be anything from 0 (outside corner) to 1 (boundary between lower left and lower right sub-squares). The figures below illustrate the effect of changing the enter/exit point while leaving all the centers in their default positions of (0.5, 0.5).

 normal (0.5) 0.25 0.75 iteration 0 iteration 3

### 4 Corners Point

In Hilbert's original construction, he used an initial square, broken into 4 sub-squares. The 4 corners of the sub-squares all met at the center of the larger square. There's no reason why the 4 sub-regions need to be square. In this formula, they are all rectangles and their shapes are determined by the point where the 4 corners meet. However, in order to make the enter and exit points align properly, the lower left and upper right regions need to be square. So the 4 corners point can vary along a line from the very lower left corner up to the very top right corner of the 2x2 block. The default setting for the 4 corners parameter is 0.5; it can vary from 0 to 1. The figures below illustrate the effect of changing it while leaving all the centers in their default positions of (0.5, 0.5).

 normal (0.5) 0.25 0.75 iteration 0 iteration 3

### Coloring Options

No coloring formula would be complete without a boatload of coloring options. Here, they're available under the "color by" parameter.

The "distance" method colors the pixel by its distance from the curve. See my article, "Using Ultra Fractal as a Drawing Tool," for more information on how that works. Note that this is the only mode in which the curve will be visible, so it's the only choice where the center coordinates and enter/exit point matter.

The "last = lsb" mode builds the color #index out of the sequence of sub-squares visited. As an example, imagine that you roll a single die 4 times, and get the numbers 1, 6, 2, and 3. When the 1 comes up, you start a tally with 1. Then the 6 comes up. Tack the 6 onto the 1 to get 16. (Or, multiply the 1 by 10 and add 6). The 2 makes 162, and the 3 yields 1623. Since there were 4 numbers, divide by 104 (10000) to get 0.1623. This is how the "last = lsb" mode works. Each sub-square is assigned a number 0 - 3, and when it is used, its value gets tacked on to the end of the string. Then, the final number is divided by 4iterations to get the final #index between 0 and 1. Since each subsequent iteration's value is less and less significant, you won't see much difference with this mode with more than 3 or 4 iterations.

 2 iterations 4 iterations 6 iterations last = lsb last = msb

The "last = msb" methods works in a similar fashion, but the number is prepended (added to the front). So for our die example, the #index would wind up being 0.3261. Using this with many iterations can yield an image that quickly decomposes into visual noise.  Click on either of the "6 iterations" images above to see the uprs.

The last 2 options are reflections of how this formula is implemented. Rather than finding the actual locations of all the lines and comparing those to #z, I followed Samuel Monnier's lead. In his formulas, he iterates #z and compares each iterate with the base curves. Consequently, a stack of new z values is obtained, much like with a normal fractal calculation formula. So the last 2 options color by the how far the final iterate is from #z, or by the angle between the final iterate and #z. Click on either image to see the upr.

 4 iterations distance from z angle from z

Tutorial: Hilbert's Ghost

Now that we've gotten all that background out of the way, let's use it to create the image I call, "Hilbert's Ghost."  Click on the thumbnail to see a larger version.

Step 1: the formula

• Create a new fractal, using the Pixel formula from the lkm folder.
• In the Location tab, set the Center to 0/0 and the Magnification to 0.95.
• In the Formula tab, make sure that the following are set (they're defaults):
• Drawing Method: Multi-pass Linear
• Periodicity Checking: Off
• Maximum Iterations: 1
• Adjust Automatically checkbox: doesn't matter, since we're only using 1 iteration.
Step 2: the coloring
• Since all the pixels will be outside, there's nothing to do with the Inside tab.
• In the Outside tab, click on the Select icon (3 dots) and choose Hilbert curve from the lkm folder. You should see a fairly gross up-over-down-over line.
• Set the Outside parameters:
• Color Density: 32
• Transfer Function: Linear
• Click the Reset Parameters icon in the lower right corner to reset all the formula-specific parameters.
• Set the "iterations" formula parameter to 3.
• Open the Gradient Editor and delete all the control points. Continue to click the Delete icon until there's only one left, a black control point at Index 0.
• Insert a white (set Luminance to 255) control point at index 399 (the far right).
• Insert a middle gray (0 Hue, 0 Saturation, 128 Luminance) control point at index 99.
• Check the "Smooth Curves" box.
Step 3: Progress check
• On the Layers tab of the lower Properties box, set the Width and Height parameter to the same values (say, 480 pixels). You may need to clear the Maintain aspect ratio box to do this.
• You should now have an image that looks like the one on the right, the basic 3rd iteration Hilbert curve.
The plan (click for upr):

Here's the plan, shown on the left for 0 iterations and in color. We're going to have 9 layers, each with slightly different center coordinates. The bottom layer is shown in red and the top layer in cyan. Each layer has the same entry/exit point, which is why all the lines come together at the bottom in the middle and on the right side in the middle. Each layer will have the 4 corners point be in the middle, which is why the red and cyan lines cross there. Ready?

Step 4: Set the first layer

• In the Layers tab of the lower Properties box, change the Name of this layer to "New Layer 1." This will help keep things straight when we add 8 more layers.
• In the Outside tab, set the formula-specific parameters:
• lower left center: 0/0 (0 for the Re part and 0 for the Im part)
• upper left center: 1/0
• upper right center: 1/1
• lower right center: 0/1
• enter/exit: 1 (same for all layers)
• 4 corners: 0.5 (same for all layers)
• iterations: 3 (same for all layers)
• color by: distance (same for all layers)
Step 5: Add a bunch more
• Click on the Add icon at the bottom of the Layers tab in the bottom Properties box. This should add a new layer, "New Layer 2." Since all the parameters for this layer are the same as for the previous layer, the overall image shouldn't change.
• Change the Merge mode to Multiply and the Opacity to 100%.
• Click the Add icon of "New Layer 2" 7 times to add layers up through "New Layer 9." They should all have Multiply Merge mode and Opacity of 100%. Only the center coordinates will change, according to this table:
 layer lower left upper left upper right lower right 2 0.125/0.125 0.875/0.125 0.875/0.875 0.125/0.875 3 0.25/0.25 0.75/0.25 0.75/0.75 0.25/0.75 4 0.375/0.375 0.625/0.375 0.625/0.625 0.375/0.625 5 0.5/0.5 0.5/0.5 0.5/0.5 0.5/0.5 6 0.625/0.625 0.375/0.625 0.375/0.375 0.625/0.375 7 0.75/0.75 0.25/0.75 0.25/0.25 0.75/0.25 8 0/875/0.875 0.125/0.875 0.125/0.125 0.875/0.125 9 1/1 0/1 0/0 1/0
• If the typing's too much for you, click on the thumbnail below for the upr.
• If you've made a mistake, it will probably show up as a gap between the otherwise regularly-spaced lines. The lines may appear broken if you use a small resolution. For best results, render it to disk with anti-aliasing.
• Admire your handiwork and be sure to share your Hilbert curve creations with the rest of us!

Back to Tutorials page