Z-Ordering (Morton ordering) question

[nbigaouette]

I need to sort a list of objects based on their position into a Z-oder
[1]. Everywhere I look, z-order is used by interleaving bit
representation of integers]. In my case, the objects have a double
precision[2] position in three dimension.

Somebody told me it would not work with double precision because the
mantissa has a different meaning then the exponent. But I was not
convinced and tried anyway. Actually, since the exponent is stored in
higher significant bits then the mantissa, I think I could interleave
the bits from the exponents, and then interleave the mantissa. So I
implemented that. Hell, I even did it manually (with 32 bits floats,
not 64 bits doubles).

But I cannot make it work reliably. I'd like to get some comments on
that...

My procedure was as follow. Place 16 particles on a 4x4 grid. The
positions in x and y dimensions are 1, 2, 3 and 4 bohrs[3] but
expressed in meters. The initial ordering (as found in memory) is:
13 14 15 16


9 10 11 12


5 6 7 8


1 2 3 4

The 16 [x,y] positions are, in meters:
[5.29177240552557e-11 , 5.29177240552557e-11]
[1.05835448110511e-10 , 5.29177240552557e-11]
[1.58753172165767e-10 , 5.29177240552557e-11]
[2.11670896221023e-10 , 5.29177240552557e-11]
[5.29177240552557e-11 , 1.05835448110511e-10]
[1.05835448110511e-10 , 1.05835448110511e-10]
[1.58753172165767e-10 , 1.05835448110511e-10]
[2.11670896221023e-10 , 1.05835448110511e-10]
[5.29177240552557e-11 , 1.58753172165767e-10]
[1.05835448110511e-10 , 1.58753172165767e-10]
[1.58753172165767e-10 , 1.58753172165767e-10]
[2.11670896221023e-10 , 1.58753172165767e-10]
[5.29177240552557e-11 , 2.11670896221023e-10]
[1.05835448110511e-10 , 2.11670896221023e-10]
[1.58753172165767e-10 , 2.11670896221023e-10]
[2.11670896221023e-10 , 2.11670896221023e-10]
As you might "see", the x dimension is incremented first, then y.

I then converted these decimals to binary representation[4]:
[00101110011010001011110000010000 , 00101110011010001011110000010000]
[00101110111010001011110000010000 , 00101110011010001011110000010000]
[00101111001011101000110100001100 , 00101110011010001011110000010000]
[00101111011010001011110000010000 , 00101110011010001011110000010000]
[00101110011010001011110000010000 , 00101110111010001011110000010000]
[00101110111010001011110000010000 , 00101110111010001011110000010000]
[00101111001011101000110100001100 , 00101110111010001011110000010000]
[00101111011010001011110000010000 , 00101110111010001011110000010000]
[00101110011010001011110000010000 , 00101111001011101000110100001100]
[00101110111010001011110000010000 , 00101111001011101000110100001100]
[00101111001011101000110100001100 , 00101111001011101000110100001100]
[00101111011010001011110000010000 , 00101111001011101000110100001100]
[00101110011010001011110000010000 , 00101111011010001011110000010000]
[00101110111010001011110000010000 , 00101111011010001011110000010000]
[00101111001011101000110100001100 , 00101111011010001011110000010000]
[00101111011010001011110000010000 , 00101111011010001011110000010000]

Then, I manually interleaved the x and y bits. For example, for the
first position [1,1] bohr, I first put the two binary numbers one
after the other. Secondly, I add a space between each digit, and third
shift the lower one by adding another space at the front of it. The
bit interleaving just then appears with the bits aligned:
1)
00101110011010001011110000010000
00101110011010001011110000010000
2)
0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
3)
0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
4)
0000110011111100001111001100000011001111111100000000001100000000

Doing this manual procedure for all the combinations, I get the
following:
0000110011111100001111001100000011001111111100000000001100000000 r1
0000110011111100101111001100000011001111111100000000001100000000 r2
0000110011111110000111001110100011000101111100100000000110100000 r3
0000110011111110001111001100000011001111111100000000001100000000 r4
0000110011111100011111001100000011001111111100000000001100000000 r5
0000110011111100111111001100000011001111111100000000001100000000 r6
0000110011111110010111001110101011000101111100100000000110100000 r7
0000110011111110011111001100000011001111111100000000001100000000 r8
0000110011111101001011001101010011001010111100010000001001010000 r9
0000110011111101101011001101010011001010111100010000001001010000
r10
0000110011111111000011001111110011000000111100110000000011110000
r11
0000110011111111001011001101010011001010111100010000001001010000
r12
0000110011111101001111001100000011001111111100000000001100000000
r13
0000110011111101101111001100000011001111111100000000001100000000
r14
0000110011111111000111001110100011000101111100100000000110100000
r15
0000110011111111001111001100000011001111111100000000001100000000
r16

Note that I added a name at the end to keep track of which line
represent which positions. I saved that to a file, cat'ed it, and
piped to "sort":
$ cat to_sort.txt | sort
0000110011111100001111001100000011001111111100000000001100000000 r1
0000110011111100011111001100000011001111111100000000001100000000 r5
0000110011111100101111001100000011001111111100000000001100000000 r2
0000110011111100111111001100000011001111111100000000001100000000 r6
0000110011111101001011001101010011001010111100010000001001010000 r9
0000110011111101001111001100000011001111111100000000001100000000
r13
0000110011111101101011001101010011001010111100010000001001010000
r10
0000110011111101101111001100000011001111111100000000001100000000
r14
0000110011111110000111001110100011000101111100100000000110100000 r3
0000110011111110001111001100000011001111111100000000001100000000 r4
0000110011111110010111001110101011000101111100100000000110100000 r7
0000110011111110011111001100000011001111111100000000001100000000 r8
0000110011111111000011001111110011000000111100110000000011110000
r11
0000110011111111000111001110100011000101111100100000000110100000
r15
0000110011111111001011001101010011001010111100010000001001010000
r12
0000110011111111001111001100000011001111111100000000001100000000
r16

I now have an (almost) Z-order list. Here is a what it produces:
13 14 15 16
| \ | \ | \ |
| \ | \ | \ |
9 10 | 11 12
\ | \
\ | \
5 6 | 7 ----- 8
| \ | | \
| \ | \ \
1 2 3 ----- 4

As you see, the 7 and 4 are inverted from what it should give (an "N"
ordering, instead of "Z", but that is equivalent and irrelevant). Now
if I automate all this, I get similar weird results. It is even worse
when the system is big. As examples, I have ploted the ordering for a
small grid (the previous example)[5], a bigger grid[6] and a big disk
[7]

Now I cannot belive that Z-ordering does not work with double
precision data since I almost got it. But then, I cannot correctly get
what I want... Did anybody worked with that before? Does anyone can
comment on the procedure? If you spot a mistake?

I absolutely need to make this working...

Thanx a lot.


[1] http://en.wikipedia.org/wiki/Z-order_(curve)
[2] http://en.wikipedia.org/wiki/Double_precision
[3] http://en.wikipedia.org/wiki/Bohr_radius
[4] http://www.binaryconvert.com/convert_float.html
[5] http://nbigaouette.inrs-emt.homelinux.net/perso/zorder/Zorder_grid_small.png
[6] http://nbigaouette.inrs-emt.homelinux.net/perso/zorder/Zorder_grid_big.png
[7] http://nbigaouette.inrs-emt.homelinux.net/perso/zorder/Zorder_disk.png

 

[Gene]

I need to sort a list of objects based on their position into a Z-oder
[1]. Everywhere I look, z-order is used by interleaving bit
representation of integers]. In my case, the objects have a double
precision[2] position in three dimension.

Somebody told me it would not work with double precision because the
mantissa has a different meaning then the exponent. But I was not
convinced and tried anyway. Actually, since the exponent is stored in
higher significant bits then the mantissa, I think I could interleave
the bits from the exponents, and then interleave the mantissa. So I
implemented that. Hell, I even did it manually (with 32 bits floats,
not 64 bits doubles).

But I cannot make it work reliably. I'd like to get some comments on
that...

My procedure was as follow. Place 16 particles on a 4x4 grid. The
positions in x and y dimensions are 1, 2, 3 and 4 bohrs[3] but
expressed in meters. The initial ordering (as found in memory) is:
13      14      15      16

9       10      11      12

5       6       7       8

1       2       3       4

The 16 [x,y] positions are, in meters:
[5.29177240552557e-11 , 5.29177240552557e-11]
[1.05835448110511e-10 , 5.29177240552557e-11]
[1.58753172165767e-10 , 5.29177240552557e-11]
[2.11670896221023e-10 , 5.29177240552557e-11]
[5.29177240552557e-11 , 1.05835448110511e-10]
[1.05835448110511e-10 , 1.05835448110511e-10]
[1.58753172165767e-10 , 1.05835448110511e-10]
[2.11670896221023e-10 , 1.05835448110511e-10]
[5.29177240552557e-11 , 1.58753172165767e-10]
[1.05835448110511e-10 , 1.58753172165767e-10]
[1.58753172165767e-10 , 1.58753172165767e-10]
[2.11670896221023e-10 , 1.58753172165767e-10]
[5.29177240552557e-11 , 2.11670896221023e-10]
[1.05835448110511e-10 , 2.11670896221023e-10]
[1.58753172165767e-10 , 2.11670896221023e-10]
[2.11670896221023e-10 , 2.11670896221023e-10]
As you might "see", the x dimension is incremented first, then y.

I then converted these decimals to binary representation[4]:
[00101110011010001011110000010000 , 00101110011010001011110000010000]
[00101110111010001011110000010000 , 00101110011010001011110000010000]
[00101111001011101000110100001100 , 00101110011010001011110000010000]
[00101111011010001011110000010000 , 00101110011010001011110000010000]
[00101110011010001011110000010000 , 00101110111010001011110000010000]
[00101110111010001011110000010000 , 00101110111010001011110000010000]
[00101111001011101000110100001100 , 00101110111010001011110000010000]
[00101111011010001011110000010000 , 00101110111010001011110000010000]
[00101110011010001011110000010000 , 00101111001011101000110100001100]
[00101110111010001011110000010000 , 00101111001011101000110100001100]
[00101111001011101000110100001100 , 00101111001011101000110100001100]
[00101111011010001011110000010000 , 00101111001011101000110100001100]
[00101110011010001011110000010000 , 00101111011010001011110000010000]
[00101110111010001011110000010000 , 00101111011010001011110000010000]
[00101111001011101000110100001100 , 00101111011010001011110000010000]
[00101111011010001011110000010000 , 00101111011010001011110000010000]

Then, I manually interleaved the x and y bits. For example, for the
first position [1,1] bohr, I first put the two binary numbers one
after the other. Secondly, I add a space between each digit, and third
shift the lower one by adding another space at the front of it. The
bit interleaving just then appears with the bits aligned:
1)
00101110011010001011110000010000
00101110011010001011110000010000
2)
0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
3)
0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
4)
0000110011111100001111001100000011001111111100000000001100000000

Doing this manual procedure for all the combinations, I get the
following:
0000110011111100001111001100000011001111111100000000001100000000    r1
0000110011111100101111001100000011001111111100000000001100000000    r2
0000110011111110000111001110100011000101111100100000000110100000    r3
0000110011111110001111001100000011001111111100000000001100000000    r4
0000110011111100011111001100000011001111111100000000001100000000    r5
0000110011111100111111001100000011001111111100000000001100000000    r6
0000110011111110010111001110101011000101111100100000000110100000    r7
0000110011111110011111001100000011001111111100000000001100000000    r8
0000110011111101001011001101010011001010111100010000001001010000    r9
0000110011111101101011001101010011001010111100010000001001010000
r10
0000110011111111000011001111110011000000111100110000000011110000
r11
0000110011111111001011001101010011001010111100010000001001010000
r12
0000110011111101001111001100000011001111111100000000001100000000
r13
0000110011111101101111001100000011001111111100000000001100000000
r14
0000110011111111000111001110100011000101111100100000000110100000
r15
0000110011111111001111001100000011001111111100000000001100000000
r16

Note that I added a name at the end to keep track of which line
represent which positions. I saved that to a file, cat'ed it, and
piped to "sort":
$ cat to_sort.txt | sort
0000110011111100001111001100000011001111111100000000001100000000    r1
0000110011111100011111001100000011001111111100000000001100000000    r5
0000110011111100101111001100000011001111111100000000001100000000    r2
0000110011111100111111001100000011001111111100000000001100000000    r6
0000110011111101001011001101010011001010111100010000001001010000    r9
0000110011111101001111001100000011001111111100000000001100000000
r13
0000110011111101101011001101010011001010111100010000001001010000
r10
0000110011111101101111001100000011001111111100000000001100000000
r14
0000110011111110000111001110100011000101111100100000000110100000    r3
0000110011111110001111001100000011001111111100000000001100000000    r4
0000110011111110010111001110101011000101111100100000000110100000    r7
0000110011111110011111001100000011001111111100000000001100000000    r8
0000110011111111000011001111110011000000111100110000000011110000
r11
0000110011111111000111001110100011000101111100100000000110100000
r15
0000110011111111001011001101010011001010111100010000001001010000
r12
0000110011111111001111001100000011001111111100000000001100000000
r16

I now have an (almost) Z-order list. Here is a what it produces:
13      14      15      16
|  \    | \     |  \    |
|    \  |  \    |    \  |
9       10  |   11      12
   \        |      \
     \      |        \
5       6   |   7 ----- 8
|  \    |   |      \
|    \  |    \       \
1       2       3 ----- 4

As you see, the 7 and 4 are inverted from what it should give (an "N"
ordering, instead of "Z", but that is equivalent and irrelevant). Now
if I automate all this, I get similar weird results. It is even worse
when the system is big. As examples, I have ploted the ordering for a
small grid (the previous example)[5], a bigger grid[6] and a big disk
[7]

Now I cannot belive that Z-ordering does not work with double
precision data since I almost got it. But then, I cannot correctly get
what I want... Did anybody worked with that before? Does anyone can
comment on the procedure? If you spot a mistake?

I absolutely need to make this working...

Thanx a lot.

[1]http://en.wikipedia.org/wiki/Z-order_(curve)
[2]http://en.wikipedia.org/wiki/Double_precision
[3]http://en.wikipedia.org/wiki/Bohr_radius
[4]http://www.binaryconvert.com/convert_float.html
[5]http://nbigaouette.inrs-emt.homelinux.net/perso/zorder/Zorder_grid_sm....
[6]http://nbigaouette.inrs-emt.homelinux.net/perso/zorder/Zorder_grid_bi....
[7]http://nbigaouette.inrs-emt.homelinux.net/perso/zorder/Zorder_disk.png

The people who told you that it's nonsense to mix bits of floating
point numbers were correct. The bit-interleave algorithm exploits the
fact that bit i has a weight of 2^i. This is only true of non-
negative integers.

In a floating point number (ignoring signs for the moment), bit i of
the mantissa has a weight of 2^(i + E) where E is the value of the
exponent.

To get correct results, you'd need to build Morton codes by decoding
the floating point values into integers according to the above and
then bit-interleaving those integers.

Here's the problem. The IEEE double precision floating point format
can express a dynamic range of something like 2^(2048 + 52) = 2^2100.
(This is approximate. I'm not an IEEE format expert.) This means that
a precise but naive Morton-order coordinate (if you don't know
anything about the range of your data) representation would need up to
roughly 2,100 bits. Of course many of these bits will be zero, so you
could reduce the space with a fancy data structure accounting for
sparseness, but then the comparison and sorting algorithms are more
complicated.

If you know the dynamic range of your data is small compared to the
full IEEE representation space, you should be able to do fine if you
convert your a double coords (X, Y) into e.g. 64 bit integer coords
(Xi, Yi) with something like

Xi = floor( (X - Xmin) / (Xmax - Xmin) )
Yi = floor( (Y - Ymin) / (Ymax - Ymin) )

and now build a 128-bit Morton code out of Xi and Yi.

The 64 bits integers would allow for dynamic range e.g. |Xmax/Xmin|
and |Ymax/yMin| to be roughly 2^(63 - 51) = 2^12 = 4096 before you'd
run into problems with multiple floating point values mapping to a
single integer. (Check this. I'm making rough approximations again.)

Of course if you aren't concerned with exact precision in the morton
order, you could use smaller integers and accept the fact that
coordinates close together on either axis might sort incorrectly.

 

[Gene]

I need to sort a list of objects based on their position into a Z-oder
[1]. Everywhere I look, z-order is used by interleaving bit
representation of integers]. In my case, the objects have a double
precision[2] position in three dimension.

Somebody told me it would not work with double precision because the
mantissa has a different meaning then the exponent. But I was not
convinced and tried anyway. Actually, since the exponent is stored in
higher significant bits then the mantissa, I think I could interleave
the bits from the exponents, and then interleave the mantissa. So I
implemented that. Hell, I even did it manually (with 32 bits floats,
not 64 bits doubles).

But I cannot make it work reliably. I'd like to get some comments on
that...

My procedure was as follow. Place 16 particles on a 4x4 grid. The
positions in x and y dimensions are 1, 2, 3 and 4 bohrs[3] but
expressed in meters. The initial ordering (as found in memory) is:
13      14      15      16

9       10      11      12

5       6       7       8

1       2       3       4

The 16 [x,y] positions are, in meters:
[5.29177240552557e-11 , 5.29177240552557e-11]
[1.05835448110511e-10 , 5.29177240552557e-11]
[1.58753172165767e-10 , 5.29177240552557e-11]
[2.11670896221023e-10 , 5.29177240552557e-11]
[5.29177240552557e-11 , 1.05835448110511e-10]
[1.05835448110511e-10 , 1.05835448110511e-10]
[1.58753172165767e-10 , 1.05835448110511e-10]
[2.11670896221023e-10 , 1.05835448110511e-10]
[5.29177240552557e-11 , 1.58753172165767e-10]
[1.05835448110511e-10 , 1.58753172165767e-10]
[1.58753172165767e-10 , 1.58753172165767e-10]
[2.11670896221023e-10 , 1.58753172165767e-10]
[5.29177240552557e-11 , 2.11670896221023e-10]
[1.05835448110511e-10 , 2.11670896221023e-10]
[1.58753172165767e-10 , 2.11670896221023e-10]
[2.11670896221023e-10 , 2.11670896221023e-10]
As you might "see", the x dimension is incremented first, then y.

I then converted these decimals to binary representation[4]:
[00101110011010001011110000010000 , 00101110011010001011110000010000]
[00101110111010001011110000010000 , 00101110011010001011110000010000]
[00101111001011101000110100001100 , 00101110011010001011110000010000]
[00101111011010001011110000010000 , 00101110011010001011110000010000]
[00101110011010001011110000010000 , 00101110111010001011110000010000]
[00101110111010001011110000010000 , 00101110111010001011110000010000]
[00101111001011101000110100001100 , 00101110111010001011110000010000]
[00101111011010001011110000010000 , 00101110111010001011110000010000]
[00101110011010001011110000010000 , 00101111001011101000110100001100]
[00101110111010001011110000010000 , 00101111001011101000110100001100]
[00101111001011101000110100001100 , 00101111001011101000110100001100]
[00101111011010001011110000010000 , 00101111001011101000110100001100]
[00101110011010001011110000010000 , 00101111011010001011110000010000]
[00101110111010001011110000010000 , 00101111011010001011110000010000]
[00101111001011101000110100001100 , 00101111011010001011110000010000]
[00101111011010001011110000010000 , 00101111011010001011110000010000]

Then, I manually interleaved the x and y bits. For example, for the
first position [1,1] bohr, I first put the two binary numbers one
after the other. Secondly, I add a space between each digit, and third
shift the lower one by adding another space at the front of it. The
bit interleaving just then appears with the bits aligned:
1)
00101110011010001011110000010000
00101110011010001011110000010000
2)
0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
3)
0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
4)
0000110011111100001111001100000011001111111100000000001100000000

Doing this manual procedure for all the combinations, I get the
following:
0000110011111100001111001100000011001111111100000000001100000000    r1
0000110011111100101111001100000011001111111100000000001100000000    r2
0000110011111110000111001110100011000101111100100000000110100000    r3
0000110011111110001111001100000011001111111100000000001100000000    r4
0000110011111100011111001100000011001111111100000000001100000000    r5
0000110011111100111111001100000011001111111100000000001100000000    r6
0000110011111110010111001110101011000101111100100000000110100000    r7
0000110011111110011111001100000011001111111100000000001100000000    r8
0000110011111101001011001101010011001010111100010000001001010000    r9
0000110011111101101011001101010011001010111100010000001001010000
r10
0000110011111111000011001111110011000000111100110000000011110000
r11
0000110011111111001011001101010011001010111100010000001001010000
r12
0000110011111101001111001100000011001111111100000000001100000000
r13
0000110011111101101111001100000011001111111100000000001100000000
r14
0000110011111111000111001110100011000101111100100000000110100000
r15
0000110011111111001111001100000011001111111100000000001100000000
r16

Note that I added a name at the end to keep track of which line
represent which positions. I saved that to a file, cat'ed it, and
piped to "sort":
$ cat to_sort.txt | sort
0000110011111100001111001100000011001111111100000000001100000000    r1
0000110011111100011111001100000011001111111100000000001100000000    r5
0000110011111100101111001100000011001111111100000000001100000000    r2
0000110011111100111111001100000011001111111100000000001100000000    r6
0000110011111101001011001101010011001010111100010000001001010000    r9
0000110011111101001111001100000011001111111100000000001100000000
r13
0000110011111101101011001101010011001010111100010000001001010000
r10
0000110011111101101111001100000011001111111100000000001100000000
r14
0000110011111110000111001110100011000101111100100000000110100000    r3
0000110011111110001111001100000011001111111100000000001100000000    r4
0000110011111110010111001110101011000101111100100000000110100000    r7
0000110011111110011111001100000011001111111100000000001100000000    r8
0000110011111111000011001111110011000000111100110000000011110000
r11
0000110011111111000111001110100011000101111100100000000110100000
r15
0000110011111111001011001101010011001010111100010000001001010000
r12
0000110011111111001111001100000011001111111100000000001100000000
r16

I now have an (almost) Z-order list. Here is a what it produces:
13      14      15      16
|  \    | \     |  \    |
|    \  |  \    |    \  |
9       10  |   11      12
   \        |      \
     \      |        \
5       6   |   7 ----- 8
|  \    |   |      \
|    \  |    \       \
1       2       3 ----- 4

As you see, the 7 and 4 are inverted from what it should give (an "N"
ordering, instead of "Z", but that is equivalent and irrelevant). Now
if I automate all this, I get similar weird results. It is even worse
when the system is big. As examples, I have ploted the ordering for a
small grid (the previous example)[5], a bigger grid[6] and a big disk
[7]

Now I cannot belive that Z-ordering does not work with double
precision data since I almost got it. But then, I cannot correctly get
what I want... Did anybody worked with that before? Does anyone can
comment on the procedure? If you spot a mistake?

I absolutely need to make this working...

Thanx a lot.

[1]http://en.wikipedia.org/wiki/Z-order_(curve)
[2]http://en.wikipedia.org/wiki/Double_precision
[3]http://en.wikipedia.org/wiki/Bohr_radius
[4]http://www.binaryconvert.com/convert_float.html
[5]http://nbigaouette.inrs-emt.homelinux.net/perso/zorder/Zorder_grid_sm...
[6]http://nbigaouette.inrs-emt.homelinux.net/perso/zorder/Zorder_grid_bi...
[7]http://nbigaouette.inrs-emt.homelinux.net/perso/zorder/Zorder_disk.png

The people who told you that it's nonsense to mix bits of floating
point numbers were correct.  The bit-interleave algorithm exploits the
fact that bit i has a weight of 2^i.  This is only true of non-
negative integers.

In a floating point number (ignoring signs for the moment), bit i of
the mantissa has a weight of 2^(i + E) where E is the value of the
exponent.

To get correct results, you'd need to build Morton codes by decoding
the floating point values into integers according to the above and
then bit-interleaving those integers.

Here's the problem.  The IEEE double precision floating point format
can express a dynamic range of something like 2^(2048 + 52) = 2^2100.
(This is approximate. I'm not an IEEE format expert.) This means that
a precise but naive Morton-order coordinate (if you don't know
anything about the range of your data) representation would need up to
roughly 2,100 bits.  Of course many of these bits will be zero, so you
could reduce the space with a fancy data structure accounting for
sparseness, but then the comparison and sorting algorithms are more
complicated.

If you know the dynamic range of your data is small compared to the
full IEEE representation space, you should be able to do fine if you
convert your a double coords (X, Y) into e.g. 64 bit integer coords
(Xi, Yi) with something like

Xi = floor( (X - Xmin) / (Xmax - Xmin) )
Yi = floor( (Y - Ymin) / (Ymax - Ymin) )

and now build a 128-bit Morton code out of Xi and Yi.

The 64 bits integers would allow for dynamic range e.g. |Xmax/Xmin|
and |Ymax/yMin| to be roughly 2^(63 - 51) = 2^12 = 4096 before you'd
run into problems with multiple floating point values mapping to a
single integer.  (Check this. I'm making rough approximations again.)

Of course if you aren't concerned with exact precision in the morton
order, you could use smaller integers and accept the fact that
coordinates close together on either axis might sort incorrectly.

Sorry I typed too fast. "2^(i + E)" above is qualitative: the exct
magnitude of a bit in the mantissa depends on bit numbering and where
the implicit binary point lies. I'll let others work out the precise
expression. Also, the naively stored Morton coordinate might have
4200 bits, not 2100.

Gene