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 =========================================================================*/
118 #ifndef __vtkHyperOctree_h
119 #define __vtkHyperOctree_h
120 
121 #include "vtkDataSet.h"
122 
125 class vtkHyperOctreeInternal;
127 
128 class vtkHyperOctreeIdSet; // Pimpl idiom
129 class vtkPolygon;
130 class vtkIdTypeArray;
131 class vtkPoints;
132 class vtkPointLocator;
135 
136 class vtkLine;
137 class vtkPixel;
138 class vtkVoxel;
139 class vtkCellLinks;
140 
142 {
143 public:
144  static vtkInformationIntegerKey* LEVELS();
145  static vtkInformationIntegerKey* DIMENSION();
146  static vtkInformationDoubleVectorKey* SIZES();
147  static vtkHyperOctree *New();
148 
149  vtkTypeMacro(vtkHyperOctree,vtkDataSet);
150  void PrintSelf(ostream& os, vtkIndent indent);
151 
153  int GetDataObjectType();
154 
157  void CopyStructure(vtkDataSet *ds);
158 
159  // Return the node describes by the path from the root.
160  // Path is a sequence of number between 0 and 7.
161  // \pre path_exists: path!=0
162  // \pre node_exists: IsANode(path)
163 // vtkOctree *GetNode(vtkPath *path);
164 
168  int GetDimension();
169 
173  void SetDimension(int dim);
174 
175  // Return if the node for the given path exists or not.
176  // \pre path_exists: path!=0
177 // int IsANode(vtkPath *path);
178 
179  // Return if the node for the given path is a leaf or not.
180  // \pre path_exists: path!=0
181  // \pre node_exists: IsANode(path)
182 // int IsALeaf(vtkPath *path);
183 
184  // Measurement: topology
185 
189 
191  vtkIdType GetNumberOfLeaves();
192 
196 
203  vtkIdType GetMaxNumberOfPoints(int level);
204 
215  vtkIdType GetMaxNumberOfPointsOnBoundary(int level);
216 
221  vtkIdType GetMaxNumberOfCellsOnBoundary(int level);
222 
225  vtkIdType GetNumberOfLevels();
226 
227  // Measurement: geometry
228 
230 
231  vtkSetVector3Macro(Size,double);
233 
235 
236  vtkGetVector3Macro(Size,double);
238 
240 
241  vtkSetVector3Macro(Origin,double);
242  // Return the origin (position of corner (0,0,0) ) of the root.
243  vtkGetVector3Macro(Origin,double);
245 
248  vtkHyperOctreeCursor *NewCellCursor();
249 
253  void SubdivideLeaf(vtkHyperOctreeCursor *leaf);
254 
259  void CollapseTerminalNode(vtkHyperOctreeCursor *node);
260 
263  virtual double *GetPoint(vtkIdType ptId);
264 
268  virtual void GetPoint(vtkIdType id, double x[3]);
269 
272  virtual vtkCell *GetCell(vtkIdType cellId);
273 
278  virtual void GetCell(vtkIdType cellId, vtkGenericCell *cell);
279 
280 
284  virtual int GetCellType(vtkIdType cellId);
285 
287 
290  virtual void GetCellPoints(vtkIdType cellId, vtkIdList *ptIds);
291  virtual void GetCellPoints(vtkIdType cellId, vtkIdType& npts,
292  vtkIdType* &pts);
294 
298  virtual void GetPointCells(vtkIdType ptId, vtkIdList *cellIds);
299 
300 
302 
306  virtual void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds,
307  vtkIdList *cellIds);
309 
310  virtual vtkIdType FindPoint(double x[3]);
311 
313 
321  virtual vtkIdType FindCell(double x[3], vtkCell *cell, vtkIdType cellId,
322  double tol2, int& subId, double pcoords[3],
323  double *weights);
325 
327 
332  virtual vtkIdType FindCell(double x[3], vtkCell *cell,
333  vtkGenericCell *gencell, vtkIdType cellId,
334  double tol2, int& subId, double pcoords[3],
335  double *weights);
337 
339  void Initialize();
340 
344  virtual int GetMaxCellSize();
345 
347 
348  void ShallowCopy(vtkDataObject *src);
349  void DeepCopy(vtkDataObject *src);
351 
353 
358  void GetPointsOnFace(vtkHyperOctreeCursor *sibling,
359  int face,
360  int level,
361  vtkHyperOctreePointsGrabber *grabber);
363 
365 
370  void GetPointsOnParentFaces(int faces[3],
371  int level,
372  vtkHyperOctreeCursor *cursor,
373  vtkHyperOctreePointsGrabber *grabber);
375 
377 
388  void GetPointsOnEdge(vtkHyperOctreeCursor *sibling,
389  int level,
390  int axis,
391  int k,
392  int j,
393  vtkHyperOctreePointsGrabber *grabber);
395 
397 
406  void GetPointsOnParentEdge(vtkHyperOctreeCursor *cursor,
407  int level,
408  int axis,
409  int k,
410  int j,
411  vtkHyperOctreePointsGrabber *grabber);
413 
415 
420  void GetPointsOnEdge2D(vtkHyperOctreeCursor *sibling,
421  int edge,
422  int level,
423  vtkHyperOctreePointsGrabber *grabber);
425 
427 
432  void GetPointsOnParentEdge2D(vtkHyperOctreeCursor *cursor,
433  int edge,
434  int level,
435  vtkHyperOctreePointsGrabber *grabber);
437 
440  vtkDataSetAttributes* GetLeafData();
441 
443 
444  void SetDualGridFlag(int flag);
445  vtkGetMacro(DualGridFlag,int);
447 
453  unsigned long GetActualMemorySize();
454 
455  //BTX
457 
458  static vtkHyperOctree* GetData(vtkInformation* info);
459  static vtkHyperOctree* GetData(vtkInformationVector* v, int i=0);
460  //ETX
462 
463 protected:
464  // Constructor with default bounds (0,1, 0,1, 0,1).
465  vtkHyperOctree();
466  ~vtkHyperOctree();
467 
468  void ComputeBounds();
469 
470  int Dimension; // 1, 2 or 3.
471 
472  double Size[3]; // size on each axis
473  double Origin[3]; // position of corner (0,0,0) of the root.
474 
475  vtkHyperOctreeInternal *CellTree;
476 
477  vtkHyperOctreeCursor *TmpChild; // to avoid allocation in the loop
478 
479  //BTX
481  //ETX
482 
483  // Initialize the arrays if necessary, then return it.
484  void UpdateDualArrays();
485  vtkPoints* GetLeafCenters();
486  vtkIdTypeArray* GetCornerLeafIds();
489 
490  void UpdateGridArrays();
491  vtkPoints* GetCornerPoints();
492  vtkIdTypeArray* GetLeafCornerIds();
495 
496  void DeleteInternalArrays();
497 
498  void TraverseDualRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
499  unsigned short *xyzIds, int level);
500  void TraverseGridRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
501  unsigned char* visited,
502  double* origin, double* size);
503  void EvaluateDualCorner(vtkHyperOctreeLightWeightCursor* neighborhood);
504  vtkIdType EvaluateGridCorner(int level,vtkHyperOctreeLightWeightCursor* neighborhood,
505  unsigned char* visited, int* cornerNeighborIds);
506 
507  // This is a table for traversing a neighborhood down an octree.
508  // 8 children x 27 cursors
509  // First three bits encode the child, rest encode the cursor id.
510  // 8xCursorId + childId.
511  // This will be shorter when we get rid of the 3x3x3 neighborhood.
512  // I was using unsigned char, but VS60 optimized build had a problem.
513  int NeighborhoodTraversalTable[216];
514  void GenerateGridNeighborhoodTraversalTable();
515  void GenerateDualNeighborhoodTraversalTable();
516 
517  // for the GetCell method
519  vtkPixel *Pixel;
521 
523  void BuildLinks();
524 
525  vtkIdType RecursiveFindPoint(double x[3],
527  double *origin, double *size);
528 
529  // This toggles the data set API between the leaf cells and
530  // the dual grid (leaves are points, corners are cells).
532 
533 private:
534  vtkHyperOctree(const vtkHyperOctree&); // Not implemented.
535  void operator=(const vtkHyperOctree&); // Not implemented.
536 };
537 
538 
539 //BTX
540 
542 {
543 public:
546 
547  void Initialize(vtkHyperOctree* tree);
548  void ToRoot();
549  void ToChild(int child);
550  unsigned short GetIsLeaf();
551  int GetLeafIndex() {return this->Index;} // Only valid for leaves.
552  vtkHyperOctree* GetTree() { return this->Tree; }
553  unsigned short GetLevel() {return this->Level;}
554 private:
555  vtkHyperOctree* Tree;
556  int Index;
557  unsigned short IsLeaf;
558  unsigned short Level;
559 };
560 
561 //ETX
562 
563 #endif
vtkVoxel * Voxel
virtual vtkIdType GetNumberOfCells()=0
virtual void GetPointCells(vtkIdType ptId, vtkIdList *cellIds)=0
vtkIdTypeArray * CornerLeafIds
unsigned long GetActualMemorySize()
vtkPoints * CornerPoints
virtual vtkIdType FindCell(double x[3], vtkCell *cell, vtkIdType cellId, double tol2, int &subId, double pcoords[3], double *weights)=0
Store vtkAlgorithm input/output information.
#define VTK_FILTERING_EXPORT
virtual vtkIdType GetNumberOfPoints()=0
abstract class to specify dataset behavior
Definition: vtkDataSet.h:58
vtkPoints * LeafCenters
virtual void ComputeBounds()
An object used by filters to store points computed on face or edge of an hyperoctant. It is an abstract class. vtkClipHyperOctree and vtkHyperOctreeCutter use vtkHyperOctreeClipCutPointsGrabber vtkHyperOctreeContourFilter use an internal one: vtkHyperOctreeContourFilterPointsGrabber.
helper class to generate triangulations
dynamic, self-adjusting array of vtkIdType
int vtkIdType
Definition: vtkType.h:255
A dataset structured as a tree where each node has exactly 2^n children.
static vtkDataSet * GetData(vtkInformation *info)
provides thread-safe access to cells
cell represents a 1D line
Definition: vtkLine.h:33
void PrintSelf(ostream &os, vtkIndent indent)
a cell that represents a 3D orthogonal parallelepiped
Definition: vtkVoxel.h:42
Key for double vector values.
a simple class to control print indentation
Definition: vtkIndent.h:37
virtual int GetMaxCellSize()=0
list of point or cell ids
Definition: vtkIdList.h:34
virtual void GetCellPoints(vtkIdType cellId, vtkIdList *ptIds)=0
Key for integer values in vtkInformation.
int GetDataObjectType()
Definition: vtkDataSet.h:265
a cell that represents an n-sided polygon
Definition: vtkPolygon.h:43
vtkCellLinks * Links
vtkPixel * Pixel
represent and manipulate attribute data in a dataset
virtual void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds, vtkIdList *cellIds)
void DeepCopy(vtkDataObject *src)
Objects that can traverse hyperoctree nodes.
vtkHyperOctreeInternal * CellTree
void Initialize()
virtual void CopyStructure(vtkDataSet *ds)=0
Store zero or more vtkInformation instances.
virtual double * GetPoint(vtkIdType ptId)=0
vtkIdTypeArray * LeafCornerIds
vtkHyperOctreeCursor * TmpChild
helper class to get VTK data object types as string and instantiate them
vtkIdType FindPoint(double x, double y, double z)
Definition: vtkDataSet.h:148
virtual vtkCell * GetCell(vtkIdType cellId)=0
represent and manipulate 3D points
Definition: vtkPoints.h:38
virtual int GetCellType(vtkIdType cellId)=0
void ShallowCopy(vtkDataObject *src)