VTK  9.1.0
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
52class vtkCommunicator;
53class vtkSubGroup;
54class vtkIntArray;
55class vtkKdNode;
56
57class VTKFILTERSPARALLEL_EXPORT vtkPKdTree : public vtkKdTree
58{
59public:
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
92
102
104
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
142
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
270 int ProcessId, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
272 int ProcessId, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
274 int ProcessId, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
276
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
314protected:
316 ~vtkPKdTree() override;
317
319 int MultiProcessBuildLocator(double* bounds);
320
321private:
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
Used to send/receive messages in a multiprocess environment.
abstract class to specify dataset behavior
Definition: vtkDataSet.h:166
list of point or cell ids
Definition: vtkIdList.h:140
a simple class to control print indentation
Definition: vtkIndent.h:113
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:149
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning.
Definition: vtkKdNode.h:43
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:141
int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels)
static int Select(int dim, float *c1, int *ids, int nvals, double &coord)
void operator=(const vtkKdTree &)=delete
Multiprocessing communication superclass.
Build a k-d tree decomposition of a list of points.
Definition: vtkPKdTree.h:58
int ViewOrderAllProcessesFromPosition(const double cameraPosition[3], vtkIntArray *orderedList)
Return a list of all processes in order from front to back given a camera position.
vtkIdType GetTotalNumberOfCells()
Get the total number of cells distributed across the data files read by all processes.
Definition: vtkPKdTree.h:81
void PrintTiming(ostream &os, vtkIndent indent) override
Print timing of k-d tree build.
int GetCellArrayGlobalRange(const char *name, float range[2])
An added feature of vtkPKdTree is that it will calculate the the global range of field arrays across ...
int GetPointArrayGlobalRange(const char *name, float range[2])
void BuildLocator() override
Build the spatial decomposition.
int CreateProcessCellCountData()
Create tables of counts of cells per process per region.
static const int ContiguousAssignment
Definition: vtkPKdTree.h:125
int GetPointArrayGlobalRange(int arrayIndex, double range[2])
int GetTotalProcessesInRegion(int regionId)
Returns the total number of processes that have data falling within this spatial region.
int GetRegionsCellCountForProcess(int ProcessId, int *count, int len)
Writes to the supplied integer array the number of cells this process has for each region.
int GetRegionAssignmentMapLength()
/ Returns the number of regions in the region assignment map.
Definition: vtkPKdTree.h:163
int AssignRegionsContiguous()
Let the PKdTree class assign a process to each region by assigning contiguous sets of spatial regions...
int MultiProcessBuildLocator(double *bounds)
int GetRegionListForProcess(int processId, vtkIntArray *regions)
Adds the region IDs for which this process has data to the supplied vtkIntArray.
void SetController(vtkMultiProcessController *c)
Set/Get the communicator object.
int GetCellArrayGlobalRange(int arrayIndex, float range[2])
int GetRegionAssignmentList(int procId, vtkIntArray *list)
Writes the list of region IDs assigned to the specified process.
static vtkPKdTree * New()
int GetPointArrayGlobalRange(const char *name, double range[2])
vtkIdType GetCellListsForProcessRegions(int ProcessId, vtkDataSet *set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
After regions have been assigned to processes, I may want to know which cells I have that are in the ...
int ViewOrderAllProcessesInDirection(const double directionOfProjection[3], vtkIntArray *orderedList)
Return a list of all processes in order from front to back given a vector direction of projection.
int AssignRegions(int *map, int numRegions)
Assign spatial regions to processes via a user defined map.
void PrintTables(ostream &os, vtkIndent indent)
int HasData(int processId, int regionId)
Returns 1 if the process has data for the given region, 0 otherwise.
int GetProcessCellCountForRegion(int processId, int regionId)
Returns the number of cells the specified process has in the specified region.
int GetTotalRegionsForProcess(int processId)
Returns the total number of spatial regions that a given process has data for.
int GetProcessesCellCountForRegion(int regionId, int *count, int len)
Writes the number of cells each process has for the region to the supplied list of length len.
int GetPointArrayGlobalRange(int arrayIndex, float range[2])
void SingleProcessBuildLocator()
int GetCellArrayGlobalRange(const char *name, double range[2])
static const int UserDefinedAssignment
Definition: vtkPKdTree.h:126
~vtkPKdTree() override
static const int RoundRobinAssignment
Definition: vtkPKdTree.h:127
vtkIdType GetCellListsForProcessRegions(int ProcessId, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
After regions have been assigned to processes, I may want to know which cells I have that are in the ...
static const int NoRegionAssignment
Definition: vtkPKdTree.h:124
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
int GetProcessAssignedToRegion(int regionId)
Returns the ID of the process assigned to the region.
void GetAllProcessesBorderingOnPoint(float x, float y, float z, vtkIntArray *list)
The k-d tree spatial regions have been assigned to processes.
int GetCellArrayGlobalRange(int arrayIndex, double range[2])
int AssignRegionsRoundRobin()
Let the PKdTree class assign a process to each region in a round robin fashion.
int CreateGlobalDataArrayBounds()
A convenience function which compiles the global bounds of the data arrays across processes.
int GetProcessListForRegion(int regionId, vtkIntArray *processes)
Adds the list of processes having data for the given region to the supplied list, returns the number ...
vtkIdType GetCellListsForProcessRegions(int ProcessId, int set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
After regions have been assigned to processes, I may want to know which cells I have that are in the ...
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
scalable collective communication for a subset of members of a parallel VTK application
Definition: vtkSubGroup.h:52
int vtkIdType
Definition: vtkType.h:332
#define max(a, b)