• Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

dox/Parallel/vtkPKdTree.h

Go to the documentation of this file.
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

Generated by  doxygen 1.7.1