VTK
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 
42 #ifndef __vtkPKdTree_h
43 #define __vtkPKdTree_h
44 
45 #include "vtkKdTree.h"
46 
48 class vtkCommunicator;
49 class vtkSubGroup;
50 class vtkIntArray;
51 class vtkKdNode;
52 
54 {
55 public:
56  vtkTypeMacro(vtkPKdTree, vtkKdTree);
57 
58 
59  void PrintSelf(ostream& os, vtkIndent indent);
60  void PrintTiming(ostream& os, vtkIndent indent);
61  void PrintTables(ostream& os, vtkIndent indent);
62 
63  static vtkPKdTree *New();
64 
68  void BuildLocator();
69 
73  vtkIdType GetTotalNumberOfCells(){return this->TotalNumCells;}
74 
80  int CreateProcessCellCountData();
81 
87  int CreateGlobalDataArrayBounds();
88 
90 
91  void SetController(vtkMultiProcessController *c);
92  vtkGetObjectMacro(Controller, vtkMultiProcessController);
94 
96 
103  vtkGetMacro(RegionAssignment, int);
105 
106  static const int NoRegionAssignment;
107  static const int ContiguousAssignment;
108  static const int UserDefinedAssignment;
109  static const int RoundRobinAssignment;
110 
114  int AssignRegions(int *map, int numRegions);
115 
119  int AssignRegionsRoundRobin();
120 
126  int AssignRegionsContiguous();
127 
129 
131  const int* GetRegionAssignmentMap()
132  { return this->RegionAssignmentMap; }
134 
136 
137  vtkGetMacro(RegionAssignmentMapLength, int);
139 
143  int GetRegionAssignmentList(int procId, vtkIntArray *list);
144 
146 
151  void GetAllProcessesBorderingOnPoint(float x, float y, float z,
152  vtkIntArray *list);
154 
156  int GetProcessAssignedToRegion(int regionId);
157 
159  int HasData(int processId, int regionId);
160 
163  int GetProcessCellCountForRegion(int processId, int regionId);
164 
167  int GetTotalProcessesInRegion(int regionId);
168 
171  int GetProcessListForRegion(int regionId, vtkIntArray *processes);
172 
177  int GetProcessesCellCountForRegion(int regionId, int *count, int len);
178 
181  int GetTotalRegionsForProcess(int processId);
182 
185  int GetRegionListForProcess(int processId, vtkIntArray *regions);
186 
191  int GetRegionsCellCountForProcess(int ProcessId, int *count, int len);
192 
194 
211  vtkIdType GetCellListsForProcessRegions(int ProcessId, int set,
212  vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
213  vtkIdType GetCellListsForProcessRegions(int ProcessId, vtkDataSet *set,
214  vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
215  vtkIdType GetCellListsForProcessRegions(int ProcessId,
216  vtkIdList *inRegionCells,
217  vtkIdList *onBoundaryCells);
219 
221 
224  VTK_LEGACY(int DepthOrderAllProcesses(double *directionOfProjection,
225  vtkIntArray *orderedList));
227 
229 
234  int ViewOrderAllProcessesInDirection(const double directionOfProjection[3],
235  vtkIntArray *orderedList);
237 
239 
244  int ViewOrderAllProcessesFromPosition(const double cameraPosition[3],
245  vtkIntArray *orderedList);
247 
253  int GetCellArrayGlobalRange(const char *name, float range[2]);
254  int GetPointArrayGlobalRange(const char *name, float range[2]);
255  int GetCellArrayGlobalRange(const char *name, double range[2]);
256  int GetPointArrayGlobalRange(const char *name, double range[2]);
257 
258  int GetCellArrayGlobalRange(int arrayIndex, double range[2]);
259  int GetPointArrayGlobalRange(int arrayIndex, double range[2]);
260  int GetCellArrayGlobalRange(int arrayIndex, float range[2]);
261  int GetPointArrayGlobalRange(int arrayIndex, float range[2]);
262 
263 protected:
264 
265  vtkPKdTree();
266  ~vtkPKdTree();
267 
268  void SingleProcessBuildLocator();
269  int MultiProcessBuildLocator(double *bounds);
270 
271 private:
272 
273  int RegionAssignment;
274 
275  vtkMultiProcessController *Controller;
276 
277  vtkSubGroup *SubGroup;
278 
279  static char *StrDupWithNew(const char *s);
280 
281  int NumProcesses;
282  int MyId;
283 
284  // basic tables - each region is the responsibility of one process, but
285  // one process may be assigned many regions
286 
287  int *RegionAssignmentMap; // indexed by region ID
288  int RegionAssignmentMapLength;
289  int **ProcessAssignmentMap; // indexed by process ID
290  int *NumRegionsAssigned; // indexed by process ID
291 
292  int UpdateRegionAssignment();
293 
294  // basic tables reflecting the data that was read from disk
295  // by each process
296 
297  char *DataLocationMap; // by process, by region
298 
299  int *NumProcessesInRegion; // indexed by region ID
300  int **ProcessList; // indexed by region ID
301 
302  int *NumRegionsInProcess; // indexed by process ID
303  int **RegionList; // indexed by process ID
304 
305  vtkIdType **CellCountList; // indexed by region ID
306 
307  double *CellDataMin; // global range for data arrays
308  double *CellDataMax;
309  double *PointDataMin;
310  double *PointDataMax;
311  char **CellDataName;
312  char **PointDataName;
313  int NumCellArrays;
314  int NumPointArrays;
315 
316  // distribution of indices for select operation
317 
318  int BuildGlobalIndexLists(vtkIdType ncells);
319 
320  vtkIdType *StartVal;
321  vtkIdType *EndVal;
322  vtkIdType *NumCells;
323  vtkIdType TotalNumCells;
324 
325  // local share of points to be partitioned, and local cache
326 
327  int WhoHas(int pos);
328  int _whoHas(int L, int R, int pos);
329  float *GetLocalVal(int pos);
330  float *GetLocalValNext(int pos);
331  void SetLocalVal(int pos, float *val);
332  void ExchangeVals(int pos1, int pos2);
333  void ExchangeLocalVals(int pos1, int pos2);
334 
335  float *PtArray;
336  float *PtArray2;
337  float *CurrentPtArray;
338  float *NextPtArray;
339  int PtArraySize;
340 
341  int *SelectBuffer;
342 
343  // Parallel build of k-d tree
344 
345  int AllCheckForFailure(int rc, const char *where, const char *how);
346  void AllCheckParameters();
347 
349 
351  bool VolumeBounds(double*);
352  int DivideRegion(vtkKdNode *kd, int L, int level, int tag);
353  int BreadthFirstDivide(double *bounds);
354  void enQueueNode(vtkKdNode *kd, int L, int level, int tag);
356 
357  int Select(int dim, int L, int R);
358  void _select(int L, int R, int K, int dim);
359  void DoTransfer(int from, int to, int fromIndex, int toIndex, int count);
360 
361  int *PartitionAboutMyValue(int L, int R, int K, int dim);
362  int *PartitionAboutOtherValue(int L, int R, float T, int dim);
363  int *PartitionSubArray(int L, int R, int K, int dim, int p1, int p2);
364 
365  int CompleteTree();
366 #ifdef YIELDS_INCONSISTENT_REGION_BOUNDARIES
367  void RetrieveData(vtkKdNode *kd, int *buf);
368 #else
369  void ReduceData(vtkKdNode *kd, int *sources);
370  void BroadcastData(vtkKdNode *kd);
371 #endif
372 
373  float *DataBounds(int L, int K, int R);
374  void GetLocalMinMax(int L, int R, int me, float *min, float *max);
375 
376  static int FillOutTree(vtkKdNode *kd, int level);
377  static int ComputeDepth(vtkKdNode *kd);
378  static void PackData(vtkKdNode *kd, double *data);
379  static void UnpackData(vtkKdNode *kd, double *data);
380  static void CheckFixRegionBoundaries(vtkKdNode *tree);
381 
382  // list management
383 
384  int AllocateDoubleBuffer();
385  void FreeDoubleBuffer();
386  void SwitchDoubleBuffer();
387  int AllocateSelectBuffer();
388  void FreeSelectBuffer();
389 
390  void InitializeGlobalIndexLists();
391  int AllocateAndZeroGlobalIndexLists();
392  void FreeGlobalIndexLists();
393  void InitializeRegionAssignmentLists();
394  int AllocateAndZeroRegionAssignmentLists();
395  void FreeRegionAssignmentLists();
396  void InitializeProcessDataLists();
397  int AllocateAndZeroProcessDataLists();
398  void FreeProcessDataLists();
399  void InitializeFieldArrayMinMax();
400  int AllocateAndZeroFieldArrayMinMax();
401  void FreeFieldArrayMinMax();
402 
403  void ReleaseTables();
404 
405  // Assigning regions to processors
406 
407  void AddProcessRegions(int procId, vtkKdNode *kd);
408  void BuildRegionListsForProcesses();
409 
410  // Gather process/region data totals
411 
412  int *CollectLocalRegionProcessData();
413  int BuildRegionProcessTables();
414  int BuildFieldArrayMinMax();
415  void AddEntry(int *list, int len, int id);
416 #ifdef VTK_USE_64BIT_IDS
417  void AddEntry(vtkIdType *list, int len, vtkIdType id);
418 #endif
419  static int BinarySearch(vtkIdType *list, int len, vtkIdType which);
420 
421  static int FindNextLocalArrayIndex(const char *n, const char **names, int len, int start=0);
422 
423  vtkPKdTree(const vtkPKdTree&); // Not implemented
424  void operator=(const vtkPKdTree&); // Not implemented
425 };
426 
427 #endif