About OCtree

Any question about the database & algorithms library 'CCLib'
cnnewton
Posts: 9
Joined: Wed Sep 28, 2011 7:08 am

About OCtree

Postby cnnewton » Fri Oct 14, 2011 2:44 am

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
Site Admin
Posts: 3375
Joined: Wed Oct 13, 2010 7:34 am
Location: Grenoble, France
Contact:

Re: About OCtree

Postby daniel » Fri Oct 14, 2011 9:16 am

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
Posts: 9
Joined: Wed Sep 28, 2011 7:08 am

Re: About OCtree

Postby cnnewton » Mon Oct 17, 2011 1:56 am

Thank you very much.

luke_penn
Posts: 13
Joined: Sun Oct 23, 2011 3:54 pm

Re: About OCtree

Postby luke_penn » Thu Apr 12, 2012 9:35 am

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
Site Admin
Posts: 3375
Joined: Wed Oct 13, 2010 7:34 am
Location: Grenoble, France
Contact:

Re: About OCtree

Postby daniel » Fri Apr 13, 2012 1:38 pm

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
Daniel, CloudCompare admin


Return to “CCLib”

Who is online

Users browsing this forum: No registered users and 1 guest