Space-filling curves are important in many graphics applications because they help expose spatial locality. We often hear about different algorithms using Z-curves, Morton codes, Hilbert curves, etc. What are the differences between some of these different curves and how do they apply to various applications?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Try the book Space-Filling Curves - An Introduction with Applications in Scientific Computing. $\endgroup$– lhfSep 11, 2015 at 19:14
-
$\begingroup$ See also section 2.1.1.2 of Samet's Foundations of Multidimensional and Metric Data Structures. $\endgroup$– lhfSep 12, 2015 at 1:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The difference is how well a mapping preserves locality and how easy it is to encode/decode the keys. The paper "Linear Clustering of Objects with Multiple Attributes" by H V Jagadish says: "Through algebraic analysis, and through computer simulation, we showed that under most circumstances, the Hilbert mapping performed as well as or better than the best of alternative mappings suggested in the literature". On the other hand, z-order is a bit simpler to use, for example compare the various methods listed in Bit Twiddling Hacks for z-order and Wikipedia for Hilbert-order.
As for the applications, I think the main advantage in using space filling curves is that they map points from higher dimensional space to space of lower dimension. For example, they make it possible to window query for points using traditional B-tree database index. Again, on the other hand, the disadvantage is that one needs to know the bounds of the input in advance as it is difficult to "resize" the mapping later.
PS: "Z-curve" is the same as "Morton code".
PPS: Additional mappings include Peano curve and for applications see also Geohash.
$\begingroup$
$\endgroup$
Those space filling curves allow to keep locality in multiple dimensions when you "walk" linearly along the curve.
From what I have seen, Z-Order (also known as Morton code) is the most employed because of its computational cost which is constant (and cheap) to access any point of the curve directly. (And easy to implement in hardware with 0 cycle penalty, as it corresponds to "just switching" address wires).
A concrete example of Z-Order curve is texture swizzling : which is basically increasing the cache-hit rate for texture read on GPUs. (See images in the article about Z-Curve https://en.wikipedia.org/wiki/Z-order_curve)
If the texture is simply stored linearly, you get the maximum cache hit if you render just the texture as 2D image, but if you rotated it by 90 degree on screen, you get into the worst case scenario (cache miss for every texture read).
As a result, it is better to trade off a little and lower your best case scenario and have better cache hit for most of the patterns.
As a personal note, from what I have seen, other curves may require recursive step for their computation and result in bigger cost than Z-Curve with a minimal gain in term of locality coherence. So, I have not heard about those curve used with a practical purpose, except as a research subject in mathematic or creative/funny rendering.