Consistent Ordering of N-Dimensional Neighbors
When recursing down quad/octrees, it's useful to track the neighbors of the current cell. Neighbors share either a corner, edge, or (in 3D) face with the current cell, so we can often skip calculations if they've already been done by a neighbor.
This writeup explains a meaningful way to count and order these neighbors.
In 2D, a cell has 8 neighbors, shown below:
In 3D, a cell has 26 neighbors, forming a 3x3x3 cube (with the current cell in the center). Generalized, in \( N \)-dimensions, a cell has \( 3^N - 1 \) neighbors.
How do we assign indices 0-7 (in 2D) or 0-25 (in 3D) to these neighbors in a consistent fashion?
Taking a step back, let's consider a similar, simpler numbering problem.
Each cell in a quad/octree splits into \( 2^N \) children:
They can be numbered by treating each value in the range \( [0, 2^N) \) as a bitfield which indicates whether to pick the high or low side of each axis split.
For example, in 2D,
00 picks the low side of the X and Y axis splits;
01 picks the quadrant with high X and low Y, etc.
Here's the full numbering scheme:
Back to our original problem: To track neighbors, instead of using an \( N \)-digit binary number, we use an \( N \)-digit ternary number. Here's how we number the 8 neighbors in the 2D case:
The cleverness lies on how ternary digits are interpreted:
0means this neighbor is on the low side of the axis
1means this neighbor is on the high side of the axis
2means this neighbor spans the entire axis
This interpretation gives an internally consistent numering scheme for neighbors in \(N\)-dimensional grids.
Usefully, it even encodes excluding the original cell
from the list of neighbors!
In the diagram above, the original cell spans all axes,
and should thus be numbered
22 (or 8 in base 10).
If we consider the range \( [0, 3^N - 1) \),
then the central cell is one past the end of the range,
so it is excluded without any extra effort.