# Z-Ordering (Morton ordering) question

Discussion in 'C Programming' started by nbigaouette, Nov 5, 2009.

1. ### nbigaouetteGuest

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
[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

nbigaouette, Nov 5, 2009

2. ### GeneGuest

On Nov 5, 6:50 pm, nbigaouette <> wrote:
> 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
> [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, Nov 6, 2009

3. ### GeneGuest

On Nov 5, 8:47 pm, Gene <> wrote:
> On Nov 5, 6:50 pm, nbigaouette <> wrote:
>
> > 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
> > [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

Gene, Nov 6, 2009