vtkHyperOctree.h

Go to the documentation of this file.

/*=========================================================================
 
  Program:   Visualization Toolkit
  Module:    vtkHyperOctree.h
 
  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
 
     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.
 
=========================================================================*/
#ifndef vtkHyperOctree_h
#define vtkHyperOctree_h
 
#include "vtkCommonDataModelModule.h" // For export macro
#include "vtkDataSet.h"
 
class vtkHyperOctreeLightWeightCursor;
class vtkHyperOctreeCursor;
class vtkHyperOctreeInternal;
class vtkHyperOctreePointsGrabber;
 
class vtkHyperOctreeIdSet; // Pimpl idiom
class vtkPolygon;
class vtkIdTypeArray;
class vtkPoints;
class vtkPointLocator;
class vtkOrderedTriangulator;
class vtkDataSetAttributes;
 
class vtkLine;
class vtkPixel;
class vtkVoxel;
class vtkCellLinks;
 
class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctree : public vtkDataSet
{
public:
  static vtkInformationIntegerKey* LEVELS();
  static vtkInformationIntegerKey* DIMENSION();
  static vtkInformationDoubleVectorKey* SIZES();
  static vtkHyperOctree *New();
 
  vtkTypeMacro(vtkHyperOctree,vtkDataSet);
  void PrintSelf(ostream& os, vtkIndent indent);
 
  int GetDataObjectType();
 
  void CopyStructure(vtkDataSet *ds);
 
  // Return the node describes by the path from the root.
  // Path is a sequence of number between 0 and 7.
  // \pre path_exists: path!=0
  // \pre node_exists: IsANode(path)
//  vtkOctree *GetNode(vtkPath *path);
 
  int GetDimension();
 
  void SetDimension(int dim);
 
  // Return if the node for the given path exists or not.
  // \pre path_exists: path!=0
//  int IsANode(vtkPath *path);
 
  // Return if the node for the given path is a leaf or not.
  // \pre path_exists: path!=0
  // \pre node_exists: IsANode(path)
//  int IsALeaf(vtkPath *path);
 
  // Measurement: topology
 
  vtkIdType GetNumberOfCells();
 
  vtkIdType GetNumberOfLeaves();
 
  vtkIdType GetNumberOfPoints();
 
  vtkIdType GetMaxNumberOfPoints(int level);
 
  vtkIdType GetMaxNumberOfPointsOnBoundary(int level);
 
  vtkIdType GetMaxNumberOfCellsOnBoundary(int level);
 
  vtkIdType GetNumberOfLevels();
 
  // Measurement: geometry
 
 
  vtkSetVector3Macro(Size,double);
 
 
  vtkGetVector3Macro(Size,double);
 
 
  vtkSetVector3Macro(Origin,double);
  // Return the origin (position of corner (0,0,0) ) of the root.
  vtkGetVector3Macro(Origin,double);
 
  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 GetCellPoints(vtkIdType cellId, vtkIdList *ptIds);
  virtual void GetCellPoints(vtkIdType cellId, vtkIdType& npts,
                             vtkIdType* &pts);
 
  virtual void GetPointCells(vtkIdType ptId, vtkIdList *cellIds);
 
 
 
  virtual void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds,
                                vtkIdList *cellIds);
 
  virtual vtkIdType FindPoint(double x[3]);
 
 
  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 Initialize();
 
  virtual int GetMaxCellSize();
 
 
  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);
 
  vtkDataSetAttributes* GetLeafData();
 
 
  void SetDualGridFlag(int flag);
  vtkGetMacro(DualGridFlag,int);
 
  unsigned long GetActualMemorySize();
 
  //BTX
 
  static vtkHyperOctree* GetData(vtkInformation* info);
  static vtkHyperOctree* GetData(vtkInformationVector* v, int i=0);
  //ETX
 
protected:
  // Constructor with default bounds (0,1, 0,1, 0,1).
  vtkHyperOctree();
  ~vtkHyperOctree();
 
  void ComputeBounds();
 
  int Dimension; // 1, 2 or 3.
 
  double Size[3]; // size on each axis
  double Origin[3]; // position of corner (0,0,0) of the root.
 
  vtkHyperOctreeInternal *CellTree;
 
  vtkHyperOctreeCursor *TmpChild; // to avoid allocation in the loop
 
  //BTX
  friend class vtkHyperOctreeLightWeightCursor;
  //ETX
 
  // Initialize the arrays if necessary, then return it.
  void UpdateDualArrays();
  vtkPoints* GetLeafCenters();
  vtkIdTypeArray* GetCornerLeafIds();
  vtkPoints *LeafCenters;
  vtkIdTypeArray *CornerLeafIds;
 
  void UpdateGridArrays();
  vtkPoints* GetCornerPoints();
  vtkIdTypeArray* GetLeafCornerIds();
  vtkPoints* CornerPoints;
  vtkIdTypeArray* LeafCornerIds;
 
  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);
 
  // This is a table for traversing a neighborhood down an octree.
  // 8 children x 27 cursors
  // First three bits encode the child,  rest encode the cursor id.
  // 8xCursorId + childId.
  // This will be shorter when we get rid of the 3x3x3 neighborhood.
  // I was using unsigned char, but VS60 optimized build had a problem.
  int NeighborhoodTraversalTable[216];
  void GenerateGridNeighborhoodTraversalTable();
  void GenerateDualNeighborhoodTraversalTable();
 
  // for the GetCell method
  vtkLine *Line;
  vtkPixel *Pixel;
  vtkVoxel *Voxel;
 
  vtkCellLinks* Links;
  void BuildLinks();
 
  vtkIdType RecursiveFindPoint(double x[3],
    vtkHyperOctreeLightWeightCursor* cursor,
    double *origin, double *size);
 
  // This toggles the data set API between the leaf cells and
  // the dual grid (leaves are points, corners are cells).
  int DualGridFlag;
 
private:
  vtkHyperOctree(const vtkHyperOctree&);  // Not implemented.
  void operator=(const vtkHyperOctree&);    // Not implemented.
};
 
 
//BTX
 
class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctreeLightWeightCursor
{
public:
  vtkHyperOctreeLightWeightCursor();
  void Initialize(vtkHyperOctree* tree);
  void ToRoot();
  void ToChild(int child);
  unsigned short GetIsLeaf();
  int GetLeafIndex() {return this->Index;} // Only valid for leaves.
  vtkHyperOctree* GetTree() { return this->Tree; }
  unsigned short GetLevel() {return this->Level;}
private:
  vtkHyperOctree* Tree;
  int Index;
  unsigned short IsLeaf;
  unsigned short Level;
};
 
//ETX
 
#endif