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 #if !defined(VTK_LEGACY_REMOVE)
144 class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctree : public vtkDataSet
145 {
146 public:
147  static vtkInformationIntegerKey* LEVELS();
148  static vtkInformationIntegerKey* DIMENSION();
149  static vtkInformationDoubleVectorKey* SIZES();
150  static vtkHyperOctree *New();
151 
152  vtkTypeMacro(vtkHyperOctree,vtkDataSet);
153  void PrintSelf(ostream& os, vtkIndent indent) override;
154 
158  int GetDataObjectType() override;
159 
164  void CopyStructure(vtkDataSet *ds) override;
165 
166  // Return the node describes by the path from the root.
167  // Path is a sequence of number between 0 and 7.
168  // \pre path_exists: path!=0
169  // \pre node_exists: IsANode(path)
170 // vtkOctree *GetNode(vtkPath *path);
171 
177  int GetDimension();
178 
184  void SetDimension(int dim);
185 
186  // Return if the node for the given path exists or not.
187  // \pre path_exists: path!=0
188 // int IsANode(vtkPath *path);
189 
190  // Return if the node for the given path is a leaf or not.
191  // \pre path_exists: path!=0
192  // \pre node_exists: IsANode(path)
193 // int IsALeaf(vtkPath *path);
194 
195  // Measurement: topology
196 
201  vtkIdType GetNumberOfCells() override;
202 
206  vtkIdType GetNumberOfLeaves();
207 
212  vtkIdType GetNumberOfPoints() override;
213 
222  vtkIdType GetMaxNumberOfPoints(int level);
223 
236  vtkIdType GetMaxNumberOfPointsOnBoundary(int level);
237 
244  vtkIdType GetMaxNumberOfCellsOnBoundary(int level);
245 
250  vtkIdType GetNumberOfLevels();
251 
252  // Measurement: geometry
253 
255 
258  vtkSetVector3Macro(Size,double);
260 
262 
265  vtkGetVector3Macro(Size,double);
267 
269 
272  vtkSetVector3Macro(Origin,double);
273  // Return the origin (position of corner (0,0,0) ) of the root.
274  vtkGetVector3Macro(Origin,double);
276 
282  vtkHyperOctreeCursor *NewCellCursor();
283 
290  void SubdivideLeaf(vtkHyperOctreeCursor *leaf);
291 
299  void CollapseTerminalNode(vtkHyperOctreeCursor *node);
300 
305  double *GetPoint(vtkIdType ptId) override;
306 
313  void GetPoint(vtkIdType id, double x[3]) override;
314 
319  using vtkDataSet::GetCell;
320  vtkCell *GetCell(vtkIdType cellId) override;
321 
329  void GetCell(vtkIdType cellId, vtkGenericCell *cell) override;
330 
331 
337  int GetCellType(vtkIdType cellId) override;
338 
340 
345  void GetCellPoints(vtkIdType cellId, vtkIdList *ptIds) override;
346  virtual void GetCellPoints(vtkIdType cellId, vtkIdType& npts,
347  vtkIdType* &pts);
349 
355  void GetPointCells(vtkIdType ptId, vtkIdList *cellIds) override;
356 
357 
365  void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds,
366  vtkIdList *cellIds) override;
367 
368  vtkIdType FindPoint(double x[3]) override;
369 
381  vtkIdType FindCell(double x[3], vtkCell *cell, vtkIdType cellId,
382  double tol2, int& subId, double pcoords[3],
383  double *weights) override;
384 
392  vtkIdType FindCell(double x[3], vtkCell *cell,
393  vtkGenericCell *gencell, vtkIdType cellId,
394  double tol2, int& subId, double pcoords[3],
395  double *weights) override;
396 
401  void Initialize() override;
402 
409  int GetMaxCellSize() override;
410 
412 
415  void ShallowCopy(vtkDataObject *src) override;
416  void DeepCopy(vtkDataObject *src) override;
418 
427  void GetPointsOnFace(vtkHyperOctreeCursor *sibling,
428  int face,
429  int level,
430  vtkHyperOctreePointsGrabber *grabber);
431 
440  void GetPointsOnParentFaces(int faces[3],
441  int level,
442  vtkHyperOctreeCursor *cursor,
443  vtkHyperOctreePointsGrabber *grabber);
444 
459  void GetPointsOnEdge(vtkHyperOctreeCursor *sibling,
460  int level,
461  int axis,
462  int k,
463  int j,
464  vtkHyperOctreePointsGrabber *grabber);
465 
480  void GetPointsOnParentEdge(vtkHyperOctreeCursor *cursor,
481  int level,
482  int axis,
483  int k,
484  int j,
485  vtkHyperOctreePointsGrabber *grabber);
486 
495  void GetPointsOnEdge2D(vtkHyperOctreeCursor *sibling,
496  int edge,
497  int level,
498  vtkHyperOctreePointsGrabber *grabber);
499 
508  void GetPointsOnParentEdge2D(vtkHyperOctreeCursor *cursor,
509  int edge,
510  int level,
511  vtkHyperOctreePointsGrabber *grabber);
512 
517  vtkDataSetAttributes* GetLeafData();
518 
520 
523  void SetDualGridFlag(int flag);
524  vtkGetMacro(DualGridFlag,int);
526 
535  unsigned long GetActualMemorySize() override;
536 
538 
542  static vtkHyperOctree* GetData(vtkInformationVector* v, int i=0);
544 
545 protected:
546  // Constructor with default bounds (0,1, 0,1, 0,1).
547  vtkHyperOctree();
548  ~vtkHyperOctree() override;
549 
550  void ComputeBounds() override;
551 
552  int Dimension; // 1, 2 or 3.
553 
554  double Size[3]; // size on each axis
555  double Origin[3]; // position of corner (0,0,0) of the root.
556 
557  vtkHyperOctreeInternal *CellTree;
558 
559  vtkHyperOctreeCursor *TmpChild; // to avoid allocation in the loop
560 
562 
563  // Initialize the arrays if necessary, then return it.
564  void UpdateDualArrays();
565  vtkPoints* GetLeafCenters();
566  vtkIdTypeArray* GetCornerLeafIds();
569 
570  void UpdateGridArrays();
571  vtkPoints* GetCornerPoints();
572  vtkIdTypeArray* GetLeafCornerIds();
575 
576  void DeleteInternalArrays();
577 
578  void TraverseDualRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
579  unsigned short *xyzIds, int level);
580  void TraverseGridRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
581  unsigned char* visited,
582  double* origin, double* size);
583  void EvaluateDualCorner(vtkHyperOctreeLightWeightCursor* neighborhood);
584  vtkIdType EvaluateGridCorner(int level,vtkHyperOctreeLightWeightCursor* neighborhood,
585  unsigned char* visited, int* cornerNeighborIds);
586 
587  // This is a table for traversing a neighborhood down an octree.
588  // 8 children x 27 cursors
589  // First three bits encode the child, rest encode the cursor id.
590  // 8xCursorId + childId.
591  // This will be shorter when we get rid of the 3x3x3 neighborhood.
592  // I was using unsigned char, but VS60 optimized build had a problem.
593  int NeighborhoodTraversalTable[216];
594  void GenerateGridNeighborhoodTraversalTable();
595  void GenerateDualNeighborhoodTraversalTable();
596 
597  // for the GetCell method
601 
603  void BuildLinks();
604 
605  vtkIdType RecursiveFindPoint(double x[3],
607  double *origin, double *size);
608 
609  // This toggles the data set API between the leaf cells and
610  // the dual grid (leaves are points, corners are cells).
612 
613 private:
614  vtkHyperOctree(const vtkHyperOctree&) = delete;
615  void operator=(const vtkHyperOctree&) = delete;
616 };
617 
618 class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctreeLightWeightCursor
619 {
620 public:
622  void Initialize(vtkHyperOctree* tree);
623  void ToRoot();
624  void ToChild(int child);
625  unsigned short GetIsLeaf();
626  int GetLeafIndex() {return this->Index;} // Only valid for leaves.
627  vtkHyperOctree* GetTree() { return this->Tree; }
628  unsigned short GetLevel() {return this->Level;}
629 private:
630  vtkHyperOctree* Tree;
631  int Index;
632  unsigned short IsLeaf;
633  unsigned short Level;
634 };
635 #endif // LEGACY remove
636 
637 #endif
vtkVoxel * Voxel
virtual vtkIdType GetNumberOfCells()=0
Determine the number of cells composing the dataset.
virtual void GetPointCells(vtkIdType ptId, vtkIdList *cellIds)=0
Topological inquiry to get cells using point.
vtkIdTypeArray * CornerLeafIds
vtkPoints * CornerPoints
static vtkDataObject * New()
virtual vtkIdType FindCell(double x[3], vtkCell *cell, vtkIdType cellId, double tol2, int &subId, double pcoords[3], double *weights)=0
Locate cell based on global coordinate x and tolerance squared.
quickly locate points in 3-space
Store vtkAlgorithm input/output information.
virtual vtkIdType GetNumberOfPoints()=0
Determine the number of points composing the dataset.
abstract class to specify dataset behavior
Definition: vtkDataSet.h:62
a cell that represents an orthogonal quadrilateral
Definition: vtkPixel.h:40
vtkPoints * LeafCenters
virtual void ComputeBounds()
Compute the data bounding box from data points.
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.
static vtkDataSet * GetData(vtkInformation *info)
Retrieve an instance of this class from an information object.
provides thread-safe access to cells
cell represents a 1D line
Definition: vtkLine.h:35
abstract class to specify cell behavior
Definition: vtkCell.h:59
a cell that represents a 3D orthogonal parallelepiped
Definition: vtkVoxel.h:44
unsigned long GetActualMemorySize() override
Return the actual size of the data in kibibytes (1024 bytes).
a simple class to control print indentation
Definition: vtkIndent.h:39
virtual int GetMaxCellSize()=0
Convenience method returns largest cell size in dataset.
list of point or cell ids
Definition: vtkIdList.h:36
virtual void GetCellPoints(vtkIdType cellId, vtkIdList *ptIds)=0
Topological inquiry to get points defining cell.
Key for integer values in vtkInformation.
int GetDataObjectType() override
Return the type of data object.
Definition: vtkDataSet.h:359
a cell that represents an n-sided polygon
Definition: vtkPolygon.h:45
vtkCellLinks * Links
vtkPixel * Pixel
void DeepCopy(vtkDataObject *src) override
Shallow and Deep copy.
represent and manipulate attribute data in a dataset
virtual void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds, vtkIdList *cellIds)
Topological inquiry to get all cells using list of points exclusive of cell specified (e....
Objects that can traverse hyperoctree nodes.
vtkHyperOctreeInternal * CellTree
void Initialize() override
Restore data object to initial state.
virtual void CopyStructure(vtkDataSet *ds)=0
Copy the geometric and topological structure of an object.
void ShallowCopy(vtkDataObject *src) override
Shallow and Deep copy.
Store zero or more vtkInformation instances.
virtual double * GetPoint(vtkIdType ptId)=0
Get point coordinates with ptId such that: 0 <= ptId < NumberOfPoints.
vtkIdTypeArray * LeafCornerIds
vtkHyperOctreeCursor * TmpChild
general representation of visualization data
Definition: vtkDataObject.h:64
vtkIdType FindPoint(double x, double y, double z)
Locate the closest point to the global coordinate x.
Definition: vtkDataSet.h:197
virtual vtkCell * GetCell(vtkIdType cellId)=0
Get cell with cellId such that: 0 <= cellId < NumberOfCells.
represent and manipulate 3D points
Definition: vtkPoints.h:39
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
virtual int GetCellType(vtkIdType cellId)=0
Get type of cell with cellId such that: 0 <= cellId < NumberOfCells.