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) VTK_OVERRIDE;

  int GetDataObjectType() VTK_OVERRIDE;

  void CopyStructure(vtkDataSet *ds) VTK_OVERRIDE;

  // 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() VTK_OVERRIDE;

  vtkIdType GetNumberOfLeaves();

  vtkIdType GetNumberOfPoints() VTK_OVERRIDE;

  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);

  double *GetPoint(vtkIdType ptId) VTK_OVERRIDE;

  void GetPoint(vtkIdType id, double x[3]) VTK_OVERRIDE;

  vtkCell *GetCell(vtkIdType cellId) VTK_OVERRIDE;

  void GetCell(vtkIdType cellId, vtkGenericCell *cell) VTK_OVERRIDE;


  int GetCellType(vtkIdType cellId) VTK_OVERRIDE;


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

  void GetPointCells(vtkIdType ptId, vtkIdList *cellIds) VTK_OVERRIDE;


  void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds,
                        vtkIdList *cellIds) VTK_OVERRIDE;

  vtkIdType FindPoint(double x[3]) VTK_OVERRIDE;

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

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

  void Initialize() VTK_OVERRIDE;

  int GetMaxCellSize() VTK_OVERRIDE;


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

  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() VTK_OVERRIDE;


  static vtkHyperOctree* GetData(vtkInformation* info);
  static vtkHyperOctree* GetData(vtkInformationVector* v, int i=0);

protected:
  // Constructor with default bounds (0,1, 0,1, 0,1).
  vtkHyperOctree();
  ~vtkHyperOctree() VTK_OVERRIDE;

  void ComputeBounds() VTK_OVERRIDE;

  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

  friend class vtkHyperOctreeLightWeightCursor;

  // 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&) VTK_DELETE_FUNCTION;
  void operator=(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
};

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;
};

#endif