VTK
vtkKdTree.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkKdTree.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 /*----------------------------------------------------------------------------
16  Copyright (c) Sandia Corporation
17  See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
18 ----------------------------------------------------------------------------*/
19 
56 #ifndef vtkKdTree_h
57 #define vtkKdTree_h
58 
59 #include "vtkCommonDataModelModule.h" // For export macro
60 #include "vtkLocator.h"
61 
62 class vtkTimerLog;
63 class vtkIdList;
64 class vtkIdTypeArray;
65 class vtkIntArray;
66 class vtkPointSet;
67 class vtkPoints;
68 class vtkCellArray;
69 class vtkCell;
70 class vtkKdNode;
71 class vtkBSPCuts;
74 
75 class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
76 {
77 public:
78  vtkTypeMacro(vtkKdTree, vtkLocator);
79  void PrintSelf(ostream& os, vtkIndent indent) override;
80 
81  static vtkKdTree *New();
82 
84 
87  vtkBooleanMacro(Timing, vtkTypeBool);
88  vtkSetMacro(Timing, vtkTypeBool);
89  vtkGetMacro(Timing, vtkTypeBool);
91 
93 
96  vtkSetMacro(MinCells, int);
97  vtkGetMacro(MinCells, int);
99 
107  vtkGetMacro(NumberOfRegionsOrLess, int);
108  vtkSetMacro(NumberOfRegionsOrLess, int);
109 
117  vtkGetMacro(NumberOfRegionsOrMore, int);
118  vtkSetMacro(NumberOfRegionsOrMore, int);
119 
127  vtkGetMacro(FudgeFactor, double);
128  vtkSetMacro(FudgeFactor, double);
129 
135  vtkGetObjectMacro(Cuts, vtkBSPCuts);
136 
143  void SetCuts(vtkBSPCuts *cuts);
144 
148  void OmitXPartitioning();
149 
153  void OmitYPartitioning();
154 
158  void OmitZPartitioning();
159 
163  void OmitXYPartitioning();
164 
168  void OmitYZPartitioning();
169 
173  void OmitZXPartitioning();
174 
178  void OmitNoPartitioning();
179 
194  void SetDataSet(vtkDataSet *set) override;
195 
200  virtual void AddDataSet(vtkDataSet *set);
201 
203 
206  virtual void RemoveDataSet(int index);
207  virtual void RemoveDataSet(vtkDataSet *set);
208  virtual void RemoveAllDataSets();
210 
214  int GetNumberOfDataSets();
215 
225  vtkDataSet *GetDataSet(int n);
226 
231  vtkDataSet *GetDataSet() override { return this->GetDataSet(0); }
232 
234 
237  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
239 
244  int GetDataSetIndex(vtkDataSet *set);
245 
250  void GetBounds(double *bounds);
251 
260  void SetNewBounds(double *bounds);
261 
263 
266  vtkGetMacro(NumberOfRegions, int);
268 
272  void GetRegionBounds(int regionID, double bounds[6]);
273 
277  void GetRegionDataBounds(int regionID, double bounds[6]);
278 
280 
283  void PrintTree();
284  void PrintVerboseTree();
286 
290  void PrintRegion(int id);
291 
304  void CreateCellLists(int dataSetIndex, int *regionReqList,
305  int reqListSize);
306  void CreateCellLists(vtkDataSet *set, int *regionReqList,
307  int reqListSize);
308  void CreateCellLists(int *regionReqList, int listSize);
309  void CreateCellLists();
310 
312 
319  vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
320  vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
321  vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
323 
327  void DeleteCellLists();
328 
333  vtkIdList *GetCellList(int regionID);
334 
345  vtkIdList *GetBoundaryCellList(int regionID);
346 
348 
368  vtkIdType GetCellLists(vtkIntArray *regions, int set,
369  vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
370  vtkIdType GetCellLists(vtkIntArray *regions, vtkDataSet *set,
371  vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
372  vtkIdType GetCellLists(vtkIntArray *regions, vtkIdList *inRegionCells,
373  vtkIdList *onBoundaryCells);
375 
377 
383  int GetRegionContainingCell(vtkDataSet *set, vtkIdType cellID);
384  int GetRegionContainingCell(int set, vtkIdType cellID);
385  int GetRegionContainingCell(vtkIdType cellID);
387 
396  int *AllGetRegionContainingCell();
397 
401  int GetRegionContainingPoint(double x, double y, double z);
402 
408  void BuildLocator() override;
409 
424  int MinimalNumberOfConvexSubRegions(vtkIntArray *regionIdList,
425  double **convexRegionBounds);
426 
434  int ViewOrderAllRegionsInDirection(const double directionOfProjection[3],
435  vtkIntArray *orderedList);
436 
444  int ViewOrderRegionsInDirection(vtkIntArray *regionIds,
445  const double directionOfProjection[3],
446  vtkIntArray *orderedList);
447 
455  int ViewOrderAllRegionsFromPosition(const double directionOfProjection[3],
456  vtkIntArray *orderedList);
457 
465  int ViewOrderRegionsFromPosition(vtkIntArray *regionIds,
466  const double directionOfProjection[3],
467  vtkIntArray *orderedList);
468 
470 
483  void BuildLocatorFromPoints(vtkPointSet *pointset);
484  void BuildLocatorFromPoints(vtkPoints *ptArray);
485  void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays);
487 
502  vtkIdTypeArray *BuildMapForDuplicatePoints(float tolerance);
503 
505 
510  vtkIdType FindPoint(double *x);
511  vtkIdType FindPoint(double x, double y, double z);
513 
515 
520  vtkIdType FindClosestPoint(double *x, double &dist2);
521  vtkIdType FindClosestPoint(double x, double y, double z, double &dist2);
523 
529  vtkIdType FindClosestPointWithinRadius(
530  double radius, const double x[3], double& dist2);
531 
533 
538  vtkIdType FindClosestPointInRegion(int regionId, double *x, double &dist2);
539  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z,
540  double &dist2);
542 
549  void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result);
550 
559  void FindClosestNPoints(int N, const double x[3], vtkIdList *result);
560 
565  vtkIdTypeArray *GetPointsInRegion(int regionId);
566 
571  void FreeSearchStructure() override;
572 
578  void GenerateRepresentation(int level, vtkPolyData *pd) override;
579 
584  void GenerateRepresentation(int *regionList, int len, vtkPolyData *pd);
585 
587 
593  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
594  vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
595  vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
597 
601  virtual void PrintTiming(ostream& os, vtkIndent indent);
602 
607  virtual int NewGeometry();
608 
614  virtual int NewGeometry(vtkDataSet **sets, int numDataSets);
615 
621  virtual void InvalidateGeometry();
622 
628  static vtkKdNode *CopyTree(vtkKdNode *kd);
629 
636  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
637 
638 protected:
639 
640  vtkKdTree();
641  ~vtkKdTree() override;
642 
645 
646  void SetCalculator(vtkKdNode *kd);
647 
648  int ProcessUserDefinedCuts(double *bounds);
649 
650  void SetCuts(vtkBSPCuts *cuts, int userDefined);
651 
657  void UpdateBuildTime();
658 
666  int DivideTest(int numberOfPoints, int level);
667 
668  enum {
669  XDIM = 0, // don't change these values
670  YDIM = 1,
671  ZDIM = 2
672  };
673 
675 
677  vtkKdNode **RegionList; // indexed by region ID
678 
680 
681  static void DeleteAllDescendants(vtkKdNode *nd);
682 
683  void BuildRegionList();
684  virtual int SelectCutDirection(vtkKdNode *kd);
685  void SetActualLevel(){this->Level = vtkKdTree::ComputeLevel(this->Top);}
686 
692  void GetRegionsAtLevel(int level, vtkKdNode **nodes);
693 
699  static void GetLeafNodeIds(vtkKdNode *node, vtkIntArray *ids);
700 
701 
706  int GetNumberOfCells();
707 
713  int GetDataSetsNumberOfCells(int set1, int set2);
714 
721  void ComputeCellCenter(vtkDataSet *set, int cellId, float *center);
722  void ComputeCellCenter(vtkDataSet *set, int cellId, double *center);
723 
733  float *ComputeCellCenters();
734  float *ComputeCellCenters(int set);
735  float *ComputeCellCenters(vtkDataSet *set);
736 
738 
744  void UpdateProgress(double amount);
745 
747 
750  vtkSetClampMacro(Progress,double,0.0,1.0);
751  vtkGetMacro(Progress,double);
753 
754 protected:
755  // So that each suboperation can report progress
756  // in [0,1], yet we will be able to report a global
757  // progress. Sub-operations must use UpdateSubOperationProgress()
758  // for this to work.
759  double ProgressScale;
761 
762  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
763  // Actual progress is given by
764  // (this->ProgressOffset + this->ProgressScale* amount).
765  void UpdateSubOperationProgress(double amount);
766 
767  static void _SetNewBounds(vtkKdNode *kd, double *b, int *fixDim);
768  static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from);
769  static void CopyKdNode(vtkKdNode *to, vtkKdNode *from);
770  static void SetDataBoundsToSpatialBounds(vtkKdNode *kd);
771  static void ZeroNumberOfPoints(vtkKdNode *kd);
772 
773  // Recursive helper for public FindPointsWithinRadius
774  void FindPointsWithinRadius(vtkKdNode* node, double R2,
775  const double x[3], vtkIdList* ids);
776 
777  // Recursive helper for public FindPointsWithinRadius
778  void AddAllPointsInRegion(vtkKdNode* node, vtkIdList* ids);
779 
780  // Recursive helper for public FindPointsInArea
781  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
782 
783  // Recursive helper for public FindPointsInArea
784  void AddAllPointsInRegion(vtkKdNode* node, vtkIdTypeArray* ids);
785 
786  int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels);
787 
788  void DoMedianFind(vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3);
789 
790  void SelfRegister(vtkKdNode *kd);
791 
792  struct _cellList{
793  vtkDataSet *dataSet; // cell lists for which data set
794  int *regionIds; // nullptr if listing all regions
795  int nRegions;
799  };
800 
801  void InitializeCellLists();
802  vtkIdList *GetList(int regionId, vtkIdList **which);
803 
804  void ComputeCellCenter(vtkCell* cell, double *center, double *weights);
805 
806  void GenerateRepresentationDataBounds(int level, vtkPolyData *pd);
807  void _generateRepresentationDataBounds(vtkKdNode *kd, vtkPoints *pts,
808  vtkCellArray *polys, int level);
809 
810  void GenerateRepresentationWholeSpace(int level, vtkPolyData *pd);
811  void _generateRepresentationWholeSpace(vtkKdNode *kd, vtkPoints *pts,
812  vtkCellArray *polys, int level);
813 
814  void AddPolys(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys);
815 
816  void _printTree(int verbose);
817 
818  int SearchNeighborsForDuplicate(int regionId, float *point,
819  int **pointsSoFar, int *len,
820  float tolerance, float tolerance2);
821 
822  int SearchRegionForDuplicate(float *point, int *pointsSoFar,
823  int len, float tolerance2);
824 
825  int _FindClosestPointInRegion(int regionId,
826  double x, double y, double z, double &dist2);
827 
828  int FindClosestPointInSphere(double x, double y, double z, double radius,
829  int skipRegion, double &dist2);
830 
831  int _ViewOrderRegionsInDirection(vtkIntArray *IdsOfInterest,
832  const double dop[3],
833  vtkIntArray *orderedList);
834 
835  static int __ViewOrderRegionsInDirection(vtkKdNode *node, vtkIntArray *list,
836  vtkIntArray *IdsOfInterest,
837  const double dir[3], int nextId);
838 
839  int _ViewOrderRegionsFromPosition(vtkIntArray *IdsOfInterest,
840  const double pos[3],
841  vtkIntArray *orderedList);
842 
843  static int __ViewOrderRegionsFromPosition(vtkKdNode *node, vtkIntArray *list,
844  vtkIntArray *IdsOfInterest,
845  const double pos[3], int nextId);
846 
847  static int __ConvexSubRegions(int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes);
848  static int FoundId(vtkIntArray *idArray, int id);
849 
850  void NewParitioningRequest(int req);
851  void SetInputDataInfo(int i,
852  int dims[3], double origin[3], double spacing[3]);
853  int CheckInputDataInfo(int i,
854  int dims[3], double origin[3], double spacing[3]);
855  void ClearLastBuildCache();
856 
857  static void __printTree(vtkKdNode *kd, int depth, int verbose);
858 
859  static int MidValue(int dim, float *c1, int nvals, double &coord);
860 
861  static int Select(int dim, float *c1, int *ids, int nvals, double &coord);
862  static float FindMaxLeftHalf(int dim, float *c1, int K);
863  static void _Select(int dim, float *X, int *ids, int L, int R, int K);
864 
865  static int ComputeLevel(vtkKdNode *kd);
866  static int SelfOrder(int id, vtkKdNode *kd);
867  static int findRegion(vtkKdNode *node, float x, float y, float z);
868  static int findRegion(vtkKdNode *node, double x, double y, double z);
869 
870  static vtkKdNode **_GetRegionsAtLevel(int level, vtkKdNode **nodes,
871  vtkKdNode *kd);
872 
873  static void AddNewRegions(vtkKdNode *kd, float *c1,
874  int midpt, int dim, double coord);
875 
876  void NewPartitioningRequest(int req);
877 
880 
882  double CellBoundsCache[6]; // to optimize IntersectsCell()
883 
885 
886  struct _cellList CellList;
887 
888  // Region Ids, by data set by cell id - this list is large (one
889  // int per cell) but accelerates creation of cell lists
890 
892 
893  int MinCells;
894  int NumberOfRegions; // number of leaf nodes
895 
897  double FudgeFactor; // a very small distance, relative to the dataset's size
898 
899  // These instance variables are used by the special locator created
900  // to find duplicate points. (BuildLocatorFromPoints)
901 
906 
907  float MaxWidth;
908 
909  // These Last* values are here to save state so we can
910  // determine later if k-d tree must be rebuilt.
911 
915  unsigned long *LastDataSetObserverTags;
918  double *LastBounds;
921 
923  double Progress;
924 
925  vtkKdTree(const vtkKdTree&) = delete;
926  void operator=(const vtkKdTree&) = delete;
927 };
928 #endif
vtkKdNode ** RegionList
Definition: vtkKdTree.h:677
virtual void BuildLocator()=0
Build the locator from the input dataset.
vtkTypeBool IncludeRegionBoundaryCells
Definition: vtkKdTree.h:881
vtkDataSet ** LastInputDataSets
Definition: vtkKdTree.h:914
maintain an unordered list of dataset objects
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning.
Definition: vtkKdNode.h:42
Perform calculations (mostly intersection calculations) on regions of a 3D binary spatial partitionin...
vtkKdNode * Top
Definition: vtkKdTree.h:676
float MaxWidth
Definition: vtkKdTree.h:907
This class represents an axis-aligned Binary Spatial Partitioning of a 3D space.
Definition: vtkBSPCuts.h:44
abstract class to specify dataset behavior
Definition: vtkDataSet.h:56
int LastNumDataSets
Definition: vtkKdTree.h:912
int NumberOfLocatorPoints
Definition: vtkKdTree.h:902
static int ComputeLevel(vtkKdNode *kd)
int * LastDataSetType
Definition: vtkKdTree.h:916
abstract base class for objects that accelerate spatial searches
Definition: vtkLocator.h:69
void PrintSelf(ostream &os, vtkIndent indent) override
Standard type and print methods.
int NumberOfRegionsOrLess
Definition: vtkKdTree.h:878
abstract class for specifying dataset behavior
Definition: vtkPointSet.h:39
vtkDataSet * GetDataSet() override
Return the 0'th data set.
Definition: vtkKdTree.h:231
dynamic, self-adjusting array of vtkIdType
int UserDefinedCuts
Definition: vtkKdTree.h:644
int vtkIdType
Definition: vtkType.h:345
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:79
int LastDataCacheSize
Definition: vtkKdTree.h:913
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
double ProgressScale
Definition: vtkKdTree.h:751
double * LastInputDataInfo
Definition: vtkKdTree.h:917
int vtkTypeBool
Definition: vtkABI.h:69
Timer support and logging.
Definition: vtkTimerLog.h:85
int * CellRegionList
Definition: vtkKdTree.h:891
virtual void SetDataSet(vtkDataSet *)
Build the locator from the points/cells defining this dataset.
abstract class to specify cell behavior
Definition: vtkCell.h:56
unsigned long * LastDataSetObserverTags
Definition: vtkKdTree.h:915
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:39
void SetActualLevel()
Definition: vtkKdTree.h:685
virtual vtkDataSet * GetDataSet()
Build the locator from the points/cells defining this dataset.
a simple class to control print indentation
Definition: vtkIndent.h:33
vtkBSPCuts * Cuts
Definition: vtkKdTree.h:922
list of point or cell ids
Definition: vtkIdList.h:30
vtkTimerLog * TimerLog
Definition: vtkKdTree.h:679
vtkDataSet * dataSet
Definition: vtkKdTree.h:793
double ProgressOffset
Definition: vtkKdTree.h:760
vtkIdType * LastNumPoints
Definition: vtkKdTree.h:919
int * LocatorIds
Definition: vtkKdTree.h:904
int MinCells
Definition: vtkKdTree.h:893
int NumberOfRegions
Definition: vtkKdTree.h:894
vtkTypeBool GenerateRepresentationUsingDataBounds
Definition: vtkKdTree.h:884
object to represent cell connectivity
Definition: vtkCellArray.h:44
double Progress
Definition: vtkKdTree.h:923
vtkIdList ** boundaryCells
Definition: vtkKdTree.h:797
vtkTypeBool Timing
Definition: vtkKdTree.h:896
double * LastBounds
Definition: vtkKdTree.h:918
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:75
float * LocatorPoints
Definition: vtkKdTree.h:903
vtkIdList ** cells
Definition: vtkKdTree.h:796
vtkIdList * emptyList
Definition: vtkKdTree.h:798
int ValidDirections
Definition: vtkKdTree.h:674
vtkIdType * LastNumCells
Definition: vtkKdTree.h:920
static vtkObject * New()
Create an object with Debug turned off, modified time initialized to zero, and reference counting on.
int * LocatorRegionLocation
Definition: vtkKdTree.h:905
vtkDataSetCollection * DataSets
Definition: vtkKdTree.h:737
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
Method to build a representation at a particular level.
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:643
represent and manipulate 3D points
Definition: vtkPoints.h:33
double FudgeFactor
Definition: vtkKdTree.h:897
int NumberOfRegionsOrMore
Definition: vtkKdTree.h:879