[vtkusers] CellLocator, Octrees and Segfaults...

[Obada Mahdi]

Hi Radu!

On 10/24/06, Radu Bogdan Rusu <rusu at cs.tum.edu> wrote:
> Yeah, what I don't understand is why:
>
> this->MarkParents((void*)VTK_CELL_INSIDE,i,j,k,ndivs,this->Level);
>
> ...in: void vtkCellLocator::BuildLocator()
> ...where: #define VTK_CELL_INSIDE 1
> ...because: void vtkCellLocator::MarkParents(void* a, int i, int j, int k, int ndivs, int
> level)
> ...contains: this->Tree[parentIdx] = (vtkIdList *)a;

I am not sure that I understand the question :-)  Here is what I think
is going on, please excuse the traffic if I am just repeating what you
already know:

When the locator is built, cells are distributed over 8^l leaf nodes
of an octree, where l is the height of the tree (which is computed
automatically, based on the number of cells, unless given explicitly).
 These leaf nodes contain either NULL if they are empty, or hold a
pointer to an instance of vtkIdList otherwise.  These are the only
nodes that can carry cell IDs.

In addition, inner nodes of the octree are marked as empty (NULL,
value from initialization) or non-empty (VTK_CELL_INSIDE), depending
on whether at least one child (leaf) node contains cells or not.  This
is done by MarkParents(), by tagging every node on the path towards
the root node.  This is required for e.g. speeding up intersection
tests (eliminating parts of the tree by top-down testing intersection
with bounding boxes).

The octree maintained by vtkCellLocator is quite simple and has a very
specific structure--maybe that is why there is no more elaborate
interface for navigating through the tree, but frankly, I do not
understand that interface, too.  It is also not picked up by
vtkOBBTree, which directly inherits from vtkCellLocator and does not
provide methods for accessing tree nodes at all (as far as I can see).
 Maybe the best thing is to follow the suggestion from the
documentation of vtkCellLocator, which states that it is meant to be
subclassed.

> Is there any other way of actually "iterating" through the octants, then ?

If you want to exploit the structure of the flattened octree
representation to iterate just over leaf nodes, you can use something
like:

// fetch total number of nodes (inner+leaf)
int numNodes = locator->GetNumberOfBuckets();
// compute 8^(tree height), which is the number of leaf nodes
int numLeafNodes = ( 2 << (3 * locator->GetLevel()) );
for ( int i = numNodes - numLeafNodes; i < numNodes; i++ ) {
  idList = locator->GetCells(i);
  if ( idList != NULL ) ...
}


HTH,

Obada