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;
126 class vtkHyperOctreePointsGrabber;
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
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
quickly locate points in 3-space
Store vtkAlgorithm input/output information.
#define VTK_FILTERING_EXPORT
virtual vtkIdType GetNumberOfPoints()=0
abstract class to specify dataset behavior
Definition: vtkDataSet.h:58
a cell that represents an orthogonal quadrilateral
Definition: vtkPixel.h:38
vtkPoints * LeafCenters
virtual void ComputeBounds()
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
abstract class to specify cell behavior
Definition: vtkCell.h:57
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)