vtkPKdTree.h

Go to the documentation of this file.

/*=========================================================================
 
  Program:   Visualization Toolkit
  Module:    vtkPKdTree.h
 
  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
 
     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.
 
=========================================================================*/
/*----------------------------------------------------------------------------
 Copyright (c) Sandia Corporation
 See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
----------------------------------------------------------------------------*/
 
#ifndef vtkPKdTree_h
#define vtkPKdTree_h
 
#include "vtkFiltersParallelModule.h" // For export macro
#include "vtkKdTree.h"
 
class vtkMultiProcessController;
class vtkCommunicator;
class vtkSubGroup;
class vtkIntArray;
class vtkKdNode;
 
class VTKFILTERSPARALLEL_EXPORT vtkPKdTree : public vtkKdTree
{
public:
  vtkTypeMacro(vtkPKdTree, vtkKdTree);
 
 
  void PrintSelf(ostream& os, vtkIndent indent);
  void PrintTiming(ostream& os, vtkIndent indent);
  void PrintTables(ostream& os, vtkIndent indent);
 
  static vtkPKdTree *New();
 
  void BuildLocator();
 
  vtkIdType GetTotalNumberOfCells(){return this->TotalNumCells;}
 
  int CreateProcessCellCountData();
 
  int CreateGlobalDataArrayBounds();
 
 
  void SetController(vtkMultiProcessController *c);
  vtkGetObjectMacro(Controller, vtkMultiProcessController);
 
 
  vtkGetMacro(RegionAssignment, int);
 
  static const int NoRegionAssignment;
  static const int ContiguousAssignment;
  static const int UserDefinedAssignment;
  static const int RoundRobinAssignment;
 
  int AssignRegions(int *map, int numRegions);
 
  int AssignRegionsRoundRobin();
 
  int AssignRegionsContiguous();
 
 
  const int* GetRegionAssignmentMap()
    { return this->RegionAssignmentMap; }
 
 
  vtkGetMacro(RegionAssignmentMapLength, int);
 
  int GetRegionAssignmentList(int procId, vtkIntArray *list);
 
 
  void GetAllProcessesBorderingOnPoint(float x, float y, float z,
                                       vtkIntArray *list);
 
  int GetProcessAssignedToRegion(int regionId);
 
  int HasData(int processId, int regionId);
 
  int GetProcessCellCountForRegion(int processId, int regionId);
 
  int GetTotalProcessesInRegion(int regionId);
 
  int GetProcessListForRegion(int regionId, vtkIntArray *processes);
 
  int GetProcessesCellCountForRegion(int regionId, int *count, int len);
 
  int GetTotalRegionsForProcess(int processId);
 
  int GetRegionListForProcess(int processId, vtkIntArray *regions);
 
  int GetRegionsCellCountForProcess(int ProcessId, int *count, int len);
 
 
  vtkIdType GetCellListsForProcessRegions(int ProcessId, int set,
            vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
  vtkIdType GetCellListsForProcessRegions(int ProcessId, vtkDataSet *set,
            vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
  vtkIdType GetCellListsForProcessRegions(int ProcessId,
                                          vtkIdList *inRegionCells,
                                          vtkIdList *onBoundaryCells);
 
 
  int ViewOrderAllProcessesInDirection(const double directionOfProjection[3],
                                       vtkIntArray *orderedList);
 
 
  int ViewOrderAllProcessesFromPosition(const double cameraPosition[3],
                                        vtkIntArray *orderedList);
 
  int GetCellArrayGlobalRange(const char *name, float range[2]);
  int GetPointArrayGlobalRange(const char *name, float range[2]);
  int GetCellArrayGlobalRange(const char *name, double range[2]);
  int GetPointArrayGlobalRange(const char *name, double range[2]);
 
  int GetCellArrayGlobalRange(int arrayIndex, double range[2]);
  int GetPointArrayGlobalRange(int arrayIndex, double range[2]);
  int GetCellArrayGlobalRange(int arrayIndex, float range[2]);
  int GetPointArrayGlobalRange(int arrayIndex, float range[2]);
 
protected:
 
  vtkPKdTree();
  ~vtkPKdTree();
 
  void SingleProcessBuildLocator();
  int MultiProcessBuildLocator(double *bounds);
 
private:
 
  int RegionAssignment;
 
  vtkMultiProcessController *Controller;
 
  vtkSubGroup *SubGroup;
 
  static char *StrDupWithNew(const char *s);
 
  int NumProcesses;
  int MyId;
 
  // basic tables - each region is the responsibility of one process, but
  //                one process may be assigned many regions
 
  int *RegionAssignmentMap;        // indexed by region ID
  int RegionAssignmentMapLength;
  int **ProcessAssignmentMap;      // indexed by process ID
  int *NumRegionsAssigned;         // indexed by process ID
 
  int UpdateRegionAssignment();
 
  // basic tables reflecting the data that was read from disk
  // by each process
 
  char *DataLocationMap;              // by process, by region
 
  int *NumProcessesInRegion;          // indexed by region ID
  int **ProcessList;                  // indexed by region ID
 
  int *NumRegionsInProcess;           // indexed by process ID
  int **RegionList;                   // indexed by process ID
 
  vtkIdType **CellCountList;                // indexed by region ID
 
  double *CellDataMin;           // global range for data arrays
  double *CellDataMax;
  double *PointDataMin;
  double *PointDataMax;
  char **CellDataName;
  char **PointDataName;
  int NumCellArrays;
  int NumPointArrays;
 
  // distribution of indices for select operation
 
  int BuildGlobalIndexLists(vtkIdType ncells);
 
  vtkIdType *StartVal;
  vtkIdType *EndVal;
  vtkIdType *NumCells;
  vtkIdType TotalNumCells;
 
  // local share of points to be partitioned, and local cache
 
  int WhoHas(int pos);
  int _whoHas(int L, int R, int pos);
  float *GetLocalVal(int pos);
  float *GetLocalValNext(int pos);
  void SetLocalVal(int pos, float *val);
  void ExchangeVals(int pos1, int pos2);
  void ExchangeLocalVals(int pos1, int pos2);
 
  float *PtArray;
  float *PtArray2;
  float *CurrentPtArray;
  float *NextPtArray;
  int PtArraySize;
 
  int *SelectBuffer;
 
  // Parallel build of k-d tree
 
  int AllCheckForFailure(int rc, const char *where, const char *how);
  void AllCheckParameters();
 
 
  bool VolumeBounds(double*);
  int DivideRegion(vtkKdNode *kd, int L, int level, int tag);
  int BreadthFirstDivide(double *bounds);
  void enQueueNode(vtkKdNode *kd, int L, int level, int tag);
 
  int Select(int dim, int L, int R);
  void _select(int L, int R, int K, int dim);
  void DoTransfer(int from, int to, int fromIndex, int toIndex, int count);
 
  int *PartitionAboutMyValue(int L, int R, int K, int dim);
  int *PartitionAboutOtherValue(int L, int R, float T, int dim);
  int *PartitionSubArray(int L, int R, int K, int dim, int p1, int p2);
 
  int CompleteTree();
#ifdef YIELDS_INCONSISTENT_REGION_BOUNDARIES
  void RetrieveData(vtkKdNode *kd, int *buf);
#else
  void ReduceData(vtkKdNode *kd, int *sources);
  void BroadcastData(vtkKdNode *kd);
#endif
 
  float *DataBounds(int L, int K, int R);
  void GetLocalMinMax(int L, int R, int me, float *min, float *max);
 
  static int FillOutTree(vtkKdNode *kd, int level);
  static int ComputeDepth(vtkKdNode *kd);
  static void PackData(vtkKdNode *kd, double *data);
  static void UnpackData(vtkKdNode *kd, double *data);
  static void CheckFixRegionBoundaries(vtkKdNode *tree);
 
  // list management
 
  int AllocateDoubleBuffer();
  void FreeDoubleBuffer();
  void SwitchDoubleBuffer();
  int AllocateSelectBuffer();
  void FreeSelectBuffer();
 
  void InitializeGlobalIndexLists();
  int AllocateAndZeroGlobalIndexLists();
  void FreeGlobalIndexLists();
  void InitializeRegionAssignmentLists();
  int AllocateAndZeroRegionAssignmentLists();
  void FreeRegionAssignmentLists();
  void InitializeProcessDataLists();
  int AllocateAndZeroProcessDataLists();
  void FreeProcessDataLists();
  void InitializeFieldArrayMinMax();
  int AllocateAndZeroFieldArrayMinMax();
  void FreeFieldArrayMinMax();
 
  void ReleaseTables();
 
  // Assigning regions to processors
 
  void AddProcessRegions(int procId, vtkKdNode *kd);
  void BuildRegionListsForProcesses();
 
  // Gather process/region data totals
 
  int *CollectLocalRegionProcessData();
  int BuildRegionProcessTables();
  int BuildFieldArrayMinMax();
  void AddEntry(int *list, int len, int id);
#ifdef VTK_USE_64BIT_IDS
  void AddEntry(vtkIdType *list, int len, vtkIdType id);
#endif
  static int BinarySearch(vtkIdType *list, int len, vtkIdType which);
 
  static int FindNextLocalArrayIndex(const char *n, const char **names, int len, int start=0);
 
  vtkPKdTree(const vtkPKdTree&); // Not implemented
  void operator=(const vtkPKdTree&); // Not implemented
};
 
#endif