Space-Filling Curves
Saturday 30 January, 2010
The past two days I’ve been reading a bit about space-filling curves. These are basically curves that allow you to traverse through a 2D (or any N-Dimensional) space without visiting a single point more than once.
You might wonder why these are important. Well, in order to achieve a high compression ratio for my depth maps, I need to find a highly coherent permutation of these. This permutation basicly corresponds to the order in which my depth maps are generated and compressed. (For a visual representation of this, check out the movies later on in this post.)
Currently I’ve been using a Zig-Zag curve. Other examples of space-filling curves are a Spiral or Hilbert curve. Especially the Hilbert curve is quite known and can be used for a variety of things. Some of the more art-like applications I found on the internet are color sorting or traversing the 3-dimensional RGB cube:
Below is a 2D representation of the Zig-Zag, Spiral and Hilbert space-filling curve:
Zig-zag (left) and spiral (right).
Hilbert curve of third order.
To give you an idea on how these curves are mapped on my 3D sphere:
Spiral
Hilbert
Of course, what’s really important are the results of using these new space curves. And unfortunately both the Spiral and Hilbert curve perform worse than my original Zig-Zag curve 
. Especially the result for the Hilbert curve suprises me, I really expected an improvement …
(Detailed results will follow later.)