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
127class vtkHyperOctreeInternal;
129
130class vtkHyperOctreeIdSet; // Pimpl idiom
131class vtkPolygon;
132class vtkIdTypeArray;
133class vtkPoints;
134class vtkPointLocator;
137
138class vtkLine;
139class vtkPixel;
140class vtkVoxel;
141class vtkCellLinks;
142
143class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctree : public vtkDataSet
144{
145public:
150
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,
429
438 void GetPointsOnParentFaces(int faces[3],
439 int level,
440 vtkHyperOctreeCursor *cursor,
442
457 void GetPointsOnEdge(vtkHyperOctreeCursor *sibling,
458 int level,
459 int axis,
460 int k,
461 int j,
463
478 void GetPointsOnParentEdge(vtkHyperOctreeCursor *cursor,
479 int level,
480 int axis,
481 int k,
482 int j,
484
493 void GetPointsOnEdge2D(vtkHyperOctreeCursor *sibling,
494 int edge,
495 int level,
497
506 void GetPointsOnParentEdge2D(vtkHyperOctreeCursor *cursor,
507 int edge,
508 int level,
510
515 vtkDataSetAttributes* GetLeafData();
516
518
521 void SetDualGridFlag(int flag);
522 vtkGetMacro(DualGridFlag,int);
524
533 unsigned long GetActualMemorySize() VTK_OVERRIDE;
534
536
540 static vtkHyperOctree* GetData(vtkInformationVector* v, int i=0);
542
543protected:
544 // Constructor with default bounds (0,1, 0,1, 0,1).
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
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
611private:
612 vtkHyperOctree(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
613 void operator=(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
614};
615
616class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctreeLightWeightCursor
617{
618public:
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;}
627private:
628 vtkHyperOctree* Tree;
629 int Index;
630 unsigned short IsLeaf;
631 unsigned short Level;
632};
633
634#endif
void GetPoint(const int i, const int j, const int k, double pnt[3])
abstract class to specify cell behavior
Definition: vtkCell.h:60
general representation of visualization data
Definition: vtkDataObject.h:65
represent and manipulate attribute data in a dataset
abstract class to specify dataset behavior
Definition: vtkDataSet.h:63
provides thread-safe access to cells
Objects that can traverse hyperoctree nodes.
void Initialize(vtkHyperOctree *tree)
An object used by filters to store points computed on face or edge of an hyperoctant.
A dataset structured as a tree where each node has exactly 2^n children.
static vtkHyperOctree * New()
static vtkInformationIntegerKey * DIMENSION()
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
static vtkInformationIntegerKey * LEVELS()
int GetDataObjectType() override
Return what type of dataset this is.
static vtkInformationDoubleVectorKey * SIZES()
list of point or cell ids
Definition: vtkIdList.h:37
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition: vtkIndent.h:40
Key for integer values in vtkInformation.
Store zero or more vtkInformation instances.
Store vtkAlgorithm input/output information.
cell represents a 1D line
Definition: vtkLine.h:36
helper class to generate triangulations
a cell that represents an orthogonal quadrilateral
Definition: vtkPixel.h:41
quickly locate points in 3-space
represent and manipulate 3D points
Definition: vtkPoints.h:40
a cell that represents an n-sided polygon
Definition: vtkPolygon.h:46
a cell that represents a 3D orthogonal parallelepiped
Definition: vtkVoxel.h:45
@ info
Definition: vtkX3D.h:376
@ level
Definition: vtkX3D.h:395
@ size
Definition: vtkX3D.h:253
void DeepCopy(vtkPistonReference *self, vtkPistonReference *other)
int vtkIdType
Definition: vtkType.h:287