How to use Morton Order in range search?

Question

If I have a dataset, where the keys are points in 3D, represented by 3 signed 64 bit integers. And I want to use a (sorted)key-value store to store them, where keys are just byte array (but I can specify a comparator). I think I can turn all those points into a byte array by using bit-interleaving, as is done with Z/Morton order like in How to compute a 3D Morton number

In addition to fetching individual points, which can be done more simply without Morton ordering, I want to do range search, where I search within a box that is aligned with the axes. I will define A and B as being respectively the box corners where all coordinates are the lowest, and the opposite corner where all coordinates are the highest.

Now my questions are:

1. For any point C, which is logically between, A and B, will the Morton number of C also be between the Morton number of A and B? (Isn't that the point of Morton order?)

2. If 1 is no, can A and B be "rounded" to values that guaranty that C will be included?

3. Assuming that 1 or 2 is possible, does the search return also points outside of that box, which I have to "post-filter" away? How big is that "error set" (does it depend on the size, or the position, of the search)?

4. Does the fact that the integers are signed cause problems? And if so, is there a work-around?

To recap, using Morton Numbers is just one possible solution to the real problem: How to efficiently range-search in 3D integer space, when the 3D points have to be mapped to a unidimensional value? I want to get all the points between A and B, by performing a single range select in the DB, using a min-key and a max-key, and ideally, getting as few points outside the box as possible.

Answer 1

4) Yes, the sign will cause an issue, but it's trivial to solve.

Just XOR the sign bit of x, y and z with 1 before you create your Morton Number.

Why this works (using 1 dimension signed bytes instead):

-1 in binary is 11111111

0 in binary is 00000000

1 in binary is 00000001

The order you want is -1, 0, 1, but the current binary order is 0, 1, -1.

-1 XOR 10000000 = 01111111

0 XOR 10000000 = 10000000

1 XOR 10000000 = 10000001

Now your binary order is correct