vtkPKdTree.h

Go to the documentation of this file.

/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkPKdTree.h

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.

=========================================================================*/
/*----------------------------------------------------------------------------
 Copyright (c) Sandia Corporation
 See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
----------------------------------------------------------------------------*/

#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

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[0]; }


  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;
};

#endif