3

I have a turtle-graphics-based algorithm for generating a space-filling Hilbert curve in two dimensions. It is recursive and goes like this:

Wa want to draw a curve of order n, in direction x (where x ∈ {L, R}), and let y be the direction opposite to x. We do as follows:

  • turn in the direction y
  • draw a Hilbert curve of order n-1, direction y
  • move one step forward
  • turn in the direction x
  • draw a Hilbert curve of order n-1, direction x
  • move one step forward
  • draw a Hilbert curve of order n-1, direction x
  • turn in the direction x
  • move one step forward
  • draw a Hilbert curve of order n-1, direction y

I understand this and was able to implement a working solution. However, I'm now trying to "upgrade" this to 3D, and here's where I basically hit a wall; in 3D, when we reach a vertex, we can turn not in two, but four directions (going straight or backing up is obviously not an option, hence four and not six). Intuitively, I think I should store the plane on which the turtle is "walking" and its general direction in the world, represented by an enum with six values:

  • Up
  • Down
  • Left
  • Right
  • In (from the camera's perspective, it goes "inside" the world)
  • Out (same as above, outside)

The turtle, like in 2D, has a state containing the information outlined above, and when it reaches as vertex (which can be thought of as a "crossing") has to make a decision where to go next, based on that state. Whereas in two dimensions it is rather simple, in three, I'm stumped.

  1. Is my approach correct? (i.e., is this what I should store in the turtle's state?)
  2. If it is, how can I use that information to make a decision where to go next?

Because there are many variants of 3D space filling Hilbert curves, I should specify that this is what I'm using as reference and to aid my imagination:

enter image description here

I'm aware that a similar question has already been asked, but the accepted answer links to a website there this problem is solved using a different approach (i.e., not turtle graphics).

Micromega
  • 12,486
  • 7
  • 35
  • 72
user4520
  • 3,401
  • 1
  • 27
  • 50
  • Generally, you turn in direction `z` and then draw a curve in direction `z`. But in step 8, you turn in direction `x`, and in step 10, you're drawing in direction `y`. Is that a typo? – Teepeemm Mar 05 '16 at 20:09
  • Possible duplicate of [Algorithm for generating a 3D Hilbert space-filling curve in Python](http://stackoverflow.com/questions/14519267/algorithm-for-generating-a-3d-hilbert-space-filling-curve-in-python) – Cimbali Mar 05 '16 at 21:47

1 Answers1

2

Your 2d algorithm can be summarized as “LRFL” or “RLFR” (with “F” being “forward”). Each letter means “turn that direction, draw a (n-1)-curve in that direction, and take a step forward”. (This assumes the x in step 8 should be a y.)

In 3d, you can summarize the algorithm as the 7 turns you would need to go along your reference. This will depend on how you visualize the turtle starting. If it starts at the empty circle, facing the filled circle, and being right-side-up (with its back facing up), then your reference would be “DLLUULL”.

Teepeemm
  • 4,331
  • 5
  • 35
  • 58