Z-Index with out of bound restrictions

Question

I need to calculate the Z-Index (Morton) of a point on a plane from its 2 coordinates x, y.

Traditionally this is just solved by the bit interleaving.

However I have boundaries, and I want the z-index of the point to only increase the morton count when it's inside the active area, and skip the count when outside.

To be clear, the typical z order in a 4x4 square is:

|  0  1  4  5 |
|  2  3  6  7 |
|  8  9 12 13 |
| 10 11 14 15 |

However if I have a 3x3 active area, I want the index to be calculated like this:

|  0  1  4  x |
|  2  3  5  x |
|  6  7  8  x |
|  x  x  x  x |

As you can see the 00-11 quad is full, the 02-13 is skipping the count for the 2 points that fall outside of the active area, same for 20-31, and for 22-33.

Important: I want to do this without iterating.

Is there a known solution for this problem?

Answer 1

I was able to get answer for the question on https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/

To handle rectangular regions, round up all dimensions to the nearest power of 2 and pack major axis linearly.

For example, endcoding point (2,3) in 5x4 rectangle as follows,

Rounding up 5x4 to nearest power of 2 results in 8x4 i.e. 3 and 2 bits

Encoding point 2,3 First interleave 2bits of 0b010, 0b11 we get 0b1110, and 3rd bit from x dimension becomes 5th bit of result.

Encoding 4,2, 0b100, 0b11 becomes 0b11010

In order to find z-order of 3x3 region, find inverse mapping for 4x4 region using above reverse of above method while generating map skip any points that fall outside 3x3 region.

mapping would look like

(0,0) -> (0,0)
(0,1) -> (1,0)
(0,2) -> (0,1)
(0,3) -> (1,1)
(1,0) -> (2,0)
(1,2) -> (2,1)
(2,0) -> (0,2)
(2,1) -> (1,2)
(3,0) -> (2,2)

python code might be useful, https://gist.github.com/kannaiah/4eb936b047a987b32555b2642a0979f7