FreeMat: vtkHyperOctree

FreeMat

- Main Page
- Related Pages

vtkHyperOctree

Section: Visualization Toolkit Filtering Classes

# Usage

An hyperoctree is a dataset where each node has either exactly 2^n children or no child at all if the node is a leaf. `n' is the dimension of the dataset (1 (binary tree), 2 (quadtree) or 3 (octree) ). The class name comes from the following paper:

     @ARTICLE{yau-srihari-1983,
      author={Mann-May Yau and Sargur N. Srihari},
      title={A Hierarchical Data Structure for Multidimensional Digital Images},
      journal={Communications of the ACM},
      month={July},
      year={1983},
      volume={26},
      number={7},
      pages={504--515}
      }

Each node is a cell. Attributes are associated with cells, not with points. The geometry is implicitly given by the size of the root node on each axis and position of the center and the orientation. (TODO: review center position and orientation). The geometry is then not limited to an hybercube but can have a rectangular shape. Attributes are associated with leaves. For LOD (Level-Of-Detail) purpose, attributes can be computed on none-leaf nodes by computing the average values from its children (which can be leaves or not).

By construction, an hyperoctree is efficient in memory usage when the geometry is sparse. The LOD feature allows to cull quickly part of the dataset.

A couple of filters can be applied on this dataset: contour, outline, geometry.

3D case (octree) for each node, each child index (from 0 to 7) is encoded in the following orientation. It is easy to access each child as a cell of a grid. Note also that the binary representation is relevant, each bit code a side: bit 0 encodes -x side (0) or +x side (1) bit 1 encodes -y side (0) or +y side (1) bit 2 encodes -z side (0) or +z side (2)

- the -z side first
- 0: -y -x sides
- 1: -y +x sides
- 2: +y -x sides
- 3: +y +x sides

                    +y
       +-+-+        ^
       |2|3|        |
       +-+-+  O +z  +-> +x
       |0|1|
       +-+-+

- then the +z side, in counter-clockwise
- 4: -y -x sides
- 5: -y +x sides
- 6: +y -x sides
- 7: +y +x sides

                    +y
       +-+-+        ^
       |6|7|        |
       +-+-+  O +z  +-> +x
       |4|5|
       +-+-+

The cases with fewer dimensions are consistent with the octree case:

Quadtree: in counter-clockwise

- 0: -y -x edges
- 1: -y +x edges
- 2: +y -x edges

- 3: +y +x edges

               +y
       +-+-+   ^
       |2|3|   |
       +-+-+  O+-> +x
       |0|1|
       +-+-+

  Binary tree:

       +0+1+  O+-> +x

To create an instance of class vtkHyperOctree, simply invoke its constructor as follows

      obj = vtkHyperOctree

# Methods

The class vtkHyperOctree has several methods that can be used. They are listed below. Note that the documentation is translated automatically from the VTK sources, and may not be completely intelligible. When in doubt, consult the VTK website. In the methods listed below, `obj` is an instance of the vtkHyperOctree class.

- `string = obj.GetClassName ()`
- `int = obj.IsA (string name)`
- `vtkHyperOctree = obj.NewInstance ()`
- `vtkHyperOctree = obj.SafeDownCast (vtkObject o)`
- `int = obj.GetDataObjectType ()` - Return what type of dataset this is.
- `obj.CopyStructure (vtkDataSet ds)` - Copy the geometric and topological structure of an input rectilinear grid object.
- `int = obj.GetDimension ()` - Return the dimension of the tree (1D:binary tree(2 children), 2D:quadtree(4 children), 3D:octree (8 children))
  Postcondition:
    valid_result: result>=1 && result<=3
- `obj.SetDimension (int dim)` - Set the dimension of the tree with `dim'. See GetDimension() for details.
  Precondition:
    valid_dim: dim>=1 && dim<=3
  Postcondition:
    dimension_is_set: GetDimension()==dim
- `vtkIdType = obj.GetNumberOfCells ()` - Return the number of cells in the dual grid.
  Postcondition:
    positive_result: result>=0
- `vtkIdType = obj.GetNumberOfLeaves ()` - Get the number of leaves in the tree.
- `vtkIdType = obj.GetNumberOfPoints ()` - Return the number of points in the dual grid.
  Postcondition:
    positive_result: result>=0
- `vtkIdType = obj.GetMaxNumberOfPoints (int level)` - Return the number of points corresponding to an hyperoctree starting at level `level' where all the leaves at at the last level. In this case, the hyperoctree is like a uniform grid. So this number is the number of points of the uniform grid.
  Precondition:
    positive_level: level>=0 && level<this->GetNumberOfLevels()
  Postcondition:
    definition: result==(2^(GetNumberOfLevels()-level-1)+1)^GetDimension()
- `vtkIdType = obj.GetMaxNumberOfPointsOnBoundary (int level)` - Return the number of points corresponding to the boundary of an hyperoctree starting at level `level' where all the leaves at at the last level. In this case, the hyperoctree is like a uniform grid. So this number is the number of points of on the boundary of the uniform grid. For an octree, the boundary are the faces. For a quadtree, the boundary are the edges.
  Precondition:
    2d_or_3d: this->GetDimension()==2 || this->GetDimension()==3
    positive_level: level>=0 && level<this->GetNumberOfLevels()
  Postcondition:
    min_result: result>=GetMaxNumberOfPoints(this->GetNumberOfLevels()-1)
    max_result: result<=GetMaxNumberOfPoints(level)
- `vtkIdType = obj.GetMaxNumberOfCellsOnBoundary (int level)` - Return the number of cells corresponding to the boundary of a cell of level `level' where all the leaves at at the last level.
  Precondition:
    positive_level: level>=0 && level<this->GetNumberOfLevels()
  Postcondition:
    positive_result: result>=0
- `vtkIdType = obj.GetNumberOfLevels ()` - Return the number of levels.
  Postcondition:
    result_greater_or_equal_to_one: result>=1
- `obj.SetSize (double , double , double )` - Set the size on each axis.
- `obj.SetSize (double a[3])` - Set the size on each axis.
- `double = obj. GetSize ()` - Return the size on each axis.
- `obj.SetOrigin (double , double , double )` - Set the origin (position of corner (0,0,0) of the root.
- `obj.SetOrigin (double a[3])` - Set the origin (position of corner (0,0,0) of the root.
- `double = obj. GetOrigin ()` - Set the origin (position of corner (0,0,0) of the root. Return the origin (position of corner (0,0,0) ) of the root.
- `vtkHyperOctreeCursor = obj.NewCellCursor ()` - Create a new cursor: an object that can traverse the cell of an hyperoctree.
  Postcondition:
    result_exists: result!=0
- `obj.SubdivideLeaf (vtkHyperOctreeCursor leaf)` - Subdivide node pointed by cursor, only if its a leaf. At the end, cursor points on the node that used to be leaf.
  Precondition:
    leaf_exists: leaf!=0
    is_a_leaf: leaf->CurrentIsLeaf()
- `obj.CollapseTerminalNode (vtkHyperOctreeCursor node)` - Collapse a node for which all children are leaves. At the end, cursor points on the leaf that used to be a node.
  Precondition:
    node_exists: node!=0
    node_is_node: !node->CurrentIsLeaf()
    children_are_leaves: node->CurrentIsTerminalNode()
- `double = obj.GetPoint (vtkIdType ptId)` - Get point coordinates with ptId such that: 0 <= ptId < NumberOfPoints. THIS METHOD IS NOT THREAD SAFE.
- `obj.GetPoint (vtkIdType id, double x[3])` - Copy point coordinates into user provided array x[3] for specified point id. THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND THE DATASET IS NOT MODIFIED
- `vtkCell = obj.GetCell (vtkIdType cellId)` - Get cell with cellId such that: 0 <= cellId < NumberOfCells. THIS METHOD IS NOT THREAD SAFE.
- `obj.GetCell (vtkIdType cellId, vtkGenericCell cell)` - Get cell with cellId such that: 0 <= cellId < NumberOfCells. This is a thread-safe alternative to the previous GetCell() method. THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND THE DATASET IS NOT MODIFIED
- `int = obj.GetCellType (vtkIdType cellId)` - Get type of cell with cellId such that: 0 <= cellId < NumberOfCells. THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND THE DATASET IS NOT MODIFIED
- `obj.GetCellPoints (vtkIdType cellId, vtkIdList ptIds)` - Topological inquiry to get points defining cell. THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND THE DATASET IS NOT MODIFIED
- `obj.GetPointCells (vtkIdType ptId, vtkIdList cellIds)` - Topological inquiry to get cells using point. THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND THE DATASET IS NOT MODIFIED
- `obj.GetCellNeighbors (vtkIdType cellId, vtkIdList ptIds, vtkIdList cellIds)` - Topological inquiry to get all cells using list of points exclusive of cell specified (e.g., cellId). Note that the list consists of only cells that use ALL the points provided. THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND THE DATASET IS NOT MODIFIED
- `vtkIdType = obj.FindPoint (double x[3])`
- `obj.Initialize ()` - Restore data object to initial state, THIS METHOD IS NOT THREAD SAFE.
- `int = obj.GetMaxCellSize ()` - Convenience method returns largest cell size in dataset. This is generally used to allocate memory for supporting data structures. This is the number of points of a cell. THIS METHOD IS THREAD SAFE
- `obj.ShallowCopy (vtkDataObject src)` - Shallow and Deep copy.
- `obj.DeepCopy (vtkDataObject src)` - Shallow and Deep copy.
- `obj.GetPointsOnFace (vtkHyperOctreeCursor sibling, int face, int level, vtkHyperOctreePointsGrabber grabber)` - Get the points of node `sibling' on its face `face'.
  Precondition:
    sibling_exists: sibling!=0
    sibling_not_leaf: !sibling->CurrentIsLeaf()
    sibling_3d: sibling->GetDimension()==3
    valid_face: face>=0 && face<6
    valid_level_not_leaf: level>=0 level<(this->GetNumberOfLevels()-1)
- `obj.GetPointsOnParentFaces (int faces[3], int level, vtkHyperOctreeCursor cursor, vtkHyperOctreePointsGrabber grabber)` - Get the points of the parent node of `cursor' on its faces `faces' at level `level' or deeper.
  Precondition:
    cursor_exists: cursor!=0
    cursor_3d: cursor->GetDimension()==3
    valid_level: level>=0
    boolean_faces: (faces[0]==0 || faces[0]==1) && (faces[1]==0 || faces[1]==1) && (faces[2]==0 || faces[2]==1)
- `obj.GetPointsOnEdge (vtkHyperOctreeCursor sibling, int level, int axis, int k, int j, vtkHyperOctreePointsGrabber grabber)` - Get the points of node `sibling' on its edge `axis','k','j'. If axis==0, the edge is X-aligned and k gives the z coordinate and j the y-coordinate. If axis==1, the edge is Y-aligned and k gives the x coordinate and j the z coordinate. If axis==2, the edge is Z-aligned and k gives the y coordinate and j the x coordinate.
  Precondition:
    sibling_exists: sibling!=0
    sibling_3d: sibling->GetDimension()==3
    sibling_not_leaf: !sibling->CurrentIsLeaf()
    valid_axis: axis>=0 && axis<3
    valid_k: k>=0 && k<=1
    valid_j: j>=0 && j<=1
    valid_level_not_leaf: level>=0 level<(this->Input->GetNumberOfLevels()-1)
- `obj.GetPointsOnParentEdge (vtkHyperOctreeCursor cursor, int level, int axis, int k, int j, vtkHyperOctreePointsGrabber grabber)` - Get the points of the parent node of `cursor' on its edge `axis','k','j' at level `level' or deeper. If axis==0, the edge is X-aligned and k gives the z coordinate and j the y-coordinate. If axis==1, the edge is Y-aligned and k gives the x coordinate and j the z coordinate. If axis==2, the edge is Z-aligned and k gives the y coordinate and j the x coordinate.
  Precondition:
    cursor_exists: cursor!=0
    cursor_3d: cursor->GetDimension()==3
    valid_level: level>=0
    valid_range_axis: axis>=0 && axis<3
    valid_range_k: k>=0 && k<=1
    valid_range_j: j>=0 && j<=1
- `obj.GetPointsOnEdge2D (vtkHyperOctreeCursor sibling, int edge, int level, vtkHyperOctreePointsGrabber grabber)` - Get the points of node `sibling' on its edge `edge'.
  Precondition:
    sibling_exists: sibling!=0
    sibling_not_leaf: !sibling->CurrentIsLeaf()
    sibling_2d: sibling->GetDimension()==2
    valid_edge: edge>=0 && edge<4
    valid_level_not_leaf: level>=0 level<(this->Input->GetNumberOfLevels()-1)
- `obj.GetPointsOnParentEdge2D (vtkHyperOctreeCursor cursor, int edge, int level, vtkHyperOctreePointsGrabber grabber)` - Get the points of the parent node of `cursor' on its edge `edge' at level `level' or deeper. (edge=0 for -X, 1 for +X, 2 for -Y, 3 for +Y)
  Precondition:
    cursor_exists: cursor!=0
    cursor_2d: cursor->GetDimension()==2
    valid_level: level>=0
    valid_edge: edge>=0 && edge<4
- `vtkDataSetAttributes = obj.GetLeafData ()` - A generic way to set the leaf data attributes. This can be either point data for dual or cell data for normal grid.
- `obj.SetDualGridFlag (int flag)` - Switch between returning leaves as cells, or the dual grid.
- `int = obj.GetDualGridFlag ()` - Switch between returning leaves as cells, or the dual grid.
- `long = obj.GetActualMemorySize ()` - Return the actual size of the data in kilobytes. This number is valid only after the pipeline has updated. The memory size returned is guaranteed to be greater than or equal to the memory required to represent the data (e.g., extra space in arrays, etc. are not included in the return value). THIS METHOD IS THREAD SAFE.