Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
First Google hit: mathforum.org/advanced/robertd/lsys3d.html –  lhf Mar 23 '12 at 16:02

1 Answer 1

up vote 1 down vote accepted

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

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.

share|improve this answer
    
Thanks, I'll give it a shot. If it's not a burden, would you mind explaining how you got to this? –  Yuval Adam Mar 28 '12 at 17:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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