vtkHyperOctree Class Reference

#include <vtkHyperOctree.h>

Inheritance diagram for vtkHyperOctree:

[legend]

Collaboration diagram for vtkHyperOctree:

[legend]

List of all members.

Detailed Description

A dataset structured as a tree where each node has exactly 2^n children.

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

Warning:: It is not a spatial search object! If you looking for this kind of octree see vtkCellLocator instead.

See also:: vtkHyperOctreeAlgorithm

Definition at line 141 of file vtkHyperOctree.h.


Public Types
typedef vtkDataSet	Superclass
Public Member Functions
virtual const char *	GetClassName ()
virtual int	IsA (const char *type)
void	PrintSelf (ostream &os, vtkIndent indent)
int	GetDataObjectType ()
void	CopyStructure (vtkDataSet *ds)
int	GetDimension ()
void	SetDimension (int dim)
vtkIdType	GetNumberOfCells ()
vtkIdType	GetNumberOfLeaves ()
vtkIdType	GetNumberOfPoints ()
vtkIdType	GetMaxNumberOfPoints (int level)
vtkIdType	GetMaxNumberOfPointsOnBoundary (int level)
vtkIdType	GetMaxNumberOfCellsOnBoundary (int level)
vtkIdType	GetNumberOfLevels ()
vtkHyperOctreeCursor *	NewCellCursor ()
void	SubdivideLeaf (vtkHyperOctreeCursor *leaf)
void	CollapseTerminalNode (vtkHyperOctreeCursor *node)
virtual double *	GetPoint (vtkIdType ptId)
virtual void	GetPoint (vtkIdType id, double x[3])
virtual vtkCell *	GetCell (vtkIdType cellId)
virtual void	GetCell (vtkIdType cellId, vtkGenericCell *cell)
virtual int	GetCellType (vtkIdType cellId)
virtual void	GetPointCells (vtkIdType ptId, vtkIdList *cellIds)
virtual vtkIdType	FindPoint (double x[3])
void	Initialize ()
virtual int	GetMaxCellSize ()
vtkDataSetAttributes *	GetLeafData ()
unsigned long	GetActualMemorySize ()

virtual void	SetSize (double, double, double)
virtual void	SetSize (double[3])

virtual double *	GetSize ()
virtual void	GetSize (double &, double &, double &)
virtual void	GetSize (double[3])

virtual void	SetOrigin (double, double, double)
virtual void	SetOrigin (double[3])
virtual double *	GetOrigin ()
virtual void	GetOrigin (double &, double &, double &)
virtual void	GetOrigin (double[3])

virtual void	GetCellPoints (vtkIdType cellId, vtkIdList *ptIds)
virtual void	GetCellPoints (vtkIdType cellId, vtkIdType &npts, vtkIdType *&pts)

virtual void	GetCellNeighbors (vtkIdType cellId, vtkIdList ptIds, vtkIdList cellIds)

virtual vtkIdType	FindCell (double x[3], vtkCell cell, vtkIdType cellId, double tol2, int &subId, double pcoords[3], double weights)

virtual vtkIdType	FindCell (double x[3], vtkCell cell, vtkGenericCell gencell, vtkIdType cellId, double tol2, int &subId, double pcoords[3], double *weights)

void	ShallowCopy (vtkDataObject *src)
void	DeepCopy (vtkDataObject *src)

void	GetPointsOnFace (vtkHyperOctreeCursor sibling, int face, int level, vtkHyperOctreePointsGrabber grabber)

void	GetPointsOnParentFaces (int faces[3], int level, vtkHyperOctreeCursor cursor, vtkHyperOctreePointsGrabber grabber)

void	GetPointsOnEdge (vtkHyperOctreeCursor sibling, int level, int axis, int k, int j, vtkHyperOctreePointsGrabber grabber)

void	GetPointsOnParentEdge (vtkHyperOctreeCursor cursor, int level, int axis, int k, int j, vtkHyperOctreePointsGrabber grabber)

void	GetPointsOnEdge2D (vtkHyperOctreeCursor sibling, int edge, int level, vtkHyperOctreePointsGrabber grabber)

void	GetPointsOnParentEdge2D (vtkHyperOctreeCursor cursor, int edge, int level, vtkHyperOctreePointsGrabber grabber)

void	SetDualGridFlag (int flag)
virtual int	GetDualGridFlag ()
Static Public Member Functions
static vtkInformationIntegerKey *	LEVELS ()
static vtkInformationIntegerKey *	DIMENSION ()
static vtkInformationDoubleVectorKey *	SIZES ()
static vtkHyperOctree *	New ()
static int	IsTypeOf (const char *type)
static vtkHyperOctree *	SafeDownCast (vtkObject *o)

static vtkHyperOctree *	GetData (vtkInformation *info)
static vtkHyperOctree *	GetData (vtkInformationVector *v, int i=0)
Protected Member Functions
	vtkHyperOctree ()
	~vtkHyperOctree ()
void	ComputeBounds ()
void	UpdateDualArrays ()
vtkPoints *	GetLeafCenters ()
vtkIdTypeArray *	GetCornerLeafIds ()
void	UpdateGridArrays ()
vtkPoints *	GetCornerPoints ()
vtkIdTypeArray *	GetLeafCornerIds ()
void	DeleteInternalArrays ()
void	TraverseDualRecursively (vtkHyperOctreeLightWeightCursor neighborhood, unsigned short xyzIds, int level)
void	TraverseGridRecursively (vtkHyperOctreeLightWeightCursor neighborhood, unsigned char visited, double origin, double size)
void	EvaluateDualCorner (vtkHyperOctreeLightWeightCursor *neighborhood)
vtkIdType	EvaluateGridCorner (int level, vtkHyperOctreeLightWeightCursor neighborhood, unsigned char visited, int *cornerNeighborIds)
void	GenerateGridNeighborhoodTraversalTable ()
void	GenerateDualNeighborhoodTraversalTable ()
void	BuildLinks ()
vtkIdType	RecursiveFindPoint (double x[3], vtkHyperOctreeLightWeightCursor cursor, double origin, double *size)
Protected Attributes
int	Dimension
double	Size [3]
double	Origin [3]
vtkHyperOctreeInternal *	CellTree
vtkHyperOctreeCursor *	TmpChild
vtkPoints *	LeafCenters
vtkIdTypeArray *	CornerLeafIds
vtkPoints *	CornerPoints
vtkIdTypeArray *	LeafCornerIds
int	NeighborhoodTraversalTable [216]
vtkLine *	Line
vtkPixel *	Pixel
vtkVoxel *	Voxel
vtkCellLinks *	Links
int	DualGridFlag
Friends
class	vtkHyperOctreeLightWeightCursor

Member Typedef Documentation

typedef vtkDataSet vtkHyperOctree::Superclass

Reimplemented from vtkDataSet.

Definition at line 149 of file vtkHyperOctree.h.

Constructor & Destructor Documentation

vtkHyperOctree::vtkHyperOctree ( ) [protected]

vtkHyperOctree::~vtkHyperOctree ( ) [protected]

Member Function Documentation

static vtkInformationIntegerKey* vtkHyperOctree::LEVELS ( ) [static]

static vtkInformationIntegerKey* vtkHyperOctree::DIMENSION ( ) [static]

static vtkInformationDoubleVectorKey* vtkHyperOctree::SIZES ( ) [static]

static vtkHyperOctree* vtkHyperOctree::New ( ) [static]

Create an object with Debug turned off, modified time initialized to zero, and reference counting on.

Reimplemented from vtkDataObject.

virtual const char* vtkHyperOctree::GetClassName ( ) [virtual]

Reimplemented from vtkDataSet.

static int vtkHyperOctree::IsTypeOf ( const char * name ) [static]

Return 1 if this class type is the same type of (or a subclass of) the named class. Returns 0 otherwise. This method works in combination with vtkTypeMacro found in vtkSetGet.h.

Reimplemented from vtkDataSet.

virtual int vtkHyperOctree::IsA ( const char * name ) [virtual]

Return 1 if this class is the same type of (or a subclass of) the named class. Returns 0 otherwise. This method works in combination with vtkTypeMacro found in vtkSetGet.h.

Reimplemented from vtkDataSet.

static vtkHyperOctree* vtkHyperOctree::SafeDownCast ( vtkObject * o ) [static]

Reimplemented from vtkDataSet.

void vtkHyperOctree::PrintSelf	(	ostream &	os,
		vtkIndent	indent
	)			`[virtual]`

Methods invoked by print to print information about the object including superclasses. Typically not called by the user (use Print() instead) but used in the hierarchical print process to combine the output of several classes.

Reimplemented from vtkDataSet.

int vtkHyperOctree::GetDataObjectType ( ) [virtual]

Return what type of dataset this is.

Reimplemented from vtkDataSet.

void vtkHyperOctree::CopyStructure ( vtkDataSet * ds ) [virtual]

Copy the geometric and topological structure of an input rectilinear grid object.

Implements vtkDataSet.

int vtkHyperOctree::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

void vtkHyperOctree::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 vtkHyperOctree::GetNumberOfCells ( ) [virtual]

Return the number of cells in the dual grid.

Postcondition:: positive_result: result>=0

Implements vtkDataSet.

vtkIdType vtkHyperOctree::GetNumberOfLeaves ( )

Get the number of leaves in the tree.

vtkIdType vtkHyperOctree::GetNumberOfPoints ( ) [virtual]

Return the number of points in the dual grid.

Postcondition:: positive_result: result>=0

Implements vtkDataSet.

vtkIdType vtkHyperOctree::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 vtkHyperOctree::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 vtkHyperOctree::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 vtkHyperOctree::GetNumberOfLevels ( )

Return the number of levels.

Postcondition:: result_greater_or_equal_to_one: result>=1

virtual void vtkHyperOctree::SetSize	(	double	,
		double	,
		double
	)			`[virtual]`

Set the size on each axis.

virtual void vtkHyperOctree::SetSize ( double [3] ) [virtual]

Set the size on each axis.

virtual double* vtkHyperOctree::GetSize ( ) [virtual]

Return the size on each axis.

virtual void vtkHyperOctree::GetSize	(	double &	,
		double &	,
		double &
	)			`[virtual]`

Return the size on each axis.

virtual void vtkHyperOctree::GetSize ( double [3] ) [virtual]

Return the size on each axis.

virtual void vtkHyperOctree::SetOrigin	(	double	,
		double	,
		double
	)			`[virtual]`