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 20 /** 21 * @class vtkPKdTree 22 * @brief Build a k-d tree decomposition of a list of points. 23 * 24 * 25 * Build, in parallel, a k-d tree decomposition of one or more 26 * vtkDataSets distributed across processors. We assume each 27 * process has read in one portion of a large distributed data set. 28 * When done, each process has access to the k-d tree structure, 29 * can obtain information about which process contains 30 * data for each spatial region, and can depth sort the spatial 31 * regions. 32 * 33 * This class can also assign spatial regions to processors, based 34 * on one of several region assignment schemes. By default 35 * a contiguous, convex region is assigned to each process. Several 36 * queries return information about how many and what cells I have 37 * that lie in a region assigned to another process. 38 * 39 * @sa 40 * vtkKdTree 41 */ 42 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 51 class vtkMultiProcessController; 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 68 /** 69 * Build the spatial decomposition. Call this explicitly 70 * after changing any parameters affecting the build of the 71 * tree. It must be called by all processes in the parallel 72 * application, or it will hang. 73 */ 74 void BuildLocator() override; 75 76 /** 77 * Get the total number of cells distributed across the data 78 * files read by all processes. You must have called BuildLocator 79 * before calling this method. 80 */ GetTotalNumberOfCells()81 vtkIdType GetTotalNumberOfCells() { return this->TotalNumCells; } 82 83 /** 84 * Create tables of counts of cells per process per region. 85 * These tables can be accessed with queries like 86 * "HasData", "GetProcessCellCountForRegion", and so on. 87 * You must have called BuildLocator() beforehand. This 88 * method must be called by all processes or it will hang. 89 * Returns 1 on error, 0 when no error. 90 */ 91 int CreateProcessCellCountData(); 92 93 /** 94 * A convenience function which compiles the global 95 * bounds of the data arrays across processes. 96 * These bounds can be accessed with 97 * "GetCellArrayGlobalRange" and "GetPointArrayGlobalRange". 98 * This method must be called by all processes or it will hang. 99 * Returns 1 on error, 0 when no error. 100 */ 101 int CreateGlobalDataArrayBounds(); 102 103 ///@{ 104 /** 105 * Set/Get the communicator object 106 */ 107 void SetController(vtkMultiProcessController* c); 108 vtkGetObjectMacro(Controller, vtkMultiProcessController); 109 ///@} 110 111 ///@{ 112 /** 113 * The PKdTree class can assign spatial regions to processors after 114 * building the k-d tree, using one of several partitioning criteria. 115 * These functions Set/Get whether this assignment is computed. 116 * The default is "Off", no assignment is computed. If "On", and 117 * no assignment scheme is specified, contiguous assignment will be 118 * computed. Specifying an assignment scheme (with AssignRegions*()) 119 * automatically turns on RegionAssignment. 120 */ 121 vtkGetMacro(RegionAssignment, int); 122 ///@} 123 124 static const int NoRegionAssignment; 125 static const int ContiguousAssignment; 126 static const int UserDefinedAssignment; 127 static const int RoundRobinAssignment; 128 129 /** 130 * Assign spatial regions to processes via a user defined map. 131 * The user-supplied map is indexed by region ID, and provides a 132 * process ID for each region. 133 */ 134 int AssignRegions(int* map, int numRegions); 135 136 /** 137 * Let the PKdTree class assign a process to each region in a 138 * round robin fashion. If the k-d tree has not yet been 139 * built, the regions will be assigned after BuildLocator executes. 140 */ 141 int AssignRegionsRoundRobin(); 142 143 /** 144 * Let the PKdTree class assign a process to each region 145 * by assigning contiguous sets of spatial regions to each 146 * process. The set of regions assigned to each process will 147 * always have a union that is a convex space (a box). 148 * If the k-d tree has not yet been built, the regions 149 * will be assigned after BuildLocator executes. 150 */ 151 int AssignRegionsContiguous(); 152 153 /** 154 * Returns the region assignment map where index is the region and value is 155 * the processes id for that region. 156 */ GetRegionAssignmentMap()157 const int* GetRegionAssignmentMap() { return &this->RegionAssignmentMap[0]; } 158 159 ///@{ 160 /** 161 * / Returns the number of regions in the region assignment map. 162 */ GetRegionAssignmentMapLength()163 int GetRegionAssignmentMapLength() { return static_cast<int>(this->RegionAssignmentMap.size()); } 164 ///@} 165 166 /** 167 * Writes the list of region IDs assigned to the specified 168 * process. Regions IDs start at 0 and increase by 1 from there. 169 * Returns the number of regions in the list. 170 */ 171 int GetRegionAssignmentList(int procId, vtkIntArray* list); 172 173 /** 174 * The k-d tree spatial regions have been assigned to processes. 175 * Given a point on the boundary of one of the regions, this 176 * method creates a list of all processes whose region 177 * boundaries include that point. This may be required when 178 * looking for processes that have cells adjacent to the cells 179 * of a given process. 180 */ 181 void GetAllProcessesBorderingOnPoint(float x, float y, float z, vtkIntArray* list); 182 183 /** 184 * Returns the ID of the process assigned to the region. 185 */ 186 int GetProcessAssignedToRegion(int regionId); 187 188 /** 189 * Returns 1 if the process has data for the given region, 190 * 0 otherwise. 191 */ 192 int HasData(int processId, int regionId); 193 194 /** 195 * Returns the number of cells the specified process has in the 196 * specified region. 197 */ 198 int GetProcessCellCountForRegion(int processId, int regionId); 199 200 /** 201 * Returns the total number of processes that have data 202 * falling within this spatial region. 203 */ 204 int GetTotalProcessesInRegion(int regionId); 205 206 /** 207 * Adds the list of processes having data for the given 208 * region to the supplied list, returns the number of 209 * processes added. 210 */ 211 int GetProcessListForRegion(int regionId, vtkIntArray* processes); 212 213 /** 214 * Writes the number of cells each process has for the region 215 * to the supplied list of length len. Returns the number of 216 * cell counts written. The order of the cell counts corresponds 217 * to the order of process IDs in the process list returned by 218 * GetProcessListForRegion. 219 */ 220 int GetProcessesCellCountForRegion(int regionId, int* count, int len); 221 222 /** 223 * Returns the total number of spatial regions that a given 224 * process has data for. 225 */ 226 int GetTotalRegionsForProcess(int processId); 227 228 /** 229 * Adds the region IDs for which this process has data to 230 * the supplied vtkIntArray. Returns the number of regions. 231 */ 232 int GetRegionListForProcess(int processId, vtkIntArray* regions); 233 234 /** 235 * Writes to the supplied integer array the number of cells this 236 * process has for each region. Returns the number of 237 * cell counts written. The order of the cell counts corresponds 238 * to the order of region IDs in the region list returned by 239 * GetRegionListForProcess. 240 */ 241 int GetRegionsCellCountForProcess(int ProcessId, int* count, int len); 242 243 ///@{ 244 /** 245 * After regions have been assigned to processes, I may want to know 246 * which cells I have that are in the regions assigned to a particular 247 * process. 248 249 * This method takes a process ID and two vtkIdLists. It 250 * writes to the first list the IDs of the cells 251 * contained in the process' regions. (That is, their cell 252 * centroid is contained in the region.) To the second list it 253 * write the IDs of the cells which intersect the process' regions 254 * but whose cell centroid lies elsewhere. 255 256 * The total number of cell IDs written to both lists is returned. 257 * Either list pointer passed in can be nullptr, and it will be ignored. 258 * If there are multiple data sets, you must specify which data set 259 * you wish cell IDs for. 260 261 * The caller should delete these two lists when done. This method 262 * uses the cell lists created in vtkKdTree::CreateCellLists(). 263 * If the cell lists for the process' regions do not exist, this 264 * method will first build the cell lists for all regions by calling 265 * CreateCellLists(). You must remember to DeleteCellLists() when 266 * done with all calls to this method, as cell lists can require a 267 * great deal of memory. 268 */ 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); 275 ///@} 276 277 /** 278 * Return a list of all processes in order from front to back given a 279 * vector direction of projection. Use this to do visibility sorts 280 * in parallel projection mode. `orderedList' will be resized to the number 281 * of processes. The return value is the number of processes. 282 * \pre orderedList_exists: orderedList!=0 283 */ 284 int ViewOrderAllProcessesInDirection( 285 const double directionOfProjection[3], vtkIntArray* orderedList); 286 287 /** 288 * Return a list of all processes in order from front to back given a 289 * camera position. Use this to do visibility sorts in perspective 290 * projection mode. `orderedList' will be resized to the number 291 * of processes. The return value is the number of processes. 292 * \pre orderedList_exists: orderedList!=0 293 */ 294 int ViewOrderAllProcessesFromPosition(const double cameraPosition[3], vtkIntArray* orderedList); 295 296 /** 297 * An added feature of vtkPKdTree is that it will calculate the 298 * the global range of field arrays across all processes. You 299 * call CreateGlobalDataArrayBounds() to do this calculation. 300 * Then the following methods return the ranges. 301 * Returns 1 on error, 0 otherwise. 302 */ 303 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 398 ///@{ 399 /** 400 * Return the global bounds over all processes. Returns true 401 * if successful and false otherwise. 402 */ 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); 407 ///@} 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 481