[Paraview] vtkHyperOctree

[Brad King]

Jean M. Favre wrote:
> Second question: I don't see what method should be used for
> parallelizing the construction of the octree.

vtkHyperOctree uses a compact representation within a few
contiguous arrays and use indexes instead of pointers.
It allocates all octree nodes in these arrays.  New nodes
get spots at the end.  When a node is deleted we move a node
from the end back to fill in the hole.  This keeps the arrays
contiguous and gives good locality of reference and makes
*serial* operations very fast.

The trade-off is that the structure (at least in the current
implementation) does not support updates from more than one
thread at a time.  Any kind of parallel octree construction
would have to do one of the following:

(a) Use synchronization primitives to update the structure.

(b) Construct one octree in each thread whose root node is
    one of the children of the final octree, and combine them
    at the end, serially.

(c) Investigate the implementation of vtkHyperOctree in more
    detail than I'm posting off the top of my head to see if
    it can be taught to do parallel updates (not likely).

Summary: vtkHyperOctree was optimized for computation within
a single thread.  Its design does not lend well to threading.

-Brad