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) VTK_OVERRIDE;
59 
64  static vtkCellTreeLocator *New();
65 
70  vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell *cell, double pcoords[3],
71  double* weights ) VTK_OVERRIDE;
72 
77  int IntersectWithLine(double a0[3], double a1[3], double tol,
78  double& t, double x[3], double pcoords[3],
79  int &subId, vtkIdType &cellId,
80  vtkGenericCell *cell) VTK_OVERRIDE;
81 
87  void FindCellsWithinBounds(double *bbox, vtkIdList *cells) VTK_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 
101  double p1[3], double p2[3], double tol, double& t, double x[3],
102  double pcoords[3], int &subId) VTK_OVERRIDE
103  {
104  return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
105  }
106 
113  int IntersectWithLine(
114  double p1[3], double p2[3], double tol, double &t, double x[3],
115  double pcoords[3], int &subId, vtkIdType &cellId) VTK_OVERRIDE;
116 
121  const double p1[3], const double p2[3],
122  vtkPoints *points, vtkIdList *cellIds) VTK_OVERRIDE
123  {
124  return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
125  }
126 
130  vtkIdType FindCell(double x[3]) VTK_OVERRIDE
131  { return this->Superclass::FindCell(x); }
132 
134 
137  void FreeSearchStructure() VTK_OVERRIDE;
138  void GenerateRepresentation(int level, vtkPolyData *pd) VTK_OVERRIDE;
139  virtual void BuildLocatorInternal();
140  virtual void BuildLocatorIfNeeded();
141  virtual void ForceBuildLocator();
142  void BuildLocator() VTK_OVERRIDE;
144 
146 
150  class VTKFILTERSGENERAL_EXPORT vtkCellTree
151  {
152  public:
153  std::vector<vtkCellTreeNode> Nodes;
154  std::vector<unsigned int> Leaves;
155  friend class vtkCellPointTraversal;
156  friend class vtkCellTreeNode;
157  friend class vtkCellTreeBuilder;
159 
160  public:
161  float DataBBox[6]; // This store the bounding values of the dataset
162  };
163 
174  class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
175  {
176  public:
177 
178  protected:
179  unsigned int Index;
180  float LeftMax; // left max value
181  float RightMin; // right min value
182 
183  unsigned int Sz; // size
184  unsigned int St; // start
185 
186  friend class vtkCellTree;
187  friend class vtkCellPointTraversal;
188  friend class vtkCellTreeBuilder;
189 
190  public:
191  void MakeNode( unsigned int left, unsigned int d, float b[2] );
192  void SetChildren( unsigned int left );
193  bool IsNode() const;
194  unsigned int GetLeftChildIndex() const;
195  unsigned int GetRightChildIndex() const;
196  unsigned int GetDimension() const;
197  const float& GetLeftMaxValue() const;
198  const float& GetRightMinValue() const;
199  void MakeLeaf( unsigned int start, unsigned int size );
200  bool IsLeaf() const;
201  unsigned int Start() const;
202  unsigned int Size() const;
203  };
204 
205 protected:
207  ~vtkCellTreeLocator() VTK_OVERRIDE;
208 
209  // Test ray against node BBox : clip t values to extremes
210  bool RayMinMaxT(const double origin[3],
211  const double dir[3],
212  double &rTmin,
213  double &rTmax);
214 
215  bool RayMinMaxT(const double bounds[6],
216  const double origin[3],
217  const double dir[3],
218  double &rTmin,
219  double &rTmax);
220 
221  int getDominantAxis(const double dir[3]);
222 
223  // Order nodes as near/far relative to ray
224  void Classify(const double origin[3],
225  const double dir[3],
226  double &rDist,
227  vtkCellTreeNode *&near, vtkCellTreeNode *&mid,
228  vtkCellTreeNode *&far, int &mustCheck);
229 
230  // From vtkModifiedBSPTRee
231  // We provide a function which does the cell/ray test so that
232  // it can be overriden by subclasses to perform special treatment
233  // (Example : Particles stored in tree, have no dimension, so we must
234  // override the cell test to return a value based on some particle size
235  virtual int IntersectCellInternal( vtkIdType cell_ID, const double p1[3],
236  const double p2[3],
237  const double tol,
238  double &t,
239  double ipt[3],
240  double pcoords[3],
241  int &subId);
242 
243 
244  int NumberOfBuckets;
245 
246  vtkCellTree* Tree;
247 
248  friend class vtkCellPointTraversal;
249  friend class vtkCellTreeNode;
250  friend class vtkCellTreeBuilder;
251 
252 private:
253  vtkCellTreeLocator(const vtkCellTreeLocator&) VTK_DELETE_FUNCTION;
254  void operator=(const vtkCellTreeLocator&) VTK_DELETE_FUNCTION;
255 };
256 
257 #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.
vtkAbstractCellLocator::IntersectWithLine
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.
vtkCellTreeLocator::vtkCellTree
Internal classes made public to allow subclasses to create customized some traversal algorithms.
Definition: vtkCellTreeLocator.h:150
vtkCellTreeLocator::vtkCellTree::Nodes
std::vector< vtkCellTreeNode > Nodes
Definition: vtkCellTreeLocator.h:153
vtkCellTreeLocator::vtkCellTreeNode::St
unsigned int St
Definition: vtkCellTreeLocator.h:184
vtkCellTreeLocator::FindCell
vtkIdType FindCell(double x[3]) override
reimplemented from vtkAbstractCellLocator to support bad compilers
Definition: vtkCellTreeLocator.h:130
vtkCellTreeLocator::vtkCellTreeNode
This class is the basic building block of the cell tree.
Definition: vtkCellTreeLocator.h:174
vtkIdType
int vtkIdType
Definition: vtkType.h:287
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
vtkCellTreeLocator::IntersectWithLine
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
Definition: vtkCellTreeLocator.h:100
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:183
vtkX3D::level
Definition: vtkX3D.h:395
vtkX3D::points
Definition: vtkX3D.h:446
vtkCellTreeLocator::vtkCellTreeNode::Index
unsigned int Index
Definition: vtkCellTreeLocator.h:179
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
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:120
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:180
vtkCellTreeLocator::vtkCellTree::Leaves
std::vector< unsigned int > Leaves
Definition: vtkCellTreeLocator.h:154
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:181