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  vtkCell *GetCell(vtkIdType cellId) VTK_OVERRIDE;
319 
327  void GetCell(vtkIdType cellId, vtkGenericCell *cell) VTK_OVERRIDE;
328 
329 
335  int GetCellType(vtkIdType cellId) VTK_OVERRIDE;
336 
338 
343  void GetCellPoints(vtkIdType cellId, vtkIdList *ptIds) VTK_OVERRIDE;
344  virtual void GetCellPoints(vtkIdType cellId, vtkIdType& npts,
345  vtkIdType* &pts);
347 
353  void GetPointCells(vtkIdType ptId, vtkIdList *cellIds) VTK_OVERRIDE;
354 
355 
363  void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds,
364  vtkIdList *cellIds) VTK_OVERRIDE;
365 
366  vtkIdType FindPoint(double x[3]) VTK_OVERRIDE;
367 
379  vtkIdType FindCell(double x[3], vtkCell *cell, vtkIdType cellId,
380  double tol2, int& subId, double pcoords[3],
381  double *weights) VTK_OVERRIDE;
382 
390  vtkIdType FindCell(double x[3], vtkCell *cell,
391  vtkGenericCell *gencell, vtkIdType cellId,
392  double tol2, int& subId, double pcoords[3],
393  double *weights) VTK_OVERRIDE;
394 
399  void Initialize() VTK_OVERRIDE;
400 
407  int GetMaxCellSize() VTK_OVERRIDE;
408 
410 
413  void ShallowCopy(vtkDataObject *src) VTK_OVERRIDE;
414  void DeepCopy(vtkDataObject *src) VTK_OVERRIDE;
416 
425  void GetPointsOnFace(vtkHyperOctreeCursor *sibling,
426  int face,
427  int level,
428  vtkHyperOctreePointsGrabber *grabber);
429 
438  void GetPointsOnParentFaces(int faces[3],
439  int level,
440  vtkHyperOctreeCursor *cursor,
441  vtkHyperOctreePointsGrabber *grabber);
442 
457  void GetPointsOnEdge(vtkHyperOctreeCursor *sibling,
458  int level,
459  int axis,
460  int k,
461  int j,
462  vtkHyperOctreePointsGrabber *grabber);
463 
478  void GetPointsOnParentEdge(vtkHyperOctreeCursor *cursor,
479  int level,
480  int axis,
481  int k,
482  int j,
483  vtkHyperOctreePointsGrabber *grabber);
484 
493  void GetPointsOnEdge2D(vtkHyperOctreeCursor *sibling,
494  int edge,
495  int level,
496  vtkHyperOctreePointsGrabber *grabber);
497 
506  void GetPointsOnParentEdge2D(vtkHyperOctreeCursor *cursor,
507  int edge,
508  int level,
509  vtkHyperOctreePointsGrabber *grabber);
510 
515  vtkDataSetAttributes* GetLeafData();
516 
518 
521  void SetDualGridFlag(int flag);
522  vtkGetMacro(DualGridFlag,int);
524 
533  unsigned long GetActualMemorySize() VTK_OVERRIDE;
534 
536 
539  static vtkHyperOctree* GetData(vtkInformation* info);
540  static vtkHyperOctree* GetData(vtkInformationVector* v, int i=0);
542 
543 protected:
544  // Constructor with default bounds (0,1, 0,1, 0,1).
545  vtkHyperOctree();
546  ~vtkHyperOctree() VTK_OVERRIDE;
547 
548  void ComputeBounds() VTK_OVERRIDE;
549 
550  int Dimension; // 1, 2 or 3.
551 
552  double Size[3]; // size on each axis
553  double Origin[3]; // position of corner (0,0,0) of the root.
554 
555  vtkHyperOctreeInternal *CellTree;
556 
557  vtkHyperOctreeCursor *TmpChild; // to avoid allocation in the loop
558 
560 
561  // Initialize the arrays if necessary, then return it.
562  void UpdateDualArrays();
563  vtkPoints* GetLeafCenters();
564  vtkIdTypeArray* GetCornerLeafIds();
565  vtkPoints *LeafCenters;
566  vtkIdTypeArray *CornerLeafIds;
567 
568  void UpdateGridArrays();
569  vtkPoints* GetCornerPoints();
570  vtkIdTypeArray* GetLeafCornerIds();
571  vtkPoints* CornerPoints;
572  vtkIdTypeArray* LeafCornerIds;
573 
574  void DeleteInternalArrays();
575 
576  void TraverseDualRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
577  unsigned short *xyzIds, int level);
578  void TraverseGridRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
579  unsigned char* visited,
580  double* origin, double* size);
581  void EvaluateDualCorner(vtkHyperOctreeLightWeightCursor* neighborhood);
582  vtkIdType EvaluateGridCorner(int level,vtkHyperOctreeLightWeightCursor* neighborhood,
583  unsigned char* visited, int* cornerNeighborIds);
584 
585  // This is a table for traversing a neighborhood down an octree.
586  // 8 children x 27 cursors
587  // First three bits encode the child, rest encode the cursor id.
588  // 8xCursorId + childId.
589  // This will be shorter when we get rid of the 3x3x3 neighborhood.
590  // I was using unsigned char, but VS60 optimized build had a problem.
591  int NeighborhoodTraversalTable[216];
592  void GenerateGridNeighborhoodTraversalTable();
593  void GenerateDualNeighborhoodTraversalTable();
594 
595  // for the GetCell method
596  vtkLine *Line;
597  vtkPixel *Pixel;
598  vtkVoxel *Voxel;
599 
600  vtkCellLinks* Links;
601  void BuildLinks();
602 
603  vtkIdType RecursiveFindPoint(double x[3],
605  double *origin, double *size);
606 
607  // This toggles the data set API between the leaf cells and
608  // the dual grid (leaves are points, corners are cells).
609  int DualGridFlag;
610 
611 private:
612  vtkHyperOctree(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
613  void operator=(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
614 };
615 
616 class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctreeLightWeightCursor
617 {
618 public:
620  void Initialize(vtkHyperOctree* tree);
621  void ToRoot();
622  void ToChild(int child);
623  unsigned short GetIsLeaf();
624  int GetLeafIndex() {return this->Index;} // Only valid for leaves.
625  vtkHyperOctree* GetTree() { return this->Tree; }
626  unsigned short GetLevel() {return this->Level;}
627 private:
628  vtkHyperOctree* Tree;
629  int Index;
630  unsigned short IsLeaf;
631  unsigned short Level;
632 };
633 
634 #endif
vtkPoints
represent and manipulate 3D points
Definition: vtkPoints.h:39
vtkpiston::DeepCopy
void DeepCopy(vtkPistonReference *self, vtkPistonReference *other)
vtkHyperOctreeLightWeightCursor::GetLevel
unsigned short GetLevel()
Definition: vtkHyperOctree.h:626
vtkIdType
int vtkIdType
Definition: vtkType.h:287
vtkPolygon
a cell that represents an n-sided polygon
Definition: vtkPolygon.h:45
vtkDataSetAttributes
represent and manipulate attribute data in a dataset
Definition: vtkDataSetAttributes.h:58
vtkInformationVector
Store zero or more vtkInformation instances.
Definition: vtkInformationVector.h:41
vtkPointLocator
quickly locate points in 3-space
Definition: vtkPointLocator.h:53
vtkDataSet::GetDataObjectType
int GetDataObjectType() override
Return the type of data object.
Definition: vtkDataSet.h:354
vtkHyperOctreeCursor
Objects that can traverse hyperoctree nodes.
Definition: vtkHyperOctreeCursor.h:51
vtkDataSet::PrintSelf
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
vtkHyperOctreePointsGrabber
An object used by filters to store points computed on face or edge of an hyperoctant....
Definition: vtkHyperOctreePointsGrabber.h:35
GetPoint
void GetPoint(const int i, const int j, const int k, double pnt[3])
vtkLine
cell represents a 1D line
Definition: vtkLine.h:35
vtkOrderedTriangulator
helper class to generate triangulations
Definition: vtkOrderedTriangulator.h:117
vtkHyperOctreeLightWeightCursor::GetTree
vtkHyperOctree * GetTree()
Definition: vtkHyperOctree.h:625
vtkX3D::level
@ level
Definition: vtkX3D.h:395
vtkCell
abstract class to specify cell behavior
Definition: vtkCell.h:59
vtkInformationIntegerKey
Key for integer values in vtkInformation.
Definition: vtkInformationIntegerKey.h:34
vtkIndent
a simple class to control print indentation
Definition: vtkIndent.h:39
vtkDataSet::Initialize
void Initialize() override
Restore data object to initial state.
vtkIdList
list of point or cell ids
Definition: vtkIdList.h:36
vtkX3D::size
@ size
Definition: vtkX3D.h:253
vtkHyperOctreeLightWeightCursor
Definition: vtkHyperOctree.h:616
vtkDataSet.h
vtkDataSet
abstract class to specify dataset behavior
Definition: vtkDataSet.h:62
vtkInformation
Store vtkAlgorithm input/output information.
Definition: vtkInformation.h:86
vtkX3D::info
@ info
Definition: vtkX3D.h:376
vtkIdTypeArray
dynamic, self-adjusting array of vtkIdType
Definition: vtkIdTypeArray.h:41
vtkPixel
a cell that represents an orthogonal quadrilateral
Definition: vtkPixel.h:40
vtkInformationDoubleVectorKey
Key for double vector values.
Definition: vtkInformationDoubleVectorKey.h:34
vtkGenericCell
provides thread-safe access to cells
Definition: vtkGenericCell.h:39
vtkHyperOctreeLightWeightCursor::GetLeafIndex
int GetLeafIndex()
Definition: vtkHyperOctree.h:624
vtkHyperOctree
A dataset structured as a tree where each node has exactly 2^n children.
Definition: vtkHyperOctree.h:143
vtkDataObject
general representation of visualization data
Definition: vtkDataObject.h:64
vtkDataObject::New
static vtkDataObject * New()
vtkVoxel
a cell that represents a 3D orthogonal parallelepiped
Definition: vtkVoxel.h:44