VTK  9.0.1
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 "vtkAbstractCellLocator.h"
41 #include "vtkFiltersGeneralModule.h" // For export macro
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 
62  static vtkCellTreeLocator* New();
63 
68  vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell* cell, double pcoords[3],
69  double* weights) override;
70 
75  int IntersectWithLine(const double a0[3], const double a1[3], double tol, double& t, double x[3],
76  double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
77 
83  void FindCellsWithinBounds(double* bbox, vtkIdList* cells) override;
84 
85  /*
86  if the borland compiler is ever removed, we can use these declarations
87  instead of reimplementaing the calls in this subclass
88  using vtkAbstractCellLocator::IntersectWithLine;
89  using vtkAbstractCellLocator::FindClosestPoint;
90  using vtkAbstractCellLocator::FindClosestPointWithinRadius;
91  */
92 
96  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
97  double pcoords[3], int& subId) override
98  {
99  return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
100  }
101 
108  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
109  double pcoords[3], int& subId, vtkIdType& cellId) override;
110 
115  const double p1[3], const double p2[3], vtkPoints* points, vtkIdList* cellIds) override
116  {
117  return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
118  }
119 
123  vtkIdType FindCell(double x[3]) override { return this->Superclass::FindCell(x); }
124 
126 
129  void FreeSearchStructure() override;
130  void GenerateRepresentation(int level, vtkPolyData* pd) override;
131  virtual void BuildLocatorInternal();
132  virtual void BuildLocatorIfNeeded();
133  virtual void ForceBuildLocator();
134  void BuildLocator() override;
136 
138 
142  class VTKFILTERSGENERAL_EXPORT vtkCellTree
143  {
144  public:
145  std::vector<vtkCellTreeNode> Nodes;
146  std::vector<unsigned int> Leaves;
147  friend class vtkCellPointTraversal;
148  friend class vtkCellTreeNode;
149  friend class vtkCellTreeBuilder;
151 
152  public:
153  float DataBBox[6]; // This store the bounding values of the dataset
154  };
155 
166  class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
167  {
168  public:
169  protected:
170  unsigned int Index;
171  float LeftMax; // left max value
172  float RightMin; // right min value
173 
174  unsigned int Sz; // size
175  unsigned int St; // start
176 
177  friend class vtkCellTree;
178  friend class vtkCellPointTraversal;
179  friend class vtkCellTreeBuilder;
180 
181  public:
182  void MakeNode(unsigned int left, unsigned int d, float b[2]);
183  void SetChildren(unsigned int left);
184  bool IsNode() const;
185  unsigned int GetLeftChildIndex() const;
186  unsigned int GetRightChildIndex() const;
187  unsigned int GetDimension() const;
188  const float& GetLeftMaxValue() const;
189  const float& GetRightMinValue() const;
190  void MakeLeaf(unsigned int start, unsigned int size);
191  bool IsLeaf() const;
192  unsigned int Start() const;
193  unsigned int Size() const;
194  };
195 
196 protected:
198  ~vtkCellTreeLocator() override;
199 
200  // Test ray against node BBox : clip t values to extremes
201  bool RayMinMaxT(const double origin[3], const double dir[3], double& rTmin, double& rTmax);
202 
203  bool RayMinMaxT(const double bounds[6], const double origin[3], const double dir[3],
204  double& rTmin, double& rTmax);
205 
206  int getDominantAxis(const double dir[3]);
207 
208  // Order nodes as near/far relative to ray
209  void Classify(const double origin[3], const double dir[3], double& rDist, vtkCellTreeNode*& near,
210  vtkCellTreeNode*& mid, vtkCellTreeNode*& far, int& mustCheck);
211 
212  // From vtkModifiedBSPTRee
213  // We provide a function which does the cell/ray test so that
214  // it can be overridden by subclasses to perform special treatment
215  // (Example : Particles stored in tree, have no dimension, so we must
216  // override the cell test to return a value based on some particle size
217  virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
218  const double tol, double& t, double ipt[3], double pcoords[3], int& subId);
219 
221 
223 
224  friend class vtkCellPointTraversal;
225  friend class vtkCellTreeNode;
226  friend class vtkCellTreeBuilder;
227 
228 private:
229  vtkCellTreeLocator(const vtkCellTreeLocator&) = delete;
230  void operator=(const vtkCellTreeLocator&) = delete;
231 };
232 
233 #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:338
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: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:179
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