3
$\begingroup$

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:

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've actually thought the same thing, but I was not completely sure it's impossible to do without memory sacrifice, so I rather asked. $\endgroup$ – sarasvati Aug 1 '16 at 19:43
  • $\begingroup$ FYI, the Morton curve has several large jumps in it, breaking contiguity. The Hilbert curve would be a better choice if preserving spatial locality is important. $\endgroup$ – sssssssssssss Apr 16 '18 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.