VTK  9.2.6
vtkPKdTree.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkPKdTree.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 
43 #ifndef vtkPKdTree_h
44 #define vtkPKdTree_h
45 
46 #include "vtkFiltersParallelModule.h" // For export macro
47 #include "vtkKdTree.h"
48 #include <string> // Instead of using char*
49 #include <vector> // For automatic array memory management
50 
52 class vtkCommunicator;
53 class vtkSubGroup;
54 class vtkIntArray;
55 class vtkKdNode;
56 
57 class VTKFILTERSPARALLEL_EXPORT vtkPKdTree : public vtkKdTree
58 {
59 public:
60  vtkTypeMacro(vtkPKdTree, vtkKdTree);
61 
62  void PrintSelf(ostream& os, vtkIndent indent) override;
63  void PrintTiming(ostream& os, vtkIndent indent) override;
64  void PrintTables(ostream& os, vtkIndent indent);
65 
66  static vtkPKdTree* New();
67 
74  void BuildLocator() override;
75 
81  vtkIdType GetTotalNumberOfCells() { return this->TotalNumCells; }
82 
91  int CreateProcessCellCountData();
92 
101  int CreateGlobalDataArrayBounds();
102 
104 
107  void SetController(vtkMultiProcessController* c);
108  vtkGetObjectMacro(Controller, vtkMultiProcessController);
110 
112 
121  vtkGetMacro(RegionAssignment, int);
123 
124  static const int NoRegionAssignment;
125  static const int ContiguousAssignment;
126  static const int UserDefinedAssignment;
127  static const int RoundRobinAssignment;
128 
134  int AssignRegions(int* map, int numRegions);
135 
141  int AssignRegionsRoundRobin();
142 
151  int AssignRegionsContiguous();
152 
157  const int* GetRegionAssignmentMap() { return &this->RegionAssignmentMap[0]; }
158 
160 
163  int GetRegionAssignmentMapLength() { return static_cast<int>(this->RegionAssignmentMap.size()); }
165 
171  int GetRegionAssignmentList(int procId, vtkIntArray* list);
172 
181  void GetAllProcessesBorderingOnPoint(float x, float y, float z, vtkIntArray* list);
182 
186  int GetProcessAssignedToRegion(int regionId);
187 
192  int HasData(int processId, int regionId);
193 
198  int GetProcessCellCountForRegion(int processId, int regionId);
199 
204  int GetTotalProcessesInRegion(int regionId);
205 
211  int GetProcessListForRegion(int regionId, vtkIntArray* processes);
212 
220  int GetProcessesCellCountForRegion(int regionId, int* count, int len);
221 
226  int GetTotalRegionsForProcess(int processId);
227 
232  int GetRegionListForProcess(int processId, vtkIntArray* regions);
233 
241  int GetRegionsCellCountForProcess(int ProcessId, int* count, int len);
242 
244 
269  vtkIdType GetCellListsForProcessRegions(
270  int ProcessId, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
271  vtkIdType GetCellListsForProcessRegions(
272  int ProcessId, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
273  vtkIdType GetCellListsForProcessRegions(
274  int ProcessId, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
276 
284  int ViewOrderAllProcessesInDirection(
285  const double directionOfProjection[3], vtkIntArray* orderedList);
286 
294  int ViewOrderAllProcessesFromPosition(const double cameraPosition[3], vtkIntArray* orderedList);
295 
304  int GetCellArrayGlobalRange(const char* name, float range[2]);
305  int GetPointArrayGlobalRange(const char* name, float range[2]);
306  int GetCellArrayGlobalRange(const char* name, double range[2]);
307  int GetPointArrayGlobalRange(const char* name, double range[2]);
308 
309  int GetCellArrayGlobalRange(int arrayIndex, double range[2]);
310  int GetPointArrayGlobalRange(int arrayIndex, double range[2]);
311  int GetCellArrayGlobalRange(int arrayIndex, float range[2]);
312  int GetPointArrayGlobalRange(int arrayIndex, float range[2]);
313 
314 protected:
315  vtkPKdTree();
316  ~vtkPKdTree() override;
317 
318  void SingleProcessBuildLocator();
319  int MultiProcessBuildLocator(double* bounds);
320 
321 private:
322  int RegionAssignment;
323 
324  vtkMultiProcessController* Controller;
325 
326  vtkSubGroup* SubGroup;
327 
328  void StrDupWithNew(const char* s, std::string& output);
329 
330  int NumProcesses;
331  int MyId;
332 
333  // basic tables - each region is the responsibility of one process, but
334  // one process may be assigned many regions
335 
336  std::vector<int> RegionAssignmentMap; // indexed by region ID
337  std::vector<std::vector<int>> ProcessAssignmentMap; // indexed by process ID
338  std::vector<int> NumRegionsAssigned; // indexed by process ID
339 
340  int UpdateRegionAssignment();
341 
342  // basic tables reflecting the data that was read from disk
343  // by each process
344 
345  std::vector<char> DataLocationMap; // by process, by region
346 
347  std::vector<int> NumProcessesInRegion; // indexed by region ID
348  std::vector<std::vector<int>> ProcessList; // indexed by region ID
349 
350  std::vector<int> NumRegionsInProcess; // indexed by process ID
351  std::vector<std::vector<int>> ParallelRegionList; // indexed by process ID
352 
353  std::vector<std::vector<vtkIdType>> CellCountList; // indexed by region ID
354 
355  std::vector<double> CellDataMin; // global range for data arrays
356  std::vector<double> CellDataMax;
357  std::vector<double> PointDataMin;
358  std::vector<double> PointDataMax;
359  std::vector<std::string> CellDataName;
360  std::vector<std::string> PointDataName;
361  int NumCellArrays;
362  int NumPointArrays;
363 
364  // distribution of indices for select operation
365 
366  int BuildGlobalIndexLists(vtkIdType ncells);
367 
368  std::vector<vtkIdType> StartVal;
369  std::vector<vtkIdType> EndVal;
370  std::vector<vtkIdType> NumCells;
371  vtkIdType TotalNumCells;
372 
373  // local share of points to be partitioned, and local cache
374 
375  int WhoHas(int pos);
376  int _whoHas(int L, int R, int pos);
377  float* GetLocalVal(int pos);
378  float* GetLocalValNext(int pos);
379  void SetLocalVal(int pos, float* val);
380  void ExchangeVals(int pos1, int pos2);
381  void ExchangeLocalVals(int pos1, int pos2);
382 
383  // keep PtArray and PtArray2 as dynamically allocated since it's set as a return
384  // value from parent class method
385  float* PtArray;
386  float* PtArray2;
387  float* CurrentPtArray; // just pointer to other memory but never allocated
388  float* NextPtArray; // just pointer to other memory but never allocated
389  int PtArraySize;
390 
391  std::vector<int> SelectBuffer;
392 
393  // Parallel build of k-d tree
394 
395  int AllCheckForFailure(int rc, const char* where, const char* how);
396  void AllCheckParameters();
397 
399 
403  bool VolumeBounds(double*);
404  int DivideRegion(vtkKdNode* kd, int L, int level, int tag);
405  int BreadthFirstDivide(double* bounds);
406  void enQueueNode(vtkKdNode* kd, int L, int level, int tag);
408 
409  int Select(int dim, int L, int R);
410  void _select(int L, int R, int K, int dim);
411  void DoTransfer(int from, int to, int fromIndex, int toIndex, int count);
412 
413  int* PartitionAboutMyValue(int L, int R, int K, int dim);
414  int* PartitionAboutOtherValue(int L, int R, float T, int dim);
415  int* PartitionSubArray(int L, int R, int K, int dim, int p1, int p2);
416 
417  int CompleteTree();
418 #ifdef YIELDS_INCONSISTENT_REGION_BOUNDARIES
419  void RetrieveData(vtkKdNode* kd, int* buf);
420 #else
421  void ReduceData(vtkKdNode* kd, int* sources);
422  void BroadcastData(vtkKdNode* kd);
423 #endif
424 
425  void GetDataBounds(int L, int K, int R, float dataBounds[12]);
426  void GetLocalMinMax(int L, int R, int me, float* min, float* max);
427 
428  static int FillOutTree(vtkKdNode* kd, int level);
429  static int ComputeDepth(vtkKdNode* kd);
430  static void PackData(vtkKdNode* kd, double* data);
431  static void UnpackData(vtkKdNode* kd, double* data);
432  static void CheckFixRegionBoundaries(vtkKdNode* tree);
433 
434  // list management
435 
436  int AllocateDoubleBuffer();
437  void FreeDoubleBuffer();
438  void SwitchDoubleBuffer();
439  void AllocateSelectBuffer();
440  void FreeSelectBuffer();
441 
442  void InitializeGlobalIndexLists();
443  void AllocateAndZeroGlobalIndexLists();
444  void FreeGlobalIndexLists();
445  void InitializeRegionAssignmentLists();
446  void AllocateAndZeroRegionAssignmentLists();
447  void FreeRegionAssignmentLists();
448  void InitializeProcessDataLists();
449  void AllocateAndZeroProcessDataLists();
450  void FreeProcessDataLists();
451  void InitializeFieldArrayMinMax();
452  void AllocateAndZeroFieldArrayMinMax();
453  void FreeFieldArrayMinMax();
454 
455  void ReleaseTables();
456 
457  // Assigning regions to processors
458 
459  void AddProcessRegions(int procId, vtkKdNode* kd);
460  void BuildRegionListsForProcesses();
461 
462  // Gather process/region data totals
463 
464  bool CollectLocalRegionProcessData(std::vector<int>&); // returns false for failure
465  int BuildRegionProcessTables();
466  int BuildFieldArrayMinMax();
467  void AddEntry(int* list, int len, int id);
468 #ifdef VTK_USE_64BIT_IDS
469  void AddEntry(vtkIdType* list, int len, vtkIdType id);
470 #endif
471  static int BinarySearch(vtkIdType* list, int len, vtkIdType which);
472 
473  static int FindNextLocalArrayIndex(
474  const char* n, const std::vector<std::string>& names, int len, int start = 0);
475 
476  vtkPKdTree(const vtkPKdTree&) = delete;
477  void operator=(const vtkPKdTree&) = delete;
478 };
479 
480 #endif
int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels)
void operator=(const vtkKdTree &)=delete
static const int RoundRobinAssignment
Definition: vtkPKdTree.h:127
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning...
Definition: vtkKdNode.h:45
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:157
Build a k-d tree decomposition of a list of points.
Definition: vtkPKdTree.h:57
int GetRegionAssignmentMapLength()
/ Returns the number of regions in the region assignment map.
Definition: vtkPKdTree.h:163
abstract class to specify dataset behavior
Definition: vtkDataSet.h:62
vtkIdType GetTotalNumberOfCells()
Get the total number of cells distributed across the data files read by all processes.
Definition: vtkPKdTree.h:81
void BuildLocator() override
Create the k-d tree decomposition of the cells of the data set or data sets.
int vtkIdType
Definition: vtkType.h:332
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:45
a simple class to control print indentation
Definition: vtkIndent.h:39
list of point or cell ids
Definition: vtkIdList.h:33
static const int ContiguousAssignment
Definition: vtkPKdTree.h:125
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:51
static const int NoRegionAssignment
Definition: vtkPKdTree.h:121
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:81
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:126
Used to send/receive messages in a multiprocess environment.
#define max(a, b)
Multiprocessing communication superclass.