I'm writing a balanced $n_d$-Hyperoctree data structure in which the only fundamental operations I provide are edge traversals between parent and child nodes. I'm storing the nodes using a Morton z-curve.
Using only this information:
- The level of a node can be computed by traversing to the root of the tree.
- Neighbor searches are performed by traversing the tree up until a common parent is found, and then traversing the tree back down again.
I can compute the following constants depending on the number of spatial dimensions $n_d$:
- the #of children of a node: $2^{n_d}$,
the #of $n_d - m$ dimensional neighbors for each node (in 3D, $n_d - 1$ neighbors are faces, $n_d - 2$ neighbors are edges, $n_d - 3$ neighbors are corners):
$2^{n_d} \begin{pmatrix} n_d \\ m \end{pmatrix}$
The neighbors sharing a $n_d - 1$-dimensional face with each Hypercube form the set $\mathcal{N}_{n_d - 1}$. They are numerated within this set as follows. The neighbor at the negative side from the node center comes first, then it comes the neighbor at the positive side. That is, for $n_d = 1$ I just have $\mathcal{N}_{n_d - 1} = \lbrace 0, 1 \rbrace = \lbrace \mathrm{Left}, \mathrm{Right} \rbrace$.
In $n_d = 2$, $\mathcal{N}_{n_d - 1} = \lbrace 0, 1, 2, 3 \rbrace = \lbrace \mathrm{L}, \mathrm{R}, \mathrm{Top}, \mathrm{Bottom} \rbrace$.
In $n_d = 3$ it is $\mathcal{N}_{n_d - 1} = \lbrace 0, 1, 2, 3, 4, 5 \rbrace = \lbrace \mathrm{L}, \mathrm{R}, \mathrm{T}, \mathrm{B}, \mathrm{Front}, \mathrm{Back} \rbrace$
and so on.
I haven't been able yet to generalize the algorithm for finding the $n_d - 1$ neighbor located at a given position to arbitrary dimensions. My current algorithm traverses the tree up until a common parent node is found. During the up traversal it stores the child positions w.r.t. their parents of the nodes traversed. Then it traverses the tree back down using the reversed path of the up traversal. The child positions are found by finding the siblings of the child positions during the up traversal in the inverted neighbor direction, which can be computed as:
$\mathrm{inverted\_neighbor\_position}_{n_d - 1}(p) = (p + 1) * (p \% 2 = 0) + (p - 1) * (p \% 2 \neq 0)$
However, to know if a common parent has been found, it checks if a parent node has a childe at a given relative position of another child which expressed as a neighbor position, i.e., it checks if a node has a sibling in a given neighbor direction within its parent. I have only a hand-coded stencil for this check and haven't been able to generalized.
Can this check for a "common parent" be generalized to arbitrary dimensions? How?
Example up to 3D: for a child and a neighbor position, returns the child position of the sibling:
// i means, there is no sibling for that child in that direction //0 1 2 3 4 5 << nghbr position { i, 1, i, 2, i, 4}, // child 0 { 0, i, i, 3, i, 5}, // child 1 { i, 3, 0, i, i, 6}, // child 2 { 2, i, 1, i, i, 7}, // child 3 { i, 5, i, 6, 0, i}, // child 4 { 4, i, i, 7, 1, i}, // child 5 { i, 7, 4, i, 2, i}, // child 6 { 6, i, 5, i, 3, i} // child 7
Assuming that the $n_d - 1$ dimensional neighbors can be found:
How can I find $n_d - m$ dimensional neighbors?
- Right now, I hand-coded traversals that perform $m$ times searches for $(n_d - 1)$ neighbors. Is there a general way to generate these traversals for $n_d$ dimensions and the $n_d - m$ neighbors?
What is a suitable order for $n_d - m$ dimensional neighbors where $m > 1$ ?
Most of the research I've found in the literature uses hand coded stencils for, 1,2,3 and 4 dimensions, but no general ways of generating these stencils. So if anyone can point me to relevant literature I would appreciate it.
