VTK  9.3.1
vtkKdTree.h
Go to the documentation of this file.
1 // SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
2 // SPDX-FileCopyrightText: Copyright (c) Sandia Corporation
3 // SPDX-License-Identifier: BSD-3-Clause
4 
47 #ifndef vtkKdTree_h
48 #define vtkKdTree_h
49 
50 #include "vtkCommonDataModelModule.h" // For export macro
51 #include "vtkLocator.h"
52 
53 VTK_ABI_NAMESPACE_BEGIN
54 class vtkTimerLog;
55 class vtkIdList;
56 class vtkIdTypeArray;
57 class vtkIntArray;
58 class vtkPointSet;
59 class vtkPoints;
60 class vtkCellArray;
61 class vtkCell;
62 class vtkKdNode;
63 class vtkBSPCuts;
66 
67 class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
68 {
69 public:
70  vtkTypeMacro(vtkKdTree, vtkLocator);
71  void PrintSelf(ostream& os, vtkIndent indent) override;
72 
73  static vtkKdTree* New();
74 
76 
79  vtkBooleanMacro(Timing, vtkTypeBool);
80  vtkSetMacro(Timing, vtkTypeBool);
81  vtkGetMacro(Timing, vtkTypeBool);
83 
85 
88  vtkSetMacro(MinCells, int);
89  vtkGetMacro(MinCells, int);
91 
99  vtkGetMacro(NumberOfRegionsOrLess, int);
100  vtkSetMacro(NumberOfRegionsOrLess, int);
101 
109  vtkGetMacro(NumberOfRegionsOrMore, int);
110  vtkSetMacro(NumberOfRegionsOrMore, int);
111 
119  vtkGetMacro(FudgeFactor, double);
120  vtkSetMacro(FudgeFactor, double);
121 
127  vtkGetObjectMacro(Cuts, vtkBSPCuts);
128 
135  void SetCuts(vtkBSPCuts* cuts);
136 
140  void OmitXPartitioning();
141 
145  void OmitYPartitioning();
146 
150  void OmitZPartitioning();
151 
155  void OmitXYPartitioning();
156 
160  void OmitYZPartitioning();
161 
165  void OmitZXPartitioning();
166 
170  void OmitNoPartitioning();
171 
186  void SetDataSet(vtkDataSet* set) override;
187 
192  virtual void AddDataSet(vtkDataSet* set);
193 
195 
198  virtual void RemoveDataSet(int index);
199  virtual void RemoveDataSet(vtkDataSet* set);
200  virtual void RemoveAllDataSets();
202 
206  int GetNumberOfDataSets();
207 
217  vtkDataSet* GetDataSet(int n);
218 
223  vtkDataSet* GetDataSet() override { return this->GetDataSet(0); }
224 
226 
229  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
231 
236  int GetDataSetIndex(vtkDataSet* set);
237 
242  void GetBounds(double* bounds);
243 
252  void SetNewBounds(double* bounds);
253 
255 
258  vtkGetMacro(NumberOfRegions, int);
260 
264  void GetRegionBounds(int regionID, double bounds[6]);
265 
269  void GetRegionDataBounds(int regionID, double bounds[6]);
270 
272 
275  void PrintTree();
276  void PrintVerboseTree();
278 
282  void PrintRegion(int id);
283 
296  void CreateCellLists(int dataSetIndex, int* regionReqList, int reqListSize);
297  void CreateCellLists(vtkDataSet* set, int* regionReqList, int reqListSize);
298  void CreateCellLists(int* regionReqList, int listSize);
299  void CreateCellLists();
300 
302 
309  vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
310  vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
311  vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
313 
317  void DeleteCellLists();
318 
323  vtkIdList* GetCellList(int regionID);
324 
335  vtkIdList* GetBoundaryCellList(int regionID);
336 
338 
358  vtkIdType GetCellLists(
359  vtkIntArray* regions, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
360  vtkIdType GetCellLists(
361  vtkIntArray* regions, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
362  vtkIdType GetCellLists(
363  vtkIntArray* regions, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
365 
367 
373  int GetRegionContainingCell(vtkDataSet* set, vtkIdType cellID);
374  int GetRegionContainingCell(int set, vtkIdType cellID);
375  int GetRegionContainingCell(vtkIdType cellID);
377 
386  int* AllGetRegionContainingCell();
387 
391  int GetRegionContainingPoint(double x, double y, double z);
392 
398  void BuildLocator() override;
399 
403  void ForceBuildLocator() override;
404 
419  int MinimalNumberOfConvexSubRegions(vtkIntArray* regionIdList, double** convexRegionBounds);
420 
428  int ViewOrderAllRegionsInDirection(
429  const double directionOfProjection[3], vtkIntArray* orderedList);
430 
438  int ViewOrderRegionsInDirection(
439  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
440 
448  int ViewOrderAllRegionsFromPosition(
449  const double directionOfProjection[3], vtkIntArray* orderedList);
450 
458  int ViewOrderRegionsFromPosition(
459  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
460 
462 
475  void BuildLocatorFromPoints(vtkPointSet* pointset);
476  void BuildLocatorFromPoints(vtkPoints* ptArray);
477  void BuildLocatorFromPoints(vtkPoints** ptArray, int numPtArrays);
479 
494  vtkIdTypeArray* BuildMapForDuplicatePoints(float tolerance);
495 
497 
502  vtkIdType FindPoint(double* x);
503  vtkIdType FindPoint(double x, double y, double z);
505 
507 
512  vtkIdType FindClosestPoint(double* x, double& dist2);
513  vtkIdType FindClosestPoint(double x, double y, double z, double& dist2);
515 
521  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2);
522 
524 
529  vtkIdType FindClosestPointInRegion(int regionId, double* x, double& dist2);
530  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
532 
539  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result);
540 
549  void FindClosestNPoints(int N, const double x[3], vtkIdList* result);
550 
555  vtkIdTypeArray* GetPointsInRegion(int regionId);
556 
561  void FreeSearchStructure() override;
562 
568  void GenerateRepresentation(int level, vtkPolyData* pd) override;
569 
574  void GenerateRepresentation(int* regionList, int len, vtkPolyData* pd);
575 
577 
583  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
584  vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
585  vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
587 
591  virtual void PrintTiming(ostream& os, vtkIndent indent);
592 
597  virtual int NewGeometry();
598 
604  virtual int NewGeometry(vtkDataSet** sets, int numDataSets);
605 
611  virtual void InvalidateGeometry();
612 
618  static vtkKdNode* CopyTree(vtkKdNode* kd);
619 
626  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
627 
628 protected:
629  vtkKdTree();
630  ~vtkKdTree() override;
631 
632  void BuildLocatorInternal() override;
633 
636 
637  void SetCalculator(vtkKdNode* kd);
638 
639  int ProcessUserDefinedCuts(double* bounds);
640 
641  void SetCuts(vtkBSPCuts* cuts, int userDefined);
642 
648  void UpdateBuildTime();
649 
657  int DivideTest(int numberOfPoints, int level);
658 
659  enum
660  {
661  XDIM = 0, // don't change these values
662  YDIM = 1,
663  ZDIM = 2
664  };
665 
667 
669  vtkKdNode** RegionList; // indexed by region ID
670 
672 
673  static void DeleteAllDescendants(vtkKdNode* nd);
674 
675  void BuildRegionList();
676  virtual int SelectCutDirection(vtkKdNode* kd);
677  void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }
678 
684  void GetRegionsAtLevel(int level, vtkKdNode** nodes);
685 
691  static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);
692 
697  int GetNumberOfCells();
698 
704  int GetDataSetsNumberOfCells(int set1, int set2);
705 
712  void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
713  void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);
714 
724  float* ComputeCellCenters();
725  float* ComputeCellCenters(int set);
726  float* ComputeCellCenters(vtkDataSet* set);
727 
729 
735  void UpdateProgress(double amount);
736 
738 
741  vtkSetClampMacro(Progress, double, 0.0, 1.0);
742  vtkGetMacro(Progress, double);
744 
745  // So that each suboperation can report progress
746  // in [0,1], yet we will be able to report a global
747  // progress. Sub-operations must use UpdateSubOperationProgress()
748  // for this to work.
749  double ProgressScale;
751 
752  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
753  // Actual progress is given by
754  // (this->ProgressOffset + this->ProgressScale* amount).
755  void UpdateSubOperationProgress(double amount);
756 
757  static void SetNewBounds_(vtkKdNode* kd, double* b, int* fixDim);
758  static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
759  static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
760  static void SetDataBoundsToSpatialBounds(vtkKdNode* kd);
761  static void ZeroNumberOfPoints(vtkKdNode* kd);
762 
763  // Recursive helper for public FindPointsWithinRadius
764  void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
765 
766  // Recursive helper for public FindPointsWithinRadius
767  void AddAllPointsInRegion(vtkKdNode* node, vtkIdList* ids);
768 
769  // Recursive helper for public FindPointsInArea
770  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
771 
772  // Recursive helper for public FindPointsInArea
773  void AddAllPointsInRegion(vtkKdNode* node, vtkIdTypeArray* ids);
774 
775  int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
776 
777  void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
778 
779  void SelfRegister(vtkKdNode* kd);
780 
781  struct cellList_
782  {
783  vtkDataSet* dataSet; // cell lists for which data set
784  int* regionIds; // nullptr if listing all regions
785  int nRegions;
789  };
790 
791  void InitializeCellLists();
792  vtkIdList* GetList(int regionId, vtkIdList** which);
793 
794  void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
795 
796  void GenerateRepresentationDataBounds(int level, vtkPolyData* pd);
797  void _generateRepresentationDataBounds(
798  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
799 
800  void GenerateRepresentationWholeSpace(int level, vtkPolyData* pd);
801  void _generateRepresentationWholeSpace(
802  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
803 
804  void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
805 
806  void printTree_(int verbose);
807 
808  int SearchNeighborsForDuplicate(
809  int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
810 
811  int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
812 
813  int FindClosestPointInRegion_(int regionId, double x, double y, double z, double& dist2);
814 
815  int FindClosestPointInSphere(
816  double x, double y, double z, double radius, int skipRegion, double& dist2);
817 
818  int ViewOrderRegionsInDirection_(
819  vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
820 
821  static int ViewOrderRegionsInDirection_P(vtkKdNode* node, vtkIntArray* list,
822  vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
823 
824  int ViewOrderRegionsFromPosition_(
825  vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
826 
827  static int ViewOrderRegionsFromPosition_P(vtkKdNode* node, vtkIntArray* list,
828  vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
829 
830  static int ConvexSubRegions_(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
831  static int FoundId(vtkIntArray* idArray, int id);
832 
833  void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
834  int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
835  void ClearLastBuildCache();
836 
837  static void printTree_P(vtkKdNode* kd, int depth, int verbose);
838 
839  static int MidValue(int dim, float* c1, int nvals, double& coord);
840 
841  static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
842  static float FindMaxLeftHalf(int dim, float* c1, int K);
843  static void Select_(int dim, float* X, int* ids, int L, int R, int K);
844 
845  static int ComputeLevel(vtkKdNode* kd);
846  static int SelfOrder(int id, vtkKdNode* kd);
847  static int findRegion(vtkKdNode* node, float x, float y, float z);
848  static int findRegion(vtkKdNode* node, double x, double y, double z);
849 
850  static vtkKdNode** GetRegionsAtLevel_(int level, vtkKdNode** nodes, vtkKdNode* kd);
851 
852  static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
853 
854  void NewPartitioningRequest(int req);
855 
858 
860  double CellBoundsCache[6]; // to optimize IntersectsCell()
861 
863 
864  struct cellList_ CellList;
865 
866  // Region Ids, by data set by cell id - this list is large (one
867  // int per cell) but accelerates creation of cell lists
868 
870 
871  int MinCells;
872  int NumberOfRegions; // number of leaf nodes
873 
875  double FudgeFactor; // a very small distance, relative to the dataset's size
876 
877  // These instance variables are used by the special locator created
878  // to find duplicate points. (BuildLocatorFromPoints)
879 
884 
885  float MaxWidth;
886 
887  // These Last* values are here to save state so we can
888  // determine later if k-d tree must be rebuilt.
889 
893  unsigned long* LastDataSetObserverTags;
896  double* LastBounds;
899 
901  double Progress;
902 
903  vtkKdTree(const vtkKdTree&) = delete;
904  void operator=(const vtkKdTree&) = delete;
905 };
906 VTK_ABI_NAMESPACE_END
907 #endif
vtkKdNode ** RegionList
Definition: vtkKdTree.h:669
virtual void BuildLocator()=0
Build the locator from the input dataset.
void GetBounds(T a, double bds[6])
vtkTypeBool IncludeRegionBoundaryCells
Definition: vtkKdTree.h:859
vtkDataSet ** LastInputDataSets
Definition: vtkKdTree.h:892
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:31
Perform calculations (mostly intersection calculations) on regions of a 3D binary spatial partitionin...
vtkKdNode * Top
Definition: vtkKdTree.h:668
float MaxWidth
Definition: vtkKdTree.h:885
This class represents an axis-aligned Binary Spatial Partitioning of a 3D space.
Definition: vtkBSPCuts.h:30
abstract class to specify dataset behavior
Definition: vtkDataSet.h:52
int LastNumDataSets
Definition: vtkKdTree.h:890
int NumberOfLocatorPoints
Definition: vtkKdTree.h:880
static int ComputeLevel(vtkKdNode *kd)
int * LastDataSetType
Definition: vtkKdTree.h:894
abstract base class for objects that accelerate spatial searches
Definition: vtkLocator.h:58
void PrintSelf(ostream &os, vtkIndent indent) override
Standard type and print methods.
int NumberOfRegionsOrLess
Definition: vtkKdTree.h:856
concrete class for storing a set of points
Definition: vtkPointSet.h:58
vtkDataSet * GetDataSet() override
Return the 0'th data set.
Definition: vtkKdTree.h:223
vtkDataSet * dataSet
Definition: vtkKdTree.h:783
dynamic, self-adjusting array of vtkIdType
int UserDefinedCuts
Definition: vtkKdTree.h:635
int vtkIdType
Definition: vtkType.h:315
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:79
int LastDataCacheSize
Definition: vtkKdTree.h:891
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
double ProgressScale
Definition: vtkKdTree.h:742
double * LastInputDataInfo
Definition: vtkKdTree.h:895
vtkIdList * emptyList
Definition: vtkKdTree.h:788
int vtkTypeBool
Definition: vtkABI.h:64
Timer support and logging.
Definition: vtkTimerLog.h:84
int * CellRegionList
Definition: vtkKdTree.h:869
virtual void SetDataSet(vtkDataSet *)
Build the locator from the points/cells defining this dataset.
abstract class to specify cell behavior
Definition: vtkCell.h:49
unsigned long * LastDataSetObserverTags
Definition: vtkKdTree.h:893
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:34
void SetActualLevel()
Definition: vtkKdTree.h:677
virtual vtkDataSet * GetDataSet()
Build the locator from the points/cells defining this dataset.
a simple class to control print indentation
Definition: vtkIndent.h:28
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition: vtkLocator.h:192
vtkBSPCuts * Cuts
Definition: vtkKdTree.h:900
list of point or cell ids
Definition: vtkIdList.h:22
vtkTimerLog * TimerLog
Definition: vtkKdTree.h:671
double ProgressOffset
Definition: vtkKdTree.h:750
vtkIdType * LastNumPoints
Definition: vtkKdTree.h:897
int * LocatorIds
Definition: vtkKdTree.h:882
int MinCells
Definition: vtkKdTree.h:871
int NumberOfRegions
Definition: vtkKdTree.h:872
vtkTypeBool GenerateRepresentationUsingDataBounds
Definition: vtkKdTree.h:862
vtkIdList ** cells
Definition: vtkKdTree.h:786
object to represent cell connectivity
Definition: vtkCellArray.h:175
double Progress
Definition: vtkKdTree.h:901
vtkTypeBool Timing
Definition: vtkKdTree.h:874
double * LastBounds
Definition: vtkKdTree.h:896
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:67
vtkIdList ** boundaryCells
Definition: vtkKdTree.h:787
float * LocatorPoints
Definition: vtkKdTree.h:881
int ValidDirections
Definition: vtkKdTree.h:666
vtkIdType * LastNumCells
Definition: vtkKdTree.h:898
static vtkObject * New()
Create an object with Debug turned off, modified time initialized to zero, and reference counting on...
int * LocatorRegionLocation
Definition: vtkKdTree.h:883
vtkDataSetCollection * DataSets
Definition: vtkKdTree.h:728
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
Method to build a representation at a particular level.
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:634
represent and manipulate 3D points
Definition: vtkPoints.h:28
virtual void ForceBuildLocator()
Build the locator from the input dataset (even if UseExistingSearchStructure is on).
Definition: vtkLocator.h:156
double FudgeFactor
Definition: vtkKdTree.h:875
int NumberOfRegionsOrMore
Definition: vtkKdTree.h:857