Nearest Neighbors in radius via Z-order order curve?

Question

Given a $M\times M\times M$ 3D cube grid $C$, how can I map the 3D grid-coordinates to 1D coordinates such that every cell's nearest neighbors can be represented by a continuous range of corresponding 1D values?

One of the 3D-to-1D mappings could be Z-indexing, but I don't know how to access the neighbors in the way I described above.

---

Why do I need this: I'm writing an OpenCL kernel function, that processes particles. In each cell of the grid $C$ can be arbitrary (non-negative :) number of particles. The particles are stored in memory sorted by their cell's id given by the 1D coordinates. And to get the best GPU performance when reading neighbors, I need the neighboring particles to be close in memory (i.e. the 1D coordinates of a grid cells that are close to each other in space are also close).

If you want more of the context, you can see my questions at different SE sites:

• Nearest Neighbors in CUDA particles
• Z-order curve — how to query all nearest neighbors?

Answer 1

What you are asking is not possible, because you cannot order all cells in such a way that neighbors are always in a continuous range. Suppose we try to construct continuous neighbor lists in 3D. Each interior cell $C_i$ has six neighbors, so it should appear six times in a neighbor list. The only way to construct six continuous neighbor list is as follows:

• $C_{i-5}$ to $C_{i}$
• $C_{i-4}$ to $C_{i+1}$
• ..
• $C_{i}$ to $C_{i+5}$

These lists contain 11 different cells. However, the left and right $x$-neighbor of $C_i$ already have $5+5+1=11$ different cells in their neighbor list (their only shared neighbor is $C_i$). Because there are also $y$ and $z$-neighbors, we cannot have continuous neighbor lists.

You could instead compute a Morton number $m_i$ for each cell (i.e., use the Z-curve), and then store these numbers in a sorted 1D array. Given any cell, you can compute the Morton number of a neighbor in time $O(1)$, and do a binary search in time $O(\log N)$, where $N$ is the number of cells.