Get Neighbour-Nodes from a node

[ghost]

Is it possible to get neighbouring nodes from a node?
I would like to use the leaf_iterator (or tree_iterator) and to extract the information from the neighbours of every node.

Thank you!

[ahornung]

It's not implemented right now, the nodes have no information about their direct neighbors. What you can do is get the node's key (from iterator), then search for that key +/-1 in each dimension.

[ghost]

Hi Armin,
thanks for answering! If I understood your correctly, you mean the following steps:

1. find a node by key
2. get its coordinates (x,y,z)
3. calculate neighbouring 8 coordinates
4. search the nodes for every of the generated coordinates.

However, I would prefer to use references to parent nodes. I extended the createChild(int) method in the OcTreeNode class and if you like, you can accept the merge request from my fork.

By the way! This is a superior framework! Works on windows and linux. (even gs 4.7 :) )
Thank you very much!

[ahornung]

The straighforward way would be:

1. find a node by key (from coordinates or iterator)
2. add / subtract 1 from the key values to driectly get the neighbor key
3. search neighbor node by key

See my comments in your pull request for the parent pointers.

[ahornung]

An alternative way would be to temporarily store parent information in a recursive call while the tree is traversed, and use that for faster neighbor queries. Some experimental work in that direction was started in the OcTreeLUT classes (unfinished / unused right now).

[ghost]

Oh thank you!
the 3 steps sound promising. Is there a short explanation of how the key is generated? In which direction do I traverse the nodes if I add 1 or subtract 1?

Edit: Sorry for the last message. I found this paper, which is referenced by the OcTreeLUT : http://www.cs.umd.edu/~hjs/pubs/SameCG89.pdf
Great stuff! :)

[ahornung]

Have a look at coordToKey, the keys are a simple discretization of the coordinates. So +1 on the first dimension will be +res in x.

[alexjung]

Does this also apply to keys of nodes in coarser resolution? Is +1 still +res (getResolution()) or +res in this depth of the tree?

[ahornung]

Keys only represent the coordinates at the tree resolution (voxel coordinates). With a depth and the function computeIndexKey(..) you can get a coarser key, but need to consider the depth yourself (e.g. add +2 at depth 15, +4 at 14 and so on).

[hmluqman]

I am facing similar issue. I am feeding Octomap::PointCloud. by using iterator I found the octreeNode of each occupied node. But How to find keys of each occupied node from OctreeNode ?
I want to find the neighbours of each occupied node.

[BoltzmannBrain]

Once upon a time there was OcTreeLUT that implemented a lookup table to compute keys of neighbor cells directly.