dox/Filtering/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 "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 VTK_FILTERING_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 VTK_FILTERING_EXPORT vtkHyperOctreeLightWeightCursor
{
public:  
  vtkHyperOctreeLightWeightCursor();
  ~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