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

dox/Filtering/vtkKdTree.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Visualization Toolkit
00004   Module:    $RCSfile: vtkKdTree.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 
00061 #ifndef __vtkKdTree_h
00062 #define __vtkKdTree_h
00063 
00064 #include "vtkLocator.h"
00065 
00066 class vtkTimerLog;
00067 class vtkIdList;
00068 class vtkIdTypeArray;
00069 class vtkIntArray;
00070 class vtkPointSet;
00071 class vtkPoints;
00072 class vtkCellArray;
00073 class vtkCell;
00074 class vtkKdNode;
00075 class vtkBSPCuts;
00076 class vtkBSPIntersections;
00077 class vtkDataSetCollection;
00078 
00079 class VTK_FILTERING_EXPORT vtkKdTree : public vtkLocator
00080 {
00081 public:
00082   vtkTypeRevisionMacro(vtkKdTree, vtkLocator);
00083   void PrintSelf(ostream& os, vtkIndent indent);
00084 
00085   static vtkKdTree *New();
00086 
00088 
00089   vtkBooleanMacro(Timing, int);
00090   vtkSetMacro(Timing, int);
00091   vtkGetMacro(Timing, int);
00093 
00095 
00096   vtkSetMacro(MinCells, int);
00097   vtkGetMacro(MinCells, int);
00099 
00104   vtkGetMacro(NumberOfRegionsOrLess, int);
00105   vtkSetMacro(NumberOfRegionsOrLess, int);
00106 
00111   vtkGetMacro(NumberOfRegionsOrMore, int);
00112   vtkSetMacro(NumberOfRegionsOrMore, int);
00113   
00119   vtkGetMacro(FudgeFactor, double);
00120   vtkSetMacro(FudgeFactor, double);
00121 
00125   vtkGetObjectMacro(Cuts, vtkBSPCuts);
00126 
00131   void SetCuts(vtkBSPCuts *cuts);
00132 
00134   void OmitXPartitioning();
00135   
00137   void OmitYPartitioning();
00138 
00140   void OmitZPartitioning();
00141 
00143   void OmitXYPartitioning();
00144 
00146   void OmitYZPartitioning();
00147   
00149   void OmitZXPartitioning();
00150 
00152   void OmitNoPartitioning();
00153 
00163   virtual void SetDataSet(vtkDataSet *set);
00164 
00168   virtual void AddDataSet(vtkDataSet *set);
00169 
00171 
00172   virtual void RemoveDataSet(int index);
00173   virtual void RemoveDataSet(vtkDataSet *set);
00174   virtual void RemoveAllDataSets();
00176 
00178   int GetNumberOfDataSets();
00179 
00185   vtkDataSet *GetDataSet(int n);
00186 
00189   vtkDataSet *GetDataSet(){ return this->GetDataSet(0); }
00190 
00192 
00193   vtkGetObjectMacro(DataSets, vtkDataSetCollection);
00195 
00198   int GetDataSetIndex(vtkDataSet *set);
00199 
00202   void GetBounds(double *bounds);
00203 
00210   void SetNewBounds(double *bounds);
00211 
00213 
00214   vtkGetMacro(NumberOfRegions, int);
00216 
00218   void GetRegionBounds(int regionID, double bounds[6]);
00219 
00221   void GetRegionDataBounds(int regionID, double bounds[6]);
00222 
00224 
00225   void PrintTree();
00226   void PrintVerboseTree();
00228   
00230   void PrintRegion(int id);
00231   
00240   void CreateCellLists(int dataSetIndex, int *regionReqList, 
00241                        int reqListSize);
00242   void CreateCellLists(vtkDataSet *set, int *regionReqList,
00243                        int reqListSize);
00244   void CreateCellLists(int *regionReqList, int listSize);
00245   void CreateCellLists(); 
00246   
00248 
00252   vtkSetMacro(IncludeRegionBoundaryCells, int);
00253   vtkGetMacro(IncludeRegionBoundaryCells, int);
00254   vtkBooleanMacro(IncludeRegionBoundaryCells, int);
00256 
00258   void DeleteCellLists();
00259 
00262   vtkIdList *GetCellList(int regionID);
00263 
00271   vtkIdList *GetBoundaryCellList(int regionID);
00272 
00274 
00288   vtkIdType GetCellLists(vtkIntArray *regions, int set, 
00289                    vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
00290   vtkIdType GetCellLists(vtkIntArray *regions, vtkDataSet *set,
00291             vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
00292   vtkIdType GetCellLists(vtkIntArray *regions, vtkIdList *inRegionCells,
00293                                     vtkIdList *onBoundaryCells);
00295   
00297 
00300   int GetRegionContainingCell(vtkDataSet *set, vtkIdType cellID);
00301   int GetRegionContainingCell(int set, vtkIdType cellID);
00302   int GetRegionContainingCell(vtkIdType cellID);
00304 
00309   int *AllGetRegionContainingCell();
00310 
00312   int GetRegionContainingPoint(double x, double y, double z);
00313   
00317   void BuildLocator();
00318 
00330   int MinimalNumberOfConvexSubRegions(vtkIntArray *regionIdList,
00331                                       double **convexRegionBounds);
00332 
00335   VTK_LEGACY(int DepthOrderAllRegions(double *dop, vtkIntArray *orderedList));
00336 
00338 
00340   VTK_LEGACY(int DepthOrderRegions(vtkIntArray *regionIds, double *dop,
00341                                    vtkIntArray *orderedList));
00343 
00345 
00351   int ViewOrderAllRegionsInDirection(const double directionOfProjection[3],
00352                                      vtkIntArray *orderedList);
00354 
00356 
00361   int ViewOrderRegionsInDirection(vtkIntArray *regionIds,
00362                                   const double directionOfProjection[3],
00363                                   vtkIntArray *orderedList);
00365 
00367 
00373   int ViewOrderAllRegionsFromPosition(const double directionOfProjection[3],
00374                                       vtkIntArray *orderedList);
00376 
00378 
00383   int ViewOrderRegionsFromPosition(vtkIntArray *regionIds,
00384                                    const double directionOfProjection[3],
00385                                    vtkIntArray *orderedList);
00387 
00389 
00397   void BuildLocatorFromPoints(vtkPointSet *pointset);
00398   void BuildLocatorFromPoints(vtkPoints *ptArray);
00399   void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays);
00401   
00411   vtkIdTypeArray *BuildMapForDuplicatePoints(float tolerance);
00412 
00414 
00417   vtkIdType FindPoint(double *x);
00418   vtkIdType FindPoint(double x, double y, double z);
00420 
00422 
00425   vtkIdType FindClosestPoint(double *x, double &dist2);
00426   vtkIdType FindClosestPoint(double x, double y, double z, double &dist2);
00428 
00430 
00433   vtkIdType FindClosestPointWithinRadius(
00434     double radius, const double x[3], double& dist2);
00436 
00438 
00441   vtkIdType FindClosestPointInRegion(int regionId, double *x, double &dist2);
00442   vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, 
00443                                      double &dist2);
00445 
00450   void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result);
00451 
00458   void FindClosestNPoints(int N, const double x[3], vtkIdList *result);
00459 
00462   vtkIdTypeArray *GetPointsInRegion(int regionId);
00463 
00466   void FreeSearchStructure();
00467   
00470   void GenerateRepresentation(int level, vtkPolyData *pd);
00471   
00474   void GenerateRepresentation(int *regionList, int len, vtkPolyData *pd);
00475 
00477 
00481   vtkBooleanMacro(GenerateRepresentationUsingDataBounds, int);
00482   vtkSetMacro(GenerateRepresentationUsingDataBounds, int);
00483   vtkGetMacro(GenerateRepresentationUsingDataBounds, int);
00485 
00487   virtual void PrintTiming(ostream& os, vtkIndent indent);
00488 
00491   virtual int NewGeometry();
00492 
00495   virtual int NewGeometry(vtkDataSet **sets, int numDataSets);
00496 
00500   virtual void InvalidateGeometry();
00501 
00505   static vtkKdNode *CopyTree(vtkKdNode *kd);
00506 
00511   void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
00512 
00513 protected:
00514 
00515   vtkKdTree();
00516   ~vtkKdTree();
00517 
00518   vtkBSPIntersections *BSPCalculator;
00519   int UserDefinedCuts;
00520 
00521   void SetCalculator(vtkKdNode *kd);
00522 
00523   int ProcessUserDefinedCuts(double *bounds);
00524 
00525   void SetCuts(vtkBSPCuts *cuts, int userDefined);
00526 
00530   void UpdateBuildTime();
00531 
00537   int DivideTest(int numberOfPoints, int level);
00538 
00539 //BTX
00540   enum {
00541     XDIM = 0,  // don't change these values
00542     YDIM = 1,
00543     ZDIM = 2
00544   };
00545 //ETX
00546 
00547   int ValidDirections;
00548 
00549   vtkKdNode *Top;
00550   vtkKdNode **RegionList;      // indexed by region ID
00551 
00552   vtkTimerLog *TimerLog;
00553 
00554   static void DeleteAllDescendants(vtkKdNode *nd);
00555 
00556   void BuildRegionList();
00557   virtual int SelectCutDirection(vtkKdNode *kd);
00558   void SetActualLevel(){this->Level = vtkKdTree::ComputeLevel(this->Top);}
00559 
00563   void GetRegionsAtLevel(int level, vtkKdNode **nodes);
00564 
00568   static void GetLeafNodeIds(vtkKdNode *node, vtkIntArray *ids);
00569 
00570 
00573   int GetNumberOfCells();
00574 
00577   int GetDataSetsNumberOfCells(int set1, int set2);
00578 
00583   void ComputeCellCenter(vtkDataSet *set, int cellId, float *center);
00584   void ComputeCellCenter(vtkDataSet *set, int cellId, double *center);
00585 
00592   float *ComputeCellCenters();
00593   float *ComputeCellCenters(int set);
00594   float *ComputeCellCenters(vtkDataSet *set);
00595 
00596   vtkDataSetCollection *DataSets;
00597 
00598   virtual void ReportReferences(vtkGarbageCollector*);
00599 
00602   void UpdateProgress(double amount);
00603 
00605 
00606   vtkSetClampMacro(Progress,double,0.0,1.0);
00607   vtkGetMacro(Progress,double);
00609 
00610 protected:
00611   // So that each suboperation can report progress
00612   // in [0,1], yet we will be able to report a global 
00613   // progress. Sub-operations must use UpdateSubOperationProgress()
00614   // for this to work.
00615   double ProgressScale;
00616   double ProgressOffset;
00617   
00618   // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
00619   // Actual progress is given by 
00620   // (this->ProgressOffset + this->ProgressScale* amount).
00621   void UpdateSubOperationProgress(double amount);
00622 
00623   static void _SetNewBounds(vtkKdNode *kd, double *b, int *fixDim);
00624   static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from);
00625   static void CopyKdNode(vtkKdNode *to, vtkKdNode *from);
00626   static void SetDataBoundsToSpatialBounds(vtkKdNode *kd);
00627   static void ZeroNumberOfPoints(vtkKdNode *kd);
00628 
00629 //BTX
00630   // Recursive helper for public FindPointsWithinRadius
00631   void FindPointsWithinRadius(vtkKdNode* node, double R2, 
00632                               const double x[3], vtkIdList* ids);  
00633 
00634   // Recursive helper for public FindPointsWithinRadius
00635   void AddAllPointsInRegion(vtkKdNode* node, vtkIdList* ids);
00636 
00637   // Recursive helper for public FindPointsInArea
00638   void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
00639 
00640   // Recursive helper for public FindPointsInArea
00641   void AddAllPointsInRegion(vtkKdNode* node, vtkIdTypeArray* ids);
00642 
00643   int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels);
00644 
00645   void DoMedianFind(vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3);
00646 
00647   void SelfRegister(vtkKdNode *kd);
00648 
00649   struct _cellList{
00650     vtkDataSet *dataSet;        // cell lists for which data set
00651     int *regionIds;            // NULL if listing all regions
00652     int nRegions;
00653     vtkIdList **cells;
00654     vtkIdList **boundaryCells;
00655     vtkIdList *emptyList;
00656   };
00657 //ETX
00658 
00659   void InitializeCellLists();
00660   vtkIdList *GetList(int regionId, vtkIdList **which);
00661 
00662   void ComputeCellCenter(vtkCell* cell, double *center, double *weights);
00663 
00664   void GenerateRepresentationDataBounds(int level, vtkPolyData *pd);
00665   void _generateRepresentationDataBounds(vtkKdNode *kd, vtkPoints *pts,
00666                                          vtkCellArray *polys, int level);
00667 
00668   void GenerateRepresentationWholeSpace(int level, vtkPolyData *pd);
00669   void _generateRepresentationWholeSpace(vtkKdNode *kd, vtkPoints *pts,
00670                                          vtkCellArray *polys, int level);
00671 
00672   void AddPolys(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys);
00673 
00674   void _printTree(int verbose);
00675 
00676   int SearchNeighborsForDuplicate(int regionId, float *point,
00677                                   int **pointsSoFar, int *len, 
00678                                   float tolerance, float tolerance2);
00679 
00680   int SearchRegionForDuplicate(float *point, int *pointsSoFar, 
00681                                int len, float tolerance2);
00682 
00683   int _FindClosestPointInRegion(int regionId, 
00684                           double x, double y, double z, double &dist2);
00685 
00686   int FindClosestPointInSphere(double x, double y, double z, double radius,
00687                                int skipRegion, double &dist2);
00688 
00689   int _ViewOrderRegionsInDirection(vtkIntArray *IdsOfInterest,
00690                                    const double dop[3],
00691                                    vtkIntArray *orderedList);
00692 
00693   static int __ViewOrderRegionsInDirection(vtkKdNode *node, vtkIntArray *list, 
00694                                            vtkIntArray *IdsOfInterest,
00695                                            const double dir[3], int nextId);
00696 
00697   int _ViewOrderRegionsFromPosition(vtkIntArray *IdsOfInterest,
00698                                     const double pos[3],
00699                                     vtkIntArray *orderedList);
00700 
00701   static int __ViewOrderRegionsFromPosition(vtkKdNode *node, vtkIntArray *list, 
00702                                             vtkIntArray *IdsOfInterest,
00703                                             const double pos[3], int nextId);
00704 
00705   static int __ConvexSubRegions(int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes);
00706   static int FoundId(vtkIntArray *idArray, int id);
00707 
00708   void NewParitioningRequest(int req);
00709   void SetInputDataInfo(int i, 
00710        int dims[3], double origin[3], double spacing[3]);
00711   int CheckInputDataInfo(int i, 
00712        int dims[3], double origin[3], double spacing[3]);
00713   void ClearLastBuildCache();
00714 
00715 //BTX
00716   static void __printTree(vtkKdNode *kd, int depth, int verbose);
00717 //ETX
00718 
00719   static int MidValue(int dim, float *c1, int nvals, double &coord);
00720 
00721   static int Select(int dim, float *c1, int *ids, int nvals, double &coord);
00722   static float FindMaxLeftHalf(int dim, float *c1, int K);
00723   static void _Select(int dim, float *X, int *ids, int L, int R, int K);
00724 
00725 //BTX
00726   static int ComputeLevel(vtkKdNode *kd);
00727   static int SelfOrder(int id, vtkKdNode *kd);
00728   static int findRegion(vtkKdNode *node, float x, float y, float z);
00729   static int findRegion(vtkKdNode *node, double x, double y, double z);
00730 //ETX
00731 
00732   static vtkKdNode **_GetRegionsAtLevel(int level, vtkKdNode **nodes, 
00733                                         vtkKdNode *kd);
00734 
00735   static void AddNewRegions(vtkKdNode *kd, float *c1, 
00736                             int midpt, int dim, double coord);
00737 
00738   void NewPartitioningRequest(int req);
00739 
00740   int NumberOfRegionsOrLess;
00741   int NumberOfRegionsOrMore;
00742 
00743   int IncludeRegionBoundaryCells;
00744   double CellBoundsCache[6];       // to optimize IntersectsCell()
00745 
00746   int GenerateRepresentationUsingDataBounds;
00747 
00748 //BTX
00749   struct _cellList CellList;
00750 //ETX
00751 
00752   // Region Ids, by data set by cell id - this list is large (one
00753   // int per cell) but accelerates creation of cell lists
00754 
00755   int *CellRegionList;
00756 
00757   int MinCells;
00758   int NumberOfRegions;              // number of leaf nodes
00759 
00760   int Timing;
00761   double FudgeFactor;   // a very small distance, relative to the dataset's size
00762 
00763   // These instance variables are used by the special locator created
00764   // to find duplicate points. (BuildLocatorFromPoints)
00765 
00766   int NumberOfLocatorPoints;
00767   float *LocatorPoints;
00768   int *LocatorIds;
00769   int *LocatorRegionLocation;
00770 
00771   float MaxWidth;
00772 
00773   // These Last* values are here to save state so we can
00774   // determine later if k-d tree must be rebuilt.
00775 
00776   int LastNumDataSets;
00777   int LastDataCacheSize;
00778   vtkDataSet **LastInputDataSets;
00779   unsigned long *LastDataSetObserverTags;
00780   int *LastDataSetType;
00781   double *LastInputDataInfo;
00782   double *LastBounds;
00783   vtkIdType *LastNumPoints;
00784   vtkIdType *LastNumCells;
00785 
00786   vtkBSPCuts *Cuts;
00787   double Progress;
00788 
00789   vtkKdTree(const vtkKdTree&); // Not implemented
00790   void operator=(const vtkKdTree&); // Not implemented
00791 };
00792 #endif

Generated by  doxygen 1.7.1