VTK
|
00001 /*========================================================================= 00002 00003 Program: Visualization Toolkit 00004 Module: $RCSfile: vtkHyperOctree.h,v $ 00005 00006 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen 00007 All rights reserved. 00008 See Copyright.txt or http://www.kitware.com/Copyright.htm for details. 00009 00010 This software is distributed WITHOUT ANY WARRANTY; without even 00011 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 00012 PURPOSE. See the above copyright notice for more information. 00013 00014 =========================================================================*/ 00114 #ifndef __vtkHyperOctree_h 00115 #define __vtkHyperOctree_h 00116 00117 #include "vtkDataSet.h" 00118 00119 class vtkHyperOctreeLightWeightCursor; 00120 class vtkHyperOctreeCursor; 00121 class vtkHyperOctreeInternal; 00122 class vtkHyperOctreePointsGrabber; 00123 00124 class vtkHyperOctreeIdSet; // Pimpl idiom 00125 class vtkPolygon; 00126 class vtkIdTypeArray; 00127 class vtkPoints; 00128 class vtkPointLocator; 00129 class vtkOrderedTriangulator; 00130 class vtkDataSetAttributes; 00131 00132 class vtkLine; 00133 class vtkPixel; 00134 class vtkVoxel; 00135 class vtkCellLinks; 00136 00137 class VTK_FILTERING_EXPORT vtkHyperOctree : public vtkDataSet 00138 { 00139 public: 00140 static vtkInformationIntegerKey* LEVELS(); 00141 static vtkInformationIntegerKey* DIMENSION(); 00142 static vtkInformationDoubleVectorKey* SIZES(); 00143 static vtkHyperOctree *New(); 00144 00145 vtkTypeRevisionMacro(vtkHyperOctree,vtkDataSet); 00146 void PrintSelf(ostream& os, vtkIndent indent); 00147 00149 int GetDataObjectType(); 00150 00153 void CopyStructure(vtkDataSet *ds); 00154 00155 // Return the node describes by the path from the root. 00156 // Path is a sequence of number between 0 and 7. 00157 // \pre path_exists: path!=0 00158 // \pre node_exists: IsANode(path) 00159 // vtkOctree *GetNode(vtkPath *path); 00160 00161 // Status 00162 // Return the dimension of the tree (1D:binary tree(2 children), 2D:quadtree(4 children), 00163 // 3D:octree (8 children)) 00164 // \post valid_result: result>=1 && result<=3 00165 int GetDimension(); 00166 00167 // Set the dimension of the tree with `dim'. See GetDimension() for details. 00168 // \pre valid_dim: dim>=1 && dim<=3 00169 // \post dimension_is_set: GetDimension()==dim 00170 void SetDimension(int dim); 00171 00172 // Return if the node for the given path exists or not. 00173 // \pre path_exists: path!=0 00174 // int IsANode(vtkPath *path); 00175 00176 // Return if the node for the given path is a leaf or not. 00177 // \pre path_exists: path!=0 00178 // \pre node_exists: IsANode(path) 00179 // int IsALeaf(vtkPath *path); 00180 00181 // Measurement: topology 00182 00185 vtkIdType GetNumberOfCells(); 00186 00188 vtkIdType GetNumberOfLeaves(); 00189 00192 vtkIdType GetNumberOfPoints(); 00193 00200 vtkIdType GetMaxNumberOfPoints(int level); 00201 00212 vtkIdType GetMaxNumberOfPointsOnBoundary(int level); 00213 00218 vtkIdType GetMaxNumberOfCellsOnBoundary(int level); 00219 00222 vtkIdType GetNumberOfLevels(); 00223 00224 // Measurement: geometry 00225 00227 00228 vtkSetVector3Macro(Size,double); 00230 00232 00233 vtkGetVector3Macro(Size,double); 00235 00237 00238 vtkSetVector3Macro(Origin,double); 00239 // Return the origin (position of corner (0,0,0) ) of the root. 00240 vtkGetVector3Macro(Origin,double); 00242 00245 vtkHyperOctreeCursor *NewCellCursor(); 00246 00250 void SubdivideLeaf(vtkHyperOctreeCursor *leaf); 00251 00256 void CollapseTerminalNode(vtkHyperOctreeCursor *node); 00257 00260 virtual double *GetPoint(vtkIdType ptId); 00261 00265 virtual void GetPoint(vtkIdType id, double x[3]); 00266 00269 virtual vtkCell *GetCell(vtkIdType cellId); 00270 00275 virtual void GetCell(vtkIdType cellId, vtkGenericCell *cell); 00276 00277 00281 virtual int GetCellType(vtkIdType cellId); 00282 00284 00287 virtual void GetCellPoints(vtkIdType cellId, vtkIdList *ptIds); 00288 virtual void GetCellPoints(vtkIdType cellId, vtkIdType& npts, 00289 vtkIdType* &pts); 00291 00295 virtual void GetPointCells(vtkIdType ptId, vtkIdList *cellIds); 00296 00297 00299 00303 virtual void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds, 00304 vtkIdList *cellIds); 00306 00307 virtual vtkIdType FindPoint(double x[3]); 00308 00310 00318 virtual vtkIdType FindCell(double x[3], vtkCell *cell, vtkIdType cellId, 00319 double tol2, int& subId, double pcoords[3], 00320 double *weights); 00322 00324 00329 virtual vtkIdType FindCell(double x[3], vtkCell *cell, 00330 vtkGenericCell *gencell, vtkIdType cellId, 00331 double tol2, int& subId, double pcoords[3], 00332 double *weights); 00334 00336 void Initialize(); 00337 00341 virtual int GetMaxCellSize(); 00342 00344 00345 void ShallowCopy(vtkDataObject *src); 00346 void DeepCopy(vtkDataObject *src); 00348 00350 00355 void GetPointsOnFace(vtkHyperOctreeCursor *sibling, 00356 int face, 00357 int level, 00358 vtkHyperOctreePointsGrabber *grabber); 00360 00362 00367 void GetPointsOnParentFaces(int faces[3], 00368 int level, 00369 vtkHyperOctreeCursor *cursor, 00370 vtkHyperOctreePointsGrabber *grabber); 00372 00374 00385 void GetPointsOnEdge(vtkHyperOctreeCursor *sibling, 00386 int level, 00387 int axis, 00388 int k, 00389 int j, 00390 vtkHyperOctreePointsGrabber *grabber); 00392 00394 00403 void GetPointsOnParentEdge(vtkHyperOctreeCursor *cursor, 00404 int level, 00405 int axis, 00406 int k, 00407 int j, 00408 vtkHyperOctreePointsGrabber *grabber); 00410 00412 00417 void GetPointsOnEdge2D(vtkHyperOctreeCursor *sibling, 00418 int edge, 00419 int level, 00420 vtkHyperOctreePointsGrabber *grabber); 00422 00424 00429 void GetPointsOnParentEdge2D(vtkHyperOctreeCursor *cursor, 00430 int edge, 00431 int level, 00432 vtkHyperOctreePointsGrabber *grabber); 00434 00437 vtkDataSetAttributes* GetLeafData(); 00438 00440 00441 void SetDualGridFlag(int flag); 00442 vtkGetMacro(DualGridFlag,int); 00444 00450 unsigned long GetActualMemorySize(); 00451 00452 //BTX 00454 00455 static vtkHyperOctree* GetData(vtkInformation* info); 00456 static vtkHyperOctree* GetData(vtkInformationVector* v, int i=0); 00457 //ETX 00459 00460 protected: 00461 // Constructor with default bounds (0,1, 0,1, 0,1). 00462 vtkHyperOctree(); 00463 ~vtkHyperOctree(); 00464 00465 void ComputeBounds(); 00466 00467 int Dimension; // 1, 2 or 3. 00468 00469 double Size[3]; // size on each axis 00470 double Origin[3]; // position of corner (0,0,0) of the root. 00471 00472 vtkHyperOctreeInternal *CellTree; 00473 00474 vtkHyperOctreeCursor *TmpChild; // to avoid allocation in the loop 00475 00476 //BTX 00477 friend class vtkHyperOctreeLightWeightCursor; 00478 //ETX 00479 00480 // Initialize the arrays if necessary, then return it. 00481 void UpdateDualArrays(); 00482 vtkPoints* GetLeafCenters(); 00483 vtkIdTypeArray* GetCornerLeafIds(); 00484 vtkPoints *LeafCenters; 00485 vtkIdTypeArray *CornerLeafIds; 00486 00487 void UpdateGridArrays(); 00488 vtkPoints* GetCornerPoints(); 00489 vtkIdTypeArray* GetLeafCornerIds(); 00490 vtkPoints* CornerPoints; 00491 vtkIdTypeArray* LeafCornerIds; 00492 00493 void DeleteInternalArrays(); 00494 00495 void TraverseDualRecursively(vtkHyperOctreeLightWeightCursor* neighborhood, 00496 unsigned short *xyzIds, int level); 00497 void TraverseGridRecursively(vtkHyperOctreeLightWeightCursor* neighborhood, 00498 unsigned char* visited, 00499 double* origin, double* size); 00500 void EvaluateDualCorner(vtkHyperOctreeLightWeightCursor* neighborhood); 00501 vtkIdType EvaluateGridCorner(int level,vtkHyperOctreeLightWeightCursor* neighborhood, 00502 unsigned char* visited, int* cornerNeighborIds); 00503 00504 // This is a table for traversing a neighborhood down an octree. 00505 // 8 children x 27 cursors 00506 // First three bits encode the child, rest encode the cursor id. 00507 // 8xCursorId + childId. 00508 // This will be shorter when we get rid of the 3x3x3 neighborhood. 00509 // I was using unsigned char, but VS60 optimized build had a problem. 00510 int NeighborhoodTraversalTable[216]; 00511 void GenerateGridNeighborhoodTraversalTable(); 00512 void GenerateDualNeighborhoodTraversalTable(); 00513 00514 // for the GetCell method 00515 vtkLine *Line; 00516 vtkPixel *Pixel; 00517 vtkVoxel *Voxel; 00518 00519 vtkCellLinks* Links; 00520 void BuildLinks(); 00521 00522 vtkIdType RecursiveFindPoint(double x[3], 00523 vtkHyperOctreeLightWeightCursor* cursor, 00524 double *origin, double *size); 00525 00526 // This toggles the data set API between the leaf cells and 00527 // the dual grid (leaves are points, corners are cells). 00528 int DualGridFlag; 00529 00530 private: 00531 vtkHyperOctree(const vtkHyperOctree&); // Not implemented. 00532 void operator=(const vtkHyperOctree&); // Not implemented. 00533 }; 00534 00535 00536 //BTX 00537 00538 class VTK_FILTERING_EXPORT vtkHyperOctreeLightWeightCursor 00539 { 00540 public: 00541 vtkHyperOctreeLightWeightCursor(); 00542 ~vtkHyperOctreeLightWeightCursor(); 00543 00544 void Initialize(vtkHyperOctree* tree); 00545 void ToRoot(); 00546 void ToChild(int child); 00547 unsigned short GetIsLeaf(); 00548 int GetLeafIndex() {return this->Index;} // Only valid for leaves. 00549 vtkHyperOctree* GetTree() { return this->Tree; } 00550 unsigned short GetLevel() {return this->Level;} 00551 private: 00552 vtkHyperOctree* Tree; 00553 int Index; 00554 unsigned short IsLeaf; 00555 unsigned short Level; 00556 }; 00557 00558 //ETX 00559 00560 #endif