3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

You are asking two different questions:

  1. What are the $2^{n_d} \binom{n_d}{m}$-many codimension $m$ neighbors of a given node?

  2. Given a description of a neighbor, how to locate it?

Regarding the first question, a neighbor of codimension $m$ is given by (1) a subset $S$ of the coordinates of size $m$, (2) for each $x \in S$, a direction $d_x \in \{-1,+1\}$. The address of a neighbor is obtined by adding $d_x$ to coordinate $x$.

Regarding the second question, the simplest algorithm would consist of the following steps:

  1. Find the address of the node by traversing the tree up.

  2. Find the address of the neighbor. This part is described above.

  3. Find the neighbor by traversing the tree down.

These steps are straightforward generalizations of the algorithm described in the link.

$\endgroup$
  • $\begingroup$ Regarding 1) I can only find a neighbor by adding $d_x$ to $x$ if I'm using some sort of hashing (spatial-/geohashing) to store my nodes right? I am not using it since that would require me to allocate memory for all possible nodes up-to a given level and in my case the octrees are very deep but very sparse, or did I understand this wrong? Is there a general way of find the neighbors by using tree traversals only? $\endgroup$ – gnzlbg Apr 14 '14 at 11:13
  • $\begingroup$ Regarding 2) Thanks for the link, I'm looking into it! (Please someone upvote him, I can't since my reputation is < 15...). $\endgroup$ – gnzlbg Apr 14 '14 at 11:14
  • $\begingroup$ Regarding 1 (after reading the link): I use the octree to represent a topology (without any spatial information). So I have the parent/child edges for every node, but I don't have e.g. coordinates. I'm specifically looking for a way to find the set of neighbors of codimension m from the tree structure only (i.e. the bare minimum). $\endgroup$ – gnzlbg Apr 14 '14 at 11:25
  • $\begingroup$ @gnzlbg You will have to provide more information on what exactly you're doing: what exactly is your data structure, and what works for low dimensions. This is impossible to glean from your question, unfortunately. $\endgroup$ – Yuval Filmus Apr 14 '14 at 13:49
  • $\begingroup$ thanks for your feedback, I've tried to improve the question. Could you let me know if it is better now? $\endgroup$ – gnzlbg Apr 14 '14 at 14:31

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.