Z-Ordering (Morton ordering) question

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

  1. nbigaouette

    nbigaouette Guest

    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
     
    nbigaouette, Nov 5, 2009
    #1
    1. Advertising

  2. nbigaouette

    Gene Guest

    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
    > [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, Nov 6, 2009
    #2
    1. Advertising

  3. nbigaouette

    Gene Guest

    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
    > > [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
     
    Gene, Nov 6, 2009
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. nospam
    Replies:
    13
    Views:
    630
    Guinness Mann
    Oct 7, 2003
  2. Craig Douglas

    Ordering FileInfo[] by date

    Craig Douglas, Jan 30, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    369
    Craig Douglas
    Jan 30, 2004
  3. Kottiyath

    An ordering question

    Kottiyath, Mar 13, 2009, in forum: Python
    Replies:
    7
    Views:
    277
    Gabriel Genellina
    Mar 14, 2009
  4. Aryk Grosz
    Replies:
    3
    Views:
    115
    Aryk Grosz
    Jun 27, 2007
  5. John

    question about hash ordering

    John, Oct 2, 2003, in forum: Perl Misc
    Replies:
    2
    Views:
    98
    Tad McClellan
    Oct 2, 2003
Loading...

Share This Page