VTK  9.3.1
vtkPKdTree.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 
28 #ifndef vtkPKdTree_h
29 #define vtkPKdTree_h
30 
31 #include "vtkFiltersParallelModule.h" // For export macro
32 #include "vtkKdTree.h"
33 #include <string> // Instead of using char*
34 #include <vector> // For automatic array memory management
35 
36 VTK_ABI_NAMESPACE_BEGIN
38 class vtkCommunicator;
39 class vtkSubGroup;
40 class vtkIntArray;
41 class vtkKdNode;
42 
43 class VTKFILTERSPARALLEL_EXPORT vtkPKdTree : public vtkKdTree
44 {
45 public:
46  vtkTypeMacro(vtkPKdTree, vtkKdTree);
47 
48  void PrintSelf(ostream& os, vtkIndent indent) override;
49  void PrintTiming(ostream& os, vtkIndent indent) override;
50  void PrintTables(ostream& os, vtkIndent indent);
51 
52  static vtkPKdTree* New();
53 
60  void BuildLocator() override;
61 
67  vtkIdType GetTotalNumberOfCells() { return this->TotalNumCells; }
68 
77  int CreateProcessCellCountData();
78 
87  int CreateGlobalDataArrayBounds();
88 
90 
93  void SetController(vtkMultiProcessController* c);
94  vtkGetObjectMacro(Controller, vtkMultiProcessController);
96 
98 
107  vtkGetMacro(RegionAssignment, int);
109 
110  static const int NoRegionAssignment;
111  static const int ContiguousAssignment;
112  static const int UserDefinedAssignment;
113  static const int RoundRobinAssignment;
114 
120  int AssignRegions(int* map, int numRegions);
121 
127  int AssignRegionsRoundRobin();
128 
137  int AssignRegionsContiguous();
138 
143  const int* GetRegionAssignmentMap() { return this->RegionAssignmentMap.data(); }
144 
146 
149  int GetRegionAssignmentMapLength() { return static_cast<int>(this->RegionAssignmentMap.size()); }
151 
157  int GetRegionAssignmentList(int procId, vtkIntArray* list);
158 
167  void GetAllProcessesBorderingOnPoint(float x, float y, float z, vtkIntArray* list);
168 
172  int GetProcessAssignedToRegion(int regionId);
173 
178  int HasData(int processId, int regionId);
179 
184  int GetProcessCellCountForRegion(int processId, int regionId);
185 
190  int GetTotalProcessesInRegion(int regionId);
191 
197  int GetProcessListForRegion(int regionId, vtkIntArray* processes);
198 
206  int GetProcessesCellCountForRegion(int regionId, int* count, int len);
207 
212  int GetTotalRegionsForProcess(int processId);
213 
218  int GetRegionListForProcess(int processId, vtkIntArray* regions);
219 
227  int GetRegionsCellCountForProcess(int ProcessId, int* count, int len);
228 
230 
255  vtkIdType GetCellListsForProcessRegions(
256  int ProcessId, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
257  vtkIdType GetCellListsForProcessRegions(
258  int ProcessId, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
259  vtkIdType GetCellListsForProcessRegions(
260  int ProcessId, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
262 
270  int ViewOrderAllProcessesInDirection(
271  const double directionOfProjection[3], vtkIntArray* orderedList);
272 
280  int ViewOrderAllProcessesFromPosition(const double cameraPosition[3], vtkIntArray* orderedList);
281 
290  int GetCellArrayGlobalRange(const char* name, float range[2]);
291  int GetPointArrayGlobalRange(const char* name, float range[2]);
292  int GetCellArrayGlobalRange(const char* name, double range[2]);
293  int GetPointArrayGlobalRange(const char* name, double range[2]);
294 
295  int GetCellArrayGlobalRange(int arrayIndex, double range[2]);
296  int GetPointArrayGlobalRange(int arrayIndex, double range[2]);
297  int GetCellArrayGlobalRange(int arrayIndex, float range[2]);
298  int GetPointArrayGlobalRange(int arrayIndex, float range[2]);
299 
300 protected:
301  vtkPKdTree();
302  ~vtkPKdTree() override;
303 
304  void SingleProcessBuildLocator();
305  int MultiProcessBuildLocator(double* bounds);
306 
307 private:
308  int RegionAssignment;
309 
310  vtkMultiProcessController* Controller;
311 
312  vtkSubGroup* SubGroup;
313 
314  void StrDupWithNew(const char* s, std::string& output);
315 
316  int NumProcesses;
317  int MyId;
318 
319  // basic tables - each region is the responsibility of one process, but
320  // one process may be assigned many regions
321 
322  std::vector<int> RegionAssignmentMap; // indexed by region ID
323  std::vector<std::vector<int>> ProcessAssignmentMap; // indexed by process ID
324  std::vector<int> NumRegionsAssigned; // indexed by process ID
325 
326  int UpdateRegionAssignment();
327 
328  // basic tables reflecting the data that was read from disk
329  // by each process
330 
331  std::vector<char> DataLocationMap; // by process, by region
332 
333  std::vector<int> NumProcessesInRegion; // indexed by region ID
334  std::vector<std::vector<int>> ProcessList; // indexed by region ID
335 
336  std::vector<int> NumRegionsInProcess; // indexed by process ID
337  std::vector<std::vector<int>> ParallelRegionList; // indexed by process ID
338 
339  std::vector<std::vector<vtkIdType>> CellCountList; // indexed by region ID
340 
341  std::vector<double> CellDataMin; // global range for data arrays
342  std::vector<double> CellDataMax;
343  std::vector<double> PointDataMin;
344  std::vector<double> PointDataMax;
345  std::vector<std::string> CellDataName;
346  std::vector<std::string> PointDataName;
347  int NumCellArrays;
348  int NumPointArrays;
349 
350  // distribution of indices for select operation
351 
352  int BuildGlobalIndexLists(vtkIdType ncells);
353 
354  std::vector<vtkIdType> StartVal;
355  std::vector<vtkIdType> EndVal;
356  std::vector<vtkIdType> NumCells;
357  vtkIdType TotalNumCells;
358 
359  // local share of points to be partitioned, and local cache
360 
361  int WhoHas(int pos);
362  int _whoHas(int L, int R, int pos);
363  float* GetLocalVal(int pos);
364  float* GetLocalValNext(int pos);
365  void SetLocalVal(int pos, float* val);
366  void ExchangeVals(int pos1, int pos2);
367  void ExchangeLocalVals(int pos1, int pos2);
368 
369  // keep PtArray and PtArray2 as dynamically allocated since it's set as a return
370  // value from parent class method
371  float* PtArray;
372  float* PtArray2;
373  float* CurrentPtArray; // just pointer to other memory but never allocated
374  float* NextPtArray; // just pointer to other memory but never allocated
375  int PtArraySize;
376 
377  std::vector<int> SelectBuffer;
378 
379  // Parallel build of k-d tree
380 
381  int AllCheckForFailure(int rc, const char* where, const char* how);
382  void AllCheckParameters();
383 
385 
389  bool VolumeBounds(double*);
390  int DivideRegion(vtkKdNode* kd, int L, int level, int tag);
391  int BreadthFirstDivide(double* bounds);
392  void enQueueNode(vtkKdNode* kd, int L, int level, int tag);
394 
395  int Select(int dim, int L, int R);
396  void _select(int L, int R, int K, int dim);
397  void DoTransfer(int from, int to, int fromIndex, int toIndex, int count);
398 
399  int* PartitionAboutMyValue(int L, int R, int K, int dim);
400  int* PartitionAboutOtherValue(int L, int R, float T, int dim);
401  int* PartitionSubArray(int L, int R, int K, int dim, int p1, int p2);
402 
403  int CompleteTree();
404 #ifdef YIELDS_INCONSISTENT_REGION_BOUNDARIES
405  void RetrieveData(vtkKdNode* kd, int* buf);
406 #else
407  void ReduceData(vtkKdNode* kd, int* sources);
408  void BroadcastData(vtkKdNode* kd);
409 #endif
410 
411  void GetDataBounds(int L, int K, int R, float dataBounds[12]);
412  void GetLocalMinMax(int L, int R, int me, float* min, float* max);
413 
414  static int FillOutTree(vtkKdNode* kd, int level);
415  static int ComputeDepth(vtkKdNode* kd);
416  static void PackData(vtkKdNode* kd, double* data);
417  static void UnpackData(vtkKdNode* kd, double* data);
418  static void CheckFixRegionBoundaries(vtkKdNode* tree);
419 
420  // list management
421 
422  int AllocateDoubleBuffer();
423  void FreeDoubleBuffer();
424  void SwitchDoubleBuffer();
425  void AllocateSelectBuffer();
426  void FreeSelectBuffer();
427 
428  void InitializeGlobalIndexLists();
429  void AllocateAndZeroGlobalIndexLists();
430  void FreeGlobalIndexLists();
431  void InitializeRegionAssignmentLists();
432  void AllocateAndZeroRegionAssignmentLists();
433  void FreeRegionAssignmentLists();
434  void InitializeProcessDataLists();
435  void AllocateAndZeroProcessDataLists();
436  void FreeProcessDataLists();
437  void InitializeFieldArrayMinMax();
438  void AllocateAndZeroFieldArrayMinMax();
439  void FreeFieldArrayMinMax();
440 
441  void ReleaseTables();
442 
443  // Assigning regions to processors
444 
445  void AddProcessRegions(int procId, vtkKdNode* kd);
446  void BuildRegionListsForProcesses();
447 
448  // Gather process/region data totals
449 
450  bool CollectLocalRegionProcessData(std::vector<int>&); // returns false for failure
451  int BuildRegionProcessTables();
452  int BuildFieldArrayMinMax();
453  void AddEntry(int* list, int len, int id);
454 #ifdef VTK_USE_64BIT_IDS
455  void AddEntry(vtkIdType* list, int len, vtkIdType id);
456 #endif
457  static int BinarySearch(vtkIdType* list, int len, vtkIdType which);
458 
459  static int FindNextLocalArrayIndex(
460  const char* n, const std::vector<std::string>& names, int len, int start = 0);
461 
462  vtkPKdTree(const vtkPKdTree&) = delete;
463  void operator=(const vtkPKdTree&) = delete;
464 };
465 
466 VTK_ABI_NAMESPACE_END
467 #endif
int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels)
void operator=(const vtkKdTree &)=delete
static const int RoundRobinAssignment
Definition: vtkPKdTree.h:113
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning...
Definition: vtkKdNode.h:31
const int * GetRegionAssignmentMap()
Returns the region assignment map where index is the region and value is the processes id for that re...
Definition: vtkPKdTree.h:143
Build a k-d tree decomposition of a list of points.
Definition: vtkPKdTree.h:43
int GetRegionAssignmentMapLength()
/ Returns the number of regions in the region assignment map.
Definition: vtkPKdTree.h:149
abstract class to specify dataset behavior
Definition: vtkDataSet.h:52
vtkIdType GetTotalNumberOfCells()
Get the total number of cells distributed across the data files read by all processes.
Definition: vtkPKdTree.h:67
void BuildLocator() override
Create the k-d tree decomposition of the cells of the data set or data sets.
int vtkIdType
Definition: vtkType.h:315
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:34
a simple class to control print indentation
Definition: vtkIndent.h:28
list of point or cell ids
Definition: vtkIdList.h:22
static const int ContiguousAssignment
Definition: vtkPKdTree.h:111
static int Select(int dim, float *c1, int *ids, int nvals, double &coord)
virtual void PrintTiming(ostream &os, vtkIndent indent)
Print timing of k-d tree build.
static vtkKdTree * New()
scalable collective communication for a subset of members of a parallel VTK application ...
Definition: vtkSubGroup.h:37
static const int NoRegionAssignment
Definition: vtkPKdTree.h:107
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:67
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
static const int UserDefinedAssignment
Definition: vtkPKdTree.h:112
Used to send/receive messages in a multiprocess environment.
#define max(a, b)
Multiprocessing communication superclass.