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
-
Gradient Offset: 0
-
Repeat Gradient checkbox: cleared
-
Click the Reset Parameters icon in the lower right corner to reset all
the formula-specific parameters.
-
Set the "iterations" formula parameter to 3.
-
Set the gradient.
-
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.
-
Close the Gradient Editor.
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
|
lower right
|
upper 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
Up
to my home page