00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00042 #ifndef __vtkPKdTree_h
00043 #define __vtkPKdTree_h
00044
00045 #include "vtkKdTree.h"
00046
00047 class vtkMultiProcessController;
00048 class vtkCommunicator;
00049 class vtkSubGroup;
00050 class vtkIntArray;
00051 class vtkKdNode;
00052
00053 class VTK_PARALLEL_EXPORT vtkPKdTree : public vtkKdTree
00054 {
00055 public:
00056 vtkTypeRevisionMacro(vtkPKdTree, vtkKdTree);
00057
00058
00059 void PrintSelf(ostream& os, vtkIndent indent);
00060 void PrintTiming(ostream& os, vtkIndent indent);
00061 void PrintTables(ostream& os, vtkIndent indent);
00062
00063 static vtkPKdTree *New();
00064
00068 void BuildLocator();
00069
00073 vtkIdType GetTotalNumberOfCells(){return this->TotalNumCells;}
00074
00080 int CreateProcessCellCountData();
00081
00087 int CreateGlobalDataArrayBounds();
00088
00090
00091 void SetController(vtkMultiProcessController *c);
00092 vtkGetObjectMacro(Controller, vtkMultiProcessController);
00094
00096
00103 vtkGetMacro(RegionAssignment, int);
00105
00106 static const int NoRegionAssignment;
00107 static const int ContiguousAssignment;
00108 static const int UserDefinedAssignment;
00109 static const int RoundRobinAssignment;
00110
00114 int AssignRegions(int *map, int numRegions);
00115
00119 int AssignRegionsRoundRobin();
00120
00126 int AssignRegionsContiguous();
00127
00131 int GetRegionAssignmentList(int procId, vtkIntArray *list);
00132
00134
00139 void GetAllProcessesBorderingOnPoint(float x, float y, float z,
00140 vtkIntArray *list);
00142
00144 int GetProcessAssignedToRegion(int regionId);
00145
00147 int HasData(int processId, int regionId);
00148
00151 int GetProcessCellCountForRegion(int processId, int regionId);
00152
00155 int GetTotalProcessesInRegion(int regionId);
00156
00159 int GetProcessListForRegion(int regionId, vtkIntArray *processes);
00160
00165 int GetProcessesCellCountForRegion(int regionId, int *count, int len);
00166
00169 int GetTotalRegionsForProcess(int processId);
00170
00173 int GetRegionListForProcess(int processId, vtkIntArray *regions);
00174
00179 int GetRegionsCellCountForProcess(int ProcessId, int *count, int len);
00180
00182
00199 vtkIdType GetCellListsForProcessRegions(int ProcessId, int set,
00200 vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
00201 vtkIdType GetCellListsForProcessRegions(int ProcessId, vtkDataSet *set,
00202 vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
00203 vtkIdType GetCellListsForProcessRegions(int ProcessId,
00204 vtkIdList *inRegionCells,
00205 vtkIdList *onBoundaryCells);
00207
00209
00212 VTK_LEGACY(int DepthOrderAllProcesses(double *directionOfProjection,
00213 vtkIntArray *orderedList));
00215
00217
00222 int ViewOrderAllProcessesInDirection(const double directionOfProjection[3],
00223 vtkIntArray *orderedList);
00225
00227
00232 int ViewOrderAllProcessesFromPosition(const double cameraPosition[3],
00233 vtkIntArray *orderedList);
00235
00241 int GetCellArrayGlobalRange(const char *name, float range[2]);
00242 int GetPointArrayGlobalRange(const char *name, float range[2]);
00243 int GetCellArrayGlobalRange(const char *name, double range[2]);
00244 int GetPointArrayGlobalRange(const char *name, double range[2]);
00245
00246 int GetCellArrayGlobalRange(int arrayIndex, double range[2]);
00247 int GetPointArrayGlobalRange(int arrayIndex, double range[2]);
00248 int GetCellArrayGlobalRange(int arrayIndex, float range[2]);
00249 int GetPointArrayGlobalRange(int arrayIndex, float range[2]);
00250
00251 protected:
00252
00253 vtkPKdTree();
00254 ~vtkPKdTree();
00255
00256 void SingleProcessBuildLocator();
00257 int MultiProcessBuildLocator(double *bounds);
00258
00259 private:
00260
00261 int RegionAssignment;
00262
00263 vtkMultiProcessController *Controller;
00264
00265 vtkSubGroup *SubGroup;
00266
00267 static char *StrDupWithNew(const char *s);
00268
00269 int NumProcesses;
00270 int MyId;
00271
00272
00273
00274
00275 int *RegionAssignmentMap;
00276 int RegionAssignmentMapLength;
00277 int **ProcessAssignmentMap;
00278 int *NumRegionsAssigned;
00279
00280 int UpdateRegionAssignment();
00281
00282
00283
00284
00285 char *DataLocationMap;
00286
00287 int *NumProcessesInRegion;
00288 int **ProcessList;
00289
00290 int *NumRegionsInProcess;
00291 int **RegionList;
00292
00293 vtkIdType **CellCountList;
00294
00295 double *CellDataMin;
00296 double *CellDataMax;
00297 double *PointDataMin;
00298 double *PointDataMax;
00299 char **CellDataName;
00300 char **PointDataName;
00301 int NumCellArrays;
00302 int NumPointArrays;
00303
00304
00305
00306 int BuildGlobalIndexLists(vtkIdType ncells);
00307
00308 vtkIdType *StartVal;
00309 vtkIdType *EndVal;
00310 vtkIdType *NumCells;
00311 vtkIdType TotalNumCells;
00312
00313
00314
00315 int WhoHas(int pos);
00316 int _whoHas(int L, int R, int pos);
00317 float *GetLocalVal(int pos);
00318 float *GetLocalValNext(int pos);
00319 void SetLocalVal(int pos, float *val);
00320 void ExchangeVals(int pos1, int pos2);
00321 void ExchangeLocalVals(int pos1, int pos2);
00322
00323 float *PtArray;
00324 float *PtArray2;
00325 float *CurrentPtArray;
00326 float *NextPtArray;
00327 int PtArraySize;
00328
00329 int *SelectBuffer;
00330
00331
00332
00333 int AllCheckForFailure(int rc, const char *where, const char *how);
00334 void AllCheckParameters();
00335 double *VolumeBounds();
00336 int DivideRegion(vtkKdNode *kd, int L, int level, int tag);
00337 int BreadthFirstDivide(double *bounds);
00338 void enQueueNode(vtkKdNode *kd, int L, int level, int tag);
00339
00340 int Select(int dim, int L, int R);
00341 void _select(int L, int R, int K, int dim);
00342 void DoTransfer(int from, int to, int fromIndex, int toIndex, int count);
00343
00344 int *PartitionAboutMyValue(int L, int R, int K, int dim);
00345 int *PartitionAboutOtherValue(int L, int R, float T, int dim);
00346 int *PartitionSubArray(int L, int R, int K, int dim, int p1, int p2);
00347
00348 int CompleteTree();
00349 #ifdef YIELDS_INCONSISTENT_REGION_BOUNDARIES
00350 void RetrieveData(vtkKdNode *kd, int *buf);
00351 #else
00352 void ReduceData(vtkKdNode *kd, int *sources);
00353 void BroadcastData(vtkKdNode *kd);
00354 #endif
00355
00356 float *DataBounds(int L, int K, int R);
00357 void GetLocalMinMax(int L, int R, int me, float *min, float *max);
00358
00359 static int FillOutTree(vtkKdNode *kd, int level);
00360 static int ComputeDepth(vtkKdNode *kd);
00361 static void PackData(vtkKdNode *kd, double *data);
00362 static void UnpackData(vtkKdNode *kd, double *data);
00363 static void CheckFixRegionBoundaries(vtkKdNode *tree);
00364
00365
00366
00367 int AllocateDoubleBuffer();
00368 void FreeDoubleBuffer();
00369 void SwitchDoubleBuffer();
00370 int AllocateSelectBuffer();
00371 void FreeSelectBuffer();
00372
00373 void InitializeGlobalIndexLists();
00374 int AllocateAndZeroGlobalIndexLists();
00375 void FreeGlobalIndexLists();
00376 void InitializeRegionAssignmentLists();
00377 int AllocateAndZeroRegionAssignmentLists();
00378 void FreeRegionAssignmentLists();
00379 void InitializeProcessDataLists();
00380 int AllocateAndZeroProcessDataLists();
00381 void FreeProcessDataLists();
00382 void InitializeFieldArrayMinMax();
00383 int AllocateAndZeroFieldArrayMinMax();
00384 void FreeFieldArrayMinMax();
00385
00386 void ReleaseTables();
00387
00388
00389
00390 void AddProcessRegions(int procId, vtkKdNode *kd);
00391 void BuildRegionListsForProcesses();
00392
00393
00394
00395 int *CollectLocalRegionProcessData();
00396 int BuildRegionProcessTables();
00397 int BuildFieldArrayMinMax();
00398 void AddEntry(int *list, int len, int id);
00399 #ifdef VTK_USE_64BIT_IDS
00400 void AddEntry(vtkIdType *list, int len, vtkIdType id);
00401 #endif
00402 static int BinarySearch(vtkIdType *list, int len, vtkIdType which);
00403
00404 static int FindNextLocalArrayIndex(const char *n, const char **names, int len, int start=0);
00405
00406 vtkPKdTree(const vtkPKdTree&);
00407 void operator=(const vtkPKdTree&);
00408 };
00409
00410 #endif