vtkPKdTree.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 vtkPKdTree_h
#define vtkPKdTree_h
 
#include "vtkFiltersParallelModule.h" // For export macro
#include "vtkKdTree.h"
#include <string> // Instead of using char*
#include <vector> // For automatic array memory management
 
VTK_ABI_NAMESPACE_BEGIN
class vtkMultiProcessController;
class vtkCommunicator;
class vtkSubGroup;
class vtkIntArray;
class vtkKdNode;
 
class VTKFILTERSPARALLEL_EXPORT vtkPKdTree : public vtkKdTree
{
public:
  vtkTypeMacro(vtkPKdTree, vtkKdTree);
 
  void PrintSelf(ostream& os, vtkIndent indent) override;
  void PrintTiming(ostream& os, vtkIndent indent) override;
  void PrintTables(ostream& os, vtkIndent indent);
 
  static vtkPKdTree* New();

  void BuildLocator() override;

  vtkIdType GetTotalNumberOfCells() { return this->TotalNumCells; }

  int CreateProcessCellCountData();

  int CreateGlobalDataArrayBounds();


  void SetController(vtkMultiProcessController* c);
  vtkGetObjectMacro(Controller, vtkMultiProcessController);


  vtkGetMacro(RegionAssignment, int);
 
  static const int NoRegionAssignment;
  static const int ContiguousAssignment;
  static const int UserDefinedAssignment;
  static const int RoundRobinAssignment;

  int AssignRegions(int* map, int numRegions);

  int AssignRegionsRoundRobin();

  int AssignRegionsContiguous();

  const int* GetRegionAssignmentMap() { return this->RegionAssignmentMap.data(); }


  int GetRegionAssignmentMapLength() { return static_cast<int>(this->RegionAssignmentMap.size()); }

  int GetRegionAssignmentList(int procId, vtkIntArray* list);

  void GetAllProcessesBorderingOnPoint(float x, float y, float z, vtkIntArray* list);

  int GetProcessAssignedToRegion(int regionId);

  int HasData(int processId, int regionId);

  int GetProcessCellCountForRegion(int processId, int regionId);

  int GetTotalProcessesInRegion(int regionId);

  int GetProcessListForRegion(int regionId, vtkIntArray* processes);

  int GetProcessesCellCountForRegion(int regionId, int* count, int len);

  int GetTotalRegionsForProcess(int processId);

  int GetRegionListForProcess(int processId, vtkIntArray* regions);

  int GetRegionsCellCountForProcess(int ProcessId, int* count, int len);


  vtkIdType GetCellListsForProcessRegions(
    int ProcessId, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
  vtkIdType GetCellListsForProcessRegions(
    int ProcessId, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
  vtkIdType GetCellListsForProcessRegions(
    int ProcessId, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);

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

  int ViewOrderAllProcessesFromPosition(const double cameraPosition[3], vtkIntArray* orderedList);

 
  int GetCellArrayGlobalRange(const char* name, float range[2]);
  int GetPointArrayGlobalRange(const char* name, float range[2]);
  int GetCellArrayGlobalRange(const char* name, double range[2]);
  int GetPointArrayGlobalRange(const char* name, double range[2]);
 
  int GetCellArrayGlobalRange(int arrayIndex, double range[2]);
  int GetPointArrayGlobalRange(int arrayIndex, double range[2]);
  int GetCellArrayGlobalRange(int arrayIndex, float range[2]);
  int GetPointArrayGlobalRange(int arrayIndex, float range[2]);
 
protected:
  vtkPKdTree();
  ~vtkPKdTree() override;
 
  void SingleProcessBuildLocator();
  int MultiProcessBuildLocator(double* bounds);
 
private:
  int RegionAssignment;
 
  vtkMultiProcessController* Controller;
 
  vtkSubGroup* SubGroup;
 
  void StrDupWithNew(const char* s, std::string& output);
 
  int NumProcesses;
  int MyId;
 
  // basic tables - each region is the responsibility of one process, but
  //                one process may be assigned many regions
 
  std::vector<int> RegionAssignmentMap;               // indexed by region ID
  std::vector<std::vector<int>> ProcessAssignmentMap; // indexed by process ID
  std::vector<int> NumRegionsAssigned;                // indexed by process ID
 
  int UpdateRegionAssignment();
 
  // basic tables reflecting the data that was read from disk
  // by each process
 
  std::vector<char> DataLocationMap; // by process, by region
 
  std::vector<int> NumProcessesInRegion;     // indexed by region ID
  std::vector<std::vector<int>> ProcessList; // indexed by region ID
 
  std::vector<int> NumRegionsInProcess;             // indexed by process ID
  std::vector<std::vector<int>> ParallelRegionList; // indexed by process ID
 
  std::vector<std::vector<vtkIdType>> CellCountList; // indexed by region ID
 
  std::vector<double> CellDataMin; // global range for data arrays
  std::vector<double> CellDataMax;
  std::vector<double> PointDataMin;
  std::vector<double> PointDataMax;
  std::vector<std::string> CellDataName;
  std::vector<std::string> PointDataName;
  int NumCellArrays;
  int NumPointArrays;
 
  // distribution of indices for select operation
 
  int BuildGlobalIndexLists(vtkIdType ncells);
 
  std::vector<vtkIdType> StartVal;
  std::vector<vtkIdType> EndVal;
  std::vector<vtkIdType> NumCells;
  vtkIdType TotalNumCells;
 
  // local share of points to be partitioned, and local cache
 
  int WhoHas(int pos);
  int _whoHas(int L, int R, int pos);
  float* GetLocalVal(int pos);
  float* GetLocalValNext(int pos);
  void SetLocalVal(int pos, float* val);
  void ExchangeVals(int pos1, int pos2);
  void ExchangeLocalVals(int pos1, int pos2);
 
  // keep PtArray and PtArray2 as dynamically allocated since it's set as a return
  // value from parent class method
  float* PtArray;
  float* PtArray2;
  float* CurrentPtArray; // just pointer to other memory but never allocated
  float* NextPtArray;    // just pointer to other memory but never allocated
  int PtArraySize;
 
  std::vector<int> SelectBuffer;
 
  // Parallel build of k-d tree
 
  int AllCheckForFailure(int rc, const char* where, const char* how);
  void AllCheckParameters();


  bool VolumeBounds(double*);
  int DivideRegion(vtkKdNode* kd, int L, int level, int tag);
  int BreadthFirstDivide(double* bounds);
  void enQueueNode(vtkKdNode* kd, int L, int level, int tag);
 
  int Select(int dim, int L, int R);
  void _select(int L, int R, int K, int dim);
  void DoTransfer(int from, int to, int fromIndex, int toIndex, int count);
 
  int* PartitionAboutMyValue(int L, int R, int K, int dim);
  int* PartitionAboutOtherValue(int L, int R, float T, int dim);
  int* PartitionSubArray(int L, int R, int K, int dim, int p1, int p2);
 
  int CompleteTree();
#ifdef YIELDS_INCONSISTENT_REGION_BOUNDARIES
  void RetrieveData(vtkKdNode* kd, int* buf);
#else
  void ReduceData(vtkKdNode* kd, int* sources);
  void BroadcastData(vtkKdNode* kd);
#endif
 
  void GetDataBounds(int L, int K, int R, float dataBounds[12]);
  void GetLocalMinMax(int L, int R, int me, float* min, float* max);
 
  static int FillOutTree(vtkKdNode* kd, int level);
  static int ComputeDepth(vtkKdNode* kd);
  static void PackData(vtkKdNode* kd, double* data);
  static void UnpackData(vtkKdNode* kd, double* data);
  static void CheckFixRegionBoundaries(vtkKdNode* tree);
 
  // list management
 
  int AllocateDoubleBuffer();
  void FreeDoubleBuffer();
  void SwitchDoubleBuffer();
  void AllocateSelectBuffer();
  void FreeSelectBuffer();
 
  void InitializeGlobalIndexLists();
  void AllocateAndZeroGlobalIndexLists();
  void FreeGlobalIndexLists();
  void InitializeRegionAssignmentLists();
  void AllocateAndZeroRegionAssignmentLists();
  void FreeRegionAssignmentLists();
  void InitializeProcessDataLists();
  void AllocateAndZeroProcessDataLists();
  void FreeProcessDataLists();
  void InitializeFieldArrayMinMax();
  void AllocateAndZeroFieldArrayMinMax();
  void FreeFieldArrayMinMax();
 
  void ReleaseTables();
 
  // Assigning regions to processors
 
  void AddProcessRegions(int procId, vtkKdNode* kd);
  void BuildRegionListsForProcesses();
 
  // Gather process/region data totals
 
  bool CollectLocalRegionProcessData(std::vector<int>&); // returns false for failure
  int BuildRegionProcessTables();
  int BuildFieldArrayMinMax();
  void AddEntry(int* list, int len, int id);
#ifdef VTK_USE_64BIT_IDS
  void AddEntry(vtkIdType* list, int len, vtkIdType id);
#endif
  static int BinarySearch(vtkIdType* list, int len, vtkIdType which);
 
  static int FindNextLocalArrayIndex(
    const char* n, const std::vector<std::string>& names, int len, int start = 0);
 
  vtkPKdTree(const vtkPKdTree&) = delete;
  void operator=(const vtkPKdTree&) = delete;