## 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:

`0`

means this neighbor is on the low side of the axis`1`

means this neighbor is on the high side of the axis`2`

means 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.