CODEWITHSUNDEEP
z-order-curve
scrab
scrab

Reputation: 1

Morton encoding of nearest neighbours?

I am using morton encoding on a 3D grid so that a set of points (x,y,z) gives me a 1D array of morton encodings M(x,y,z), where x,y,z are integers. For every M(x,y,z), my calculations also require the 26 nearest neighbours on the grid, ie. M(x-1,y-1,z-1), M(x-1,y-1,z+0), M(x-1,y-1,z+1), M(x-1,y+0,z-1)...

My question is, how do I directly compute these neighbour encodings from M(x,y,z)? I know wikipedia has a solution for 8-bit integers in 2D:

M(x,y-1) = ((M(x,y) & 0b10101010) - 1 & 0b10101010) | (M(x,y) & 0b01010101)

What do the equivalent algorithms look like for a 3 dimensional grid?

Upvotes: 0

Views: 533

Answers (1)

shmulvad
shmulvad

Reputation: 638

Is it a strict requirement that you have to compute the neighbours in a similar manner to the formula you have written? If not, you can use the (x, y, z)-coordinates you already have from which you can obtain all the neighbour Morton order indices simply by performing regular Morton order encoding on these. Here is a simple function in Python-syntax that shows what I mean:

def get_neighbour_indices_3d(point):
    x, y, z = point  # The point you are currently looking at and know the coordinates of
    neighbours_indices = []
    for x_new in range(x-1, x+2):
        for y_new in range(y-1, y+2):
            for z_new in range(z-1, z+2):
                # Maybe do some check that you're not beyond the edge or at the original point
                neighbours_indices.append(morton_encode(x_new, y_new, z_new))
    return neighbours_indices

Upvotes: 0

Related Questions