VTK
vtkKdTree.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkKdTree.h
5 
6  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7  All rights reserved.
8  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9 
10  This software is distributed WITHOUT ANY WARRANTY; without even
11  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12  PURPOSE. See the above copyright notice for more information.
13 
14 =========================================================================*/
15 /*----------------------------------------------------------------------------
16  Copyright (c) Sandia Corporation
17  See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
18 ----------------------------------------------------------------------------*/
19 
61 #ifndef __vtkKdTree_h
62 #define __vtkKdTree_h
63 
64 #include "vtkLocator.h"
65 
66 class vtkTimerLog;
67 class vtkIdList;
68 class vtkIdTypeArray;
69 class vtkIntArray;
70 class vtkPointSet;
71 class vtkPoints;
72 class vtkCellArray;
73 class vtkCell;
74 class vtkKdNode;
75 class vtkBSPCuts;
78 
80 {
81 public:
82  vtkTypeMacro(vtkKdTree, vtkLocator);
83  void PrintSelf(ostream& os, vtkIndent indent);
84 
85  static vtkKdTree *New();
86 
88 
89  vtkBooleanMacro(Timing, int);
90  vtkSetMacro(Timing, int);
91  vtkGetMacro(Timing, int);
93 
95 
96  vtkSetMacro(MinCells, int);
97  vtkGetMacro(MinCells, int);
99 
105  vtkGetMacro(NumberOfRegionsOrLess, int);
106  vtkSetMacro(NumberOfRegionsOrLess, int);
107 
112  vtkGetMacro(NumberOfRegionsOrMore, int);
113  vtkSetMacro(NumberOfRegionsOrMore, int);
114 
120  vtkGetMacro(FudgeFactor, double);
121  vtkSetMacro(FudgeFactor, double);
122 
126  vtkGetObjectMacro(Cuts, vtkBSPCuts);
127 
132  void SetCuts(vtkBSPCuts *cuts);
133 
135  void OmitXPartitioning();
136 
138  void OmitYPartitioning();
139 
141  void OmitZPartitioning();
142 
144  void OmitXYPartitioning();
145 
147  void OmitYZPartitioning();
148 
150  void OmitZXPartitioning();
151 
153  void OmitNoPartitioning();
154 
164  virtual void SetDataSet(vtkDataSet *set);
165 
169  virtual void AddDataSet(vtkDataSet *set);
170 
172 
173  virtual void RemoveDataSet(int index);
174  virtual void RemoveDataSet(vtkDataSet *set);
175  virtual void RemoveAllDataSets();
177 
179  int GetNumberOfDataSets();
180 
186  vtkDataSet *GetDataSet(int n);
187 
190  vtkDataSet *GetDataSet(){ return this->GetDataSet(0); }
191 
193 
194  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
196 
199  int GetDataSetIndex(vtkDataSet *set);
200 
203  void GetBounds(double *bounds);
204 
211  void SetNewBounds(double *bounds);
212 
214 
215  vtkGetMacro(NumberOfRegions, int);
217 
219  void GetRegionBounds(int regionID, double bounds[6]);
220 
222  void GetRegionDataBounds(int regionID, double bounds[6]);
223 
225 
226  void PrintTree();
227  void PrintVerboseTree();
229 
231  void PrintRegion(int id);
232 
241  void CreateCellLists(int dataSetIndex, int *regionReqList,
242  int reqListSize);
243  void CreateCellLists(vtkDataSet *set, int *regionReqList,
244  int reqListSize);
245  void CreateCellLists(int *regionReqList, int listSize);
246  void CreateCellLists();
247 
249 
253  vtkSetMacro(IncludeRegionBoundaryCells, int);
254  vtkGetMacro(IncludeRegionBoundaryCells, int);
255  vtkBooleanMacro(IncludeRegionBoundaryCells, int);
257 
259  void DeleteCellLists();
260 
263  vtkIdList *GetCellList(int regionID);
264 
272  vtkIdList *GetBoundaryCellList(int regionID);
273 
275 
289  vtkIdType GetCellLists(vtkIntArray *regions, int set,
290  vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
291  vtkIdType GetCellLists(vtkIntArray *regions, vtkDataSet *set,
292  vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
293  vtkIdType GetCellLists(vtkIntArray *regions, vtkIdList *inRegionCells,
294  vtkIdList *onBoundaryCells);
296 
298 
301  int GetRegionContainingCell(vtkDataSet *set, vtkIdType cellID);
302  int GetRegionContainingCell(int set, vtkIdType cellID);
303  int GetRegionContainingCell(vtkIdType cellID);
305 
310  int *AllGetRegionContainingCell();
311 
313  int GetRegionContainingPoint(double x, double y, double z);
314 
318  void BuildLocator();
319 
331  int MinimalNumberOfConvexSubRegions(vtkIntArray *regionIdList,
332  double **convexRegionBounds);
333 
336  VTK_LEGACY(int DepthOrderAllRegions(double *dop, vtkIntArray *orderedList));
337 
339 
341  VTK_LEGACY(int DepthOrderRegions(vtkIntArray *regionIds, double *dop,
342  vtkIntArray *orderedList));
344 
346 
352  int ViewOrderAllRegionsInDirection(const double directionOfProjection[3],
353  vtkIntArray *orderedList);
355 
357 
362  int ViewOrderRegionsInDirection(vtkIntArray *regionIds,
363  const double directionOfProjection[3],
364  vtkIntArray *orderedList);
366 
368 
374  int ViewOrderAllRegionsFromPosition(const double directionOfProjection[3],
375  vtkIntArray *orderedList);
377 
379 
384  int ViewOrderRegionsFromPosition(vtkIntArray *regionIds,
385  const double directionOfProjection[3],
386  vtkIntArray *orderedList);
388 
390 
398  void BuildLocatorFromPoints(vtkPointSet *pointset);
399  void BuildLocatorFromPoints(vtkPoints *ptArray);
400  void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays);
402 
412  vtkIdTypeArray *BuildMapForDuplicatePoints(float tolerance);
413 
415 
418  vtkIdType FindPoint(double *x);
419  vtkIdType FindPoint(double x, double y, double z);
421 
423 
426  vtkIdType FindClosestPoint(double *x, double &dist2);
427  vtkIdType FindClosestPoint(double x, double y, double z, double &dist2);
429 
431 
434  vtkIdType FindClosestPointWithinRadius(
435  double radius, const double x[3], double& dist2);
437 
439 
442  vtkIdType FindClosestPointInRegion(int regionId, double *x, double &dist2);
443  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z,
444  double &dist2);
446 
451  void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result);
452 
459  void FindClosestNPoints(int N, const double x[3], vtkIdList *result);
460 
463  vtkIdTypeArray *GetPointsInRegion(int regionId);
464 
467  void FreeSearchStructure();
468 
472 
475  void GenerateRepresentation(int *regionList, int len, vtkPolyData *pd);
476 
478 
482  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, int);
483  vtkSetMacro(GenerateRepresentationUsingDataBounds, int);
484  vtkGetMacro(GenerateRepresentationUsingDataBounds, int);
486 
488  virtual void PrintTiming(ostream& os, vtkIndent indent);
489 
492  virtual int NewGeometry();
493 
496  virtual int NewGeometry(vtkDataSet **sets, int numDataSets);
497 
501  virtual void InvalidateGeometry();
502 
506  static vtkKdNode *CopyTree(vtkKdNode *kd);
507 
512  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
513 
514 protected:
515 
516  vtkKdTree();
517  ~vtkKdTree();
518 
521 
522  void SetCalculator(vtkKdNode *kd);
523 
524  int ProcessUserDefinedCuts(double *bounds);
525 
526  void SetCuts(vtkBSPCuts *cuts, int userDefined);
527 
531  void UpdateBuildTime();
532 
538  int DivideTest(int numberOfPoints, int level);
539 
540 //BTX
541  enum {
542  XDIM = 0, // don't change these values
543  YDIM = 1,
544  ZDIM = 2
545  };
546 //ETX
547 
549 
551  vtkKdNode **RegionList; // indexed by region ID
552 
554 
555  static void DeleteAllDescendants(vtkKdNode *nd);
556 
557  void BuildRegionList();
558  virtual int SelectCutDirection(vtkKdNode *kd);
559  void SetActualLevel(){this->Level = vtkKdTree::ComputeLevel(this->Top);}
560 
564  void GetRegionsAtLevel(int level, vtkKdNode **nodes);
565 
569  static void GetLeafNodeIds(vtkKdNode *node, vtkIntArray *ids);
570 
571 
574  int GetNumberOfCells();
575 
578  int GetDataSetsNumberOfCells(int set1, int set2);
579 
584  void ComputeCellCenter(vtkDataSet *set, int cellId, float *center);
585  void ComputeCellCenter(vtkDataSet *set, int cellId, double *center);
586 
593  float *ComputeCellCenters();
594  float *ComputeCellCenters(int set);
595  float *ComputeCellCenters(vtkDataSet *set);
596 
598 
599  virtual void ReportReferences(vtkGarbageCollector*);
600 
603  void UpdateProgress(double amount);
604 
606 
607  vtkSetClampMacro(Progress,double,0.0,1.0);
608  vtkGetMacro(Progress,double);
610 
611 protected:
612  // So that each suboperation can report progress
613  // in [0,1], yet we will be able to report a global
614  // progress. Sub-operations must use UpdateSubOperationProgress()
615  // for this to work.
616  double ProgressScale;
618 
619  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
620  // Actual progress is given by
621  // (this->ProgressOffset + this->ProgressScale* amount).
622  void UpdateSubOperationProgress(double amount);
623 
624  static void _SetNewBounds(vtkKdNode *kd, double *b, int *fixDim);
625  static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from);
626  static void CopyKdNode(vtkKdNode *to, vtkKdNode *from);
627  static void SetDataBoundsToSpatialBounds(vtkKdNode *kd);
628  static void ZeroNumberOfPoints(vtkKdNode *kd);
629 
630 //BTX
631  // Recursive helper for public FindPointsWithinRadius
632  void FindPointsWithinRadius(vtkKdNode* node, double R2,
633  const double x[3], vtkIdList* ids);
634 
635  // Recursive helper for public FindPointsWithinRadius
636  void AddAllPointsInRegion(vtkKdNode* node, vtkIdList* ids);
637 
638  // Recursive helper for public FindPointsInArea
639  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
640 
641  // Recursive helper for public FindPointsInArea
642  void AddAllPointsInRegion(vtkKdNode* node, vtkIdTypeArray* ids);
643 
644  int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels);
645 
646  void DoMedianFind(vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3);
647 
648  void SelfRegister(vtkKdNode *kd);
649 
650  struct _cellList{
651  vtkDataSet *dataSet; // cell lists for which data set
652  int *regionIds; // NULL if listing all regions
653  int nRegions;
657  };
658 //ETX
659 
660  void InitializeCellLists();
661  vtkIdList *GetList(int regionId, vtkIdList **which);
662 
663  void ComputeCellCenter(vtkCell* cell, double *center, double *weights);
664 
665  void GenerateRepresentationDataBounds(int level, vtkPolyData *pd);
666  void _generateRepresentationDataBounds(vtkKdNode *kd, vtkPoints *pts,
667  vtkCellArray *polys, int level);
668 
669  void GenerateRepresentationWholeSpace(int level, vtkPolyData *pd);
670  void _generateRepresentationWholeSpace(vtkKdNode *kd, vtkPoints *pts,
671  vtkCellArray *polys, int level);
672 
673  void AddPolys(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys);
674 
675  void _printTree(int verbose);
676 
677  int SearchNeighborsForDuplicate(int regionId, float *point,
678  int **pointsSoFar, int *len,
679  float tolerance, float tolerance2);
680 
681  int SearchRegionForDuplicate(float *point, int *pointsSoFar,
682  int len, float tolerance2);
683 
684  int _FindClosestPointInRegion(int regionId,
685  double x, double y, double z, double &dist2);
686 
687  int FindClosestPointInSphere(double x, double y, double z, double radius,
688  int skipRegion, double &dist2);
689 
690  int _ViewOrderRegionsInDirection(vtkIntArray *IdsOfInterest,
691  const double dop[3],
692  vtkIntArray *orderedList);
693 
694  static int __ViewOrderRegionsInDirection(vtkKdNode *node, vtkIntArray *list,
695  vtkIntArray *IdsOfInterest,
696  const double dir[3], int nextId);
697 
698  int _ViewOrderRegionsFromPosition(vtkIntArray *IdsOfInterest,
699  const double pos[3],
700  vtkIntArray *orderedList);
701 
702  static int __ViewOrderRegionsFromPosition(vtkKdNode *node, vtkIntArray *list,
703  vtkIntArray *IdsOfInterest,
704  const double pos[3], int nextId);
705 
706  static int __ConvexSubRegions(int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes);
707  static int FoundId(vtkIntArray *idArray, int id);
708 
709  void NewParitioningRequest(int req);
710  void SetInputDataInfo(int i,
711  int dims[3], double origin[3], double spacing[3]);
712  int CheckInputDataInfo(int i,
713  int dims[3], double origin[3], double spacing[3]);
714  void ClearLastBuildCache();
715 
716 //BTX
717  static void __printTree(vtkKdNode *kd, int depth, int verbose);
718 //ETX
719 
720  static int MidValue(int dim, float *c1, int nvals, double &coord);
721 
722  static int Select(int dim, float *c1, int *ids, int nvals, double &coord);
723  static float FindMaxLeftHalf(int dim, float *c1, int K);
724  static void _Select(int dim, float *X, int *ids, int L, int R, int K);
725 
726 //BTX
727  static int ComputeLevel(vtkKdNode *kd);
728  static int SelfOrder(int id, vtkKdNode *kd);
729  static int findRegion(vtkKdNode *node, float x, float y, float z);
730  static int findRegion(vtkKdNode *node, double x, double y, double z);
731 //ETX
732 
733  static vtkKdNode **_GetRegionsAtLevel(int level, vtkKdNode **nodes,
734  vtkKdNode *kd);
735 
736  static void AddNewRegions(vtkKdNode *kd, float *c1,
737  int midpt, int dim, double coord);
738 
739  void NewPartitioningRequest(int req);
740 
743 
745  double CellBoundsCache[6]; // to optimize IntersectsCell()
746 
748 
749 //BTX
750  struct _cellList CellList;
751 //ETX
752 
753  // Region Ids, by data set by cell id - this list is large (one
754  // int per cell) but accelerates creation of cell lists
755 
757 
758  int MinCells;
759  int NumberOfRegions; // number of leaf nodes
760 
761  int Timing;
762  double FudgeFactor; // a very small distance, relative to the dataset's size
763 
764  // These instance variables are used by the special locator created
765  // to find duplicate points. (BuildLocatorFromPoints)
766 
771 
772  float MaxWidth;
773 
774  // These Last* values are here to save state so we can
775  // determine later if k-d tree must be rebuilt.
776 
780  unsigned long *LastDataSetObserverTags;
783  double *LastBounds;
786 
788  double Progress;
789 
790  vtkKdTree(const vtkKdTree&); // Not implemented
791  void operator=(const vtkKdTree&); // Not implemented
792 };
793 #endif