VTK
|
00001 /*========================================================================= 00002 00003 Program: Visualization Toolkit 00004 Module: $RCSfile: vtkPKdTree.h,v $ 00005 00006 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen 00007 All rights reserved. 00008 See Copyright.txt or http://www.kitware.com/Copyright.htm for details. 00009 00010 This software is distributed WITHOUT ANY WARRANTY; without even 00011 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 00012 PURPOSE. See the above copyright notice for more information. 00013 00014 =========================================================================*/ 00015 /*---------------------------------------------------------------------------- 00016 Copyright (c) Sandia Corporation 00017 See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details. 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 00220 int ViewOrderAllProcessesInDirection(const double directionOfProjection[3], 00221 vtkIntArray *orderedList); 00223 00225 00228 int ViewOrderAllProcessesFromPosition(const double cameraPosition[3], 00229 vtkIntArray *orderedList); 00231 00237 int GetCellArrayGlobalRange(const char *name, float range[2]); 00238 int GetPointArrayGlobalRange(const char *name, float range[2]); 00239 int GetCellArrayGlobalRange(const char *name, double range[2]); 00240 int GetPointArrayGlobalRange(const char *name, double range[2]); 00241 00242 int GetCellArrayGlobalRange(int arrayIndex, double range[2]); 00243 int GetPointArrayGlobalRange(int arrayIndex, double range[2]); 00244 int GetCellArrayGlobalRange(int arrayIndex, float range[2]); 00245 int GetPointArrayGlobalRange(int arrayIndex, float range[2]); 00246 00247 protected: 00248 00249 vtkPKdTree(); 00250 ~vtkPKdTree(); 00251 00252 void SingleProcessBuildLocator(); 00253 int MultiProcessBuildLocator(double *bounds); 00254 00255 private: 00256 00257 int RegionAssignment; 00258 00259 vtkMultiProcessController *Controller; 00260 00261 vtkSubGroup *SubGroup; 00262 00263 static char *StrDupWithNew(const char *s); 00264 00265 int NumProcesses; 00266 int MyId; 00267 00268 // basic tables - each region is the responsibility of one process, but 00269 // one process may be assigned many regions 00270 00271 int *RegionAssignmentMap; // indexed by region ID 00272 int RegionAssignmentMapLength; 00273 int **ProcessAssignmentMap; // indexed by process ID 00274 int *NumRegionsAssigned; // indexed by process ID 00275 00276 int UpdateRegionAssignment(); 00277 00278 // basic tables reflecting the data that was read from disk 00279 // by each process 00280 00281 char *DataLocationMap; // by process, by region 00282 00283 int *NumProcessesInRegion; // indexed by region ID 00284 int **ProcessList; // indexed by region ID 00285 00286 int *NumRegionsInProcess; // indexed by process ID 00287 int **RegionList; // indexed by process ID 00288 00289 vtkIdType **CellCountList; // indexed by region ID 00290 00291 double *CellDataMin; // global range for data arrays 00292 double *CellDataMax; 00293 double *PointDataMin; 00294 double *PointDataMax; 00295 char **CellDataName; 00296 char **PointDataName; 00297 int NumCellArrays; 00298 int NumPointArrays; 00299 00300 // distribution of indices for select operation 00301 00302 int BuildGlobalIndexLists(vtkIdType ncells); 00303 00304 vtkIdType *StartVal; 00305 vtkIdType *EndVal; 00306 vtkIdType *NumCells; 00307 vtkIdType TotalNumCells; 00308 00309 // local share of points to be partitioned, and local cache 00310 00311 int WhoHas(int pos); 00312 int _whoHas(int L, int R, int pos); 00313 float *GetLocalVal(int pos); 00314 float *GetLocalValNext(int pos); 00315 void SetLocalVal(int pos, float *val); 00316 void ExchangeVals(int pos1, int pos2); 00317 void ExchangeLocalVals(int pos1, int pos2); 00318 00319 float *PtArray; 00320 float *PtArray2; 00321 float *CurrentPtArray; 00322 float *NextPtArray; 00323 int PtArraySize; 00324 00325 int *SelectBuffer; 00326 00327 // Parallel build of k-d tree 00328 00329 int AllCheckForFailure(int rc, const char *where, const char *how); 00330 void AllCheckParameters(); 00331 double *VolumeBounds(); 00332 int DivideRegion(vtkKdNode *kd, int L, int level, int tag); 00333 int BreadthFirstDivide(double *bounds); 00334 void enQueueNode(vtkKdNode *kd, int L, int level, int tag); 00335 00336 int Select(int dim, int L, int R); 00337 void _select(int L, int R, int K, int dim); 00338 void DoTransfer(int from, int to, int fromIndex, int toIndex, int count); 00339 00340 int *PartitionAboutMyValue(int L, int R, int K, int dim); 00341 int *PartitionAboutOtherValue(int L, int R, float T, int dim); 00342 int *PartitionSubArray(int L, int R, int K, int dim, int p1, int p2); 00343 00344 int CompleteTree(); 00345 #ifdef YIELDS_INCONSISTENT_REGION_BOUNDARIES 00346 void RetrieveData(vtkKdNode *kd, int *buf); 00347 #else 00348 void ReduceData(vtkKdNode *kd, int *sources); 00349 void BroadcastData(vtkKdNode *kd); 00350 #endif 00351 00352 float *DataBounds(int L, int K, int R); 00353 void GetLocalMinMax(int L, int R, int me, float *min, float *max); 00354 00355 static int FillOutTree(vtkKdNode *kd, int level); 00356 static int ComputeDepth(vtkKdNode *kd); 00357 static void PackData(vtkKdNode *kd, double *data); 00358 static void UnpackData(vtkKdNode *kd, double *data); 00359 static void CheckFixRegionBoundaries(vtkKdNode *tree); 00360 00361 // list management 00362 00363 int AllocateDoubleBuffer(); 00364 void FreeDoubleBuffer(); 00365 void SwitchDoubleBuffer(); 00366 int AllocateSelectBuffer(); 00367 void FreeSelectBuffer(); 00368 00369 void InitializeGlobalIndexLists(); 00370 int AllocateAndZeroGlobalIndexLists(); 00371 void FreeGlobalIndexLists(); 00372 void InitializeRegionAssignmentLists(); 00373 int AllocateAndZeroRegionAssignmentLists(); 00374 void FreeRegionAssignmentLists(); 00375 void InitializeProcessDataLists(); 00376 int AllocateAndZeroProcessDataLists(); 00377 void FreeProcessDataLists(); 00378 void InitializeFieldArrayMinMax(); 00379 int AllocateAndZeroFieldArrayMinMax(); 00380 void FreeFieldArrayMinMax(); 00381 00382 void ReleaseTables(); 00383 00384 // Assigning regions to processors 00385 00386 void AddProcessRegions(int procId, vtkKdNode *kd); 00387 void BuildRegionListsForProcesses(); 00388 00389 // Gather process/region data totals 00390 00391 int *CollectLocalRegionProcessData(); 00392 int BuildRegionProcessTables(); 00393 int BuildFieldArrayMinMax(); 00394 void AddEntry(int *list, int len, int id); 00395 #ifdef VTK_USE_64BIT_IDS 00396 void AddEntry(vtkIdType *list, int len, vtkIdType id); 00397 #endif 00398 static int BinarySearch(vtkIdType *list, int len, vtkIdType which); 00399 00400 static int FindNextLocalArrayIndex(const char *n, const char **names, int len, int start=0); 00401 00402 vtkPKdTree(const vtkPKdTree&); // Not implemented 00403 void operator=(const vtkPKdTree&); // Not implemented 00404 }; 00405 00406 #endif