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