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(double a0[3], 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 
98  double p1[3], double p2[3], double tol, double& t, double x[3],
99  double pcoords[3], int &subId) override
100  {
101  return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
102  }
103 
110  int IntersectWithLine(
111  double p1[3], double p2[3], double tol, double &t, double x[3],
112  double pcoords[3], int &subId, vtkIdType &cellId) override;
113 
118  const double p1[3], const double p2[3],
119  vtkPoints *points, vtkIdList *cellIds) override
120  {
121  return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
122  }
123 
127  vtkIdType FindCell(double x[3]) override
128  { return this->Superclass::FindCell(x); }
129 
131 
134  void FreeSearchStructure() override;
135  void GenerateRepresentation(int level, vtkPolyData *pd) override;
136  virtual void BuildLocatorInternal();
137  virtual void BuildLocatorIfNeeded();
138  virtual void ForceBuildLocator();
139  void BuildLocator() override;
141 
143 
147  class VTKFILTERSGENERAL_EXPORT vtkCellTree
148  {
149  public:
150  std::vector<vtkCellTreeNode> Nodes;
151  std::vector<unsigned int> Leaves;
152  friend class vtkCellPointTraversal;
153  friend class vtkCellTreeNode;
154  friend class vtkCellTreeBuilder;
156 
157  public:
158  float DataBBox[6]; // This store the bounding values of the dataset
159  };
160 
171  class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
172  {
173  public:
174 
175  protected:
176  unsigned int Index;
177  float LeftMax; // left max value
178  float RightMin; // right min value
179 
180  unsigned int Sz; // size
181  unsigned int St; // start
182 
183  friend class vtkCellTree;
184  friend class vtkCellPointTraversal;
185  friend class vtkCellTreeBuilder;
186 
187  public:
188  void MakeNode( unsigned int left, unsigned int d, float b[2] );
189  void SetChildren( unsigned int left );
190  bool IsNode() const;
191  unsigned int GetLeftChildIndex() const;
192  unsigned int GetRightChildIndex() const;
193  unsigned int GetDimension() const;
194  const float& GetLeftMaxValue() const;
195  const float& GetRightMinValue() const;
196  void MakeLeaf( unsigned int start, unsigned int size );
197  bool IsLeaf() const;
198  unsigned int Start() const;
199  unsigned int Size() const;
200  };
201 
202 protected:
204  ~vtkCellTreeLocator() override;
205 
206  // Test ray against node BBox : clip t values to extremes
207  bool RayMinMaxT(const double origin[3],
208  const double dir[3],
209  double &rTmin,
210  double &rTmax);
211 
212  bool RayMinMaxT(const double bounds[6],
213  const double origin[3],
214  const double dir[3],
215  double &rTmin,
216  double &rTmax);
217 
218  int getDominantAxis(const double dir[3]);
219 
220  // Order nodes as near/far relative to ray
221  void Classify(const double origin[3],
222  const double dir[3],
223  double &rDist,
224  vtkCellTreeNode *&near, vtkCellTreeNode *&mid,
225  vtkCellTreeNode *&far, int &mustCheck);
226 
227  // From vtkModifiedBSPTRee
228  // We provide a function which does the cell/ray test so that
229  // it can be overridden by subclasses to perform special treatment
230  // (Example : Particles stored in tree, have no dimension, so we must
231  // override the cell test to return a value based on some particle size
232  virtual int IntersectCellInternal( vtkIdType cell_ID, const double p1[3],
233  const double p2[3],
234  const double tol,
235  double &t,
236  double ipt[3],
237  double pcoords[3],
238  int &subId);
239 
240 
242 
244 
245  friend class vtkCellPointTraversal;
246  friend class vtkCellTreeNode;
247  friend class vtkCellTreeBuilder;
248 
249 private:
250  vtkCellTreeLocator(const vtkCellTreeLocator&) = delete;
251  void operator=(const vtkCellTreeLocator&) = delete;
252 };
253 
254 #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.
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:345
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
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.
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: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...
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