vtkKdTree.h

Go to the documentation of this file.

/*=========================================================================

  Program:   Visualization Toolkit
  Module:    $RCSfile: vtkKdTree.h,v $

  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 "vtkLocator.h"

class vtkTimerLog;
class vtkIdList;
class vtkIdTypeArray;
class vtkIntArray;
class vtkPoints;
class vtkCellArray;
class vtkRenderer;
class vtkPlanesIntersection;
class vtkPlanes;
class vtkCell;
class vtkCamera;
class vtkKdNode;

class VTK_PARALLEL_EXPORT vtkKdTree : public vtkLocator
{
public:
  vtkTypeRevisionMacro(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(FudgeFactor, double);
  vtkSetMacro(FudgeFactor, double);

  void OmitXPartitioning();
  
  void OmitYPartitioning();

  void OmitZPartitioning();

  void OmitXYPartitioning();

  void OmitYZPartitioning();
  
  void OmitZXPartitioning();

  void OmitNoPartitioning();

  void SetDataSet(vtkDataSet *set);
  void SetNthDataSet(int index, vtkDataSet *set);
  void RemoveDataSet(int index);
  void RemoveDataSet(vtkDataSet *set);
  void AddDataSet(vtkDataSet *set);

  int GetNumberOfDataSets(){return this->NumDataSets;};

  vtkDataSet *GetDataSet(int n);
  vtkDataSet *GetDataSet(){ return this->GetDataSet(0); }

  int GetDataSet(vtkDataSet *set);


  void GetBounds(float *bounds);
  void GetBounds(double *bounds);

  int GetNumberOfRegions(){ return this->NumRegions; }


  void GetRegionBounds(int regionID, float bounds[6]);
  void GetRegionBounds(int regionID, double bounds[6]);


  void GetRegionDataBounds(int regionID, float bounds[6]);
  void GetRegionDataBounds(int regionID, double bounds[6]);


  void PrintTree();
  void PrintVerboseTree();
  
  void PrintRegion(int id);
  
  void CreateCellLists(int DataSet, 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(float x, float y, float z);
  int GetRegionContainingPoint(double x, double y, double z);
  
  int DepthOrderAllRegions(vtkCamera *camera, vtkIntArray *orderedList);
  

  int DepthOrderRegions(vtkIntArray *regionIds, vtkCamera *camera, 
                        vtkIntArray *orderedList);


  int IntersectsBox(int regionId, float *x); 
  int IntersectsBox(int regionId, double *x); 
  int IntersectsBox(int regionId, float xmin, float xmax, 
                    float ymin, float ymax, 
                    float zmin, float zmax); 
  int IntersectsBox(int regionId, double xmin, double xmax, 
                    double ymin, double ymax, 
                    double zmin, double zmax); 


  int IntersectsBox(int *ids, int len,  float *x); 
  int IntersectsBox(int *ids, int len,  double *x); 
  int IntersectsBox(int *ids, int len,  float x0, float x1, 
                    float y0, float y1, float z0, float z1); 
  int IntersectsBox(int *ids, int len,  double x0, double x1, 
                    double y0, double y1, double z0, double z1); 


  int IntersectsSphere2(int regionId, 
                        float x, float y, float z, float rSquared);
  int IntersectsSphere2(int regionId, 
                        double x, double y, double z, double rSquared);


  int IntersectsSphere2(int *ids, int len, 
                        float x, float y, float z, float rSquared);
  int IntersectsSphere2(int *ids, int len, 
                        double x, double y, double z, double rSquared);


  int IntersectsRegion(int regionId, vtkPlanes *planes);
  int IntersectsRegion(int regionId, vtkPlanes *planes, 
                        int nvertices, float *vertices);
  int IntersectsRegion(int regionId, vtkPlanes *planes, 
                        int nvertices, double *vertices);


  int IntersectsRegion(int *ids, int len, vtkPlanes *planes);
  int IntersectsRegion(int *ids, int len, vtkPlanes *planes, 
                       int nvertices, float *vertices);
  int IntersectsRegion(int *ids, int len, vtkPlanes *planes, 
                       int nvertices, double *vertices);


  int IntersectsCell(int regionId, vtkCell *cell, int cellRegion=-1);
  int IntersectsCell(int regionId, int cellId, int cellRegion=-1);
  int IntersectsCell(int regionId, vtkDataSet *Set, int cellId, int cellRegion=-1);


  int IntersectsCell(int *ids, int len, vtkCell *cell, int cellRegion=-1);
  int IntersectsCell(int *ids, int len, int cellId, int cellRegion=-1);
  int IntersectsCell(int *ids, int len, vtkDataSet *set, int cellId, int cellRegion=-1);


  int IntersectsFrustum(int regionId, vtkRenderer *ren, 
         float x0, float x1, float y0, float y1);
  int IntersectsFrustum(int regionId, vtkRenderer *ren, 
         double x0, double x1, double y0, double y1);



  int IntersectsFrustum(int *ids, int len,  vtkRenderer *ren, 
         float x0, float x1, float y0, float y1);
  int IntersectsFrustum(int *ids, int len,  vtkRenderer *ren, 
         double x0, double x1, double y0, double y1);


  int MinimalNumberOfConvexSubRegions(vtkIntArray *regionIdList,
                                      double **convexRegionBounds);
  

  vtkBooleanMacro(ComputeIntersectionsUsingDataBounds, int);
  vtkSetMacro(ComputeIntersectionsUsingDataBounds, int);
  vtkGetMacro(ComputeIntersectionsUsingDataBounds, int);

  void BuildLocator();


  void BuildLocatorFromPoints(vtkPoints *ptArray);
  void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays);
  
  vtkIdTypeArray *BuildMapForDuplicatePoints(float tolerance);


  vtkIdType FindPoint(float *x);
  vtkIdType FindPoint(double *x);
  vtkIdType FindPoint(float x, float y, float z);
  vtkIdType FindPoint(double x, double y, double z);


  vtkIdType FindClosestPoint(float *x, float &dist2);
  vtkIdType FindClosestPoint(double *x, double &dist2);
  vtkIdType FindClosestPoint(float x, float y, float z, float &dist2);
  vtkIdType FindClosestPoint(double x, double y, double z, double &dist2);


  vtkIdType FindClosestPointInRegion(int regionId, float *x, float &dist2);
  vtkIdType FindClosestPointInRegion(int regionId, float x, float y, float z, 
                                     float &dist2);

  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);

  int NewGeometry();

  int NewGeometry(vtkDataSet **sets, int numDataSets);

//BTX                             
  static inline void SetCellBounds(vtkCell *cell, double *bounds);
//ETX

protected:

  vtkKdTree();
  ~vtkKdTree();

  void UpdateBuildTime();

//BTX
  enum {
    XDIM = 0,  // don't change these values
    YDIM = 1,
    ZDIM = 2
  };
//ETX

  int ValidDirections;

//BTX
  vtkKdNode *Top;
  vtkKdNode **RegionList;      // indexed by region ID
//ETX

  vtkTimerLog *TimerLog;

  static void DeleteNodes(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);

private:

//BTX
  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);

//BTX
  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);

  int _IntersectsBox(vtkKdNode *node, int *ids, int len,
                     double x0, double x1,
                     double y0, double y1, 
                     double z0, double z1);

  int _IntersectsSphere2(vtkKdNode *node, int *ids, int len,
                         double x, double y, double z, double rSquared);

  int _IntersectsRegion(vtkKdNode *node, int *ids, int len,
                        vtkPlanesIntersection *pi);

  int _IntersectsCell(vtkKdNode *node, int *ids, int len,
                      vtkCell *cell, int cellRegion=-1);
//ETX

  void _printTree(int verbose);

  int _DepthOrderRegions(vtkIntArray *IdsOfInterest,
                         vtkCamera *camera, vtkIntArray *orderedList);

  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, 
                          float x, float y, float z, float &dist2);

  int FindClosestPointInSphere(float x, float y, float z, float radius,
                               int skipRegion, float &dist2);

  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);
  static int __DepthOrderRegions(vtkKdNode *node,
                                 vtkIntArray *list, vtkIntArray *IdsOfInterest,
                                 double *dir, int nextId);
  static int FindInSortedList(int *list, int size, int val);
  static int FoundId(vtkIntArray *ar, int val);

//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 int __ConvexSubRegions(int *ids, int len, vtkKdNode *tree, 
                                vtkKdNode **nodes);

  static void AddNewRegions(vtkKdNode *kd, float *c1, 
                            int midpt, int dim, double coord);

  void NewPartitioningRequest(int req);

  int NumDataSetsAllocated;

  int IncludeRegionBoundaryCells;
  double CellBoundsCache[6];       // to optimize IntersectsCell()

  int GenerateRepresentationUsingDataBounds;
  int ComputeIntersectionsUsingDataBounds;

//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 NumRegions;              // number of leaf nodes

  int Timing;
  double FudgeFactor;   // a very small distance, relative to the dataset's size

  vtkDataSet **DataSets;
  int NumDataSets;

  // 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;
  int *LastDataSetType;
  double *LastInputDataInfo;
  double *LastBounds;
  int *LastNumPoints;
  int *LastNumCells;

  vtkKdTree(const vtkKdTree&); // Not implemented
  void operator=(const vtkKdTree&); // Not implemented
};

//BTX

class VTK_PARALLEL_EXPORT vtkKdNode
{
public:
  vtkKdNode();
  ~vtkKdNode();

  void SetDim(int n) { this->Dim = n; }
  int  GetDim() { return this->Dim; }

  void SetNumberOfCells(int n) { this->NumCells = n; }
  int  GetNumberOfCells() { return this->NumCells; }

  void SetBounds(double x1,double x2,double y1,double y2,double z1,double z2);
  void GetBounds(double *b) const;
  void GetBounds(float *b) const;


  void SetDataBounds(double x1,double x2,double y1,double y2,double z1,double z2);
  void SetDataBounds(float *b);  
  void GetDataBounds(double *b) const;
  void GetDataBounds(float *b) const;

  void PrintNode(int depth);
  void PrintVerboseNode(int depth);
  void AddChildNodes(vtkKdNode *left, vtkKdNode *right);

  int IntersectsBox(float x1, float x2, float y1, float y2, float z1, float z2,
                  int useDataBounds);
  int IntersectsBox(double x1,double x2,double y1,double y2,double z1,double z2,
                  int useDataBounds);
  int IntersectsSphere2(float x, float y, float z, float rSquared,
                              int useDataBounds);
  int IntersectsSphere2(double x, double y, double z, double rSquared,
                              int useDataBounds);
  int IntersectsRegion(vtkPlanesIntersection *pi, int useDataBounds);

  int IntersectsCell(vtkCell *cell, int useDataBounds, int cellRegion=-1);

  int ContainsBox(float x1, float x2, float y1, float y2, float z1, float z2,
                   int useDataBounds);
  int ContainsBox(double x1,double x2,double y1,double y2,double z1,double z2,
                   int useDataBounds);

  int ContainsPoint(float x, float y, float z, int useDataBounds);
  int ContainsPoint(double x, double y, double z, int useDataBounds);

  float GetDistance2ToBoundary(float x, float y, float z, int useDataBounds);
  float GetDistance2ToBoundary(float x, float y, float z, float *boundaryPt,
                             int useDataBounds);
  float GetDistance2ToInnerBoundary(float x, float y, float z);
  float _GetDistance2ToBoundary(float x, float y, float z, float *boundaryPt,
                             int innerBoundaryOnly, int useDataBounds);

  static const char *LevelMarker[20];

  double Min[3], Max[3];       // spatial bounds of node
  double MinVal[3], MaxVal[3]; // spatial bounds of data
  int NumCells;
  
  vtkKdNode *Up;

  vtkKdNode *Left;
  vtkKdNode *Right;

  int Dim;

  int Id;        // region id

  int MinId;
  int MaxId;

  double *CellBoundsCache;  // to optimize IntersectsCell
};
//ETX

#endif

Generated on Tue Oct 5 08:39:13 2004 for VTK by Doxygen 1.3.8-20040913