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) override;
59 
64  static vtkCellTreeLocator *New();
65 
70  vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell *cell, double pcoords[3],
71  double* weights ) override;
72 
77  int IntersectWithLine(const double a0[3], const double a1[3], double tol,
78  double& t, double x[3], double pcoords[3],
79  int &subId, vtkIdType &cellId,
80  vtkGenericCell *cell) override;
81 
87  void FindCellsWithinBounds(double *bbox, vtkIdList *cells) 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 
100  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
101  double pcoords[3], int &subId) override
102  {
103  return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
104  }
105 
112  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3],
113  double pcoords[3], int &subId, vtkIdType &cellId) override;
114 
119  const double p1[3], const double p2[3],
120  vtkPoints *points, vtkIdList *cellIds) override
121  {
122  return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
123  }
124 
128  vtkIdType FindCell(double x[3]) override
129  { return this->Superclass::FindCell(x); }
130 
132 
135  void FreeSearchStructure() override;
136  void GenerateRepresentation(int level, vtkPolyData *pd) override;
137  virtual void BuildLocatorInternal();
138  virtual void BuildLocatorIfNeeded();
139  virtual void ForceBuildLocator();
140  void BuildLocator() override;
142 
144 
148  class VTKFILTERSGENERAL_EXPORT vtkCellTree
149  {
150  public:
151  std::vector<vtkCellTreeNode> Nodes;
152  std::vector<unsigned int> Leaves;
153  friend class vtkCellPointTraversal;
154  friend class vtkCellTreeNode;
155  friend class vtkCellTreeBuilder;
157 
158  public:
159  float DataBBox[6]; // This store the bounding values of the dataset
160  };
161 
172  class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
173  {
174  public:
175 
176  protected:
177  unsigned int Index;
178  float LeftMax; // left max value
179  float RightMin; // right min value
180 
181  unsigned int Sz; // size
182  unsigned int St; // start
183 
184  friend class vtkCellTree;
185  friend class vtkCellPointTraversal;
186  friend class vtkCellTreeBuilder;
187 
188  public:
189  void MakeNode( unsigned int left, unsigned int d, float b[2] );
190  void SetChildren( unsigned int left );
191  bool IsNode() const;
192  unsigned int GetLeftChildIndex() const;
193  unsigned int GetRightChildIndex() const;
194  unsigned int GetDimension() const;
195  const float& GetLeftMaxValue() const;
196  const float& GetRightMinValue() const;
197  void MakeLeaf( unsigned int start, unsigned int size );
198  bool IsLeaf() const;
199  unsigned int Start() const;
200  unsigned int Size() const;
201  };
202 
203 protected:
205  ~vtkCellTreeLocator() override;
206 
207  // Test ray against node BBox : clip t values to extremes
208  bool RayMinMaxT(const double origin[3],
209  const double dir[3],
210  double &rTmin,
211  double &rTmax);
212 
213  bool RayMinMaxT(const double bounds[6],
214  const double origin[3],
215  const double dir[3],
216  double &rTmin,
217  double &rTmax);
218 
219  int getDominantAxis(const double dir[3]);
220 
221  // Order nodes as near/far relative to ray
222  void Classify(const double origin[3],
223  const double dir[3],
224  double &rDist,
225  vtkCellTreeNode *&near, vtkCellTreeNode *&mid,
226  vtkCellTreeNode *&far, int &mustCheck);
227 
228  // From vtkModifiedBSPTRee
229  // We provide a function which does the cell/ray test so that
230  // it can be overridden by subclasses to perform special treatment
231  // (Example : Particles stored in tree, have no dimension, so we must
232  // override the cell test to return a value based on some particle size
233  virtual int IntersectCellInternal( vtkIdType cell_ID, const double p1[3],
234  const double p2[3],
235  const double tol,
236  double &t,
237  double ipt[3],
238  double pcoords[3],
239  int &subId);
240 
241 
243 
245 
246  friend class vtkCellPointTraversal;
247  friend class vtkCellTreeNode;
248  friend class vtkCellTreeBuilder;
249 
250 private:
251  vtkCellTreeLocator(const vtkCellTreeLocator&) = delete;
252  void operator=(const vtkCellTreeLocator&) = delete;
253 };
254 
255 #endif
std::vector< vtkCellTreeNode > Nodes
virtual void BuildLocator()=0
Build the locator from the input dataset.
virtual void FindCellsWithinBounds(double *bbox, vtkIdList *cells)
Return a list of unique cell ids inside of a given bounding box.
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:349
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:84
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
provides thread-safe access to cells
virtual int IntersectWithLine(const double p1[3], const 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.
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.
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...
int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId) override
reimplemented from vtkAbstractCellLocator to support bad compilers
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
Method to build a representation at a particular level.
represent and manipulate 3D points
Definition: vtkPoints.h:39