Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Z-Ordering (Morton ordering) question

Reply
Thread Tools

Z-Ordering (Morton ordering) question

 
 
nbigaouette
Guest
Posts: n/a
 
      11-05-2009
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)
00001100111111000011110011000000110011111111000000 00001100000000

Doing this manual procedure for all the combinations, I get the
following:
00001100111111000011110011000000110011111111000000 00001100000000 r1
00001100111111001011110011000000110011111111000000 00001100000000 r2
00001100111111100001110011101000110001011111001000 00000110100000 r3
00001100111111100011110011000000110011111111000000 00001100000000 r4
00001100111111000111110011000000110011111111000000 00001100000000 r5
00001100111111001111110011000000110011111111000000 00001100000000 r6
00001100111111100101110011101010110001011111001000 00000110100000 r7
00001100111111100111110011000000110011111111000000 00001100000000 r8
00001100111111010010110011010100110010101111000100 00001001010000 r9
00001100111111011010110011010100110010101111000100 00001001010000
r10
00001100111111110000110011111100110000001111001100 00000011110000
r11
00001100111111110010110011010100110010101111000100 00001001010000
r12
00001100111111010011110011000000110011111111000000 00001100000000
r13
00001100111111011011110011000000110011111111000000 00001100000000
r14
00001100111111110001110011101000110001011111001000 00000110100000
r15
00001100111111110011110011000000110011111111000000 00001100000000
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
00001100111111000011110011000000110011111111000000 00001100000000 r1
00001100111111000111110011000000110011111111000000 00001100000000 r5
00001100111111001011110011000000110011111111000000 00001100000000 r2
00001100111111001111110011000000110011111111000000 00001100000000 r6
00001100111111010010110011010100110010101111000100 00001001010000 r9
00001100111111010011110011000000110011111111000000 00001100000000
r13
00001100111111011010110011010100110010101111000100 00001001010000
r10
00001100111111011011110011000000110011111111000000 00001100000000
r14
00001100111111100001110011101000110001011111001000 00000110100000 r3
00001100111111100011110011000000110011111111000000 00001100000000 r4
00001100111111100101110011101010110001011111001000 00000110100000 r7
00001100111111100111110011000000110011111111000000 00001100000000 r8
00001100111111110000110011111100110000001111001100 00000011110000
r11
00001100111111110001110011101000110001011111001000 00000110100000
r15
00001100111111110010110011010100110010101111000100 00001001010000
r12
00001100111111110011110011000000110011111111000000 00001100000000
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.homelinu...grid_small.png
[6] http://nbigaouette.inrs-emt.homelinu...r_grid_big.png
[7] http://nbigaouette.inrs-emt.homelinu...order_disk.png
 
Reply With Quote
 
 
 
 
Gene
Guest
Posts: n/a
 
      11-06-2009
On Nov 5, 6:50*pm, nbigaouette <(E-Mail Removed)> 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)
> 00001100111111000011110011000000110011111111000000 00001100000000
>
> Doing this manual procedure for all the combinations, I get the
> following:
> 00001100111111000011110011000000110011111111000000 00001100000000 * *r1
> 00001100111111001011110011000000110011111111000000 00001100000000 * *r2
> 00001100111111100001110011101000110001011111001000 00000110100000 * *r3
> 00001100111111100011110011000000110011111111000000 00001100000000 * *r4
> 00001100111111000111110011000000110011111111000000 00001100000000 * *r5
> 00001100111111001111110011000000110011111111000000 00001100000000 * *r6
> 00001100111111100101110011101010110001011111001000 00000110100000 * *r7
> 00001100111111100111110011000000110011111111000000 00001100000000 * *r8
> 00001100111111010010110011010100110010101111000100 00001001010000 * *r9
> 00001100111111011010110011010100110010101111000100 00001001010000
> r10
> 00001100111111110000110011111100110000001111001100 00000011110000
> r11
> 00001100111111110010110011010100110010101111000100 00001001010000
> r12
> 00001100111111010011110011000000110011111111000000 00001100000000
> r13
> 00001100111111011011110011000000110011111111000000 00001100000000
> r14
> 00001100111111110001110011101000110001011111001000 00000110100000
> r15
> 00001100111111110011110011000000110011111111000000 00001100000000
> 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
> 00001100111111000011110011000000110011111111000000 00001100000000 * *r1
> 00001100111111000111110011000000110011111111000000 00001100000000 * *r5
> 00001100111111001011110011000000110011111111000000 00001100000000 * *r2
> 00001100111111001111110011000000110011111111000000 00001100000000 * *r6
> 00001100111111010010110011010100110010101111000100 00001001010000 * *r9
> 00001100111111010011110011000000110011111111000000 00001100000000
> r13
> 00001100111111011010110011010100110010101111000100 00001001010000
> r10
> 00001100111111011011110011000000110011111111000000 00001100000000
> r14
> 00001100111111100001110011101000110001011111001000 00000110100000 * *r3
> 00001100111111100011110011000000110011111111000000 00001100000000 * *r4
> 00001100111111100101110011101010110001011111001000 00000110100000 * *r7
> 00001100111111100111110011000000110011111111000000 00001100000000 * *r8
> 00001100111111110000110011111100110000001111001100 00000011110000
> r11
> 00001100111111110001110011101000110001011111001000 00000110100000
> r15
> 00001100111111110010110011010100110010101111000100 00001001010000
> r12
> 00001100111111110011110011000000110011111111000000 00001100000000
> 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.
 
Reply With Quote
 
 
 
 
Gene
Guest
Posts: n/a
 
      11-06-2009
On Nov 5, 8:47*pm, Gene <(E-Mail Removed)> wrote:
> On Nov 5, 6:50*pm, nbigaouette <(E-Mail Removed)> 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)
> > 00001100111111000011110011000000110011111111000000 00001100000000

>
> > Doing this manual procedure for all the combinations, I get the
> > following:
> > 00001100111111000011110011000000110011111111000000 00001100000000 * *r1
> > 00001100111111001011110011000000110011111111000000 00001100000000 * *r2
> > 00001100111111100001110011101000110001011111001000 00000110100000 * *r3
> > 00001100111111100011110011000000110011111111000000 00001100000000 * *r4
> > 00001100111111000111110011000000110011111111000000 00001100000000 * *r5
> > 00001100111111001111110011000000110011111111000000 00001100000000 * *r6
> > 00001100111111100101110011101010110001011111001000 00000110100000 * *r7
> > 00001100111111100111110011000000110011111111000000 00001100000000 * *r8
> > 00001100111111010010110011010100110010101111000100 00001001010000 * *r9
> > 00001100111111011010110011010100110010101111000100 00001001010000
> > r10
> > 00001100111111110000110011111100110000001111001100 00000011110000
> > r11
> > 00001100111111110010110011010100110010101111000100 00001001010000
> > r12
> > 00001100111111010011110011000000110011111111000000 00001100000000
> > r13
> > 00001100111111011011110011000000110011111111000000 00001100000000
> > r14
> > 00001100111111110001110011101000110001011111001000 00000110100000
> > r15
> > 00001100111111110011110011000000110011111111000000 00001100000000
> > 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
> > 00001100111111000011110011000000110011111111000000 00001100000000 * *r1
> > 00001100111111000111110011000000110011111111000000 00001100000000 * *r5
> > 00001100111111001011110011000000110011111111000000 00001100000000 * *r2
> > 00001100111111001111110011000000110011111111000000 00001100000000 * *r6
> > 00001100111111010010110011010100110010101111000100 00001001010000 * *r9
> > 00001100111111010011110011000000110011111111000000 00001100000000
> > r13
> > 00001100111111011010110011010100110010101111000100 00001001010000
> > r10
> > 00001100111111011011110011000000110011111111000000 00001100000000
> > r14
> > 00001100111111100001110011101000110001011111001000 00000110100000 * *r3
> > 00001100111111100011110011000000110011111111000000 00001100000000 * *r4
> > 00001100111111100101110011101010110001011111001000 00000110100000 * *r7
> > 00001100111111100111110011000000110011111111000000 00001100000000 * *r8
> > 00001100111111110000110011111100110000001111001100 00000011110000
> > r11
> > 00001100111111110001110011101000110001011111001000 00000110100000
> > r15
> > 00001100111111110010110011010100110010101111000100 00001001010000
> > r12
> > 00001100111111110011110011000000110011111111000000 00001100000000
> > 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
question row filter (more of sql query question) =?Utf-8?B?YW5kcmV3MDA3?= ASP .Net 2 10-06-2005 01:07 PM
Quick Question - Newby Question =?Utf-8?B?UnlhbiBTbWl0aA==?= ASP .Net 4 02-16-2005 11:59 AM
Question on Transcender Question :-) eddiec MCSE 6 05-20-2004 06:59 AM
Question re: features of the 831 router (also a 924 question) Wayne Cisco 0 03-02-2004 07:57 PM
Syntax Question - Novice Question sean ASP .Net 1 10-20-2003 12:18 PM



Advertisments