vtkKdTree.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-FileCopyrightText: Copyright (c) Sandia Corporation
// SPDX-License-Identifier: BSD-3-Clause

 
#ifndef vtkKdTree_h
#define vtkKdTree_h
 
#include "vtkCommonDataModelModule.h" // For export macro
#include "vtkLocator.h"
 
VTK_ABI_NAMESPACE_BEGIN
class vtkTimerLog;
class vtkIdList;
class vtkIdTypeArray;
class vtkIntArray;
class vtkPointSet;
class vtkPoints;
class vtkCellArray;
class vtkCell;
class vtkKdNode;
class vtkBSPCuts;
class vtkBSPIntersections;
class vtkDataSetCollection;
 
class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
{
public:
  vtkTypeMacro(vtkKdTree, vtkLocator);
  void PrintSelf(ostream& os, vtkIndent indent) override;
 
  static vtkKdTree* New();


  vtkBooleanMacro(Timing, vtkTypeBool);
  vtkSetMacro(Timing, vtkTypeBool);
  vtkGetMacro(Timing, vtkTypeBool);


  vtkSetMacro(MinCells, int);
  vtkGetMacro(MinCells, int);

 
  vtkGetMacro(NumberOfRegionsOrLess, int);
  vtkSetMacro(NumberOfRegionsOrLess, int);

 
  vtkGetMacro(NumberOfRegionsOrMore, int);
  vtkSetMacro(NumberOfRegionsOrMore, int);

 
  vtkGetMacro(FudgeFactor, double);
  vtkSetMacro(FudgeFactor, double);

 
  vtkGetObjectMacro(Cuts, vtkBSPCuts);

 
  void SetCuts(vtkBSPCuts* cuts);

  void OmitXPartitioning();

  void OmitYPartitioning();

  void OmitZPartitioning();

  void OmitXYPartitioning();

  void OmitYZPartitioning();

  void OmitZXPartitioning();

  void OmitNoPartitioning();


  void SetDataSet(vtkDataSet* set) override;

  virtual void AddDataSet(vtkDataSet* set);


  virtual void RemoveDataSet(int index);
  virtual void RemoveDataSet(vtkDataSet* set);
  virtual void RemoveAllDataSets();

  int GetNumberOfDataSets();


  vtkDataSet* GetDataSet(int n);

  vtkDataSet* GetDataSet() override { return this->GetDataSet(0); }


  vtkGetObjectMacro(DataSets, vtkDataSetCollection);

  int GetDataSetIndex(vtkDataSet* set);

  void GetBounds(double* bounds);

 
  void SetNewBounds(double* bounds);


  vtkGetMacro(NumberOfRegions, int);

  void GetRegionBounds(int regionID, double bounds[6]);

  void GetRegionDataBounds(int regionID, double bounds[6]);


  void PrintTree();
  void PrintVerboseTree();

  void PrintRegion(int id);

 
  void CreateCellLists(int dataSetIndex, int* regionReqList, int reqListSize);
  void CreateCellLists(vtkDataSet* set, int* regionReqList, int reqListSize);
  void CreateCellLists(int* regionReqList, int listSize);
  void CreateCellLists();


  vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
  vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
  vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);

  void DeleteCellLists();

  vtkIdList* GetCellList(int regionID);

  vtkIdList* GetBoundaryCellList(int regionID);


  vtkIdType GetCellLists(
    vtkIntArray* regions, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
  vtkIdType GetCellLists(
    vtkIntArray* regions, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
  vtkIdType GetCellLists(
    vtkIntArray* regions, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);


  int GetRegionContainingCell(vtkDataSet* set, vtkIdType cellID);
  int GetRegionContainingCell(int set, vtkIdType cellID);
  int GetRegionContainingCell(vtkIdType cellID);

  int* AllGetRegionContainingCell();

  int GetRegionContainingPoint(double x, double y, double z);

  void BuildLocator() override;

  void ForceBuildLocator() override;

 
  int MinimalNumberOfConvexSubRegions(vtkIntArray* regionIdList, double** convexRegionBounds);

  int ViewOrderAllRegionsInDirection(
    const double directionOfProjection[3], vtkIntArray* orderedList);

  int ViewOrderRegionsInDirection(
    vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);

  int ViewOrderAllRegionsFromPosition(
    const double directionOfProjection[3], vtkIntArray* orderedList);

  int ViewOrderRegionsFromPosition(
    vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);


  void BuildLocatorFromPoints(vtkPointSet* pointset);
  void BuildLocatorFromPoints(vtkPoints* ptArray);
  void BuildLocatorFromPoints(vtkPoints** ptArray, int numPtArrays);

  vtkIdTypeArray* BuildMapForDuplicatePoints(float tolerance);


  vtkIdType FindPoint(double* x);
  vtkIdType FindPoint(double x, double y, double z);


  vtkIdType FindClosestPoint(double* x, double& dist2);
  vtkIdType FindClosestPoint(double x, double y, double z, double& dist2);

  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2);


  vtkIdType FindClosestPointInRegion(int regionId, double* x, double& dist2);
  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);

  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result);

  void FindClosestNPoints(int N, const double x[3], vtkIdList* result);

  vtkIdTypeArray* GetPointsInRegion(int regionId);

  void FreeSearchStructure() override;

  void GenerateRepresentation(int level, vtkPolyData* pd) override;

  void GenerateRepresentation(int* regionList, int len, vtkPolyData* pd);


  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
  vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
  vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);

  virtual void PrintTiming(ostream& os, vtkIndent indent);

  virtual int NewGeometry();

  virtual int NewGeometry(vtkDataSet** sets, int numDataSets);

  virtual void InvalidateGeometry();

 
  static vtkKdNode* CopyTree(vtkKdNode* kd);

  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
 
protected:
  vtkKdTree();
  ~vtkKdTree() override;
 
  void BuildLocatorInternal() override;
 
  vtkBSPIntersections* BSPCalculator;
  int UserDefinedCuts;
 
  void SetCalculator(vtkKdNode* kd);
 
  int ProcessUserDefinedCuts(double* bounds);
 
  void SetCuts(vtkBSPCuts* cuts, int userDefined);

 
  void UpdateBuildTime();

 
  int DivideTest(int numberOfPoints, int level);
 
  enum
  {
    XDIM = 0, // don't change these values
    YDIM = 1,
    ZDIM = 2
  };
 
  int ValidDirections;
 
  vtkKdNode* Top;
  vtkKdNode** RegionList; // indexed by region ID
 
  vtkTimerLog* TimerLog;
 
  static void DeleteAllDescendants(vtkKdNode* nd);
 
  void BuildRegionList();
  virtual int SelectCutDirection(vtkKdNode* kd);
  void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }

 
  void GetRegionsAtLevel(int level, vtkKdNode** nodes);

 
  static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);

 
  int GetNumberOfCells();

 
  int GetDataSetsNumberOfCells(int set1, int set2);

 
  void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
  void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);

 
  float* ComputeCellCenters();
  float* ComputeCellCenters(int set);
  float* ComputeCellCenters(vtkDataSet* set);
 
  vtkDataSetCollection* DataSets;

  void UpdateProgress(double amount);


  vtkSetClampMacro(Progress, double, 0.0, 1.0);
  vtkGetMacro(Progress, double);
 
  // So that each suboperation can report progress
  // in [0,1], yet we will be able to report a global
  // progress. Sub-operations must use UpdateSubOperationProgress()
  // for this to work.
  double ProgressScale;
  double ProgressOffset;
 
  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
  // Actual progress is given by
  // (this->ProgressOffset + this->ProgressScale* amount).
  void UpdateSubOperationProgress(double amount);
 
  static void SetNewBounds_(vtkKdNode* kd, double* b, int* fixDim);
  static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
  static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
  static void SetDataBoundsToSpatialBounds(vtkKdNode* kd);
  static void ZeroNumberOfPoints(vtkKdNode* kd);
 
  // Recursive helper for public FindPointsWithinRadius
  void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
 
  // Recursive helper for public FindPointsWithinRadius
  void AddAllPointsInRegion(vtkKdNode* node, vtkIdList* ids);
 
  // Recursive helper for public FindPointsInArea
  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
 
  // Recursive helper for public FindPointsInArea
  void AddAllPointsInRegion(vtkKdNode* node, vtkIdTypeArray* ids);
 
  int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
 
  void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
 
  void SelfRegister(vtkKdNode* kd);
 
  struct cellList_
  {
    vtkDataSet* dataSet; // cell lists for which data set
    int* regionIds;      // nullptr if listing all regions
    int nRegions;
    vtkIdList** cells;
    vtkIdList** boundaryCells;
    vtkIdList* emptyList;
  };
 
  void InitializeCellLists();
  vtkIdList* GetList(int regionId, vtkIdList** which);
 
  void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
 
  void GenerateRepresentationDataBounds(int level, vtkPolyData* pd);
  void _generateRepresentationDataBounds(
    vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
 
  void GenerateRepresentationWholeSpace(int level, vtkPolyData* pd);
  void _generateRepresentationWholeSpace(
    vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
 
  void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
 
  void printTree_(int verbose);
 
  int SearchNeighborsForDuplicate(
    int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
 
  int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
 
  int FindClosestPointInRegion_(int regionId, double x, double y, double z, double& dist2);
 
  int FindClosestPointInSphere(
    double x, double y, double z, double radius, int skipRegion, double& dist2);
 
  int ViewOrderRegionsInDirection_(
    vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
 
  static int ViewOrderRegionsInDirection_P(vtkKdNode* node, vtkIntArray* list,
    vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
 
  int ViewOrderRegionsFromPosition_(
    vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
 
  static int ViewOrderRegionsFromPosition_P(vtkKdNode* node, vtkIntArray* list,
    vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
 
  static int ConvexSubRegions_(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
  static int FoundId(vtkIntArray* idArray, int id);
 
  void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
  int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
  void ClearLastBuildCache();
 
  static void printTree_P(vtkKdNode* kd, int depth, int verbose);
 
  static int MidValue(int dim, float* c1, int nvals, double& coord);
 
  static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
  static float FindMaxLeftHalf(int dim, float* c1, int K);
  static void Select_(int dim, float* X, int* ids, int L, int R, int K);
 
  static int ComputeLevel(vtkKdNode* kd);
  static int SelfOrder(int id, vtkKdNode* kd);
  static int findRegion(vtkKdNode* node, float x, float y, float z);
  static int findRegion(vtkKdNode* node, double x, double y, double z);
 
  static vtkKdNode** GetRegionsAtLevel_(int level, vtkKdNode** nodes, vtkKdNode* kd);
 
  static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
 
  void NewPartitioningRequest(int req);
 
  int NumberOfRegionsOrLess;
  int NumberOfRegionsOrMore;
 
  vtkTypeBool IncludeRegionBoundaryCells;
  double CellBoundsCache[6]; // to optimize IntersectsCell()
 
  vtkTypeBool GenerateRepresentationUsingDataBounds;
 
  struct cellList_ CellList;
 
  // Region Ids, by data set by cell id - this list is large (one
  // int per cell) but accelerates creation of cell lists
 
  int* CellRegionList;
 
  int MinCells;
  int NumberOfRegions; // number of leaf nodes
 
  vtkTypeBool Timing;
  double FudgeFactor; // a very small distance, relative to the dataset's size
 
  // These instance variables are used by the special locator created
  // to find duplicate points. (BuildLocatorFromPoints)
 
  int NumberOfLocatorPoints;
  float* LocatorPoints;
  int* LocatorIds;
  int* LocatorRegionLocation;
 
  float MaxWidth;
 
  // These Last* values are here to save state so we can
  // determine later if k-d tree must be rebuilt.
 
  int LastNumDataSets;
  int LastDataCacheSize;
  vtkDataSet** LastInputDataSets;
  unsigned long* LastDataSetObserverTags;
  int* LastDataSetType;
  double* LastInputDataInfo;
  double* LastBounds;
  vtkIdType* LastNumPoints;
  vtkIdType* LastNumCells;
 
  vtkBSPCuts* Cuts;
  double Progress;
 
  vtkKdTree(const vtkKdTree&) = delete;
  void operator=(const vtkKdTree&) = delete;
};
VTK_ABI_NAMESPACE_END
#endif