VTK
|
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