1 /*========================================================================= 2 3 Program: Visualization Toolkit 4 Module: vtkHyperTreeGrid.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 =========================================================================*/ 15 // .NAME vtkHyperTreeGrid - A dataset containing a grid of vtkHyperTree instances 16 // arranged as a rectilinear grid. 17 // 18 // .SECTION Description 19 // An hypertree grid is a dataset containing a rectilinear grid of root nodes, 20 // each of which can be refined as a vtkHyperTree grid. This organization of the 21 // root nodes allows for the definition of tree-based AMR grids that do not have 22 // uniform geometry. 23 // Some filters can be applied on this dataset: contour, outline, geometry. 24 // 25 // .SECTION Caveats 26 // It is not a spatial search object. If you are looking for this kind of 27 // octree see vtkCellLocator instead. 28 // Extent support is not finished yet. 29 // 30 // .SECTION See Also 31 // vtkHyperTree vtkRectilinearGrid 32 // 33 // .SECTION Thanks 34 // This class was written by Philippe Pebay, Joachim Pouderoux and Charles Law, 35 // Kitware 2013 36 // This work was supported in part by Commissariat a l'Energie Atomique (CEA/DIF) 37 38 #ifndef vtkHyperTreeGrid_h 39 #define vtkHyperTreeGrid_h 40 41 #include "vtkCommonDataModelModule.h" // For export macro 42 #include "vtkDataSet.h" 43 #include <map> // STL header for dual point coordinates ajustment 44 45 class vtkHyperTreeCursor; 46 class vtkHyperTree; 47 48 class vtkBitArray; 49 class vtkCellLinks; 50 class vtkCollection; 51 class vtkDataArray; 52 class vtkDataSetAttributes; 53 class vtkIdTypeArray; 54 class vtkLine; 55 class vtkPixel; 56 class vtkPoints; 57 class vtkVoxel; 58 59 class VTKCOMMONDATAMODEL_EXPORT vtkHyperTreeGrid : public vtkDataSet 60 { 61 public: 62 //BTX 63 class vtkHyperTreeSimpleCursor; 64 class vtkHyperTreeIterator; 65 struct vtkHyperTreeGridSuperCursor; 66 //ETX 67 68 static vtkInformationIntegerKey* LEVELS(); 69 static vtkInformationIntegerKey* DIMENSION(); 70 static vtkInformationDoubleVectorKey* SIZES(); 71 static vtkHyperTreeGrid* New(); 72 73 vtkTypeMacro(vtkHyperTreeGrid, vtkDataSet); 74 void PrintSelf( ostream&, vtkIndent ); 75 76 // Description: 77 // Return what type of dataset this is. 78 int GetDataObjectType(); 79 80 // Description: 81 // Copy the internal geometric and topological structure of a 82 // vtkHyperTreeGrid object. 83 void CopyStructure( vtkDataSet* ); 84 85 // Description: 86 // Set/Get sizes of this rectilinear grid dataset 87 void SetGridSize( unsigned int[3] ); 88 void SetGridSize( unsigned int i, unsigned int j, unsigned int k ); 89 vtkGetVector3Macro(GridSize, unsigned int); 90 91 // Description: 92 // Set/Get extent of this rectilinear grid dataset 93 void SetGridExtent(int extent[6]); 94 void SetGridExtent(int iMin, int iMax, int jMin, int jMax, 95 int kMin, int kMax); 96 97 // Description: 98 // Specify whether indexing mode of grid root cells must be transposed to 99 // x-axis first, z-axis last, instead of the default z-axis first, k-axis last 100 vtkSetMacro(TransposedRootIndexing, bool); 101 vtkGetMacro(TransposedRootIndexing, bool); SetIndexingModeToKJI()102 void SetIndexingModeToKJI() 103 { this->SetTransposedRootIndexing( false ); } SetIndexingModeToIJK()104 void SetIndexingModeToIJK() 105 { this->SetTransposedRootIndexing( true ); } 106 107 // Description: 108 // Set/Get the subdivision factor in the grid refinement scheme 109 // NB: Can only be 2 or 3 110 void SetBranchFactor( unsigned int ); 111 vtkGetMacro(BranchFactor, unsigned int); 112 113 // Description: 114 // Set/Get the dimensionality of the grid 115 // NB: Can only be 1, 2 or 3 116 void SetDimension( unsigned int ); 117 vtkGetMacro(Dimension, unsigned int); 118 119 // Description: 120 // Return the number of cells in the dual grid. 121 vtkIdType GetNumberOfCells(); 122 123 // Description: 124 // Return the number of points in the dual grid. 125 vtkIdType GetNumberOfPoints(); 126 127 // Description: 128 // Get the number of leaves in the primal tree grid. 129 vtkIdType GetNumberOfLeaves(); 130 131 // Description: 132 // Return the number of levels in an individual (primal) tree 133 vtkIdType GetNumberOfLevels( vtkIdType ); 134 135 // Description: 136 // Return the number of trees in the level 0 grid. 137 vtkIdType GetNumberOfTrees(); 138 139 // Description: 140 // Specify the grid coordinates in the x-direction. 141 void SetXCoordinates( vtkDataArray* ); 142 vtkGetObjectMacro(XCoordinates, vtkDataArray); 143 144 // Description: 145 // Specify the grid coordinates in the y-direction. 146 void SetYCoordinates( vtkDataArray* ); 147 vtkGetObjectMacro(YCoordinates, vtkDataArray); 148 149 // Description: 150 // Specify the grid coordinates in the z-direction. 151 void SetZCoordinates( vtkDataArray* ); 152 vtkGetObjectMacro(ZCoordinates, vtkDataArray); 153 154 // Description: 155 // Specify the blanking mask of primal leaf cells 156 void SetMaterialMask( vtkBitArray* ); 157 vtkGetObjectMacro(MaterialMask, vtkBitArray); 158 159 // Description: 160 // Specify the visibility mask of primal leaf cells 161 virtual void SetMaterialMaskIndex( vtkIdTypeArray* ); 162 vtkGetObjectMacro(MaterialMaskIndex, vtkIdTypeArray); 163 164 // Description: 165 // This method must be called once the tree settings change 166 virtual void GenerateTrees(); 167 168 // Description: 169 // Create a new cursor: an object that can traverse 170 // the cells of an individual hyper tree. 171 // \post result_exists: result!=0 172 vtkHyperTreeCursor* NewCursor( vtkIdType ); 173 174 // Description: 175 // Subdivide node pointed by cursor, only if its a leaf. 176 // At the end, cursor points on the node that used to be leaf. 177 // \pre leaf_exists: leaf!=0 178 // \pre is_a_leaf: leaf->CurrentIsLeaf() 179 void SubdivideLeaf( vtkHyperTreeCursor*, vtkIdType ); 180 181 // Description: 182 // This method should be avoided in favor of cell/point iterators. 183 // Random access to points requires that arrays are created explicitly. 184 // Get point coordinates with ptId such that: 0 <= ptId < NumberOfPoints. 185 // THIS METHOD IS NOT THREAD SAFE. 186 virtual double* GetPoint( vtkIdType ); 187 188 // Description: 189 // This method should be avoided in favor of cell/point iterators. 190 // Random access to points requires that arrays are created explicitly. 191 // Copy point coordinates into user provided array x[3] for specified 192 // point id. 193 // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND 194 // THE DATASET IS NOT MODIFIED 195 virtual void GetPoint( vtkIdType, double[3] ); 196 197 // Description: 198 // This method should be avoided in favor of cell/point iterators. 199 // Random access to cells requires that connectivity arrays are created explicitly. 200 // Get cell with cellId such that: 0 <= cellId < NumberOfCells. 201 // THIS METHOD IS NOT THREAD SAFE. 202 virtual vtkCell* GetCell( vtkIdType ); 203 204 // Description: 205 // This method should be avoided in favor of cell/point iterators. 206 // Random access to cells requires that connectivity arrays are created explicitly. 207 // Get cell with cellId such that: 0 <= cellId < NumberOfCells. 208 // This is a thread-safe alternative to the previous GetCell() 209 // method. 210 // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND 211 // THE DATASET IS NOT MODIFIED 212 virtual void GetCell( vtkIdType, vtkGenericCell* ); 213 214 // Description: 215 // All cell types are 2: quadrilaters,3d: hexahedrons. They may be degenerate though. 216 // Get type of cell with cellId such that: 0 <= cellId < NumberOfCells. 217 // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND 218 // THE DATASET IS NOT MODIFIED 219 virtual int GetCellType( vtkIdType ); 220 221 // Description: 222 // This method should be avoided in favor of cell/point iterators. 223 // Random access to cells requires that connectivity arrays are created explicitly. 224 // Topological inquiry to get points defining cell. 225 // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND 226 // THE DATASET IS NOT MODIFIED 227 virtual void GetCellPoints( vtkIdType, vtkIdList* ); 228 229 // Description: 230 // Return a pointer to a list of point ids defining cell. 231 // NB: More efficient than alternative method. 232 virtual void GetCellPoints( vtkIdType, vtkIdType&, vtkIdType*& ); 233 234 // Description: 235 // This method should be avoided in favor of cell/point iterators. 236 // Random access to cells requires that connectivity arrays are created explicitly. 237 // Topological inquiry to get cells using point. 238 // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND 239 // THE DATASET IS NOT MODIFIED 240 virtual void GetPointCells( vtkIdType, vtkIdList* ); 241 242 // Description: 243 // This method should be avoided in favor of cell/point iterators. 244 // Random access to cells requires that connectivity arrays are created explicitly. 245 // Topological inquiry to get all cells using list of points exclusive of 246 // cell specified (e.g., cellId). Note that the list consists of only 247 // cells that use ALL the points provided. 248 // This is exactly the same as GetCellNeighbors in unstructured grid. 249 // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND 250 // THE DATASET IS NOT MODIFIED 251 virtual void GetCellNeighbors( vtkIdType, vtkIdList*, vtkIdList* ); 252 253 // Description: 254 // Find cell to which this point belongs, or at least closest one, 255 // even if the point is outside the grid. 256 // Since dual points are leaves, use the structure of the Tree instead 257 // of a point locator. 258 virtual vtkIdType FindPoint( double x[3] ); 259 260 // Description: 261 // Locate cell based on global coordinate x and tolerance 262 // squared. If cell and cellId is non-NULL, then search starts from 263 // this cell and looks at immediate neighbors. Returns cellId >= 0 264 // if inside, < 0 otherwise. The parametric coordinates are 265 // provided in pcoords[3]. The interpolation weights are returned in 266 // weights[]. (The number of weights is equal to the number of 267 // points in the found cell). Tolerance is used to control how close 268 // the point is to be considered "in" the cell. 269 // NB: There is actually no need for a starting cell, just use the 270 // point, as the tree structure is efficient enough. 271 // THIS METHOD IS NOT THREAD SAFE. 272 virtual vtkIdType FindCell( double x[3], vtkCell *cell, vtkIdType cellId, 273 double tol2, int& subId, double pcoords[3], 274 double *weights ); 275 276 // Description: 277 // This is a version of the above method that can be used with 278 // multithreaded applications. A vtkGenericCell must be passed in 279 // to be used in internal calls that might be made to GetCell() 280 // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND 281 // THE DATASET IS NOT MODIFIED 282 virtual vtkIdType FindCell( double x[3], vtkCell *cell, 283 vtkGenericCell *gencell, vtkIdType cellId, 284 double tol2, int& subId, double pcoords[3], 285 double *weights ); 286 287 // Description: 288 // Restore data object to initial state, 289 // THIS METHOD IS NOT THREAD SAFE. 290 void Initialize(); 291 292 // Description: 293 // Initialize an iterator to browse level 0 trees. 294 void InitializeTreeIterator( vtkHyperTreeIterator& ); 295 296 // Description: 297 // Convenience method returns largest cell size in dataset. This is generally 298 // used to allocate memory for supporting data structures. 299 // This is the number of points of a cell. 300 // THIS METHOD IS THREAD SAFE 301 virtual int GetMaxCellSize(); 302 303 // Description: 304 // Shallow and Deep copy. 305 void ShallowCopy( vtkDataObject* ); 306 void DeepCopy( vtkDataObject* ); 307 308 // Description: 309 // Structured extent. The extent type is a 3D extent GetExtentType()310 int GetExtentType() { return VTK_3D_EXTENT; } 311 312 // Description: 313 // Return the actual size of the data in kilobytes. This number 314 // is valid only after the pipeline has updated. The memory size 315 // returned is guaranteed to be greater than or equal to the 316 // memory required to represent the data (e.g., extra space in 317 // arrays, etc. are not included in the return value). THIS METHOD 318 // IS THREAD SAFE. 319 unsigned long GetActualMemorySize(); 320 321 // Description: 322 // Generate the table before calling InitializeSuperCursorChild. 323 void GenerateSuperCursorTraversalTable(); 324 325 //BTX 326 #ifndef __WRAP__ 327 // Description: 328 // Initialize a super cursor to point to one of the root trees 329 // in the grid. The super cursor points to a node in a tree and 330 // also keeps pointers to the 26 neighbors of said node. 331 void InitializeSuperCursor( vtkHyperTreeGridSuperCursor*, 332 unsigned int, 333 unsigned int, 334 unsigned int, 335 vtkIdType ); 336 void InitializeSuperCursor( vtkHyperTreeGridSuperCursor*, 337 vtkIdType ); 338 // Description: 339 // Initialize a cursor to point to a child of an existing super cursor. 340 // This will not work in place. 341 void InitializeSuperCursorChild( vtkHyperTreeGridSuperCursor* parent, 342 vtkHyperTreeGridSuperCursor* child, 343 unsigned int childIdx ); 344 #endif 345 //ETX 346 347 // Description: 348 // The number of children each node can have. 349 vtkGetMacro(NumberOfChildren, unsigned int); 350 351 // Description: 352 // Convert a level 0 index to its ijk coordinates according the grid size. 353 void GetLevelZeroCoordsFromIndex( vtkIdType index, 354 unsigned int &i, 355 unsigned int &j, 356 unsigned int &k ); 357 358 protected: 359 // Constructor with default bounds (0,1, 0,1, 0,1). 360 vtkHyperTreeGrid(); 361 ~vtkHyperTreeGrid(); 362 363 void ComputeBounds(); 364 365 void GetCell( vtkIdType, vtkCell* ); 366 367 void ComputeDualGrid(); 368 vtkPoints* GetPoints(); 369 vtkIdTypeArray* GetConnectivity(); 370 371 unsigned int Dimension; // 1, 2 or 3. 372 unsigned int GridSize[3]; 373 int Extent[6]; 374 unsigned int BranchFactor; 375 unsigned int NumberOfChildren; 376 bool TransposedRootIndexing; 377 378 vtkBitArray* MaterialMask; 379 vtkIdTypeArray* MaterialMaskIndex; 380 381 vtkDataArray* XCoordinates; 382 vtkDataArray* YCoordinates; 383 vtkDataArray* ZCoordinates; 384 385 std::map<vtkIdType, vtkHyperTree*> HyperTrees; 386 387 vtkPoints* Points; 388 vtkIdTypeArray* Connectivity; 389 std::map<vtkIdType, bool> PointShifted; 390 std::map<vtkIdType, double> PointShifts[3]; 391 std::map<vtkIdType, double> ReductionFactors; 392 393 void DeleteInternalArrays(); 394 void DeleteTrees(); 395 396 //BTX 397 #if !defined(__WRAP__) && !defined(__WRAP_GCCXML__) 398 void TraverseDualRecursively( vtkHyperTreeGridSuperCursor*, unsigned int ); 399 400 void TraverseDualMaskedLeaf( vtkHyperTreeGridSuperCursor* ); 401 402 void TraverseDualLeaf( vtkHyperTreeGridSuperCursor* ); 403 404 void EvaluateDualCorner( vtkHyperTreeSimpleCursor* ); 405 #endif 406 //ETX 407 408 // Used to advance the super cursor; One Entry per cursor node. 409 // Private. 410 struct vtkSuperCursorEntry 411 { 412 // For the new node, start with the node in super cursor as parent. 413 unsigned char Parent; 414 // Traverse to this child. 415 unsigned char Child; 416 }; 417 418 // Generalizing for 27 tree. Cannot use 3 bits to encode the child to move to. 419 // Input: root in supercursor(3x3x3=27), child(3x3x3=27) 420 // Output: root, child 421 // It is easier to abstract dimensions when we use a single array. 422 vtkSuperCursorEntry SuperCursorTraversalTable[27*27]; 423 424 // for the GetCell method 425 vtkLine* Line; 426 vtkPixel* Pixel; 427 vtkVoxel* Voxel; 428 429 // I would like to get rid of this. 430 // Is it a part of the vtkDataSet API? 431 vtkCellLinks* Links; 432 void BuildLinks(); 433 434 //BTX 435 vtkIdType RecursiveFindPoint( double x[3], 436 vtkHyperTreeSimpleCursor* cursor, 437 double* origin, double* size); 438 //ETX 439 440 public: 441 442 //BTX 443 // A simplified hyper tree cursor, to be used by the hyper tree 444 // grid supercursor. 445 class VTKCOMMONDATAMODEL_EXPORT vtkHyperTreeSimpleCursor 446 { 447 public: 448 vtkHyperTreeSimpleCursor(); 449 450 void Clear(); 451 void Initialize( vtkHyperTreeGrid*, vtkIdType, int[3] ); 452 void ToRoot(); 453 void ToChild( int ); 454 bool IsLeaf(); GetTree()455 vtkHyperTree* GetTree() { return this->Tree; } GetLeafIndex()456 vtkIdType GetLeafIndex() { return this->Index; } // Only valid for leaves. 457 vtkIdType GetGlobalNodeIndex(); GetLevel()458 unsigned short GetLevel() { return this->Level; } 459 460 private: 461 vtkHyperTree* Tree; 462 vtkIdType Index; 463 unsigned short Level; 464 bool Leaf; 465 }; 466 467 class VTKCOMMONDATAMODEL_EXPORT vtkHyperTreeIterator 468 { 469 public: vtkHyperTreeIterator()470 vtkHyperTreeIterator() {} 471 472 // Description: 473 // Initialize the iterator on the tree set of the given HyperTreeGrid. 474 void Initialize( vtkHyperTreeGrid* ); 475 476 // Description: 477 // Get the next tree and set its index then increment the iterator. 478 // Returns 0 at the end. 479 vtkHyperTree* GetNextTree( vtkIdType &index ); 480 481 // Description: 482 // Get the next tree and set its index then increment the iterator. 483 // Returns 0 at the end. 484 vtkHyperTree* GetNextTree(); 485 486 protected: 487 std::map<vtkIdType, vtkHyperTree*>::iterator Iterator; 488 vtkHyperTreeGrid* Tree; 489 }; 490 491 // Public structure filters use to move around the tree. 492 // The super cursor keeps neighbor cells so filters can 493 // easily access neighbor to leaves. 494 // The super cursor is 'const'. Methods in vtkHyperTreeGrid 495 // initialize and compute children for moving toward leaves. 496 struct vtkHyperTreeGridSuperCursor 497 { 498 double Origin[3]; 499 double Size[3]; 500 int NumberOfCursors; 501 int MiddleCursorId; 502 vtkHyperTreeSimpleCursor Cursors[3*3*3]; 503 GetCursorvtkHyperTreeGridSuperCursor504 vtkHyperTreeSimpleCursor* GetCursor( int idx ) 505 { 506 return this->Cursors + this->MiddleCursorId + idx; 507 } 508 }; 509 //ETX 510 511 private: 512 vtkHyperTreeGrid(const vtkHyperTreeGrid&); // Not implemented. 513 void operator=(const vtkHyperTreeGrid&); // Not implemented. 514 }; 515 516 #endif 517