vtkKdTree.h

Go to the documentation of this file.

/*=========================================================================
 
  Program:   Visualization Toolkit
  Module:    vtkKdTree.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 vtkKdTree_h
#define vtkKdTree_h
 
#include "vtkCommonDataModelModule.h" // For export macro
#include "vtkLocator.h"
 
class vtkTimerLog;
class vtkIdList;
class vtkIdTypeArray;
class vtkIntArray;
class vtkPointSet;
class vtkPoints;
class vtkCellArray;
class vtkCell;
class vtkKdNode;
class vtkBSPCuts;
class vtkBSPIntersections;
class vtkDataSetCollection;
 
class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
{
public:
  vtkTypeMacro(vtkKdTree, vtkLocator);
  void PrintSelf(ostream& os, vtkIndent indent);
 
  static vtkKdTree *New();
 
 
  vtkBooleanMacro(Timing, int);
  vtkSetMacro(Timing, int);
  vtkGetMacro(Timing, int);
 
 
  vtkSetMacro(MinCells, int);
  vtkGetMacro(MinCells, int);
 
  vtkGetMacro(NumberOfRegionsOrLess, int);
  vtkSetMacro(NumberOfRegionsOrLess, int);
 
  vtkGetMacro(NumberOfRegionsOrMore, int);
  vtkSetMacro(NumberOfRegionsOrMore, int);
 
  vtkGetMacro(FudgeFactor, double);
  vtkSetMacro(FudgeFactor, double);
 
  vtkGetObjectMacro(Cuts, vtkBSPCuts);
 
  void SetCuts(vtkBSPCuts *cuts);
 
  void OmitXPartitioning();
 
  void OmitYPartitioning();
 
  void OmitZPartitioning();
 
  void OmitXYPartitioning();
 
  void OmitYZPartitioning();
 
  void OmitZXPartitioning();
 
  void OmitNoPartitioning();
 
  virtual void SetDataSet(vtkDataSet *set);
 
  virtual void AddDataSet(vtkDataSet *set);
 
 
  virtual void RemoveDataSet(int index);
  virtual void RemoveDataSet(vtkDataSet *set);
  virtual void RemoveAllDataSets();
 
  int GetNumberOfDataSets();
 
  vtkDataSet *GetDataSet(int n);
 
  vtkDataSet *GetDataSet(){ return this->GetDataSet(0); }
 
 
  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
 
  int GetDataSetIndex(vtkDataSet *set);
 
  void GetBounds(double *bounds);
 
  void SetNewBounds(double *bounds);
 
 
  vtkGetMacro(NumberOfRegions, int);
 
  void GetRegionBounds(int regionID, double bounds[6]);
 
  void GetRegionDataBounds(int regionID, double bounds[6]);
 
 
  void PrintTree();
  void PrintVerboseTree();
 
  void PrintRegion(int id);
 
  void CreateCellLists(int dataSetIndex, int *regionReqList,
                       int reqListSize);
  void CreateCellLists(vtkDataSet *set, int *regionReqList,
                       int reqListSize);
  void CreateCellLists(int *regionReqList, int listSize);
  void CreateCellLists();
 
 
  vtkSetMacro(IncludeRegionBoundaryCells, int);
  vtkGetMacro(IncludeRegionBoundaryCells, int);
  vtkBooleanMacro(IncludeRegionBoundaryCells, int);
 
  void DeleteCellLists();
 
  vtkIdList *GetCellList(int regionID);
 
  vtkIdList *GetBoundaryCellList(int regionID);
 
 
  vtkIdType GetCellLists(vtkIntArray *regions, int set,
                   vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
  vtkIdType GetCellLists(vtkIntArray *regions, vtkDataSet *set,
            vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
  vtkIdType GetCellLists(vtkIntArray *regions, vtkIdList *inRegionCells,
                                    vtkIdList *onBoundaryCells);
 
 
  int GetRegionContainingCell(vtkDataSet *set, vtkIdType cellID);
  int GetRegionContainingCell(int set, vtkIdType cellID);
  int GetRegionContainingCell(vtkIdType cellID);
 
  int *AllGetRegionContainingCell();
 
  int GetRegionContainingPoint(double x, double y, double z);
 
  void BuildLocator();
 
  int MinimalNumberOfConvexSubRegions(vtkIntArray *regionIdList,
                                      double **convexRegionBounds);
 
 
  int ViewOrderAllRegionsInDirection(const double directionOfProjection[3],
                                     vtkIntArray *orderedList);
 
 
  int ViewOrderRegionsInDirection(vtkIntArray *regionIds,
                                  const double directionOfProjection[3],
                                  vtkIntArray *orderedList);
 
 
  int ViewOrderAllRegionsFromPosition(const double directionOfProjection[3],
                                      vtkIntArray *orderedList);
 
 
  int ViewOrderRegionsFromPosition(vtkIntArray *regionIds,
                                   const double directionOfProjection[3],
                                   vtkIntArray *orderedList);
 
 
  void BuildLocatorFromPoints(vtkPointSet *pointset);
  void BuildLocatorFromPoints(vtkPoints *ptArray);
  void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays);
 
  vtkIdTypeArray *BuildMapForDuplicatePoints(float tolerance);
 
 
  vtkIdType FindPoint(double *x);
  vtkIdType FindPoint(double x, double y, double z);
 
 
  vtkIdType FindClosestPoint(double *x, double &dist2);
  vtkIdType FindClosestPoint(double x, double y, double z, double &dist2);
 
 
  vtkIdType FindClosestPointWithinRadius(
    double radius, const double x[3], double& dist2);
 
 
  vtkIdType FindClosestPointInRegion(int regionId, double *x, double &dist2);
  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z,
                                     double &dist2);
 
  void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result);
 
  void FindClosestNPoints(int N, const double x[3], vtkIdList *result);
 
  vtkIdTypeArray *GetPointsInRegion(int regionId);
 
  void FreeSearchStructure();
 
  void GenerateRepresentation(int level, vtkPolyData *pd);
 
  void GenerateRepresentation(int *regionList, int len, vtkPolyData *pd);
 
 
  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, int);
  vtkSetMacro(GenerateRepresentationUsingDataBounds, int);
  vtkGetMacro(GenerateRepresentationUsingDataBounds, int);
 
  virtual void PrintTiming(ostream& os, vtkIndent indent);
 
  virtual int NewGeometry();
 
  virtual int NewGeometry(vtkDataSet **sets, int numDataSets);
 
  virtual void InvalidateGeometry();
 
  static vtkKdNode *CopyTree(vtkKdNode *kd);
 
  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
 
protected:
 
  vtkKdTree();
  ~vtkKdTree();
 
  vtkBSPIntersections *BSPCalculator;
  int UserDefinedCuts;
 
  void SetCalculator(vtkKdNode *kd);
 
  int ProcessUserDefinedCuts(double *bounds);
 
  void SetCuts(vtkBSPCuts *cuts, int userDefined);
 
  void UpdateBuildTime();
 
  int DivideTest(int numberOfPoints, int level);
 
//BTX
  enum {
    XDIM = 0,  // don't change these values
    YDIM = 1,
    ZDIM = 2
  };
//ETX
 
  int ValidDirections;
 
  vtkKdNode *Top;
  vtkKdNode **RegionList;      // indexed by region ID
 
  vtkTimerLog *TimerLog;
 
  static void DeleteAllDescendants(vtkKdNode *nd);
 
  void BuildRegionList();
  virtual int SelectCutDirection(vtkKdNode *kd);
  void SetActualLevel(){this->Level = vtkKdTree::ComputeLevel(this->Top);}
 
  void GetRegionsAtLevel(int level, vtkKdNode **nodes);
 
  static void GetLeafNodeIds(vtkKdNode *node, vtkIntArray *ids);
 
 
  int GetNumberOfCells();
 
  int GetDataSetsNumberOfCells(int set1, int set2);
 
  void ComputeCellCenter(vtkDataSet *set, int cellId, float *center);
  void ComputeCellCenter(vtkDataSet *set, int cellId, double *center);
 
  float *ComputeCellCenters();
  float *ComputeCellCenters(int set);
  float *ComputeCellCenters(vtkDataSet *set);
 
  vtkDataSetCollection *DataSets;
 
  void UpdateProgress(double amount);
 
 
  vtkSetClampMacro(Progress,double,0.0,1.0);
  vtkGetMacro(Progress,double);
 
protected:
  // So that each suboperation can report progress
  // in [0,1], yet we will be able to report a global
  // progress. Sub-operations must use UpdateSubOperationProgress()
  // for this to work.
  double ProgressScale;
  double ProgressOffset;
 
  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
  // Actual progress is given by
  // (this->ProgressOffset + this->ProgressScale* amount).
  void UpdateSubOperationProgress(double amount);
 
  static void _SetNewBounds(vtkKdNode *kd, double *b, int *fixDim);
  static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from);
  static void CopyKdNode(vtkKdNode *to, vtkKdNode *from);
  static void SetDataBoundsToSpatialBounds(vtkKdNode *kd);
  static void ZeroNumberOfPoints(vtkKdNode *kd);
 
//BTX
  // Recursive helper for public FindPointsWithinRadius
  void FindPointsWithinRadius(vtkKdNode* node, double R2,
                              const double x[3], vtkIdList* ids);
 
  // Recursive helper for public FindPointsWithinRadius
  void AddAllPointsInRegion(vtkKdNode* node, vtkIdList* ids);
 
  // Recursive helper for public FindPointsInArea
  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
 
  // Recursive helper for public FindPointsInArea
  void AddAllPointsInRegion(vtkKdNode* node, vtkIdTypeArray* ids);
 
  int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels);
 
  void DoMedianFind(vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3);
 
  void SelfRegister(vtkKdNode *kd);
 
  struct _cellList{
    vtkDataSet *dataSet;        // cell lists for which data set
    int *regionIds;            // NULL if listing all regions
    int nRegions;
    vtkIdList **cells;
    vtkIdList **boundaryCells;
    vtkIdList *emptyList;
  };
//ETX
 
  void InitializeCellLists();
  vtkIdList *GetList(int regionId, vtkIdList **which);
 
  void ComputeCellCenter(vtkCell* cell, double *center, double *weights);
 
  void GenerateRepresentationDataBounds(int level, vtkPolyData *pd);
  void _generateRepresentationDataBounds(vtkKdNode *kd, vtkPoints *pts,
                                         vtkCellArray *polys, int level);
 
  void GenerateRepresentationWholeSpace(int level, vtkPolyData *pd);
  void _generateRepresentationWholeSpace(vtkKdNode *kd, vtkPoints *pts,
                                         vtkCellArray *polys, int level);
 
  void AddPolys(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys);
 
  void _printTree(int verbose);
 
  int SearchNeighborsForDuplicate(int regionId, float *point,
                                  int **pointsSoFar, int *len,
                                  float tolerance, float tolerance2);
 
  int SearchRegionForDuplicate(float *point, int *pointsSoFar,
                               int len, float tolerance2);
 
  int _FindClosestPointInRegion(int regionId,
                          double x, double y, double z, double &dist2);
 
  int FindClosestPointInSphere(double x, double y, double z, double radius,
                               int skipRegion, double &dist2);
 
  int _ViewOrderRegionsInDirection(vtkIntArray *IdsOfInterest,
                                   const double dop[3],
                                   vtkIntArray *orderedList);
 
  static int __ViewOrderRegionsInDirection(vtkKdNode *node, vtkIntArray *list,
                                           vtkIntArray *IdsOfInterest,
                                           const double dir[3], int nextId);
 
  int _ViewOrderRegionsFromPosition(vtkIntArray *IdsOfInterest,
                                    const double pos[3],
                                    vtkIntArray *orderedList);
 
  static int __ViewOrderRegionsFromPosition(vtkKdNode *node, vtkIntArray *list,
                                            vtkIntArray *IdsOfInterest,
                                            const double pos[3], int nextId);
 
  static int __ConvexSubRegions(int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes);
  static int FoundId(vtkIntArray *idArray, int id);
 
  void NewParitioningRequest(int req);
  void SetInputDataInfo(int i,
       int dims[3], double origin[3], double spacing[3]);
  int CheckInputDataInfo(int i,
       int dims[3], double origin[3], double spacing[3]);
  void ClearLastBuildCache();
 
//BTX
  static void __printTree(vtkKdNode *kd, int depth, int verbose);
//ETX
 
  static int MidValue(int dim, float *c1, int nvals, double &coord);
 
  static int Select(int dim, float *c1, int *ids, int nvals, double &coord);
  static float FindMaxLeftHalf(int dim, float *c1, int K);
  static void _Select(int dim, float *X, int *ids, int L, int R, int K);
 
//BTX
  static int ComputeLevel(vtkKdNode *kd);
  static int SelfOrder(int id, vtkKdNode *kd);
  static int findRegion(vtkKdNode *node, float x, float y, float z);
  static int findRegion(vtkKdNode *node, double x, double y, double z);
//ETX
 
  static vtkKdNode **_GetRegionsAtLevel(int level, vtkKdNode **nodes,
                                        vtkKdNode *kd);
 
  static void AddNewRegions(vtkKdNode *kd, float *c1,
                            int midpt, int dim, double coord);
 
  void NewPartitioningRequest(int req);
 
  int NumberOfRegionsOrLess;
  int NumberOfRegionsOrMore;
 
  int IncludeRegionBoundaryCells;
  double CellBoundsCache[6];       // to optimize IntersectsCell()
 
  int GenerateRepresentationUsingDataBounds;
 
//BTX
  struct _cellList CellList;
//ETX
 
  // Region Ids, by data set by cell id - this list is large (one
  // int per cell) but accelerates creation of cell lists
 
  int *CellRegionList;
 
  int MinCells;
  int NumberOfRegions;              // number of leaf nodes
 
  int Timing;
  double FudgeFactor;   // a very small distance, relative to the dataset's size
 
  // These instance variables are used by the special locator created
  // to find duplicate points. (BuildLocatorFromPoints)
 
  int NumberOfLocatorPoints;
  float *LocatorPoints;
  int *LocatorIds;
  int *LocatorRegionLocation;
 
  float MaxWidth;
 
  // These Last* values are here to save state so we can
  // determine later if k-d tree must be rebuilt.
 
  int LastNumDataSets;
  int LastDataCacheSize;
  vtkDataSet **LastInputDataSets;
  unsigned long *LastDataSetObserverTags;
  int *LastDataSetType;
  double *LastInputDataInfo;
  double *LastBounds;
  vtkIdType *LastNumPoints;
  vtkIdType *LastNumCells;
 
  vtkBSPCuts *Cuts;
  double Progress;
 
  vtkKdTree(const vtkKdTree&); // Not implemented
  void operator=(const vtkKdTree&); // Not implemented
};
#endif