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
43#ifndef vtkPKdTree_h
44#define vtkPKdTree_h
45
46#include "vtkFiltersParallelModule.h" // For export macro
47#include "vtkKdTree.h"
48
50class vtkCommunicator;
51class vtkSubGroup;
52class vtkIntArray;
53class vtkKdNode;
54
55class VTKFILTERSPARALLEL_EXPORT vtkPKdTree : public vtkKdTree
56{
57public:
58 vtkTypeMacro(vtkPKdTree, vtkKdTree);
59
60
61 void PrintSelf(ostream& os, vtkIndent indent);
62 void PrintTiming(ostream& os, vtkIndent indent);
63 void PrintTables(ostream& os, vtkIndent indent);
64
65 static vtkPKdTree *New();
66
74
80 vtkIdType GetTotalNumberOfCells(){return this->TotalNumCells;}
81
91
101
103
107 vtkGetObjectMacro(Controller, vtkMultiProcessController);
109
111
120 vtkGetMacro(RegionAssignment, int);
122
123 static const int NoRegionAssignment;
124 static const int ContiguousAssignment;
125 static const int UserDefinedAssignment;
126 static const int RoundRobinAssignment;
127
133 int AssignRegions(int *map, int numRegions);
134
141
151
157 { return this->RegionAssignmentMap; }
158
160
163 vtkGetMacro(RegionAssignmentMapLength, int);
165
171 int GetRegionAssignmentList(int procId, vtkIntArray *list);
172
181 void GetAllProcessesBorderingOnPoint(float x, float y, float z,
182 vtkIntArray *list);
183
187 int GetProcessAssignedToRegion(int regionId);
188
193 int HasData(int processId, int regionId);
194
199 int GetProcessCellCountForRegion(int processId, int regionId);
200
205 int GetTotalProcessesInRegion(int regionId);
206
212 int GetProcessListForRegion(int regionId, vtkIntArray *processes);
213
221 int GetProcessesCellCountForRegion(int regionId, int *count, int len);
222
227 int GetTotalRegionsForProcess(int processId);
228
233 int GetRegionListForProcess(int processId, vtkIntArray *regions);
234
242 int GetRegionsCellCountForProcess(int ProcessId, int *count, int len);
243
245
271 vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
273 vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
275 vtkIdList *inRegionCells,
276 vtkIdList *onBoundaryCells);
278
286 int ViewOrderAllProcessesInDirection(const double directionOfProjection[3],
287 vtkIntArray *orderedList);
288
296 int ViewOrderAllProcessesFromPosition(const double cameraPosition[3],
297 vtkIntArray *orderedList);
298
307 int GetCellArrayGlobalRange(const char *name, float range[2]);
308 int GetPointArrayGlobalRange(const char *name, float range[2]);
309 int GetCellArrayGlobalRange(const char *name, double range[2]);
310 int GetPointArrayGlobalRange(const char *name, double range[2]);
311
312 int GetCellArrayGlobalRange(int arrayIndex, double range[2]);
313 int GetPointArrayGlobalRange(int arrayIndex, double range[2]);
314 int GetCellArrayGlobalRange(int arrayIndex, float range[2]);
315 int GetPointArrayGlobalRange(int arrayIndex, float range[2]);
316
317protected:
318
321
323 int MultiProcessBuildLocator(double *bounds);
324
325private:
326
327 int RegionAssignment;
328
329 vtkMultiProcessController *Controller;
330
331 vtkSubGroup *SubGroup;
332
333 static char *StrDupWithNew(const char *s);
334
335 int NumProcesses;
336 int MyId;
337
338 // basic tables - each region is the responsibility of one process, but
339 // one process may be assigned many regions
340
341 int *RegionAssignmentMap; // indexed by region ID
342 int RegionAssignmentMapLength;
343 int **ProcessAssignmentMap; // indexed by process ID
344 int *NumRegionsAssigned; // indexed by process ID
345
346 int UpdateRegionAssignment();
347
348 // basic tables reflecting the data that was read from disk
349 // by each process
350
351 char *DataLocationMap; // by process, by region
352
353 int *NumProcessesInRegion; // indexed by region ID
354 int **ProcessList; // indexed by region ID
355
356 int *NumRegionsInProcess; // indexed by process ID
357 int **RegionList; // indexed by process ID
358
359 vtkIdType **CellCountList; // indexed by region ID
360
361 double *CellDataMin; // global range for data arrays
362 double *CellDataMax;
363 double *PointDataMin;
364 double *PointDataMax;
365 char **CellDataName;
366 char **PointDataName;
367 int NumCellArrays;
368 int NumPointArrays;
369
370 // distribution of indices for select operation
371
372 int BuildGlobalIndexLists(vtkIdType ncells);
373
374 vtkIdType *StartVal;
375 vtkIdType *EndVal;
376 vtkIdType *NumCells;
377 vtkIdType TotalNumCells;
378
379 // local share of points to be partitioned, and local cache
380
381 int WhoHas(int pos);
382 int _whoHas(int L, int R, int pos);
383 float *GetLocalVal(int pos);
384 float *GetLocalValNext(int pos);
385 void SetLocalVal(int pos, float *val);
386 void ExchangeVals(int pos1, int pos2);
387 void ExchangeLocalVals(int pos1, int pos2);
388
389 float *PtArray;
390 float *PtArray2;
391 float *CurrentPtArray;
392 float *NextPtArray;
393 int PtArraySize;
394
395 int *SelectBuffer;
396
397 // Parallel build of k-d tree
398
399 int AllCheckForFailure(int rc, const char *where, const char *how);
400 void AllCheckParameters();
401
403
407 bool VolumeBounds(double*);
408 int DivideRegion(vtkKdNode *kd, int L, int level, int tag);
409 int BreadthFirstDivide(double *bounds);
410 void enQueueNode(vtkKdNode *kd, int L, int level, int tag);
412
413 int Select(int dim, int L, int R);
414 void _select(int L, int R, int K, int dim);
415 void DoTransfer(int from, int to, int fromIndex, int toIndex, int count);
416
417 int *PartitionAboutMyValue(int L, int R, int K, int dim);
418 int *PartitionAboutOtherValue(int L, int R, float T, int dim);
419 int *PartitionSubArray(int L, int R, int K, int dim, int p1, int p2);
420
421 int CompleteTree();
422#ifdef YIELDS_INCONSISTENT_REGION_BOUNDARIES
423 void RetrieveData(vtkKdNode *kd, int *buf);
424#else
425 void ReduceData(vtkKdNode *kd, int *sources);
426 void BroadcastData(vtkKdNode *kd);
427#endif
428
429 float *DataBounds(int L, int K, int R);
430 void GetLocalMinMax(int L, int R, int me, float *min, float *max);
431
432 static int FillOutTree(vtkKdNode *kd, int level);
433 static int ComputeDepth(vtkKdNode *kd);
434 static void PackData(vtkKdNode *kd, double *data);
435 static void UnpackData(vtkKdNode *kd, double *data);
436 static void CheckFixRegionBoundaries(vtkKdNode *tree);
437
438 // list management
439
440 int AllocateDoubleBuffer();
441 void FreeDoubleBuffer();
442 void SwitchDoubleBuffer();
443 int AllocateSelectBuffer();
444 void FreeSelectBuffer();
445
446 void InitializeGlobalIndexLists();
447 int AllocateAndZeroGlobalIndexLists();
448 void FreeGlobalIndexLists();
449 void InitializeRegionAssignmentLists();
450 int AllocateAndZeroRegionAssignmentLists();
451 void FreeRegionAssignmentLists();
452 void InitializeProcessDataLists();
453 int AllocateAndZeroProcessDataLists();
454 void FreeProcessDataLists();
455 void InitializeFieldArrayMinMax();
456 int AllocateAndZeroFieldArrayMinMax();
457 void FreeFieldArrayMinMax();
458
459 void ReleaseTables();
460
461 // Assigning regions to processors
462
463 void AddProcessRegions(int procId, vtkKdNode *kd);
464 void BuildRegionListsForProcesses();
465
466 // Gather process/region data totals
467
468 int *CollectLocalRegionProcessData();
469 int BuildRegionProcessTables();
470 int BuildFieldArrayMinMax();
471 void AddEntry(int *list, int len, int id);
472#ifdef VTK_USE_64BIT_IDS
473 void AddEntry(vtkIdType *list, int len, vtkIdType id);
474#endif
475 static int BinarySearch(vtkIdType *list, int len, vtkIdType which);
476
477 static int FindNextLocalArrayIndex(const char *n, const char **names, int len, int start=0);
478
479 vtkPKdTree(const vtkPKdTree&) VTK_DELETE_FUNCTION;
480 void operator=(const vtkPKdTree&) VTK_DELETE_FUNCTION;
481};
482
483#endif
Used to send/receive messages in a multiprocess environment.
abstract class to specify dataset behavior
Definition: vtkDataSet.h:63
list of point or cell ids
Definition: vtkIdList.h:37
a simple class to control print indentation
Definition: vtkIndent.h:40
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:46
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning.
Definition: vtkKdNode.h:46
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:79
int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels)
void operator=(const vtkKdTree &) VTK_DELETE_FUNCTION
static int Select(int dim, float *c1, int *ids, int nvals, double &coord)
vtkKdNode ** RegionList
Definition: vtkKdTree.h:680
Multiprocessing communication superclass.
Build a k-d tree decomposition of a list of points.
Definition: vtkPKdTree.h:56
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:80
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])
int CreateProcessCellCountData()
Create tables of counts of cells per process per region.
static const int ContiguousAssignment
Definition: vtkPKdTree.h:124
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 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)
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 BuildLocator()
Build the spatial decomposition.
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:125
void PrintSelf(ostream &os, vtkIndent indent)
Methods invoked by print to print information about the object including superclasses.
static const int RoundRobinAssignment
Definition: vtkPKdTree.h:126
vtkIdType GetCellListsForProcessRegions(int ProcessId, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
static const int NoRegionAssignment
Definition: vtkPKdTree.h:123
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:156
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 ...
void PrintTiming(ostream &os, vtkIndent indent)
Print timing of k-d tree build.
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 ...
scalable collective communication for a subset of members of a parallel VTK application
Definition: vtkSubGroup.h:52
@ level
Definition: vtkX3D.h:395
@ range
Definition: vtkX3D.h:238
@ name
Definition: vtkX3D.h:219
@ data
Definition: vtkX3D.h:315
int vtkIdType
Definition: vtkType.h:287
#define max(a, b)