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 =========================================================================*/
37 #ifndef vtkCellTreeLocator_h
38 #define vtkCellTreeLocator_h
39 
40 #include "vtkFiltersGeneralModule.h" // For export macro
41 #include "vtkAbstractCellLocator.h"
42 #include <vector> // Needed for internal class
43 
44 class vtkCellPointTraversal;
45 class vtkIdTypeArray;
46 class vtkCellArray;
47 
48 class VTKFILTERSGENERAL_EXPORT vtkCellTreeLocator : public vtkAbstractCellLocator
49 {
50  public:
51  class vtkCellTree;
53 
55  void PrintSelf(ostream& os, vtkIndent indent) override;
56 
61  static vtkCellTreeLocator *New();
62 
67  vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell *cell, double pcoords[3],
68  double* weights ) override;
69 
74  int IntersectWithLine(const double a0[3], const double a1[3], double tol,
75  double& t, double x[3], double pcoords[3],
76  int &subId, vtkIdType &cellId,
77  vtkGenericCell *cell) override;
78 
84  void FindCellsWithinBounds(double *bbox, vtkIdList *cells) override;
85 
86  /*
87  if the borland compiler is ever removed, we can use these declarations
88  instead of reimplementaing the calls in this subclass
89  using vtkAbstractCellLocator::IntersectWithLine;
90  using vtkAbstractCellLocator::FindClosestPoint;
91  using vtkAbstractCellLocator::FindClosestPointWithinRadius;
92  */
93 
97  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
98  double pcoords[3], int &subId) override
99  {
100  return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
101  }
102 
109  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3],
110  double pcoords[3], int &subId, vtkIdType &cellId) override;
111 
116  const double p1[3], const double p2[3],
117  vtkPoints *points, vtkIdList *cellIds) override
118  {
119  return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
120  }
121 
125  vtkIdType FindCell(double x[3]) override
126  { return this->Superclass::FindCell(x); }
127 
129 
132  void FreeSearchStructure() override;
133  void GenerateRepresentation(int level, vtkPolyData *pd) override;
134  virtual void BuildLocatorInternal();
135  virtual void BuildLocatorIfNeeded();
136  virtual void ForceBuildLocator();
137  void BuildLocator() override;
139 
141 
145  class VTKFILTERSGENERAL_EXPORT vtkCellTree
146  {
147  public:
148  std::vector<vtkCellTreeNode> Nodes;
149  std::vector<unsigned int> Leaves;
150  friend class vtkCellPointTraversal;
151  friend class vtkCellTreeNode;
152  friend class vtkCellTreeBuilder;
154 
155  public:
156  float DataBBox[6]; // This store the bounding values of the dataset
157  };
158 
169  class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
170  {
171  public:
172 
173  protected:
174  unsigned int Index;
175  float LeftMax; // left max value
176  float RightMin; // right min value
177 
178  unsigned int Sz; // size
179  unsigned int St; // start
180 
181  friend class vtkCellTree;
182  friend class vtkCellPointTraversal;
183  friend class vtkCellTreeBuilder;
184 
185  public:
186  void MakeNode( unsigned int left, unsigned int d, float b[2] );
187  void SetChildren( unsigned int left );
188  bool IsNode() const;
189  unsigned int GetLeftChildIndex() const;
190  unsigned int GetRightChildIndex() const;
191  unsigned int GetDimension() const;
192  const float& GetLeftMaxValue() const;
193  const float& GetRightMinValue() const;
194  void MakeLeaf( unsigned int start, unsigned int size );
195  bool IsLeaf() const;
196  unsigned int Start() const;
197  unsigned int Size() const;
198  };
199 
200 protected:
202  ~vtkCellTreeLocator() override;
203 
204  // Test ray against node BBox : clip t values to extremes
205  bool RayMinMaxT(const double origin[3],
206  const double dir[3],
207  double &rTmin,
208  double &rTmax);
209 
210  bool RayMinMaxT(const double bounds[6],
211  const double origin[3],
212  const double dir[3],
213  double &rTmin,
214  double &rTmax);
215 
216  int getDominantAxis(const double dir[3]);
217 
218  // Order nodes as near/far relative to ray
219  void Classify(const double origin[3],
220  const double dir[3],
221  double &rDist,
222  vtkCellTreeNode *&near, vtkCellTreeNode *&mid,
223  vtkCellTreeNode *&far, int &mustCheck);
224 
225  // From vtkModifiedBSPTRee
226  // We provide a function which does the cell/ray test so that
227  // it can be overridden by subclasses to perform special treatment
228  // (Example : Particles stored in tree, have no dimension, so we must
229  // override the cell test to return a value based on some particle size
230  virtual int IntersectCellInternal( vtkIdType cell_ID, const double p1[3],
231  const double p2[3],
232  const double tol,
233  double &t,
234  double ipt[3],
235  double pcoords[3],
236  int &subId);
237 
238 
240 
242 
243  friend class vtkCellPointTraversal;
244  friend class vtkCellTreeNode;
245  friend class vtkCellTreeBuilder;
246 
247 private:
248  vtkCellTreeLocator(const vtkCellTreeLocator&) = delete;
249  void operator=(const vtkCellTreeLocator&) = delete;
250 };
251 
252 #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:347
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:79
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:33
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:30
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:44
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:33