VTK  9.2.6
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 
62 #ifndef vtkKdTree_h
63 #define vtkKdTree_h
64 
65 #include "vtkCommonDataModelModule.h" // For export macro
66 #include "vtkLocator.h"
67 
68 class vtkTimerLog;
69 class vtkIdList;
70 class vtkIdTypeArray;
71 class vtkIntArray;
72 class vtkPointSet;
73 class vtkPoints;
74 class vtkCellArray;
75 class vtkCell;
76 class vtkKdNode;
77 class vtkBSPCuts;
80 
81 class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
82 {
83 public:
84  vtkTypeMacro(vtkKdTree, vtkLocator);
85  void PrintSelf(ostream& os, vtkIndent indent) override;
86 
87  static vtkKdTree* New();
88 
90 
93  vtkBooleanMacro(Timing, vtkTypeBool);
94  vtkSetMacro(Timing, vtkTypeBool);
95  vtkGetMacro(Timing, vtkTypeBool);
97 
99 
102  vtkSetMacro(MinCells, int);
103  vtkGetMacro(MinCells, int);
105 
113  vtkGetMacro(NumberOfRegionsOrLess, int);
114  vtkSetMacro(NumberOfRegionsOrLess, int);
115 
123  vtkGetMacro(NumberOfRegionsOrMore, int);
124  vtkSetMacro(NumberOfRegionsOrMore, int);
125 
133  vtkGetMacro(FudgeFactor, double);
134  vtkSetMacro(FudgeFactor, double);
135 
141  vtkGetObjectMacro(Cuts, vtkBSPCuts);
142 
149  void SetCuts(vtkBSPCuts* cuts);
150 
154  void OmitXPartitioning();
155 
159  void OmitYPartitioning();
160 
164  void OmitZPartitioning();
165 
169  void OmitXYPartitioning();
170 
174  void OmitYZPartitioning();
175 
179  void OmitZXPartitioning();
180 
184  void OmitNoPartitioning();
185 
200  void SetDataSet(vtkDataSet* set) override;
201 
206  virtual void AddDataSet(vtkDataSet* set);
207 
209 
212  virtual void RemoveDataSet(int index);
213  virtual void RemoveDataSet(vtkDataSet* set);
214  virtual void RemoveAllDataSets();
216 
220  int GetNumberOfDataSets();
221 
231  vtkDataSet* GetDataSet(int n);
232 
237  vtkDataSet* GetDataSet() override { return this->GetDataSet(0); }
238 
240 
243  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
245 
250  int GetDataSetIndex(vtkDataSet* set);
251 
256  void GetBounds(double* bounds);
257 
266  void SetNewBounds(double* bounds);
267 
269 
272  vtkGetMacro(NumberOfRegions, int);
274 
278  void GetRegionBounds(int regionID, double bounds[6]);
279 
283  void GetRegionDataBounds(int regionID, double bounds[6]);
284 
286 
289  void PrintTree();
290  void PrintVerboseTree();
292 
296  void PrintRegion(int id);
297 
310  void CreateCellLists(int dataSetIndex, int* regionReqList, int reqListSize);
311  void CreateCellLists(vtkDataSet* set, int* regionReqList, int reqListSize);
312  void CreateCellLists(int* regionReqList, int listSize);
313  void CreateCellLists();
314 
316 
323  vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
324  vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
325  vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
327 
331  void DeleteCellLists();
332 
337  vtkIdList* GetCellList(int regionID);
338 
349  vtkIdList* GetBoundaryCellList(int regionID);
350 
352 
372  vtkIdType GetCellLists(
373  vtkIntArray* regions, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
374  vtkIdType GetCellLists(
375  vtkIntArray* regions, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
376  vtkIdType GetCellLists(
377  vtkIntArray* regions, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
379 
381 
387  int GetRegionContainingCell(vtkDataSet* set, vtkIdType cellID);
388  int GetRegionContainingCell(int set, vtkIdType cellID);
389  int GetRegionContainingCell(vtkIdType cellID);
391 
400  int* AllGetRegionContainingCell();
401 
405  int GetRegionContainingPoint(double x, double y, double z);
406 
412  void BuildLocator() override;
413 
417  void ForceBuildLocator() override;
418 
433  int MinimalNumberOfConvexSubRegions(vtkIntArray* regionIdList, double** convexRegionBounds);
434 
442  int ViewOrderAllRegionsInDirection(
443  const double directionOfProjection[3], vtkIntArray* orderedList);
444 
452  int ViewOrderRegionsInDirection(
453  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
454 
462  int ViewOrderAllRegionsFromPosition(
463  const double directionOfProjection[3], vtkIntArray* orderedList);
464 
472  int ViewOrderRegionsFromPosition(
473  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
474 
476 
489  void BuildLocatorFromPoints(vtkPointSet* pointset);
490  void BuildLocatorFromPoints(vtkPoints* ptArray);
491  void BuildLocatorFromPoints(vtkPoints** ptArray, int numPtArrays);
493 
508  vtkIdTypeArray* BuildMapForDuplicatePoints(float tolerance);
509 
511 
516  vtkIdType FindPoint(double* x);
517  vtkIdType FindPoint(double x, double y, double z);
519 
521 
526  vtkIdType FindClosestPoint(double* x, double& dist2);
527  vtkIdType FindClosestPoint(double x, double y, double z, double& dist2);
529 
535  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2);
536 
538 
543  vtkIdType FindClosestPointInRegion(int regionId, double* x, double& dist2);
544  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
546 
553  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result);
554 
563  void FindClosestNPoints(int N, const double x[3], vtkIdList* result);
564 
569  vtkIdTypeArray* GetPointsInRegion(int regionId);
570 
575  void FreeSearchStructure() override;
576 
582  void GenerateRepresentation(int level, vtkPolyData* pd) override;
583 
588  void GenerateRepresentation(int* regionList, int len, vtkPolyData* pd);
589 
591 
597  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
598  vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
599  vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
601 
605  virtual void PrintTiming(ostream& os, vtkIndent indent);
606 
611  virtual int NewGeometry();
612 
618  virtual int NewGeometry(vtkDataSet** sets, int numDataSets);
619 
625  virtual void InvalidateGeometry();
626 
632  static vtkKdNode* CopyTree(vtkKdNode* kd);
633 
640  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
641 
642 protected:
643  vtkKdTree();
644  ~vtkKdTree() override;
645 
646  void BuildLocatorInternal() override;
647 
650 
651  void SetCalculator(vtkKdNode* kd);
652 
653  int ProcessUserDefinedCuts(double* bounds);
654 
655  void SetCuts(vtkBSPCuts* cuts, int userDefined);
656 
662  void UpdateBuildTime();
663 
671  int DivideTest(int numberOfPoints, int level);
672 
673  enum
674  {
675  XDIM = 0, // don't change these values
676  YDIM = 1,
677  ZDIM = 2
678  };
679 
681 
683  vtkKdNode** RegionList; // indexed by region ID
684 
686 
687  static void DeleteAllDescendants(vtkKdNode* nd);
688 
689  void BuildRegionList();
690  virtual int SelectCutDirection(vtkKdNode* kd);
691  void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }
692 
698  void GetRegionsAtLevel(int level, vtkKdNode** nodes);
699 
705  static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);
706 
711  int GetNumberOfCells();
712 
718  int GetDataSetsNumberOfCells(int set1, int set2);
719 
726  void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
727  void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);
728 
738  float* ComputeCellCenters();
739  float* ComputeCellCenters(int set);
740  float* ComputeCellCenters(vtkDataSet* set);
741 
743 
749  void UpdateProgress(double amount);
750 
752 
755  vtkSetClampMacro(Progress, double, 0.0, 1.0);
756  vtkGetMacro(Progress, double);
758 
759 protected:
760  // So that each suboperation can report progress
761  // in [0,1], yet we will be able to report a global
762  // progress. Sub-operations must use UpdateSubOperationProgress()
763  // for this to work.
764  double ProgressScale;
766 
767  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
768  // Actual progress is given by
769  // (this->ProgressOffset + this->ProgressScale* amount).
770  void UpdateSubOperationProgress(double amount);
771 
772  static void SetNewBounds_(vtkKdNode* kd, double* b, int* fixDim);
773  static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
774  static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
775  static void SetDataBoundsToSpatialBounds(vtkKdNode* kd);
776  static void ZeroNumberOfPoints(vtkKdNode* kd);
777 
778  // Recursive helper for public FindPointsWithinRadius
779  void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
780 
781  // Recursive helper for public FindPointsWithinRadius
782  void AddAllPointsInRegion(vtkKdNode* node, vtkIdList* ids);
783 
784  // Recursive helper for public FindPointsInArea
785  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
786 
787  // Recursive helper for public FindPointsInArea
788  void AddAllPointsInRegion(vtkKdNode* node, vtkIdTypeArray* ids);
789 
790  int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
791 
792  void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
793 
794  void SelfRegister(vtkKdNode* kd);
795 
796  struct cellList_
797  {
798  vtkDataSet* dataSet; // cell lists for which data set
799  int* regionIds; // nullptr if listing all regions
800  int nRegions;
804  };
805 
806  void InitializeCellLists();
807  vtkIdList* GetList(int regionId, vtkIdList** which);
808 
809  void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
810 
811  void GenerateRepresentationDataBounds(int level, vtkPolyData* pd);
812  void _generateRepresentationDataBounds(
813  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
814 
815  void GenerateRepresentationWholeSpace(int level, vtkPolyData* pd);
816  void _generateRepresentationWholeSpace(
817  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
818 
819  void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
820 
821  void printTree_(int verbose);
822 
823  int SearchNeighborsForDuplicate(
824  int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
825 
826  int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
827 
828  int FindClosestPointInRegion_(int regionId, double x, double y, double z, double& dist2);
829 
830  int FindClosestPointInSphere(
831  double x, double y, double z, double radius, int skipRegion, double& dist2);
832 
833  int ViewOrderRegionsInDirection_(
834  vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
835 
836  static int ViewOrderRegionsInDirection_P(vtkKdNode* node, vtkIntArray* list,
837  vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
838 
839  int ViewOrderRegionsFromPosition_(
840  vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
841 
842  static int ViewOrderRegionsFromPosition_P(vtkKdNode* node, vtkIntArray* list,
843  vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
844 
845  static int ConvexSubRegions_(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
846  static int FoundId(vtkIntArray* idArray, int id);
847 
848  void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
849  int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
850  void ClearLastBuildCache();
851 
852  static void printTree_P(vtkKdNode* kd, int depth, int verbose);
853 
854  static int MidValue(int dim, float* c1, int nvals, double& coord);
855 
856  static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
857  static float FindMaxLeftHalf(int dim, float* c1, int K);
858  static void Select_(int dim, float* X, int* ids, int L, int R, int K);
859 
860  static int ComputeLevel(vtkKdNode* kd);
861  static int SelfOrder(int id, vtkKdNode* kd);
862  static int findRegion(vtkKdNode* node, float x, float y, float z);
863  static int findRegion(vtkKdNode* node, double x, double y, double z);
864 
865  static vtkKdNode** GetRegionsAtLevel_(int level, vtkKdNode** nodes, vtkKdNode* kd);
866 
867  static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
868 
869  void NewPartitioningRequest(int req);
870 
873 
875  double CellBoundsCache[6]; // to optimize IntersectsCell()
876 
878 
879  struct cellList_ CellList;
880 
881  // Region Ids, by data set by cell id - this list is large (one
882  // int per cell) but accelerates creation of cell lists
883 
885 
886  int MinCells;
887  int NumberOfRegions; // number of leaf nodes
888 
890  double FudgeFactor; // a very small distance, relative to the dataset's size
891 
892  // These instance variables are used by the special locator created
893  // to find duplicate points. (BuildLocatorFromPoints)
894 
899 
900  float MaxWidth;
901 
902  // These Last* values are here to save state so we can
903  // determine later if k-d tree must be rebuilt.
904 
908  unsigned long* LastDataSetObserverTags;
911  double* LastBounds;
914 
916  double Progress;
917 
918  vtkKdTree(const vtkKdTree&) = delete;
919  void operator=(const vtkKdTree&) = delete;
920 };
921 #endif
vtkKdNode ** RegionList
Definition: vtkKdTree.h:683
virtual void BuildLocator()=0
Build the locator from the input dataset.
void GetBounds(T a, double bds[6])
vtkTypeBool IncludeRegionBoundaryCells
Definition: vtkKdTree.h:874
vtkDataSet ** LastInputDataSets
Definition: vtkKdTree.h:907
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:45
Perform calculations (mostly intersection calculations) on regions of a 3D binary spatial partitionin...
vtkKdNode * Top
Definition: vtkKdTree.h:682
float MaxWidth
Definition: vtkKdTree.h:900
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:62
int LastNumDataSets
Definition: vtkKdTree.h:905
int NumberOfLocatorPoints
Definition: vtkKdTree.h:895
static int ComputeLevel(vtkKdNode *kd)
int * LastDataSetType
Definition: vtkKdTree.h:909
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:871
concrete class for storing a set of points
Definition: vtkPointSet.h:69
vtkDataSet * GetDataSet() override
Return the 0'th data set.
Definition: vtkKdTree.h:237
vtkDataSet * dataSet
Definition: vtkKdTree.h:798
dynamic, self-adjusting array of vtkIdType
int UserDefinedCuts
Definition: vtkKdTree.h:649
int vtkIdType
Definition: vtkType.h:332
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:90
int LastDataCacheSize
Definition: vtkKdTree.h:906
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
double ProgressScale
Definition: vtkKdTree.h:756
double * LastInputDataInfo
Definition: vtkKdTree.h:910
vtkIdList * emptyList
Definition: vtkKdTree.h:803
int vtkTypeBool
Definition: vtkABI.h:69
Timer support and logging.
Definition: vtkTimerLog.h:95
int * CellRegionList
Definition: vtkKdTree.h:884
virtual void SetDataSet(vtkDataSet *)
Build the locator from the points/cells defining this dataset.
abstract class to specify cell behavior
Definition: vtkCell.h:60
unsigned long * LastDataSetObserverTags
Definition: vtkKdTree.h:908
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:45
void SetActualLevel()
Definition: vtkKdTree.h:691
virtual vtkDataSet * GetDataSet()
Build the locator from the points/cells defining this dataset.
a simple class to control print indentation
Definition: vtkIndent.h:39
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition: vtkLocator.h:203
vtkBSPCuts * Cuts
Definition: vtkKdTree.h:915
list of point or cell ids
Definition: vtkIdList.h:33
vtkTimerLog * TimerLog
Definition: vtkKdTree.h:685
double ProgressOffset
Definition: vtkKdTree.h:765
vtkIdType * LastNumPoints
Definition: vtkKdTree.h:912
int * LocatorIds
Definition: vtkKdTree.h:897
int MinCells
Definition: vtkKdTree.h:886
int NumberOfRegions
Definition: vtkKdTree.h:887
vtkTypeBool GenerateRepresentationUsingDataBounds
Definition: vtkKdTree.h:877
vtkIdList ** cells
Definition: vtkKdTree.h:801
object to represent cell connectivity
Definition: vtkCellArray.h:186
double Progress
Definition: vtkKdTree.h:916
vtkTypeBool Timing
Definition: vtkKdTree.h:889
double * LastBounds
Definition: vtkKdTree.h:911
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:81
vtkIdList ** boundaryCells
Definition: vtkKdTree.h:802
float * LocatorPoints
Definition: vtkKdTree.h:896
int ValidDirections
Definition: vtkKdTree.h:680
vtkIdType * LastNumCells
Definition: vtkKdTree.h:913
static vtkObject * New()
Create an object with Debug turned off, modified time initialized to zero, and reference counting on...
int * LocatorRegionLocation
Definition: vtkKdTree.h:898
vtkDataSetCollection * DataSets
Definition: vtkKdTree.h:742
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
Method to build a representation at a particular level.
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:648
represent and manipulate 3D points
Definition: vtkPoints.h:39
virtual void ForceBuildLocator()
Build the locator from the input dataset (even if UseExistingSearchStructure is on).
Definition: vtkLocator.h:167
double FudgeFactor
Definition: vtkKdTree.h:890
int NumberOfRegionsOrMore
Definition: vtkKdTree.h:872