Representing a 3D Hilbert Curve as an L-system

Question

A 2D Hilbert curve can be represented as the following L-system:

A → -BF+AFA+FB-
B → +AF-BFB-FA+

where F denotes a step forward, - denotes a 90 degree turn left, and + a 90 degree turn right.

(source: http://en.wikipedia.org/wiki/Hilbert_curve#Representation_as_Lindenmayer_system)

How would I go about finding the 3D L-system equivalent of the space-filling Hilbert curve?

Answer 1

Here is code from my L-system processing system. I hope the syntax is self-explaining (for someone who knows L-systems).

lsystem Hilbert3D {

    set iterations = 3;
    set symbols axiom = X;

    interpret F as DrawForward(10);
    interpret + as Yaw(90);
    interpret - as Yaw(-90);
    interpret ^ as Pitch(90);
    interpret & as Pitch(-90);
    interpret > as Roll(90);
    interpret < as Roll(-90);

    rewrite X to ^ < X F ^ < X F X - F ^ > > X F X & F + > > X F X - F > X - >;

}

Source: http://malsys.cz/g/Rrl8LtQx

Unfortunately I don't know source of this concrete L-system. I probably found it using google. Also it may not be original Hilbert curve since there are more ways how to fill cube with poly-line. But I will try to explain how to construct something like this.

Hilbert curve is space-filling curve, it fills cube. So rewrite step should create cube from line. There are more ways how to create cube from lines in space. One way is this:

rewrite X to ^ F + F + F & F & F + F + F ^;

Notice, that X will yield to cube but it will not change the orientation after interpreting it (it behaves like ordinary line – orientation at beginning is the same as at the end and one step ahead). To test this behavior, rewritten X and F must end in the same place with the same orientation.

Than from cube you want larger cube. This can be achieved by copying our first cube 8 times (to all 8 vertices of cube). The lines from first iteration will "connect" our new 8 cubes to one poly-line. Sou you just need place X (which yields to cube) to appropriate places (to vertices, between edges). In following rewrite rule, X are placed randomly just to illustrate the result.

rewrite X to ^ X F X + F + X F & X F & X F + X F + X F ^ X;

The tricky part is to achieve that each cube will be generated to appropriate place (in correct orientation). You need rotate turtle before interpreting X to correct position to place the cube (which will be created from X) in correct orientation. I leave the corrections up to you :)

Hint: Imagine that F is line and X is do the same change in space like F (moves forward) but it draws cube to some direction as a side effect.

EDIT: L-system of 3D extension of Hilbert curve can be also found in The Algorithmic Beauty of Plants on page 20. This awesome book about L-systems can be downloaded from algorithmicbotany.org.