About OCtree

[cnnewton]

Hi,
What is the difference between Cell Code and Cell Index ? Cell Code is ID of Cells ? Are Cells ordered by space relation in every level ?

[daniel]

Hello,

indeed, the octree cell "code" is a streaming value that represents the position of the cell relatively to its parent for successive level of subdivisions (3 bits for each level). You have a quick description of this in this article: http://www.danielgm.net/phd/isprs_laser ... 05_dgm.pdf

By the way, this is why in the standard version is limited to 10 levels of subdivision (10*3 = 30 bits < 32 bits) as codes are stored as 32 bits integers.

The cell index is simply the index of the cell code inside the sorted cell code list (= the true octree structure). Once we have computed all cell codes (on for each 3D point), we sort them so that all the point lying in the same cell are next to each other, and their neighbors are not very far (depending on the subdivision scheme and subdivision level). So, in order to be able to know which cell code corresponds to which point, we associate a code with an index.

[cnnewton]

Thank you very much.

[luke_penn]

Hi, I am working for implementing a fast point picking using dgmOctree...

I implemented the ray/box checking algorithm, and I've been able to make it works for a given level of subdivision of the octree (giving back the code of the cell that the ray intersect at the given level)
This is pretty fast but I would like to improve the speed, so...Now I would like to make it works in a hierarchical fashion. So I would like to:
get all cells at level 0 (just one)
get cells intersecting at level 0 (1 or 0)
if 1: get the the cells at level 1 that are included into the intersecting cell at level 0
and so on in a similar manner, until level 10 is reached.

My question:
if I have a cell at level 'i' how can I get the 8 cell codes (absolute codes - btw does this correspond to not-truncated codes?) for the 'children' cells (8 cells contained into the parent cell) at level 'i+1'? I cannot see any dedicated method inside dgmOctree...

Thanks !

Luca Penasa

[daniel]

Hi Luca,

the DgmOctree structure is very poor for top-down traversal algorithms. By the way, this is why CloudCompare can't use LOD strategies to display big clouds faster.

If you have a (truncated) cell code at level i, you just have to shift the code of 3 bits and add the subcell code (from 0 to 7). But the only way to know if the cell exist or not is to check that the (truncated) cell code exists in the cells list (which is very slow).

You can do this a little more efficiently by traversing the whole list, considering the smallest part of the code as possible depending on whether the cell is intersected or not (there's an example on how to do this with the 'executeFunctionForAllCellsAtStartingLevel' method - the criteria for going deeper in the octree is the number of points inside the cell). But you still have to test all codes (even if you ignore the current cell) as you don't know when the next cell starts.

Eventually, there's experimental code to cope with this limitation (by replacing the DgmOctree streamed structure by a more 'classical' hierarchical structure) but it's a very early prototype (it was meant to test if the standard octree structure was better for distance computation - but it was not). Look at the OCTREE_TREE_TEST preprocessor in the DgmOctree.cpp code. We could simply create a new class (HierarchicalOctree or something like that) and put this code here. Then you could use it for your own problem (and we could also use it for LOD display for instance). The sole issue is that it's not compatible with the DgmOctree structure and the memory consumption doubles if we need both structures at the same time...

There are several example

[DirtyMclean]

Perhaps somebody can help me?

I fully understand how the octree subdivides into ever smaller cubes. My question though, is how does it determine the position of the single point inside each cube?

Does it create a new point based on an average of all the points inside the cube, or does it keep just one of the existing points, based on some 'best point' criteria?

Any help would be greatly appreciated. Thanks.

[daniel]

Well, the octree gives you the list of points falling into each cell. Therefore it's up to you to decide how you want to represent them (as a single point). For instance the 'Subsample with octree' tool lets you choose if you want the average point (= barycenter), or the point closest to the cell center.

[DirtyMclean]

Thanks for the quick reply. How am I able to make this choice? I do not see an option for it in the Subsample with Octree tool.

[daniel]

Ah sorry, I was thinking about the code:
https://github.com/CloudCompare/CCCoreL ... ools.h#L44

Via the GUI, you don't have the choice, we always use 'CELL_GRAVITY_CENTER' (or 'NEAREST_POINT_TO_CELL_CENTER' if you use the Subsample tool instead of the Resample tool). The 'CELL_CENTER' option is never available.

[DirtyMclean]

Thanks! I read it and understand what the different codes and their parameters do. But I'm not much of a coder. Would love to know how to use them. Is there a quick start guide? Haha

So anyway,could you just let me know which type of point is created in each cell when using the Cloud Compare GUI (nearest to centre, gravity centre, etc)?

What is gravity centre by the way?