<p>Those space filling curves allow to keep locality in multiple dimensions when you "walk" linearly along the curve.</p>

<p>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).</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Z-order_curve">https://en.wikipedia.org/wiki/Z-order_curve</a>)</p>

<p>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).</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-09-12T05:55:26.723Z
2015-09-12T06:03:22.127Z
2015-09-12T06:03:22.127Z
Romain Piquois
<p>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 <a href="https://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious">Bit Twiddling Hacks</a> for z-order and <a href="https://en.wikipedia.org/wiki/Hilbert_curve#Applications_and_mapping_algorithms">Wikipedia</a> for Hilbert-order.</p>

<p>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.</p>

<p>PS: "Z-curve" is the same as "Morton code".</p>

<p>PPS: Additional mappings include <a href="https://en.wikipedia.org/wiki/Peano_curve">Peano curve</a> and for applications see also <a href="https://en.wikipedia.org/wiki/Geohash">Geohash</a>.</p>

CC BY-SA 3.0
2015-09-11T21:24:34.860Z
2015-09-11T21:36:23.550Z
2015-09-11T21:36:23.550Z
Ecir Hana
<p>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?</p>

CC BY-SA 3.0
2015-09-11T19:14:30.400Z
Try the book [Space-Filling Curves - An Introduction with Applications in Scientific Computing](http://www.space-filling-curves.org/).
lhf
CC BY-SA 3.0
2015-09-12T01:02:50.127Z
See also section 2.1.1.2 of Samet's *Foundations of Multidimensional and Metric Data Structures*.
lhf
<space-filling>
What is the difference between various space-filling curves?
ap_
# What is the difference between various space-filling curves?

(Asked by: username_0 on 2015-09-11)

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?

**Tags:** space-filling

> **Comments:**
> **username_1**: Try the book [Space-Filling Curves - An Introduction with Applications in Scientific Computing](http://www.space-filling-curves.org/).  
> **username_1**: See also section 2.1.1.2 of Samet's *Foundations of Multidimensional and Metric Data Structures*.  

---

## 2 answers

### Answer by username_3 on 2015-09-11. Score: 15 | Accepted answer

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](https://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious) for z-order and [Wikipedia](https://en.wikipedia.org/wiki/Hilbert_curve#Applications_and_mapping_algorithms) 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](https://en.wikipedia.org/wiki/Peano_curve) and for applications see also [Geohash](https://en.wikipedia.org/wiki/Geohash).


---

### Answer by username_2 on 2015-09-12. Score: 10

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.


---

