VTK
vtkHyperOctree.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkHyperOctree.h
5 
6  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7  All rights reserved.
8  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9 
10  This software is distributed WITHOUT ANY WARRANTY; without even
11  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12  PURPOSE. See the above copyright notice for more information.
13 
14 =========================================================================*/
119 #ifndef vtkHyperOctree_h
120 #define vtkHyperOctree_h
121 
122 #include "vtkCommonDataModelModule.h" // For export macro
123 #include "vtkDataSet.h"
124 
127 class vtkHyperOctreeInternal;
129 
130 class vtkHyperOctreeIdSet; // Pimpl idiom
131 class vtkPolygon;
132 class vtkIdTypeArray;
133 class vtkPoints;
134 class vtkPointLocator;
137 
138 class vtkLine;
139 class vtkPixel;
140 class vtkVoxel;
141 class vtkCellLinks;
142 
143 class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctree : public vtkDataSet
144 {
145 public:
146  static vtkInformationIntegerKey* LEVELS();
147  static vtkInformationIntegerKey* DIMENSION();
148  static vtkInformationDoubleVectorKey* SIZES();
149  static vtkHyperOctree *New();
150 
151  vtkTypeMacro(vtkHyperOctree,vtkDataSet);
152  void PrintSelf(ostream& os, vtkIndent indent) VTK_OVERRIDE;
153 
157  int GetDataObjectType() VTK_OVERRIDE;
158 
163  void CopyStructure(vtkDataSet *ds) VTK_OVERRIDE;
164 
165  // Return the node describes by the path from the root.
166  // Path is a sequence of number between 0 and 7.
167  // \pre path_exists: path!=0
168  // \pre node_exists: IsANode(path)
169 // vtkOctree *GetNode(vtkPath *path);
170 
176  int GetDimension();
177 
183  void SetDimension(int dim);
184 
185  // Return if the node for the given path exists or not.
186  // \pre path_exists: path!=0
187 // int IsANode(vtkPath *path);
188 
189  // Return if the node for the given path is a leaf or not.
190  // \pre path_exists: path!=0
191  // \pre node_exists: IsANode(path)
192 // int IsALeaf(vtkPath *path);
193 
194  // Measurement: topology
195 
200  vtkIdType GetNumberOfCells() VTK_OVERRIDE;
201 
205  vtkIdType GetNumberOfLeaves();
206 
211  vtkIdType GetNumberOfPoints() VTK_OVERRIDE;
212 
221  vtkIdType GetMaxNumberOfPoints(int level);
222 
235  vtkIdType GetMaxNumberOfPointsOnBoundary(int level);
236 
243  vtkIdType GetMaxNumberOfCellsOnBoundary(int level);
244 
249  vtkIdType GetNumberOfLevels();
250 
251  // Measurement: geometry
252 
254 
257  vtkSetVector3Macro(Size,double);
259 
261 
264  vtkGetVector3Macro(Size,double);
266 
268 
271  vtkSetVector3Macro(Origin,double);
272  // Return the origin (position of corner (0,0,0) ) of the root.
273  vtkGetVector3Macro(Origin,double);
275 
281  vtkHyperOctreeCursor *NewCellCursor();
282 
289  void SubdivideLeaf(vtkHyperOctreeCursor *leaf);
290 
298  void CollapseTerminalNode(vtkHyperOctreeCursor *node);
299 
304  double *GetPoint(vtkIdType ptId) VTK_OVERRIDE;
305 
312  void GetPoint(vtkIdType id, double x[3]) VTK_OVERRIDE;
313 
318  using vtkDataSet::GetCell;
319  vtkCell *GetCell(vtkIdType cellId) VTK_OVERRIDE;
320 
328  void GetCell(vtkIdType cellId, vtkGenericCell *cell) VTK_OVERRIDE;
329 
330 
336  int GetCellType(vtkIdType cellId) VTK_OVERRIDE;
337 
339 
344  void GetCellPoints(vtkIdType cellId, vtkIdList *ptIds) VTK_OVERRIDE;
345  virtual void GetCellPoints(vtkIdType cellId, vtkIdType& npts,
346  vtkIdType* &pts);
348 
354  void GetPointCells(vtkIdType ptId, vtkIdList *cellIds) VTK_OVERRIDE;
355 
356 
364  void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds,
365  vtkIdList *cellIds) VTK_OVERRIDE;
366 
367  vtkIdType FindPoint(double x[3]) VTK_OVERRIDE;
368 
380  vtkIdType FindCell(double x[3], vtkCell *cell, vtkIdType cellId,
381  double tol2, int& subId, double pcoords[3],
382  double *weights) VTK_OVERRIDE;
383 
391  vtkIdType FindCell(double x[3], vtkCell *cell,
392  vtkGenericCell *gencell, vtkIdType cellId,
393  double tol2, int& subId, double pcoords[3],
394  double *weights) VTK_OVERRIDE;
395 
400  void Initialize() VTK_OVERRIDE;
401 
408  int GetMaxCellSize() VTK_OVERRIDE;
409 
411 
414  void ShallowCopy(vtkDataObject *src) VTK_OVERRIDE;
415  void DeepCopy(vtkDataObject *src) VTK_OVERRIDE;
417 
426  void GetPointsOnFace(vtkHyperOctreeCursor *sibling,
427  int face,
428  int level,
429  vtkHyperOctreePointsGrabber *grabber);
430 
439  void GetPointsOnParentFaces(int faces[3],
440  int level,
441  vtkHyperOctreeCursor *cursor,
442  vtkHyperOctreePointsGrabber *grabber);
443 
458  void GetPointsOnEdge(vtkHyperOctreeCursor *sibling,
459  int level,
460  int axis,
461  int k,
462  int j,
463  vtkHyperOctreePointsGrabber *grabber);
464 
479  void GetPointsOnParentEdge(vtkHyperOctreeCursor *cursor,
480  int level,
481  int axis,
482  int k,
483  int j,
484  vtkHyperOctreePointsGrabber *grabber);
485 
494  void GetPointsOnEdge2D(vtkHyperOctreeCursor *sibling,
495  int edge,
496  int level,
497  vtkHyperOctreePointsGrabber *grabber);
498 
507  void GetPointsOnParentEdge2D(vtkHyperOctreeCursor *cursor,
508  int edge,
509  int level,
510  vtkHyperOctreePointsGrabber *grabber);
511 
516  vtkDataSetAttributes* GetLeafData();
517 
519 
522  void SetDualGridFlag(int flag);
523  vtkGetMacro(DualGridFlag,int);
525 
534  unsigned long GetActualMemorySize() VTK_OVERRIDE;
535 
537 
540  static vtkHyperOctree* GetData(vtkInformation* info);
541  static vtkHyperOctree* GetData(vtkInformationVector* v, int i=0);
543 
544 protected:
545  // Constructor with default bounds (0,1, 0,1, 0,1).
546  vtkHyperOctree();
547  ~vtkHyperOctree() VTK_OVERRIDE;
548 
549  void ComputeBounds() VTK_OVERRIDE;
550 
551  int Dimension; // 1, 2 or 3.
552 
553  double Size[3]; // size on each axis
554  double Origin[3]; // position of corner (0,0,0) of the root.
555 
556  vtkHyperOctreeInternal *CellTree;
557 
558  vtkHyperOctreeCursor *TmpChild; // to avoid allocation in the loop
559 
561 
562  // Initialize the arrays if necessary, then return it.
563  void UpdateDualArrays();
564  vtkPoints* GetLeafCenters();
565  vtkIdTypeArray* GetCornerLeafIds();
566  vtkPoints *LeafCenters;
567  vtkIdTypeArray *CornerLeafIds;
568 
569  void UpdateGridArrays();
570  vtkPoints* GetCornerPoints();
571  vtkIdTypeArray* GetLeafCornerIds();
572  vtkPoints* CornerPoints;
573  vtkIdTypeArray* LeafCornerIds;
574 
575  void DeleteInternalArrays();
576 
577  void TraverseDualRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
578  unsigned short *xyzIds, int level);
579  void TraverseGridRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
580  unsigned char* visited,
581  double* origin, double* size);
582  void EvaluateDualCorner(vtkHyperOctreeLightWeightCursor* neighborhood);
583  vtkIdType EvaluateGridCorner(int level,vtkHyperOctreeLightWeightCursor* neighborhood,
584  unsigned char* visited, int* cornerNeighborIds);
585 
586  // This is a table for traversing a neighborhood down an octree.
587  // 8 children x 27 cursors
588  // First three bits encode the child, rest encode the cursor id.
589  // 8xCursorId + childId.
590  // This will be shorter when we get rid of the 3x3x3 neighborhood.
591  // I was using unsigned char, but VS60 optimized build had a problem.
592  int NeighborhoodTraversalTable[216];
593  void GenerateGridNeighborhoodTraversalTable();
594  void GenerateDualNeighborhoodTraversalTable();
595 
596  // for the GetCell method
597  vtkLine *Line;
598  vtkPixel *Pixel;
599  vtkVoxel *Voxel;
600 
601  vtkCellLinks* Links;
602  void BuildLinks();
603 
604  vtkIdType RecursiveFindPoint(double x[3],
606  double *origin, double *size);
607 
608  // This toggles the data set API between the leaf cells and
609  // the dual grid (leaves are points, corners are cells).
610  int DualGridFlag;
611 
612 private:
613  vtkHyperOctree(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
614  void operator=(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
615 };
616 
617 class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctreeLightWeightCursor
618 {
619 public:
621  void Initialize(vtkHyperOctree* tree);
622  void ToRoot();
623  void ToChild(int child);
624  unsigned short GetIsLeaf();
625  int GetLeafIndex() {return this->Index;} // Only valid for leaves.
626  vtkHyperOctree* GetTree() { return this->Tree; }
627  unsigned short GetLevel() {return this->Level;}
628 private:
629  vtkHyperOctree* Tree;
630  int Index;
631  unsigned short IsLeaf;
632  unsigned short Level;
633 };
634 
635 #endif
static vtkDataObject * New()
quickly locate points in 3-space
Store vtkAlgorithm input/output information.
abstract class to specify dataset behavior
Definition: vtkDataSet.h:56
a cell that represents an orthogonal quadrilateral
Definition: vtkPixel.h:34
An object used by filters to store points computed on face or edge of an hyperoctant.
helper class to generate triangulations
dynamic, self-adjusting array of vtkIdType
int vtkIdType
Definition: vtkType.h:345
A dataset structured as a tree where each node has exactly 2^n children.
provides thread-safe access to cells
void GetPoint(const int i, const int j, const int k, double pnt[3])
cell represents a 1D line
Definition: vtkLine.h:29
abstract class to specify cell behavior
Definition: vtkCell.h:56
a cell that represents a 3D orthogonal parallelepiped
Definition: vtkVoxel.h:38
Key for double vector values.
a simple class to control print indentation
Definition: vtkIndent.h:33
list of point or cell ids
Definition: vtkIdList.h:30
Key for integer values in vtkInformation.
int GetDataObjectType() override
Return the type of data object.
Definition: vtkDataSet.h:353
a cell that represents an n-sided polygon
Definition: vtkPolygon.h:39
represent and manipulate attribute data in a dataset
Objects that can traverse hyperoctree nodes.
void Initialize() override
Restore data object to initial state.
Store zero or more vtkInformation instances.
general representation of visualization data
Definition: vtkDataObject.h:58
represent and manipulate 3D points
Definition: vtkPoints.h:33
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.