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;
55  class vtkCellTreeNode;
56 
58  void PrintSelf(ostream& os, vtkIndent indent) override;
59 
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:
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:40
vtkCellTreeLocator::FindCellsWithinBounds
void FindCellsWithinBounds(double *bbox, vtkIdList *cells) override
Return a list of unique cell ids inside of a given bounding box.
vtkCellTreeLocator::vtkCellTreeNode::GetRightMinValue
const float & GetRightMinValue() const
vtkCellTreeLocator::vtkCellTree
Internal classes made public to allow subclasses to create customized some traversal algorithms.
Definition: vtkCellTreeLocator.h:149
vtkCellTreeLocator::vtkCellTree::Nodes
std::vector< vtkCellTreeNode > Nodes
Definition: vtkCellTreeLocator.h:151
vtkCellTreeLocator::vtkCellTreeNode::St
unsigned int St
Definition: vtkCellTreeLocator.h:182
vtkCellTreeLocator::BuildLocatorInternal
virtual void BuildLocatorInternal()
vtkCellTreeLocator::FindCell
vtkIdType FindCell(double x[3]) override
reimplemented from vtkAbstractCellLocator to support bad compilers
Definition: vtkCellTreeLocator.h:128
vtkCellTreeLocator::IntersectWithLine
int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId, vtkIdType &cellId) override
Return intersection point (if any) AND the cell which was intersected by the finite line.
vtkCellTreeLocator::vtkCellTreeNode
This class is the basic building block of the cell tree.
Definition: vtkCellTreeLocator.h:173
vtkIdType
int vtkIdType
Definition: vtkType.h:347
vtkCellTreeLocator::vtkCellTreeNode::SetChildren
void SetChildren(unsigned int left)
vtkCellTreeLocator::~vtkCellTreeLocator
~vtkCellTreeLocator() override
vtkCellTreeLocator::vtkCellTreeNode::GetLeftChildIndex
unsigned int GetLeftChildIndex() const
vtkCellTreeLocator::PrintSelf
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
vtkAbstractCellLocator.h
vtkX3D::dir
@ dir
Definition: vtkX3D.h:324
vtkCellTreeLocator::FindCell
vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell *cell, double pcoords[3], double *weights) override
Test a point to find if it is inside a cell.
vtkCellTreeLocator::vtkCellTreeLocator
vtkCellTreeLocator()
vtkCellTreeLocator::vtkCellTreeNode::MakeLeaf
void MakeLeaf(unsigned int start, unsigned int size)
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
@ level
Definition: vtkX3D.h:395
vtkX3D::points
@ points
Definition: vtkX3D.h:446
vtkCellTreeLocator::vtkCellTreeNode::IsNode
bool IsNode() const
vtkCellTreeLocator::GenerateRepresentation
void GenerateRepresentation(int level, vtkPolyData *pd) override
Method to build a representation at a particular level.
vtkCellTreeLocator::vtkCellTreeNode::Start
unsigned int Start() const
vtkCellTreeLocator::vtkCellTreeNode::Index
unsigned int Index
Definition: vtkCellTreeLocator.h:177
vtkIndent
a simple class to control print indentation
Definition: vtkIndent.h:40
vtkCellArray
object to represent cell connectivity
Definition: vtkCellArray.h:51
vtkCellTreeLocator::Classify
void Classify(const double origin[3], const double dir[3], double &rDist, vtkCellTreeNode *&near, vtkCellTreeNode *&mid, vtkCellTreeNode *&far, int &mustCheck)
vtkIdList
list of point or cell ids
Definition: vtkIdList.h:37
vtkCellTreeLocator::RayMinMaxT
bool RayMinMaxT(const double origin[3], const double dir[3], double &rTmin, double &rTmax)
vtkX3D::size
@ size
Definition: vtkX3D.h:253
vtkCellTreeLocator::BuildLocatorIfNeeded
virtual void BuildLocatorIfNeeded()
vtkCellTreeLocator::IntersectWithLine
int IntersectWithLine(const double a0[3], const double a1[3], double tol, double &t, double x[3], double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell) override
Return intersection point (if any) AND the cell which was intersected by the finite line.
vtkAbstractCellLocator
an abstract base class for locators which find cells
Definition: vtkAbstractCellLocator.h:49
vtkCellTreeLocator::vtkCellTreeNode::GetLeftMaxValue
const float & GetLeftMaxValue() const
vtkCellTreeLocator::IntersectCellInternal
virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3], const double tol, double &t, double ipt[3], double pcoords[3], int &subId)
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::vtkCellTreeNode::GetDimension
unsigned int GetDimension() const
vtkCellTreeLocator::NumberOfBuckets
int NumberOfBuckets
Definition: vtkCellTreeLocator.h:242
vtkCellTreeLocator::vtkCellTreeNode::GetRightChildIndex
unsigned int GetRightChildIndex() const
vtkIdTypeArray
dynamic, self-adjusting array of vtkIdType
Definition: vtkIdTypeArray.h:42
vtkCellTreeLocator::vtkCellTreeNode::MakeNode
void MakeNode(unsigned int left, unsigned int d, float b[2])
vtkCellTreeLocator::New
static vtkCellTreeLocator * New()
Constructor sets the maximum number of cells in a leaf to 8 and number of buckets to 5.
vtkPolyData
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:86
vtkGenericCell
provides thread-safe access to cells
Definition: vtkGenericCell.h:40
vtkCellTreeLocator::vtkCellTreeNode::LeftMax
float LeftMax
Definition: vtkCellTreeLocator.h:178
vtkCellTreeLocator::vtkCellTree::Leaves
std::vector< unsigned int > Leaves
Definition: vtkCellTreeLocator.h:152
vtkCellTreeLocator::ForceBuildLocator
virtual void ForceBuildLocator()
vtkCellTreeLocator::RayMinMaxT
bool RayMinMaxT(const double bounds[6], const double origin[3], const double dir[3], double &rTmin, double &rTmax)
vtkCellTreeLocator::FreeSearchStructure
void FreeSearchStructure() override
Satisfy vtkLocator abstract interface.
vtkCellTreeLocator
This class implements the data structures, construction algorithms for fast cell location presented i...
Definition: vtkCellTreeLocator.h:52
vtkCellTreeLocator::getDominantAxis
int getDominantAxis(const double dir[3])
vtkCellTreeLocator::vtkCellTreeNode::RightMin
float RightMin
Definition: vtkCellTreeLocator.h:179
vtkCellTreeLocator::BuildLocator
void BuildLocator() override
Build the locator from the input dataset.
vtkCellTreeLocator::vtkCellTreeNode::Size
unsigned int Size() const
vtkCellTreeLocator::vtkCellTreeNode::IsLeaf
bool IsLeaf() const