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:

Quadtree neighbors

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:

Quadtree split

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:

Quadtree numbering

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:

Quadtree Neighbors

The cleverness lies on how ternary digits are interpreted:

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.