CesiumGS / 3d-tiles

Specification for streaming massive heterogeneous 3D geospatial datasets :earth_americas:
2.15k stars 469 forks source link

Clarify bitwise operators for implicit tiling #507

Open javagl opened 3 years ago

javagl commented 3 years ago

The 3DTILES_implicit_tiling specification has an appendix where certain bitwise operations are used that may not be defined sufficiently.


The first function is interleaveBits. It is supposed to compute the Morton index from given coordinates. Originally, it was described informally as

quadtreeMortonIndex = interleaveBits(y, x)
...
interleaveBits(0b11, 0b00) = 0b1010

but in a recent commit, this was changed to more closely resemble the description, usual definitions and existing implementations. Given the link to the Wikipedia entry, a more formal definition might not be necessary (even though the Wikipedia page doesn't go into much detail here either). But an implementation note hinting at the limits of straightforward implementations (namely, 10 bits for x/y/z coordinates of octrees, or 16 bits for x/y coordinates of quadtrees) might be worthwhile.


The second function is concatBits. It is described as

tile.globalMortonIndex = concatBits(subtreeRoot.globalMortonIndex, tile.localMortonIndex)

and the images give an idea about what the function is supposed to do, as in

0b101000100110 = concatBits(0b10100010, 0b0110)

So in this example, the first argument has to be shifted left by 4 bits and then combined with a bitwise OR with the second argument. I assume that these 4 bits are somehow related to the height of the subtree (which might be 2 in the example), but the amount of shifting would then have to be different for the case of concatenating the bits of morton indices, and the case of concatenating bits for coordinates.

javagl commented 3 years ago

This issue until now referred to two particular bitwise operations. But I think that some of the other computations could be elaborated as well.

For example, the specification defines the computation of a bit index from coordinates, via the section https://github.com/CesiumGS/3d-tiles/tree/3d-tiles-next/extensions/3DTILES_implicit_tiling#accessing-availability-bits , from which

  coordinates : bitIndex
(level, x, y) ->        levelOffset         +     mortonIndex
                 ((N^level - 1) / (N - 1))     interleaveBits(x,y)

can be derived quite straightforwardly.

I recently tried to implement some of these things, and wanted to compute the opposite direction - namely the level of a quadtree that corresponds to a given bit index in the availability info.

Maybe one can implement all that without this operation. But I think that it could be useful, at least.

Wolfram alpha roughly told me how to invert the first part. But considering the logarithms and the intention to compute all this with integer values (somewhat efficiently, if possible), it took a few more iterations until I arrived at

public static int computeQuadtreeLevel(long bitIndex)
{
    int result = 0;
    long s = bitIndex * (4 - 1) + 1;
    while ((s >>>= 2) != 0)
    {
        result++;
    }
    return result;
}

where that while loop is a log4, so to speak. And I thought: Wait, that should be easier. But peeking at the current implementation in CesiumJS convinced me: Well, maybe it is not totally trivial....

Things like the formula that is used at the linked implementation (maybe even with the comments) could become part of an extended appendix, where such "forward and backward" computations are explained in more detail.