VTK
vtkCellTreeLocator.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkCellTreeLocator.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 =========================================================================*/
40 #ifndef vtkCellTreeLocator_h
41 #define vtkCellTreeLocator_h
42 
43 #include "vtkFiltersGeneralModule.h" // For export macro
44 #include "vtkAbstractCellLocator.h"
45 #include <vector> // Needed for internal class
46 
47 class vtkCellPointTraversal;
48 class vtkIdTypeArray;
49 class vtkCellArray;
50 
51 class VTKFILTERSGENERAL_EXPORT vtkCellTreeLocator : public vtkAbstractCellLocator
52 {
53  public:
54  class vtkCellTree;
56 
58  void PrintSelf(ostream& os, vtkIndent indent) VTK_OVERRIDE;
59 
64  static vtkCellTreeLocator *New();
65 
70  vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell *cell, double pcoords[3],
71  double* weights ) VTK_OVERRIDE;
72 
77  int IntersectWithLine(double a0[3], double a1[3], double tol,
78  double& t, double x[3], double pcoords[3],
79  int &subId, vtkIdType &cellId,
80  vtkGenericCell *cell) VTK_OVERRIDE;
81 
87  void FindCellsWithinBounds(double *bbox, vtkIdList *cells) VTK_OVERRIDE;
88 
89  /*
90  if the borland compiler is ever removed, we can use these declarations
91  instead of reimplementaing the calls in this subclass
92  using vtkAbstractCellLocator::IntersectWithLine;
93  using vtkAbstractCellLocator::FindClosestPoint;
94  using vtkAbstractCellLocator::FindClosestPointWithinRadius;
95  */
96 
101  double p1[3], double p2[3], double tol, double& t, double x[3],
102  double pcoords[3], int &subId) VTK_OVERRIDE
103  {
104  return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
105  }
106 
113  int IntersectWithLine(
114  double p1[3], double p2[3], double tol, double &t, double x[3],
115  double pcoords[3], int &subId, vtkIdType &cellId) VTK_OVERRIDE;
116 
121  const double p1[3], const double p2[3],
122  vtkPoints *points, vtkIdList *cellIds) VTK_OVERRIDE
123  {
124  return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
125  }
126 
130  vtkIdType FindCell(double x[3]) VTK_OVERRIDE
131  { return this->Superclass::FindCell(x); }
132 
134 
137  void FreeSearchStructure() VTK_OVERRIDE;
138  void GenerateRepresentation(int level, vtkPolyData *pd) VTK_OVERRIDE;
139  virtual void BuildLocatorInternal();
140  virtual void BuildLocatorIfNeeded();
141  virtual void ForceBuildLocator();
142  void BuildLocator() VTK_OVERRIDE;
144 
146 
150  class VTKFILTERSGENERAL_EXPORT vtkCellTree
151  {
152  public:
153  std::vector<vtkCellTreeNode> Nodes;
154  std::vector<unsigned int> Leaves;
155  friend class vtkCellPointTraversal;
156  friend class vtkCellTreeNode;
157  friend class vtkCellTreeBuilder;
159 
160  public:
161  float DataBBox[6]; // This store the bounding values of the dataset
162  };
163 
174  class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
175  {
176  public:
177 
178  protected:
179  unsigned int Index;
180  float LeftMax; // left max value
181  float RightMin; // right min value
182 
183  unsigned int Sz; // size
184  unsigned int St; // start
185 
186  friend class vtkCellTree;
187  friend class vtkCellPointTraversal;
188  friend class vtkCellTreeBuilder;
189 
190  public:
191  void MakeNode( unsigned int left, unsigned int d, float b[2] );
192  void SetChildren( unsigned int left );
193  bool IsNode() const;
194  unsigned int GetLeftChildIndex() const;
195  unsigned int GetRightChildIndex() const;
196  unsigned int GetDimension() const;
197  const float& GetLeftMaxValue() const;
198  const float& GetRightMinValue() const;
199  void MakeLeaf( unsigned int start, unsigned int size );
200  bool IsLeaf() const;
201  unsigned int Start() const;
202  unsigned int Size() const;
203  };
204 
205 protected:
207  ~vtkCellTreeLocator() VTK_OVERRIDE;
208 
209  // Test ray against node BBox : clip t values to extremes
210  bool RayMinMaxT(const double origin[3],
211  const double dir[3],
212  double &rTmin,
213  double &rTmax);
214 
215  bool RayMinMaxT(const double bounds[6],
216  const double origin[3],
217  const double dir[3],
218  double &rTmin,
219  double &rTmax);
220 
221  int getDominantAxis(const double dir[3]);
222 
223  // Order nodes as near/far relative to ray
224  void Classify(const double origin[3],
225  const double dir[3],
226  double &rDist,
227  vtkCellTreeNode *&near, vtkCellTreeNode *&mid,
228  vtkCellTreeNode *&far, int &mustCheck);
229 
230  // From vtkModifiedBSPTRee
231  // We provide a function which does the cell/ray test so that
232  // it can be overriden by subclasses to perform special treatment
233  // (Example : Particles stored in tree, have no dimension, so we must
234  // override the cell test to return a value based on some particle size
235  virtual int IntersectCellInternal( vtkIdType cell_ID, const double p1[3],
236  const double p2[3],
237  const double tol,
238  double &t,
239  double ipt[3],
240  double pcoords[3],
241  int &subId);
242 
243 
244  int NumberOfBuckets;
245 
246  vtkCellTree* Tree;
247 
248  friend class vtkCellPointTraversal;
249  friend class vtkCellTreeNode;
250  friend class vtkCellTreeBuilder;
251 
252 private:
253  vtkCellTreeLocator(const vtkCellTreeLocator&) VTK_DELETE_FUNCTION;
254  void operator=(const vtkCellTreeLocator&) VTK_DELETE_FUNCTION;
255 };
256 
257 #endif
std::vector< vtkCellTreeNode > Nodes
virtual void FindCellsWithinBounds(double *bbox, vtkIdList *cells)
Return a list of unique cell ids inside of a given bounding box.
int IntersectWithLine(double p1[3], double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId) override
reimplemented from vtkAbstractCellLocator to support bad compilers
Internal classes made public to allow subclasses to create customized some traversal algorithms...
an abstract base class for locators which find cells
dynamic, self-adjusting array of vtkIdType
int vtkIdType
Definition: vtkType.h:287
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:85
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
provides thread-safe access to cells
a simple class to control print indentation
Definition: vtkIndent.h:39
virtual vtkIdType FindCell(double x[3])
Returns the Id of the cell containing the point, returns -1 if no cell found.
list of point or cell ids
Definition: vtkIdList.h:36
std::vector< unsigned int > Leaves
vtkIdType FindCell(double x[3]) override
reimplemented from vtkAbstractCellLocator to support bad compilers
This class is the basic building block of the cell tree.
virtual int IntersectWithLine(double p1[3], double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId)
Return intersection point (if any) of finite line with cells contained in cell locator.
object to represent cell connectivity
Definition: vtkCellArray.h:50
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
int IntersectWithLine(const double p1[3], const double p2[3], vtkPoints *points, vtkIdList *cellIds) override
reimplemented from vtkAbstractCellLocator to support bad compilers
static vtkObject * New()
Create an object with Debug turned off, modified time initialized to zero, and reference counting on...
This class implements the data structures, construction algorithms for fast cell location presented i...
represent and manipulate 3D points
Definition: vtkPoints.h:39