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
vtkPoints
represent and manipulate 3D points
Definition: vtkPoints.h:33
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:145
vtkCellTreeLocator::vtkCellTree::Nodes
std::vector< vtkCellTreeNode > Nodes
Definition: vtkCellTreeLocator.h:148
vtkCellTreeLocator::vtkCellTreeNode::St
unsigned int St
Definition: vtkCellTreeLocator.h:179
vtkCellTreeLocator::FindCell
vtkIdType FindCell(double x[3]) override
reimplemented from vtkAbstractCellLocator to support bad compilers
Definition: vtkCellTreeLocator.h:125
vtkCellTreeLocator::vtkCellTreeNode
This class is the basic building block of the cell tree.
Definition: vtkCellTreeLocator.h:169
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:178
vtkCellTreeLocator::Tree
vtkCellTree * Tree
Definition: vtkCellTreeLocator.h:241
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:97
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:174
vtkIndent
a simple class to control print indentation
Definition: vtkIndent.h:33
vtkCellArray
object to represent cell connectivity
Definition: vtkCellArray.h:44
vtkIdList
list of point or cell ids
Definition: vtkIdList.h:30
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:115
vtkCellTreeLocator::NumberOfBuckets
int NumberOfBuckets
Definition: vtkCellTreeLocator.h:239
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:35
vtkPolyData
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:79
vtkGenericCell
provides thread-safe access to cells
Definition: vtkGenericCell.h:36
vtkCellTreeLocator::vtkCellTreeNode::LeftMax
float LeftMax
Definition: vtkCellTreeLocator.h:175
vtkCellTreeLocator::vtkCellTree::Leaves
std::vector< unsigned int > Leaves
Definition: vtkCellTreeLocator.h:149
vtkCellTreeLocator
This class implements the data structures, construction algorithms for fast cell location presented i...
Definition: vtkCellTreeLocator.h:48
vtkLocator::FreeSearchStructure
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
vtkCellTreeLocator::vtkCellTreeNode::RightMin
float RightMin
Definition: vtkCellTreeLocator.h:176