An object structured as a tree where each node has exactly either 2^n or 3^n children.
More...
Inherits vtkObject.
An object structured as a tree where each node has exactly either 2^n or 3^n children.
An hypertree is a dataset where each node has either exactly 2^n or 3^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 hypertree is efficient in memory usage when the geometry is sparse. The LOD feature allows to cull quickly part of the dataset.
This is an abstract class used as a superclass by a templated compact class. All methods are pure virtual. This is done to hide templates.
- Case with 2^n children:
- 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)
- Case with 2^n children:
-
- Case with 2^n children:
- The cases with fewer dimensions are consistent with the octree case:
- Case with 2^n children:
- Quadtree: in counter-clockwise
- Case with 2^n children:
- Binary tree:
+0+1+ O+-> +x
- Warning
- It is not a spatial search object. If you are looking for this kind of octree see vtkCellLocator instead.
- Thanks:
- This class was written by Philippe Pebay, Joachim Pouderoux and Charles Law, Kitware 2013 This work was supported in part by Commissariat a l'Energie Atomique (CEA/DIF)
Definition at line 133 of file vtkHyperTree.h.