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
vtkPoints
represent and manipulate 3D points
Definition: vtkPoints.h:39
vtkAbstractCellLocator::PrintSelf
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
vtkCellTreeLocator::vtkCellTree
Internal classes made public to allow subclasses to create customized some traversal algorithms.
Definition: vtkCellTreeLocator.h:148
vtkCellTreeLocator::vtkCellTree::Nodes
std::vector< vtkCellTreeNode > Nodes
Definition: vtkCellTreeLocator.h:151
vtkCellTreeLocator::vtkCellTreeNode::St
unsigned int St
Definition: vtkCellTreeLocator.h:182
vtkCellTreeLocator::FindCell
vtkIdType FindCell(double x[3]) override
reimplemented from vtkAbstractCellLocator to support bad compilers
Definition: vtkCellTreeLocator.h:128
vtkCellTreeLocator::vtkCellTreeNode
This class is the basic building block of the cell tree.
Definition: vtkCellTreeLocator.h:172
vtkIdType
int vtkIdType
Definition: vtkType.h:347
vtkObject::New
static vtkObject * New()
Create an object with Debug turned off, modified time initialized to zero, and reference counting on.
vtkAbstractCellLocator.h
vtkAbstractCellLocator::FindCell
virtual vtkIdType FindCell(double x[3])
Returns the Id of the cell containing the point, returns -1 if no cell found.
vtkX3D::dir
Definition: vtkX3D.h:324
vtkAbstractCellLocator::FindCellsWithinBounds
virtual void FindCellsWithinBounds(double *bbox, vtkIdList *cells)
Return a list of unique cell ids inside of a given bounding box.
vtkCellTreeLocator::vtkCellTreeNode::Sz
unsigned int Sz
Definition: vtkCellTreeLocator.h:181
vtkCellTreeLocator::Tree
vtkCellTree * Tree
Definition: vtkCellTreeLocator.h:244
vtkCellTreeLocator::IntersectWithLine
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
Definition: vtkCellTreeLocator.h:100
vtkX3D::level
Definition: vtkX3D.h:395
vtkX3D::points
Definition: vtkX3D.h:446
vtkLocator::GenerateRepresentation
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
Method to build a representation at a particular level.
vtkCellTreeLocator::vtkCellTreeNode::Index
unsigned int Index
Definition: vtkCellTreeLocator.h:177
vtkIndent
a simple class to control print indentation
Definition: vtkIndent.h:39
vtkCellArray
object to represent cell connectivity
Definition: vtkCellArray.h:50
vtkIdList
list of point or cell ids
Definition: vtkIdList.h:36
vtkX3D::size
Definition: vtkX3D.h:253
vtkLocator::BuildLocator
virtual void BuildLocator()=0
Build the locator from the input dataset.
vtkAbstractCellLocator
an abstract base class for locators which find cells
Definition: vtkAbstractCellLocator.h:48
vtkCellTreeLocator::IntersectWithLine
int IntersectWithLine(const double p1[3], const double p2[3], vtkPoints *points, vtkIdList *cellIds) override
reimplemented from vtkAbstractCellLocator to support bad compilers
Definition: vtkCellTreeLocator.h:118
vtkCellTreeLocator::NumberOfBuckets
int NumberOfBuckets
Definition: vtkCellTreeLocator.h:242
vtkAbstractCellLocator::IntersectWithLine
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.
vtkIdTypeArray
dynamic, self-adjusting array of vtkIdType
Definition: vtkIdTypeArray.h:41
vtkPolyData
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:85
vtkGenericCell
provides thread-safe access to cells
Definition: vtkGenericCell.h:39
vtkCellTreeLocator::vtkCellTreeNode::LeftMax
float LeftMax
Definition: vtkCellTreeLocator.h:178
vtkCellTreeLocator::vtkCellTree::Leaves
std::vector< unsigned int > Leaves
Definition: vtkCellTreeLocator.h:152
vtkCellTreeLocator
This class implements the data structures, construction algorithms for fast cell location presented i...
Definition: vtkCellTreeLocator.h:51
vtkLocator::FreeSearchStructure
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
vtkCellTreeLocator::vtkCellTreeNode::RightMin
float RightMin
Definition: vtkCellTreeLocator.h:179