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


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?


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 - >;


Result of 2nd iteration of 3D Hilbert curve

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.

  • $\begingroup$ Thanks, I'll give it a shot. If it's not a burden, would you mind explaining how you got to this? $\endgroup$ – Yuval Adam Mar 28 '12 at 17:41
  • $\begingroup$ Are you using yaw/pitch/roll in the same sense as in airplane attitudes ( en.wikipedia.org/wiki/Degrees_of_freedom_(mechanics) )? To get your rule to work, I had to switch the yaw directions. (Maybe I have a bug in my code?) $\endgroup$ – Alexander Pruss May 24 '15 at 17:45
  • $\begingroup$ @AlexanderPruss You are right, my positive Yaw is turning left but the model you linked is turning right. However, this is given by natural implementation using quaternions. The Yaw operation is just: state.Rotation *= new Quaternion(upVector, angle); where upVector is (0, 1, 0) by default (implementation here: github.com/NightElfik/Malsys/blob/master/src/Malsys/Processing/… ). $\endgroup$ – NightElfik May 28 '15 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.