Add depth-parameter to search()

[ahornung]

The ''search()''-function can be restricted by a depth at which to stop. The used key is converted accordingly by ''genKeyAtDepth()'' to be valid for given search depth.

[ahornung]

Imported from trac issue 6. Created by michischolz on 1970-01-01T01:22:16, last modified: 1970-01-01T01:22:16

[ahornung]

Trac comment by ahornung on 1970-01-01 01:22:22:

Thanks for the patch! Could you test in your implementation if it also works identically without "genKeyAtDepth"? That function will disappear soon, and should not be necessary. Just leave "key_at_depth = key" in all cases.

[ahornung]

Trac comment by michischolz on 1970-01-01 01:22:22:

Yay! I had many problems using keys generated at level 16 for node access at depths < 16. I can test whether this maybe changed by now but for my implementations I use ''genKeyAtDepth()'' quite often. Especially when feeding BBXIterator with a Key-BBX '''and''' restricting it to a certain depth, the keys used for this BBX have to be valid for the requested depth. Otherwise I get strange results.
Another case could be my neighbour search where I use this function, but I have to check tomorrow.

Further ''updateNode()'' is basically the same as ''search()'' but implemented recursively and not using an elegant for-loop. So, adding a depth-parameter to ''updateNode()'' is also possible, I have a patch ready for that as well but thought it would be maybe nicer to rewrite ''updateNode()'' to the style of ''search()'' anyway.

[ahornung]

Trac comment by ahornung on 1970-01-01 01:22:22:

In that case genKeyAtDepth will stay (but get renamed), I assumed it's no longer used since there was no reference to it within OctoMap. All genXXX functions are now named clearer in trunk after a cleanup. But I intend to directly compute the key at depth with

{{{
OcTreeKey coordToKey(const point3d& coord, unsigned depth)
}}}

instead of shifting an existing key (which now requires genKey and genKeyAtDepth). Or do you see a use case for that?

If you have any code snipplets to test, that would be good.

Regarding ''updateNode()'': A new ticket would be good for that. But I don't fully see the use case for updating the tree at a larger resolution than tree res. During query time it creates a speedup, but the tree stays identical. I see further problems with the change detection code, which always assumes keys at lowest tree level.

[ahornung]

Trac comment by michischolz on 1970-01-01 01:22:22:

Regarding ''updateNode()'': One case for updating at a certain depth < max_deph:

• You extract information (objects) at a depth < max_depth because you are interested in this particular depth (rather the resolution at this depth)
• This extracted information is held in some other data structure, let's say a map which maps "something very fancy" to the tree key of each extracted cell
• Now many funny things happen that cause the tree to disappear. The extracted information still persists
• At some later point in the program the octree is recreated at the location where the previously extracted information is located
• New measurements at max_depth are being integrated but one wants '''also''' the previously extracted information to be reintegrated into the newly built octree. Because this stuff was extracted at depth x < max_depth we have to use ''updateNode()'' with a key for this certain depth < max_depth :)

In general I use 3d-points/coordinates only for new measurement integration. All other processes inside/around my octree are some kind of "low level" and are implemented on key-level. This is where I need the key conversion functions. But I'll check how often this is the case.

[ahornung]

Trac comment by ahornung on 1970-01-01 01:22:22:

Implemented in Rev. [392]:

• new functions adjustKeyAtDepth() and coordToKey() with depth parameter to replace genKeyAtDepth
• Patch for search integrated